数组

乘积最大子序列

Leetcode 152题。

问题

给定一个整数数组 nums ，找出一个序列中【乘积最大】的【连续】子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路

类似于之前 和最大的子序列（leetcode 53） 中的思路，动态规划的方法，那个题目的答案如下：

sum_ = sys.maxsize * -1
        max_ = sum_
        for i in nums:
            if sum_ < 0:
                sum_ = i
            else:
                sum_ += i
            if max_ < sum_:
                max_ = sum_
        return max_

在这个题目中，采用类似的方法，也设定一个阶段性的累乘变量，设定一个全局的最大值变量，逐个往后找更新即可。

但需要注意：累乘时会出现负值的情况，也就是说比如之前的累乘积是-100，是最小的，但万一下一个数字是负数，就会发生逆转，乘积就变成最大的了。因此，需要两个阶段性变量，分别记下累乘的最大和最小值。

代码

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        min_pro = nums[0]
        max_pro = nums[0]
        result = nums[0]
        for num in nums[1:]:
            tmp1 = min_pro*num
            tmp2 = max_pro*num
            min_pro = min(tmp1, num, tmp2)
            max_pro = max(tmp1, num, tmp2)
            result = max(result, max_pro)
        return result

旋转数组

Leectode 189

问题

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

示例 : 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4]

可以多想几种方案；要使用空间复杂度为1的原地算法

思路

1）两层循环，外层k遍，内层每一遍都将所有元素往右挪动1个位置 2）三次翻转；第一次对整个数组进行翻转，然后分别将前k个元素翻转、后面的元素翻转 3）不限制空间的话可以开辟新空间，将前后两部分重新进行拼接；或者可以从后面依次pop出k个元素，依次append到前面；都可以实现旋转

代码

按照三次翻转来写。注意：k可能会大于n，我们取k=k%n即可

class Solution:
    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        self.reverse(nums, 0, len(nums)-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, len(nums)-1)

存在重复元素

Leetcode 217

问题

给定整数数组，判断是否存在重复元素

思路

1）n2的复杂度，暴力两层循环去逐个判断 2）排序，然后扫一遍检查相邻两元素是否有相等的情况 3）转为set，判断set长度与list是否相等 4）从前向后扫，把出现过的元素记下来，每个新元素检查下之前是否出现过

代码

python投机取巧法：

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

移动0

leetcode 283

问题

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

思路

其实就是把非0元素往前挪，也不需要交换之类的搞那么复杂，挪到最后余下的都填成0即可。

代码

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1:
            return
        cursor = 0
        for i in range(0, len(nums)):
            if nums[i] != 0:
                nums[cursor] = nums[i]
                cursor += 1
        while cursor < len(nums):
            nums[cursor] = 0
            cursor += 1

打乱数组

Leetcode 384

问题

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

思路

感觉是个奇怪的题啊，python可以用random库的shuffle来打散，或者用代码里的方法随机交换来打散。

注意深靠背和浅拷贝。

代码

import random
class Solution:

    def __init__(self, nums: List[int]):
        self.backup = list(nums)
        self.nums = nums
        

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        self.nums = list(self.backup)
        return self.nums
        

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        length = len(self.nums)
        for i in range(length):
            rand = random.randint(0, length-1)
            self.nums[i], self.nums[rand] = self.nums[rand], self.nums[i]
        return self.nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

两个数组的交集

Leetcode 349题。

问题

给定两个数组，编写一个函数来计算它们的交集。

例如，输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]

输出结果中，每个元素一定是唯一的。 可以不考虑输出结果的顺序。

思路

由于这个题中结果要求不出现重复元素，所以可以先分别将两个数组set一下，去重，然后取set的交集。可使用python本身的交集操作符，一行代码搞定；或者遍历一个set同时在另一个中查找，来求交集。

如果不支持set，用最原始的做法的话，可以先遍历一个list，同时在另一个list中查找，如果找得到，并且这个元素未在结果list中出现的话，则将该元素加入到结果list中，完成题目要求。

还有一些方法，也参见下一道题里的描述。

代码

class Solution(object):
    def intersection(self, nums1, nums2):
        return set(nums1) & set(nums2)

补充一下，两个set之间 & 可以求交集，| 求并集， - 求差集

两个数组的交集 2

Leetcode 350题。

问题

与上一个题的区别在于，这个题要求元素可以多次出现。 比如下面示例，2在两个list中都出现了两次，则输出两个2 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2]

进阶思考：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路

1）暴力法：两层for循环，但需要注意本题中允许多次出现，所以内层循环里当某个元素被使用过一次之后，要把它置空一下避免后面再次被计数用到。

//直接从别处拿来代码示例
for(vector<int>::iterator it1 = nums1.begin(); it1 != nums1.end(); it1++) {
            for(vector<int>::iterator it2 = nums2.begin(); it2 != nums2.end(); it2++) {
                if(*it1 == *it2) {
                    ret.push_back(*it1);
                    *it2 = -10085;  // 要想办法置空这个元素，避免内层再次被用到
                }
            }
        }

2）有序时，两路并进 如果两个数组有序，可以两路并进，类似于merge，详见下面的代码。

3）哈希表 对其中一个数组构建哈希表，遍历另一数组元素时可快速查找是否重复。这是适合上一题的做法，本题中由于允许重复，哈希表中需要记录元素的出现次数，每次查找一个之后把计数减1，减到0了就相当于找不到。

这个做法感觉还是答题时必须得想到的，相比暴力减少了很多次内层的遍历操作。

代码

按照上面的方案2 来写

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1 = sorted(nums1)
        nums2 = sorted(nums2)
        i, j = 0, 0
        result = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1
        return result

递增的三元子序列

Leetcode 334 题。

问题

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。

要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)

思路

需要仔细点读题，ijk并不要求是连续的（如果是连续的，这个题出的未免也太简单了啊喂

思路是从左往右挨个读，记下当前的最小值和第二小的值，并随着读取不断更新。如果遇到比第二小还大的数，说明形成了递增的三元子序列。

代码

import sys

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if not nums or len(nums) < 3:
            return False
        min_val, mid_val = sys.maxsize, sys.maxsize
        for n in nums:
            if n  <= min_val:  #需要注意这里的条件是 小于等于，因为会出现 11111 这样的全相等值的特殊情况
                min_val = n
            elif n <= mid_val:
                mid_val = n
            else:
                return True
        return False

搜索二维矩阵 II

Leetcode 240 题，剑指Offer第一题，详见 剑指Offer (opens new window)

除自身以外数组的乘积

Leetcode 238题。

问题

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

要求：不要使用除法；o（n）时间复杂度

思路

不能使用除法，所以最直观的思路——先求总的乘积再除以每个元素——就行不通了（实际上这种想法也不那么简单吧，比如说对0元素的处理就挺麻烦）

我们以每个数为中心，可以将数组分成左右两块，该处的值就是左右两边的乘积再乘起来。所以只需要从左到右累乘一遍，再从右到左累乘一遍就可以。

代码

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if len(nums) < 1:
            return 0
        out = [1] * len(nums)  # 直接使用out输出数组来暂存结果，不开辟额外空间
		# 从左到右
        temp = nums[0]
        for i in range(1, len(nums)):
            out[i] = temp
            temp *= nums[i]
        temp = nums[-1]
		# 从右到左
        for i in range(len(nums)-2, -1, -1):
            out[i] *= temp
            temp *= nums[i]
        return out