数组

问题1. 从排序数组中删除重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。

for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路：
因为数组是排序的，所以只需用一个下标i维持元素不重复数组的最后一个元素的位置，i初始化为0，然后从第一个元素开始遍历一遍数组，如果元素与i位置的元素相同则是重复元素，可以跳过，否则把该元素放到i + 1的位置, 下标更新指向i + 1, 遍历结束后不重复数组的长度就为i + 1，同时截断数组只保留到最后一个不重复元素的位置i.

Time:  O(n)
Space: O(1)
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        i = 0
        for j in xrange(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        nums = nums[:i + 1]
        return i + 1
        

问题2. 买卖股票的最佳时机 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。

解题思路:
股票赚钱的条件就是低买高卖, 这里的限制条件是同时只能进行一笔交易，那么最大利润就是买卖的最大差价之和，考虑按横坐标为时间天，纵坐标为每天的股票价格，画出一条股价线，那么获取最大利润的策略就是每笔交易从曲线的低点(左右两边都比当天股价高)买入，高点(左右两边都比当天股价低)卖出，高点的股价减去低点的股价则为这笔交易的利润, 假设低点坐标为(x1, y1), 中间点坐标为(x2, y2), 高点坐标为(x3, y3), 那么profit = y3 - y1 = (y3 - y2) + (y2 - y1)，这样可以把查找低点和高点转换成算相邻两天的股价之差的和，当相邻两天的股价之差为负数时会带来亏损，则选择不做这笔交易。

Time:  O(n)
Space: O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        return sum(map(lambda x: max(prices[x + 1] - prices[x], 0), xrange(len(prices[:-1]))))

问题3. 旋转数组

给定一个数组，将数组中的元素向右移动 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) 的原地算法。

解题思路:
如果可用新的数组保存结果的话，那么只需要简单的分成两部分放入新数组即可，时间负责度为O(n)，但是题目要求空间复杂度为O(1)，那么只能在原数组上做变换了，最直接的想法就是做k次平移，每次平移都只需要O(1)的空间，但是时间负责则变成了O(n * k)，所以只能继续思考能不能找到O(n)时间复杂度的方法，即只需要做常数次数的平移变换(与k无关), 仔细观察输出结果与输入的对比，发现只需要把最后边的k个数放到左边，原来的n - k个数移动到右边, 可以想到reverse操作能做到这样的效果，然后接着对比发现reverse之后的左右两部分的元素顺序还需要再reverse, 这样就能达到最后的效果了。

Time:  O(n)
Space: O(1)
class Solution(object):
    
    def reverse_array(self, arr, begin, end):
        b, e = begin, end
        while b < e:
            arr[b], arr[e] = arr[e], arr[b]
            b += 1
            e -= 1
    
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        k = k % len(nums)
        self.reverse_array(nums, len(nums) - k, len(nums) - 1)
        self.reverse_array(nums, 0, len(nums) - 1 - k)
        self.reverse_array(nums, 0, len(nums) - 1)