Leetcode 初级算法-数组

初级算法-数组

知识

数组是一种线性数据结构，其常见复杂度如下：

查找O(n)，删除O(n)，插入O(n)，随机读取O(1)

若初始化一个定长数组，可以降低复杂度，但将会失去可变数组带来的简便添加元素和删除元素的方法。

技巧

双指针法（多指针法）

其核心思想是，构建单个（多个）数组中需要交互操作，同时操作，同一操作的两个（多个）位置之间的函数关系，赋予指针变量。这样，即可通过遍历一次由单位向量构成的自变量，达成同时对相应的全部位置进行操作。

运算符

运算符还包括了逻辑运算符，在写代码时不应只留意函数关系的加减乘除。

练习

26.删除有序数组中的重复项

问题：

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

解答：

首次解答：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        p = 0
        for idx in range(len(nums)-1):
            if nums[idx-p] == nums[idx-p+1]:
                del nums[idx-p]
                p = p + 1

Result：

相似解答：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        p = 0
        for idx in range(len(nums)-1):
            if nums[idx-p] == nums[idx-p+1]:
                nums.pop(idx-p)
                p = p + 1

之所以会这么慢，是因为del本身的复杂度是$O(n)$，同时for循环的复杂度也是$O(n)$。导致了整体的复杂度提升。
一个简单的改进方法是使用快慢激励双指针，两个指针初始相差一位，当两者数值不同，就将快指针指向的值赋予慢指针指向的位置，同时两指针都向前一步；当两者数值相同，或是快指针前后相同，则仅仅激励快指针。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        j = 1
        # 提前保存首位
        p = nums[0]
        while i <= len(nums)-1 and j <= len(nums)-1:
            if nums[i] == nums[j] or nums[j] == nums[j-1] :
                j = j + 1
            elif nums[i] != nums [j]:
                nums[i] = nums[j]
                i = i + 1
                j = j + 1
        # 重新放回首位
        nums.insert(0,p)
        return i+1

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

问题：

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在** 同一天** 出售。
返回 你能获得的 最大 利润 。

示例 1:

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

示例 2:

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

示例 3:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

解答：

首次解答：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        global highest
        global k 
        highest = 0
        k = []
        for idx in range(len(prices)-1):
            if Solution.iterer(idx,prices) != 0 and idx not in k:
                Solution.iterer(idx,prices)
        return highest
            
    def iterer(idx=0, prices=[], higher=0):
        #global k
        global highest
        for length in range(len(prices)-1-idx):
            if prices[idx+length+1]-prices[idx]+higher>0:     
                if prices[idx+length+1]-prices[idx]+higher>highest:
                    highest = prices[idx+length+1]-prices[idx]+higher
            if idx+length+2 < len(prices) and idx+length+2:
                for idx2 in range(len(prices)-1-idx+length+2):
                    # 无限递归
                    Solution.iterer(idx2+idx+length+2,prices,prices[idx+length+1]-prices[idx]+higher)

上面的代码在数组大的时候超时了。原因是因为无限递归的时间复杂度太高。这种时候，就应该分析题设没有给出的数学条件。
可以看出，隔多日买入卖出，可以视为每一日都买入卖出的加和。
这样，为了达成最优获利，只需要将能盈利的每日都相加即可。

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

189. 轮转数组

问题：

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [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:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

解答：

首次解答：

1. 简单法：

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

Result：

上述代码写起来还是挺简单的，但insert和pop对时间的消耗比较大。若是想要在一次循环下完成，我们需要额外的空间。

1. 迭代法：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) != 1: 
            i = 0
            j = k
            # 可变类型需要深拷贝才能不受对象变化影响
            p = copy.deepcopy(nums)
            while i<=len(nums)-1:
                while j > len(nums)-1:
                    j = j-len(nums)
                nums[j] = p[i]
                i = i+1
                j = j+1

两指针分别指向两数组，其间距相差k，对数组长度遍历一遍，即可获得结果。在上述代码中，深拷贝耗费了不少的时间，可以被优化掉。

217. 存在重复元素

问题：

https://leetcode-cn.com/problems/contains-duplicate/

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

