跳跃游戏

用s记录当前位置是否可达，如果不可达，则返回False，否则 当前位置能够达到的最远处要么是之前的最远处，要么是当前的最远处，即$max(s,i+nums[i])$，用python实现如下：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        s = 0
        for i in range(len(nums)):
            if s>=i:
                s = max(s,i+nums[i])
            else:
                return False
        return True

跳跃游戏 II

最开始想到了一个比较复杂的方案，但是比较常规，用$dp[i]$表示当前位置需要的最小跳跃数，比较经典的解法：

class Solution:
    def jump(self, nums: List[int]) -> int:
        dp = [0]*len(nums)
        for i in range(1,len(nums)):
            j = 0
            temp = 100000
            while j < i:
                if j + nums[j] >= i:
                    temp = min(temp,dp[j]+1)
                j += 1
            dp[i] = temp
        return dp[-1]

但是这道题不适合使用这个方法，根据 每走一步，选择当前能走的那些位置对应的后续能走的最大值 这个思路，就能解决这道题（不过我写的非常复杂）：

class Solution:
    def jump(self, nums: List[int]) -> int:
        s = nums[0]
        step = 0
        i = 1
        while i<len(nums):
            max_i = -1
            max_v = -1
            if s >= len(nums)-1:return step+1
            while i <= s and i < len(nums):
                v = i + nums[i]
                if v > max_v:
                    max_v = v 
                    max_i = i
                i += 1
            step += 1
            i = max_i
            s = max_v
            if i == len(nums)-1:return step
            i = i+1
        return step

看题解有好理解的写法：

class Solution:
    def jump(self, nums: List[int]) -> int:  
        stage = 0
        step = 0
        max_v = 0
        for i in range(len(nums)-1):
            max_v = max(max_v,i+nums[i])
            if i == stage:
                stage = max_v
                step += 1
        return step

删除有序数组中的重复项 II

原地更新数组，一般就是两个指针，一个指针用来遍历元素，一个指针用来添加元素

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        pre = None
        cnt = 0
        j = -1
        while i< len(nums):
            if nums[i] == pre:
                cnt += 1
            else:
                cnt = 1
            if cnt <= 2:
                j += 1
                nums[j] = nums[i]
            pre = nums[i]
            i += 1
        return j+1

多数元素

一个数如果是多数，那么它和其它数消的时候，剩下的一定是它，这是最差的情况，而从头开始消，肯定会存在非多数之间消，那么最终存在的一定是多数：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        target = None
        cnt = 0
        for v in nums:
            if cnt == 0:
                target = v
                cnt = 1
            else:
                if target == v:
                    cnt += 1
                else:
                    cnt -= 1
        return target

买卖股票的最佳时机 II

我先想到的就是，遍历整个序列，找局部最低点和最高点，然后用最高点减最低点即为一个交易的利润，然后加起来得到最终的利润：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        sum = 0
        start = None
        while i < len(prices):
            if (i == 0 or prices[i]<=prices[i-1]) and i+1 < len(prices) and prices[i+1] > prices[i]:
                start = prices[i]
            elif start!=None and i-1>=0 and prices[i]>prices[i-1] and (i+1 == len(prices) or prices[i]>=prices[i+1]):
                sum += prices[i]-start
                start = None
            i += 1
            print(start)
        return sum

有很多边界问题需要判断，看了一下提交记录中别人的解法，确实简单不少：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            tmp = prices[i] - prices[i - 1]
            if tmp > 0: profit += tmp
        return profit