Miraisen
0%

LeetCode数组篇

发表于 更新于 分类于
本文字数： 8k 阅读时长 ≈ 7 分钟

本篇为Leetcode做题过程中数组篇的总结和纠错等记录。

[TOC]

分类：

  • 数组的改变、移动
  • 数组的旋转
  • 统计数组中的元素
  • 数组的遍历
  • 二维数组及滚动数组
  • 特定顺序遍历二维数组
  • 二维数组变换
  • 前缀和数组

常用函数

zip()

用于数组合并。将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。注意Python3为了减少内存，返回的是一个对象，如果要展示，需手动list转换。

1
2
3
4
a = [2,3,4]
b = ['Gary','Bob','judy']
print(list(zip(a,b)))
[(2, 'Gary'), (3, 'Bob'), (4, 'judy')]

sorted()

对所有可迭代的对象进行排序操作，sort是应用在list上的方法。list的sort方法返回的是对已经存在的列表进行操作，无返回值，而内建函数sorted返回的是一个新的list。

1
2
3
4
5
6
sorted(iterable, cmp=None, key=None, reverse=False)
'''
cmp 比较的函数，具有两个参数
key 用来比较的元素
reverse True降序 False升序
'''

453.最小操作次数使数组元素相等（E）

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

示例 1：

1
2
3
4
5
输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2：

1
2
输入：nums = [1,1,1]
输出：0

提示：

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 答案保证符合 32-bit 整数

My Solution: （看了题解） —— 反向思维

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        m = min(nums)
        for i in range(len(nums)):
            sum += nums[i] - m
        return sum

分析：n-1个数同时减一，等于有一个数自身减一。所以把每个数减到和最小的数相等即可。计算每个数和最小值的差再求和得解。

283.移动零（E）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

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

提示:

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

My Solution: (思路正确基础上借助题解优化)

1
2
3
4
5
6
7
8
9
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(nums.count(0)):
            nums.remove(0)
            nums.append(0)

借助Python的特性完成，所以非常简单，把0移除再添加即可。

题解1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
	def moveZeroes(self, nums):
		"""
		:type nums: List[int]
		:rtype: None Do not return anything, modify nums in-place instead.
		"""
		if not nums:
			return 0
		# 第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]	
		j = 0
		for i in xrange(len(nums)):
			if nums[i]:
				nums[j] = nums[i]
				j += 1
		# 非0元素统计完了，剩下的都是0了
		# 所以第二次遍历把末尾的元素都赋为0即可
		for i in xrange(j,len(nums)):
			nums[i] = 0

# author：王尼玛

创建两个指针，第一次遍历把非零的元素赋值到数组左边，第二次遍历把剩下的元素全赋为零即可。

012.寻找数组中心下标（E）

My Solution:

采用前缀和进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # 前缀和
        sum = [0]*len(nums)
        sum[0] = nums[0]
        for i in range(1,len(nums)):
            sum[i] = sum[i-1] + nums[i]
        if sum[len(nums)-1] - sum[0] == 0:
            return 0
        for i in range(1,len(nums)):
            if sum[i-1] == sum[len(nums)-1] - sum[i]:
                return i
        return -1

665.非递减数列（M）

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

1
2
3
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

1
2
3
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示：

  • n == nums.length
  • 1 <= n <= 10^4
  • -10^5 <= nums[i] <= 10^5

My Solution:（ChatGPT纠错）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums1 = nums[:]
        l = len(nums1)
        count = 0
        for i in range(l - 1):
            if nums1[i] > nums1[i + 1]:
                if count == 1:
                    return False
                if i == 0 or nums1[i - 1] <= nums1[i + 1]:
                    nums1[i] = nums1[i + 1]
                else:
                    nums1[i + 1] = nums1[i]
                count += 1
        return True

布尔值True和 False都要首字母大写 ^ ^

count用来记录修改次数，在进行遍历时，判断当前元素是否大于下一个元素，如果大于就需要修改，此时count如果已经为1了，则超出了可修改的最大次数，直接返回False。如果尚未修改过一次，就根据当前元素和下一个元素的关系来进行不同的修改：

  • 如果当前元素是第一个元素，或者当前元素的前一个元素小于等于下一个元素，就将当前元素修改为下一个元素（以满足序列的非递减性质）

  • 否则，将下一个元素修改为当前元素。（下一个元组比当前元素小，修改为当前元素以确保非递减性质）

修改后要将count加1。

6189.按位与最大的最长子数组（M）

给你一个长度为n的整数数组nums，考虑nums中按位与(bitwise AND)运算得到的值最大的非空子数组。返回满足要求的最长子数组的长度，数组的按位与是对数组中所有数字进行按位与运算。子数组是数组中的一个连续元素序列。

分析

AND的特点是1可以变成0，0可以变成1。子数组AND的结果不会超过其中任何一个元素，因此最大值就是max(num)。

实际上就是求数组中的最大值最多连续出现了几次。

2420.找到所有好下标

给你一个大小为n下标从0开始的整数数组nums和一个正整数k。

对于k<= i <n-k之间的一个下标i，如果它满足以下条件，我们就称它为一个好下标。下标i之前的k个元素是非递增的，下标i之后的k个元素是非递减的。