解答：

首次解答：

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # 转为set剔除掉不符元素，再比较长度是否相等
        if len(list(set(nums)))==len(nums):
            return False
        else:
            return True
    # 等价于
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not len(list(set(nums))) == len(nums)

除了利用set不能保存重复元素的性质，还有没有别的办法可以做到？

可以使用一种可变数据类型来保存已经存在的内容：

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # s可以使用任何可变可查找的类型，其中，最快的是字典。
        s = set()
        for i in nums:
            if i in s:
                return True
            else:
                s.add(i)
        return False

136. 只出现一次的数字

问题：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解答：

首次解答：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in nums:
            # 使用计数函数
            if nums.count(i) == 1:
                return i

但这种方式无疑是十分缓慢的，一种简单的改进方法是使用如上一题的方法：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 构造字典
        k = {}
        p = {}
        for i in nums:
            if i in k:
                p.pop(i)
                continue
            else:
                k[i] = i
                p[i] = i
        # 返回唯一存在的对象
        return list(p.values())[0]

但是，一个新的问题又出现了，这个新方法也没有办法不使用额外空间。如果想要不使用额外空间，那么就得考虑内建的函数（算法）。

在本题中，需要接触并使用位运算（逻辑运算）：

异或运算的性质可以在数字电路中简单掌握，相同输出0，不同输出1。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # reduce()函数用于累积；lambda用于声明匿名函数。reduce()对范围nums内所有值做lambda()操作，'^'是按位异或运算符。
        return reduce(lambda x, y: x ^ y, nums)

350. 两个数组的交集 II

问题：

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

其它：

**提示：**

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

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

解答：

首次解答：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        k = []
        # 遍历数值
        for i in nums1:
            # 避免重复数值
            if i not in k:
                # 按最小出现次数
                for p in range(min(nums1.count(i),nums2.count(i))):
                    # 输入数组
                    k.append(i)
        return k

Result：

显然，这个代码的时间复杂程度太高了。为了降低代码的时间复杂度，最为简单能解决的是在中间使用的两个count()【$O(n)$】函数，将它们替换成时间复杂度更低的方法，或者是把它们移出外围for循环。

那么，一个合理的思路是，‘既然这一步是因为无法统计到元素重复次数，那就将元素重复统计放到循环之前。在这里，可以使用双指针走两个排序sort()【$O(n\times log(n))$】数组来完成。

再次解答：

class Solution(object):
    def intersect(self, nums1, nums2):
        nums1 = sorted(nums1)
        nums2 = sorted(nums2)
        i = 0
        j = 0
        k = []
        while((i<len(nums1)) and (j<len(nums2))):
            if(nums1[i] == nums2[j]):
                k.append(nums1[i])
                i = i+1
                j = j+1
            elif(nums1[i] > nums2[j]):
                j = j+1
            elif(nums1[i] < nums2[j]):
                i = i+1
        return k

66.加一

https://leetcode-cn.com/problems/plus-one

问题：

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数0之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

其它：

提示： 1 <= digits.length <= 100 0 <= digits[i] <= 9

解答：

首次解答：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # 末位+1
        digits[-1] = digits[-1] + 1
        # 捕捉进位（这个一开始可能忽略掉），其实这里可以只要后面的部分，但是这样会进循环减速。
        if digits[-1] == 10:
            # 循环进位
            for i in range(len(digits)):
                if digits[-(i+1)] == 10:
                    digits[-(i+1)] = 0
                    if i+1 < len(digits):
                        # 上位+1
                        digits[-(i+2)] = digits[-(i+2)] + 1
                    else:
                        # 顶位补长
                        digits.insert(0,1)
        return digits

Result：

发现这样子，时空消耗可能还能进一步缩减，但不是非常必要。那如何缩减代码长度呢？

一种题解：

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(j) for j in str(int(''.join([str(i) for i in digits]))+1)]

Result：

这个题解使用了数据结构的有关方法，在缩减了代码长度的同时，引入了一个新的for，这个可能会增加时间复杂度。

283.移动零

链接： https://leetcode-cn.com/problems/move-zeroes/

问题：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

