← 博客

Array

LC 188

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

方法一：切片操作；取数组里的后k个元素：nums[-k%n:]

方法二：先反转整体，再反转局部. 反转过程单独实现，不要用切片，因为可能会产生额外空间。

枚举

枚举右，维护左边

1031. 两个无重叠子数组的最大和

写一个函数，求左边的长度为l,右边的长度为r时的最大和

枚举右边的右端点，当右边的窗口每向右移动一步，左边的【可能最大值】也被更新了

双指针

相向双指针

LC 75: Sort Colors

用一个指针i来遍历这个数组，还需要用左右指针来指向下一个0或2待填入的位置。先用循环不断地填充2，然后遇到0的时候，填充0。
循环条件：i<=r。因为当i>r的时候，nums[i]肯定为2

15. 三数之和

双指针，需要注意索引处理.

首先外层指针需去重，内层的两个指针在每次获得答案的时候去重

42. 接雨水

双指针，一定要先更新最大值，再判断往哪边加水。
可以考虑普通的做法，即用两个数组保存从左边/从右边遍历时见过的最大值，这个最大值，是包括x本身的，所以要先更新最大值。

双序列

双序列双指针

88. 合并两个有序数组

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

双指针应当从后往前移动

844. 比较含退格的字符串

结束循环的条件必须是 while i>=0 or j>=0。不然的话，当 i<0, j>=0 的时候，循环就结束了，判断为 False，而j此时或许还在#上。

某个指针或许需要多一次，循环移动，来把这个字符串消耗完。比如"n"和"b#n"

244. 最短单词距离 II

拿两个list出来比较，找到里面最接近的pair.
双指针每次计算距离，然后根据值的大小，选择移动其中一个指针

三指针

2444. 统计定界子数组的数目

  • 假设所有元素都在minK, maxK 之间，那么一边遍历 array，一边看是否出现 minK, maxK，以及记录它们的 index。若当遍历到某个数时，minK 和 maxK 都找到了，则以此时的 i 为右端点，左端点在 [0,min(minI, maxI)]的所有subarray 都符合条件
  • 但事实上，有些元素不在[minK, maxK]之间，那么需要一个额外的 index 来记录上次越界元素出现的位置。则，minK和 maxK 都需要在 index 右边出现才行。并且左端点需要在[index+1, min(minI, maxI)]之间

技巧

277. 搜寻名人

  1. 遍历所有人，找到唯一一个可能是candidate的人
  • 初始化candidate=0， 枚举第1个到第n-1个候选人。
  • 一旦发现knows(candidate, i),则说明此时candidate不可能是名人了，更新candidate为i
  • 这一遍遍历结束，也不能说明所有哦人都认识candidate
  1. 对于该candidate，遍历所有人，确认他是否是真的名人

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

如果一个数组中没有重复的数，比如[1,3,4,2]。遍历index:从0到n-1 ，建立index到nums[index]的映射

0->1->3->2->4->null

如果有重复的数，比如[1,3,4,2,2]，因为所有元素都在[1, n] 范围内，所以必然存在一个环。为什么答案即环的起点呢？因为存在i,j，使得nums[i]=nums[j]=x，即两个节点会指向同一个节点

0->1->3->2->4->2->4

448. 找到所有数组中消失的数字

用原数组记录哪个数字出现过，想象有另一个长度为n的数组，从1到n，用来记录哪个数组出现过，哪个数字没出现过。

  • 比如数字4出现了，此时就把nums[4-1]+=n。
  • 如果每个数字都出现了，那么最后的nums应该是所有元素都大于n

945. 使数组唯一的最小增量

排序，然后找到数组中的最大值m,给所有数字做一个count。
从1遍历到m,如果遇到cnt[x]>1， 就把他往后推一位
最后，cnt[m+1]如果>1，把多余的都往后推

置换环

1
2
3
4
5
6
7
8

vis = [False] * n  # 标记该下标是否在某个环中被访问过

for v in a:        # 遍历所有下标（这里遍历的是 a 中的值，其实就是 0..n-1 的一个排列）
    if vis[v]: continue  # 已经在前面的环里访问过，跳过
    while not vis[v]:    # 否则，这里开始顺着 v -> a[v] -> a[a[v]] 走，直到回到已经访问过的点
        vis[v] = True
        v = a[v]
    ans -= 1  # 走完一圈，说明发现了一个完整的环

2471. 逐层排序二叉树所需的最少操作数目

比如说排序一个数组，每次操作可以两两交换，希望找到最少需要的操作数量。
array=[2,0,1,4,3] 这里[2,0,1]是一个置换环，[4,3]是一个置换环。

从第一个数开始，把这个数字当成下标去访问数组，不断循环直到回到这个数本身。

我们只需要计算每个环内需要多少次交换。对于每个环，交换次数为环的大小减一。

如果一个数组有N个数字，有M个环，则总共需要的交换次数为N-M

41. 缺失的第一个正数

记得在交换前，一定让index=arr[i]-1
还有循环条件是 while 1<=arr[i]<=n and arr[i]!=arr[arr[i]-1] 因为此时的arr[i]一定是可以对应到一个位置的，把它放到需要的位置上
不可以是arr[i]!=i+1, 因为i+1不一定在这个数组中存在，这会陷入无限循环

哈希表

最大平衡异或子数组的长度

子数组的按位异或（XOR）为 0。
子数组包含的 偶数 和 奇数 数量相等。

N xor M=K, K xor N=M，保持一个记录当前xor的变量，如果想把某个数字N从窗口中移除，直接 xor N即可

所以，可以对xor作前缀和

如何知道一个子数组，它的 偶数 和 奇数 数量相等？

diff用来表示偶数数量-奇数数量，当哈希表记录的前后两次diff相同时，表示这一段子数组的偶数和奇数数量相等

如何知道一个子数组,他的XOR为0？

同样，用hash记录每个index到目前为止的XOR，如果前后两次值一样都为M，则这一段子数组的XOR为0. (M xor 0)=M