从零开始的力扣（第二天）~

1.买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
—————————————————————————————————————————
在刚看到题的时候，第一个想法就是暴力法，遍历所有种情况，然后取之中max的数，但是这样着实没有任何技术含量，这里通过股票价格的折线图可以联想到收益的最佳解法：

可以看出所谓的收益最大化就意味着每一个波峰减去对应的前一个波谷，这样得到的所有值相加，得到结果。再进一步去理解的话，其实所谓的收益最大化就是当后项值大于前项值时，得到对应差，将所有的对应差相加，即为收益最大值：

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        all = 0        
        for i in range(0,len(prices) - 1):
            mins = prices[i+1] - prices[i]
            if mins>0:
                all = all + mins
            else:
                continue    
        return all

2.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。
—————————————————————————————————————————

1.做循环，在每一次循环中将最后一位提取到第一位

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            nums.insert(0,nums[-1])
            nums.pop()

2.通过找寻规律可知，旋转数组又可以通过翻转数组得到

即先将数组整个翻转，再将数组内前k项与后面项单独翻转，得到最终结果

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        nums[:] = nums[:][::-1]
        nums[0:k] = nums[0:k][::-1]
        nums[-(len(nums) - k):] = nums[-(len(nums) - k):][::-1]

3.先进行一次循环，将前k项与后k项做位置交换，这样剩下的末尾k项再在后n-k项中做位置交换就完成了

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        if k > len(nums):
            k = k % len(nums)
        for i in range(k):
            nums[i],nums[len(nums) - k + i] = nums[len(nums) - k + i],nums[i]
        if k < (len(nums) + 1)/2:
            for j in range(k):
                nums.insert(k,nums.pop())
        else:
            n = k % (len(nums) - k)
            for j in range(n):
                nums.insert(k,nums.pop())
        

最后一个方法我在写的时候很繁琐，考虑到k的各种取值，此处应该可以更精简。

以上就是今日经验！