其它：

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

解答：

首次解答：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 回退指针
        p = 0
        # 定义范围循环
        for idx in range(len(nums)):
            # 找0
            if nums[idx-p] == 0:
                # 原位删除，末尾填补
                nums.append(nums.pop(idx-p))
                # 指针进位
                p += 1 

Result：

这个解答的空间消耗通常，但是时间消耗很大，其主要原因在于pop和append的时间消耗。

**同类代码如下：**

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # 定义范围循环，这里range从后往前走了
        for idx in range(len(nums)-1,-1,-1):
            if nums[idx] == 0:
                nums.pop(idx)
                nums.append(0)

从后往前写的话，可以少一个指针的需求。
由于pop(i)($O(n)$)和append的影响，单指针在这道题的表现上确实是不如双指针，或者说，在上文中，我虽然定义了p指针，但其没有被有效利用上，所以想要提升效率的话，

再次解答：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        p = 0
        for idx in range(len(nums)):
            if nums[idx] != 0:
                # 交换位置
                nums[p], nums[idx] = nums[idx], nums[p]
                p += 1

Result：

1. 两数之和

问题：

https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

只会存在一个有效答案。

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解答：

首次解答：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx1 in range(len(nums)):
            for idx2 in range(len(nums)):
                if nums[idx1]+nums[idx2] == target:
                    if idx1 != idx2:
                        return [idx1,idx2]

显然这是一个$O(n^2) $复杂度的算法，但即使是上面这个程度，也还有优化的空间：因为两个idx之间显然是有对应关系的。每一个在前的元素都已经和后面的元素匹配过了。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx1 in range(len(nums)):
            for idx2 in range(len(nums)):
                if idx1 < idx2:
                    if nums[idx1]+nums[idx2] == target:
                        return [idx1,idx2]

当然，以上的双循环方法，随着数组长度的增加，其消耗的时间以二次方增加。将其时间复杂度降低，我们可以观察目前的数据形式。如果使用字典的话，我们可以在内循环中，不必再使用$O(n) $的时间复杂度，而是$O(1) $。与此同时，我们的空间复杂度会提高到$O(n) $。

再次解答：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        k = {}
        for idx1 in range(len(nums)):
            if target-nums[idx1] in k:
                return [idx1, k[target-nums[idx1]]]
            k[nums[idx1]] = idx1
        return []

注意，在上述代码中，将当前值与字典进行比较 ，和 将当前值加入字典 两步操作的顺序不可调换。程序的运行状态通常会影响程序的处理结果。在本题中，若是对调两个步骤，则无法处理以下情况：

[3,3] 6;
[3,2,4,6] 6;

通常来说，我们可以将对数据集的修改，放置在操作步骤之后来避免这种情况。当然，具体情况具体分析。

不过对于函数式编程来说，就可以不用那么考虑状态。

36. 有效的数独

问题：

https://leetcode-cn.com/problems/valid-sudoku/

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

解答：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool: 
        x = []
        for i in range(9):
            y = []
            for j in range(9):
                y.append(board[j][i])
            x.append(y)

        for m in range(3):
            for n in range(3):
                k = []
                p = 0
                for i in range(3):
                    for j in range(3):
                        # 过空格
                        if board[i+3*m][j+3*n] == '.':
                            p += 1
                        # 比小块
                        if board[i+3*m][j+3*n] != '.' and board[i+3*m][j+3*n] not in k:
                            k.append(board[i+3*m][j+3*n])
                        # 比横竖
                        if board[i+3*m][j+3*n] != '.': 
                            if  board[i+3*m].count(board[i+3*m][j+3*n]) > 1 or x[j+3*n].count(board[i+3*m][j+3*n]) > 1:
                                return False
                if len(k) != 9 - p:
                    return False
        return True

48. 旋转图像

问题：

https://leetcode-cn.com/problems/rotate-image/

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

解答：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix[0])
        for i in range(length):
            for j in range(length):
                if i<=j:
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(length):
            for j in range(length//2):
                matrix[i][j], matrix[i][-j-1] = matrix[i][-j-1], matrix[i][j]

一道数学规律题。