按升序返回所有好下标。

分析

先倒着遍历，得到从每个位置向后的最长连续非降序列的长度，然后正着遍历，得到每个位置向前的最长连续非增序列的长度，同时统计答案。

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

分析：

可以用树形图来表示解，总和为5的所有组合再加上2，就是包含2的总和7的所有组合。

对树形图的编码通过DFS实现。

image-20240427165710231

树的叶子结点个数就是组合种类数

https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/?company_slug=huawei

Solution1:

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []

        def backtracking(index,path,target):
            """
            index: 开始下标
            path: 所在树上路径
            target: 需要凑成的总和
            """
            if index >= len(candidates) or target < 0:
                return
            if target == 0:
                ans.append(path[:])
                return
            for i in range(index, len(candidates)):
                path.append(candidates[i])
                backtracking(i,path,target-candidates[i])
                path.pop()
            
        backtracking(0,[],target)
        return ans

在每一次递归调用中，我们向 path 中添加一个元素，然后在递归完成后，我们需要将这个元素从 path 中移除，以确保下一次递归使用的是上一层的路径。

考虑到递归的特性，当我们从递归函数返回到上一层时，需要回到上一层的状态。如果我们不将上一层的元素从 path 中移除，那么 path 中会保留之前层级的修改，这将导致错误的结果。

前缀和数组

1652.拆炸弹(E)

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
如果 k == 0 ，将第 i 个数字用 0 替换。
由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

分析：

code为循环数组。可以建立一个长度为2*n的前缀和数组。

如果k<0，需要取位置i前的-k个数，为了防止下标越界，先将位置i往后进行n个偏移，对应区间[i+n+k, i+n-1]。(k<0所以+k反而小)

k>0，对应区间[i+1, i+k]

对于前缀和数组来说求和就是相减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        ans = [0] * n
        if k == 0:
            return ans
        sum = [0] * (2*n+1)
        for i in range(1, 2*n+1):
            sum[i] = sum[i-1] + code[(i-1) % n]
        for i in range(1,n+1):
            if k<0:
                ans[i-1] = sum[i+n-1] - sum[i+n+k-1]
            else:
                ans[i-1] = sum[i+k] - sum[i]
        return ans

6369.左右元素和的差值(E)

answer[i] = | leftSum[i] - rightSum[i] | 的简便写法：

[abs(x-y) for x,y in zip(leftSum, rightSum)]

2575.找出字符串的可整除数组(M)

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

  • 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
  • 否则，div[i] = 0

返回 word 的可整除数组。

示例 1：

1
2
3
输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

1
2
3
输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

提示：

  • 1 <= n <= 10^5
  • word.length == n
  • word 由数字 0 到 9 组成
  • 1 <= m <= 10^9

暴力遍历会超时。应该观察到，99取模和998取模的结果是有关系的，99可以被3整除，那么998的余数依然只和8有关系，所以可以把前缀的余数*10加上个位数字继续取模。

1
2
3
4
5
6
7
8
9
class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        n = len(word)
        div = []
        x = 0
        for i in word:
            x = (x*10 + int(i)) % m
            div.append(int(x==0))
        return div

826.安排工作以达到最大收益(M)

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

  • difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
  • worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

  • 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

1
2
3
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

1
2
输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

提示:

  • n == difficulty.length
  • n == profit.length
  • m == worker.length
  • 1 <= n, m <= 104
  • 1 <= difficulty[i], profit[i], worker[i] <= 105

分析：

difficulty数组和profit数组是一一对应的，可以绑到一起。按照difficulty从小到大排序，用双指针维护工人能做的最大的profit，即为第i个工人所能获得的最大利润。累加即可得到最后的最大利润。

排序+双指针

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()
        ans = j = max_profit = 0
        for w in worker:
            while j < len(jobs) and jobs[j][0] <= w:
                max_profit = max(max_profit, jobs[j][1])
                j += 1
            ans += max_profit
        return ans

双指针专题

  • 滑动窗口：两个指针指向同一数组，遍历方向相同并且不会相交。用于区间搜索
  • 搜索：两个指针指向同一数组，遍历方向相反。待搜索的数组往往是排好序的。

167.Two Sum II - Input Array is sorted(Easy)

88.Merge Sorted Array(Easy)

求子数组和就要想到双指针。

快慢指针

142.Linked List Cycle II (Medium)

对于链表找环路的问题，可以用快慢指针作为通用解法（Floyd判圈法）。给定两个指针，分别命名为slow和fast，起始位置在链表开头。每次fast前进两步, slow前进一步。如果fast可以走到尽头，那么说明没有环路；如果fast可以无限走下去说明一定有环路，且一定存在一个时刻slow和fast相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并让slow和fast每次都前进一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。

因为第一次相遇智能保证是在环中，而不能保证是环路的开始点。

踩坑

在删除列表元素时，会影响迭代的行为导致报错。因此要从列表末尾向前遍历，需要时删除元素。

切片：[i:] 从i开始到最后一个元素（包括i）

[:i] 从0开始到i-1（不包括i）

[1:4] 只选下标1和3的元素，不包括2

a[::-1] 取a的倒序

超出时间限制

字符长度为1 <= n <= 10^5，不能采用暴力枚举，否则会超时。