Hot100
HOT100
哈希
利用哈希表降低数组O(n)查找复杂度为O(1)，python里字典用 dict() 或者 {} ,哈希集合用set()
查看器是否已存在使用 if complement in num_map ，在判断中一个in就行
两数之和：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
解：当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。关键是要看到直接减去这一点去查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
更好的考虑哈希表：插入的而同时进行哈希查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
字母异位词：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
解：关键是单词对比时怎么记录字母，可以考虑排序和计数以绕过记录,这里直接考虑哈希表来，按字母表排序，排序后作为键，注意map的查找时等于开始不等于结束，以及map的遍历访问为auto赋值，和first,second为key和val,还有插入还是考虑push_back和emplace_back吧，不要insert了，这样应该可以统一吧，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<string , vector<string>> res;
for(string& str :strs){
string key = str;
sort(key.begin(),key.end());
res[key].push_back(str);
}
vector<vector<string>> res2;
for (auto it = res.begin();it!=res.end();++it){
res2.push_back(it->second);
}
return res2;
}
};
最长连续序列：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解：O(n)只是要循环不要嵌套就行，可以并行，我们这里抓住x-1去查，而不是x+1,哈希集合查找是O(1)，简单来说就是每个数都判断一次这个数是不是连续序列的开头那个数。
以题解中的序列举例: [100，4，200，1，3，4，2] 去重后的哈希序列为： [100，4，200，1，3，2] 按照上面逻辑进行判断：
- 元素100是开头,因为没有99，且以100开头的序列长度为1
- 元素4不是开头，因为有3存在，过，
- 元素200是开头，因为没有199，且以200开头的序列长度为1
- 元素1是开头，因为没有0，且以1开头的序列长度为4，因为依次累加，2，3，4都存在。
- 元素3不是开头，因为2存在，过，
- 元素2不是开头，因为1存在，过。 每个元素只至多访问两遍，只有O(2N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans = 0;
unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
for (int x : st) { // 遍历哈希集合
if (st.contains(x - 1)) {
continue;
}
// x 是序列的起点
int y = x + 1;
while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
y++;
}
// 循环结束后，y-1 是最后一个在哈希集合中的数
ans = max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
}
return ans;
}
};
双指针
双指针是一种用两个指针（索引）协同扫描数据结构的技巧。与暴力双重循环 O(n^2) 相比，双指针往往能在 O(n) 内完成任务。
常见的三种类型：
| 类型 | 指针方向 | 典型场景 | 核心| 前提 |
|---|---|---|---|
| 对撞指针 | 两端向中间 | 有序数组搜索、回文判断 | 前提：数组有序，或问题本身具有某种单调性——移动某一端一定能让结果变大或变小 |
| 快慢指针 | 同向不同速 | 链表环检测、找中点 | Floyd 判圈算法（龟兔赛跑） |
| 同向双指针 | 同向同速/不同速 | 原地去重、移动元素 | 两个指针同向移动，一个负责”探索”，一个负责”记录”。这是滑动窗口的基础。 |
核心思路只有一句话：利用有序性或单调性，让两个指针各走一遍，就能覆盖所有需要考虑的情况。
移动0：
给定一个数组 ，编写一个函数将所有 移动到数组的末尾，同时保持非零元素的相对顺序。nums0
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
解：使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。注意到以下性质：左指针左边均为非零数；右指针左边直到左指针处均为零。因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。双指针不仅要考虑前者的遍历，也要考虑后者的遍历。一般蔚O（2n）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
盛最多水的容器：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解：注意双指针不能同时一步一步左右分别移动，会漏。在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为min(1,7)∗8=8。此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由两个指针指向的数字中较小值∗指针之间的距离决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
有读者可能会产生疑问：我们可不可以同时移动两个指针？ 不行。我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。我们left++和right–都是为了尝试取到更多的水，如果短的板不动的话，取到的水永远不会比上次多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int maxArea(vector<int>& height) {
int n= height.size();
int left =0,right =n-1, ans=0;
while(left<right){
int min_h = min(height[left],height[right]);
int area = min_h* (right-left);
ans = max(ans,area);
if(height[left]<=height[right]){
left++;
}else{
right--;
}
}
return ans;
}
};
三数之和：
给你一个整数数组 ，判断是否存在三元组 满足 、 且 ，同时还满足 。 请你返回所有和为 且不重复的三元组。nums[nums[i], nums[j], nums[k]]i != ji != kj != knums[i] + nums[j] + nums[k] == 00
注意：答案中不可以包含重复的三元组。
解：O(N^3),要去掉重复的，则先进行排序以找到规律。接下来就是去重，第一次遍历只去掉重复数，剩下的两个数使用双指针来解决。因为排序了，故进行b+c>target-a,从左指针找，否则，从右指针找。同时，要保证b再c的左边，且不要进行重复3元组的计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
接雨水：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
解：对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。
动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)？注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。如果height[left] < height[right]，则必有leftMax < rightMax,因为每次移动都是短板指针，因此height[left]和height[left]有一个始终是全局最大值，height[left] < height[right]等价于height[left] < 全局max=rightMax，这样leftMax < rightMax也就不难理解了,例如一开始如果最右边一直比左边的大，也就是至少能在边界上框住水。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
};
滑动窗口
维护一个可伸缩的区间 [left, right]，通过移动左右边界来遍历所有可能的连续子数组/子串。
什么时候该想到滑动窗口？ 当题目同时满足以下两点：看到”连续”+”条件”
- 求的是 连续子数组 或 连续子串
- 需要满足某个 条件（最长、最短、恰好包含等）
固定窗口：窗口长度不变，题目较为简单
可变窗口：窗口大小不固定，right 负责扩展，left 负责收缩。两类常见问法：
- 求最长：窗口尽量大，不满足条件时才收缩 →
while收缩 - 求最短：窗口满足条件后就尝试收缩 →
while收缩并更新答案
在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针（只处理新加入和删去的，不用手动移动，直接下标读取，一般先考虑右边的）。在任意时刻，只有一个指针运动，而另一个保持静止。模板
无重复字符的最长子串：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
解：这种查找相邻多个元素之间的关系的，用滑动窗口（特别是要相邻几个不确定时）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
找到字符串中所有字母异位词：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
解：异位词，考虑排序和计数。这里用计数+滑动窗口。利用26个字母的差，不过我们可以直接考虑所有的差。因为异位词暗示不可能p有重复的。可以直接考虑26和字母的差，在判断滑动窗口中每种字母的数量与字符串 p 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。还有，用26个是一定比slen,plen短的。最后，注意s不能比p短。同时，vector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int slen = s.size(),plen = p.size();
if(slen < plen){
return vector<int>{};
}
vector<int> count(26);
//一开始只处理前3个
for(int i=0;i<plen;++i){
++count[s[i]-'a'];
--count[p[i]-'a'];
}
int diff =0;
for(int j=0;j<26;++j){
if(count[j]!=0){
++diff;
}
}
if(diff==0){
ans.emplace_back(0);
}
for(int i=0;i<slen-plen;++i){
//窗口移动，只处理删去的和新加入的
if(count[s[i]-'a'] ==1 ){// 窗口删去字母 s[i]， 数量与字符串 p 中的数量从不同变得相同
--diff;
}else if(count[s[i]-'a'] ==0){// 窗口删去字母 s[i] ,数量与字符串 p 中的数量从相同变得不同
++diff;
}
--count[s[i]-'a'];
//处理新加入的
if (count[s[i + plen] - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
--diff;
} else if (count[s[i + plen] - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
++diff;
}
++count[s[i + plen] - 'a'];
if (diff == 0) {
ans.emplace_back(i + 1);
}
}
return ans;
}
};
子串
滑动窗口，前缀和
和为K的子数组：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
解：前缀和+哈希表。暴力的话，我们可以找前端点 i 和后端点 j ，是O(n^2)，还需要 O(n) 的时间复杂度遍历子数组来求和。但是实际上可以直接使用前缀和，需要满足：pre[j−1]==pre[i]−k，所以我们考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可，哈希表查找。我们建立哈希表 mp，以前缀和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新 mp 边计算答案，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1) 时间内得到。
首先容易子数组可以通过pre[i]-pre[j-1]来计算。假设当前遍历到 i ,前缀和为pre[i]，我们想知道之前有没有一个位置j其前缀和等于pre[j]=pre[i]-K（为了让nums[j+1…i]=K，即pre[i]-pre[j]=k，移项即可得）,该位置就是满足要求的子数组头。也就是说：只要以前出现过前缀和
pre-k，就说明存在一个子数组和为k。我们边计数前缀和边找，找用哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
滑动窗口最大值（困难）：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
解：不要忘记删去的那个也有可能就是最大值，也要处理左边窗口边界值，而不是只拿删去的与新加入的比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//我的解法，应该也是O（N）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res;
if (n == 0 || k == 0) return res;
int l = 0, r = k - 1;
// 先处理第一个窗口
int tmp = INT_MIN;
for (int i = l; i <= r; ++i) {
tmp = max(tmp, nums[i]);
}
res.push_back(tmp);
// 滑动窗口，l 和 r 向右滑
while (r < n - 1) {
++l;
++r;
// 如果上一个最大值 nums[l - 1] 被移除了，我们需要重新在窗口中找最大值
if (nums[l - 1] == tmp) {
tmp = INT_MIN;
for (int i = l; i <= r; ++i) {
tmp = max(tmp, nums[i]);
}
} else {
// 否则，只需比较新加入的 nums[r]
tmp = max(tmp, nums[r]);
}
res.push_back(tmp);
}
return res;
}
};
官方写法：(优先队列)，最大值吗，单调队列，下面的使用的是deque双端队列，自己维护单调性，确实比我的快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q; // 存储下标，保持队列单调递减
vector<int> res;
for (int i = 0; i < nums.size(); ++i) {
// 如果队首元素已经滑出窗口，则弹出
if (!q.empty() && q.front() <= i - k) {
q.pop_front();
}
// 维护队列单调性：移除所有比当前元素小的
while (!q.empty() && nums[q.back()] < nums[i]) {
q.pop_back();
}
q.push_back(i); // 当前元素加入队尾
// 当窗口大小达到 k，开始记录结果
if (i >= k - 1) {
res.push_back(nums[q.front()]); // 队首是当前窗口最大值
}
}
return res;
}
};
最小覆盖子串（困难）：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
解：滑动窗口
- 统计 t 的字符需求：用
cnt_t记录t中每个字符需要出现的次数。- 右指针扩张：
right向右移动，把字符加入窗口。- 左指针收缩：当窗口满足
cnt_s >= cnt_t时，尝试右移left缩小窗口，同时更新最短子串。- 返回结果：如果没有找到合法窗口，返回
""；否则返回s[ans_left: ans_right + 1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def minWindow(self, s: str, t: str) -> str:
cnt_t = Counter(t) # t 中每个字符需要出现的次数
cnt_s = Counter() # 当前窗口中每个字符出现的次数
ans_left, ans_right = -1, len(s)
left = 0
for right, c in enumerate(s):
cnt_s[c] += 1
# 当前窗口已经包含 t 中所有字符且数量足够
while cnt_s >= cnt_t:
if right - left < ans_right - ans_left:
ans_left, ans_right = left, right
cnt_s[s[left]] -= 1
left += 1
return "" if ans_left < 0 else s[ans_left: ans_right + 1]
普通数组
前缀和，翻转数组，双指针
最大子数组和
题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
解： 前缀和数组根据坐标连线画成一座山，最大子数组和就是最高的山峰减去前面最低的山谷的高度差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = float('-inf')
min_sum = pre_sum =0 #前缀和最小值和当前前缀和
for i in nums:
pre_sum += i
ans = max(ans, pre_sum - min_sum)
min_sum = min(min_sum, pre_sum)
return ans
# 为什么一开始前缀和最小可以为0，这是0 代表的是「空前缀」
#nums: 2 -1 3
#前缀和: 2 1 4
#前缀和数组有隐含的-1所以和0值
#下标: -1 0 1 2
#前缀和: 0 2 1 4
合并区间
题目:以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
解：合并区间的核心思想是先排序，再合并： 排序：按区间起点升序排列，这样重叠的区间就会相邻 合并：遍历排序后的区间，若当前区间起点 ≤ 上一个区间的终点，则合并；否则加入结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x:x[0])
merged =[]
for interval in intervals:
# 一开始列表为空或者当前区间与上一区间不重合，直接添加
if not merged or merged[-1][1] < interval[0]:
#merged[-1][0]是已经处理好的最后的左端点，merged[-1][1]
#merged[-1][1]才是右端点我们想要的
merged.append(interval)
else:
# 否则的话，我们就可以与上一区间进行合并
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
轮转数组
题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。要求空间复杂度O(1)。
解：1.直接法：将原数组下标为 i 的元素放至新数组下标为 (i+k)modn 的位置，最后将新数组拷贝至原数组即可。【o(n),o(n)】
2.环形法，这里不介绍
3.翻转数组：该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 kmodn 个元素就被移至数组头部，然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i:int, j:int)->None:
while i < j:
nums[i],nums[j] =nums[j],nums[i]
i+=1
j-=1
n = len(nums)
k %=n
reverse(0,n-1) #记得-1
reverse(0,k-1)
reverse(k,n-1)
除滋生之外数组的乘积
题目：
解：我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。下面让我们更加具体的描述这个算法：初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。我们需要用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。同理，对于数组 R，R[length-1] 应为 1。length 指的是输入数组的大小。其他元素：R[i] = R[i+1] * nums[i+1]。当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]。
但是这样还不够利用好空间复杂度：由于输出数组不算在空间复杂度内，那么我们可以将 L 或 R 数组用输出数组来计算。先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果。让我们来看看基于这个思想的算法。初始化 answer 数组，对于给定索引 i，answer[i] 代表的是 i 左侧所有数字的乘积。构造方式与之前相同，只是我们试图节省空间，先把 answer 作为方法一的 L 数组。这种方法的唯一变化就是我们没有构造 R 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 answer[i]=answer[i]∗R。然后 R 更新为 R=R∗nums[i]，其中变量 R 表示的就是索引右侧数字的乘积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
length = len(nums)
answer = [0]*length
# answer[i] 表示索引 i 左侧所有元素的乘积
# 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
answer[0]=1
for i in range(1,length):
answer[i] = nums[i-1] * answer[i-1]
# R 为右侧所有元素的乘积
# 刚开始右边没有元素，所以 R = 1
R = 1
for i in reversed(range(length)):
# 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R
# 更新R,R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *=nums[i]
return answer
矩阵
标记是否访问（原辅助大小，行+列数组，单个标记+1行+1列），按层遍历（注意边界），转置，翻转，在矩阵的二分查找，z查找
矩阵置0
题目：给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法（即空间O（1））
解：我们可以用两个标记数组分别记录每一行和每一列是否有零出现。=》我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。=》只使用一个标记变量记录第一列是否原本存在 0。这样，第一列的第一个元素即可以标记第一行是否出现 0。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m,n =len(matrix),len(matrix[0])
flag = False
for i in range(m):
if matrix[i][0] == 0: #第一列有0
flag = True
for j in range(1,n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] =0 # 一样使用第一行和第一列
# 标记位标记完毕现在开始更新
for i in range(m-1,-1,-1): # 从最后一行开始反向，因为看的是第一行作为标志
for j in range(1,n):
if matrix[i][0] ==0 or matrix[0][j] ==0:
matrix[i][j] =0
# 接着更新第一列，看看原本有没有0，直接看标记flag就行
if flag:
matrix[i][0] =0
螺旋矩阵
题目：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
解：可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。
1.从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。
2.从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。
3.如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。
遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]: #保证为矩阵
return list()
rows , columns = len(matrix), len(matrix[0])
order = list()
left , right ,top ,bottom =0,columns-1,0,rows-1 # 我们先按照减去1的小标约定，后面再加回来
while left <= right and top<=bottom:
for column in range(left,right+1): # Python 的 range() 是左闭右开区间,上面初始说了是下标，下面同理
order.append(matrix[top][column])
for row in range(top+1,bottom+1): # 第一行的最后一个已经加了，记得top也加1
order.append(matrix[row][right])
if left < right and top < bottom: # 终止条件和循环最后一句配合
for column in range(right-1, left-1, -1): # 类似上面，但这楼里是反向了
order.append(matrix[bottom][column])
for row in range(bottom-1,top, -1): #记得最后那个只有两个所以bottom要减去1
order.append(matrix[row][left])
left, right, top, bottom = left+1, right-1, top+1,bottom-1
return order
旋转图像
题目：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
解：水平翻转+转置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 水平翻转
for i in range(n//2):
for j in range(n):
matrix[i][j], matrix[n-1-i][j] = matrix[n-1-i][j], matrix[i][j]
#转置
for i in range(n):
for j in range(i): #注意转置（对角线翻转）是范围i
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
搜索二维矩阵 II（右上角搜索）
题目：编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
解：记得这里第二行的第一个不大于第一行最后一个不可以直接二分。得每一行都二分。或者更好的思路：Z 字形查找
我们可以从矩阵 matrix 的右上角 (0,n−1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (x,y)，那么我们希望在以 matrix 的左下角为左下角、以 (x,y) 为右上角的矩阵中进行搜索，即行的范围为 [x,m−1]，列的范围为 [0,y]：
如果 matrix[x,y]=target，说明搜索完成；
如果 matrix[x,y]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 y 列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即将 y 减少 1；
如果 matrix[x,y]<target，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 x 行的元素都是严格小于 target 的，因此我们可以将它们全部忽略，即将 x 增加 1。
在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 target。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
x,y =0,n-1
while x<m and y>=0:
if matrix[x][y] ==target:
return True
if matrix[x][y] > target:
y-=1
else:
x+=1
return False
核心思想就是：选择一个位置，使得两个方向一个越来越大，一个越来越小。 这样才能好的利用其有序性。右上角（或左下角）正好满足这一性质，因此能做到 O(m+n) 的时间复杂度。
链表
双指针，翻转（注意风筝），是否有环，环入口，
相交链表
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
解：主要的点在于不相交的部分不一样长怎么办。直观的方法是先让长的链表走s步，s是两个链表的长度之差。这里更优雅，比如公共c,不公共分别为a,b,于是A：m=a+c,B：n=b+c;接着第一轮分别走自己的，第二轮的话直接A去走B的，走b,B去走A的，走a，只要有焦点一定相遇。A少走的那部分补回来了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
pA , pB= headA, headB
while pA != pB:
pA = headB if pA is None else pA.next
pB= headA if pB is None else pB.next
return pA
没有相交怎么办？如果不相交也会到达最后的空，最多跑两轮
反转链表
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解：直接迭代即可：假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head # 最后倒过来最后是空，所以前面一开始应该就有一个空
while curr is not None: #最好记住下面4句的顺序，即从下一个开始往前3个物品（包含点，线），再回下一个，以此蔚一个循环
temp = curr.next #必须先记住下一个
curr.next = prev
prev = curr
curr = temp
return prev # curr最后指向空了
O(N),O(1)。保存后面 → 断开并指向前面 → prev前进 → curr前进
回文链表
题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表（回文 序列是向前和向后读都相同的序列。）是，返回 true ；否则，返回 false 。你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解：快慢指针？差一点就对了，只是可以处理一个步骤
找到前半部分链表的尾节点。（快慢指针）
反转后半部分链表。
判断是否回文。
恢复链表。
返回结果。
执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。
若链表有奇数个节点，则中间的节点应该看作是前半部分。！！
步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。
步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。
步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head is None:
return True
first_half_end = self.end_of_first_half(head)
second_start = self.reverse_list(first_half_end.next)
# 判断
result = True
first_position = head # 后面翻转链表还要用，不能用他们两来移动
second_position = second_start
while result and second_position is not None: # 前面及奇数个把中间节点算入前面的了，所以以后面的那个作为判别边界
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next
# 还原
first_half_end.next = self.reverse_list(second_start)
return result
def end_of_first_half(self, head):
fast, slow = head, head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def reverse_list(self, head):
prev, curr = None, head # 最后倒过来最后是空，所以前面一开始应该就有一个空
while curr is not None: #最好记住下面4句的顺序
temp = curr.next #必须先记住下一个
curr.next = prev
prev = curr
curr = temp
return prev # curr最后指向空了
前面及奇数个把中间节点算入前面的了，所以以后面的那个作为判别边界
反转一次半列就行哦，不用反转再反转
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
解:快慢指针。如果人生轨迹一样，你我迟早相遇。进入环后快指针相当于每次都向慢指针靠近一点，不管慢指针进入是快指针走了多远的距离。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None or head.next is None:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
解：一样快慢指针。只是这里还要返回入环节点。
- 使用快慢指针找到相遇点
- 设从起点到环入口的距离为
a，从环入口到相遇点的距离为b，从相遇点到环入口的距离为c - 当快慢指针相遇时，慢指针走了
a + b，快指针走了a + b + n(b + c) - 由于快指针速度是慢指针的 2 倍：
2(a + b) = a + b + n(b + c)，化简得a = (n-1)(b+c) + c - 这意味着从起点到环入口的距离等于从相遇点到环入口的距离（加上整数倍的环长）
- 因此，将一个指针置到相遇点，一个重置到起点，两个指针同时移动，相遇点就是环的入口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not fast or not fast.next:
return None
# 将slow置回头节点，fast已经置为相遇点
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
合并两个有序链表
解：无许多说，fiki，我还记得你~~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
p1 , p2 = list1,list2
res = ListNode(0)
curr = res
while p1 and p2:
if p1.val <= p2.val:
curr.next = p1
p1 = p1.next
else:
curr.next = p2
p2 = p2.next
curr = curr.next #下一步这里别忘了
curr.next = p1 if p1 else p2 # 这里后面的拼接也别忘了
return res.next # 记得是返回next
每一步curr移动别忘了，比较一个跑完了另一个最后的拼接也别忘了， 记得是返回next
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。每个链表中的节点数在范围 [1, 100]内
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807
解：如果直接化为两个完整数在相加则最后的加法是两个10^100相加，太大了这个数。应该各位相加进位。双指针,实际上就是直接相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
p1, p2 = l1, l2
eps = 0
res = ListNode(0)
curr = res
while p1 or p2 or eps: #只要还有 l1、还有 l2、或者还有一个进位，就继续计算。
v1 = p1.val if p1 else 0
v2 = p2.val if p2 else 0
tmp = v1 + v2 + eps
v = tmp % 10
eps = tmp // 10
curr.next = ListNode(v)
curr = curr.next
# 记得考虑不同长度的情况
if p1:
p1 = p1.next
if p2:
p2 = p2.next
return res.next
1.记得考虑不同长度的情况。2.还有就是边界判断最高位继续计算。3.还有就是不用区分是否小于10，直接//和%就行
删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解:双指针，快指针提前N+1个就行，后面f指向nulls时slow指向倒数n+1个，直接删去下一个就行（更方便）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
# 记得这道题要加头节点
dummy = ListNode(0)
dummy.next = head
f = s = dummy
for _ in range(n+1):
f = f.next
while f:
f = f.next
s = s.next
# Python 有垃圾回收机制，只要这个节点没有其他引用，就会自动回收。
s.next = s.next.next
return dummy.next
1.Python 有垃圾回收机制，无须delete节点。只要这个节点没有其他引用，就会自动回收。
2.这个记得要创建新的链表不要破坏原有链表。
两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
解：迭代。
创建哑结点 dummyHead，令 dummyHead.next = head。令 temp 表示当前到达的节点，初始时 temp = dummyHead。每次需要交换 temp 后面的两个节点。
如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得 temp 后面的两个节点 node1 和 node2，通过更新节点的指针关系实现两两交换节点。
具体而言，交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1，因此需要进行如下操作。
完成上述操作之后，节点关系即变成 temp -> node2 -> node1。再令 temp = node1，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。
两两交换链表中的节点之后，新的链表的头节点是 dummyHead.next，返回新的链表的头节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode | None) -> ListNode | None:
dummy = ListNode(0)
dummy.next = head
temp = dummy
while temp.next and temp.next.next:
node1 = temp.next
node2 = temp.next.next
temp.next = node2
# 主要顺序是要使用前看看奇是否要要拉取的“风筝(fiki)”
node1.next = node2.next
node2.next = node1
# 进行下一轮
temp = node1
return dummy.next
利用的是新建链表自带的虚拟头节点和tmp保留和交换。
K 个一组翻转链表(困难)
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
解：1.我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。
2.翻转一个分组内的子链表(参考之前的)，对于第一个子链表，它的头节点 head 前面是没有节点 pre 的
3.创建了节点 pre 吗？这个节点一开始被连接到了头节点的前面，而无论之后链表有没有翻转，它的 next 指针都会指向正确的头节点。那么我们只要返回它的下一个节点就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
# 翻转一个子链表，并且返回新的头与尾
def reverse(self, head: ListNode, tail: ListNode):
prev = tail.next
p = head
while prev != tail:
nex = p.next
p.next = prev
prev = p
p = nex
return tail, head
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
hair = ListNode(0)
hair.next = head
pre = hair
while head:
tail = pre
# 查看剩余部分长度是否大于等于 k
for i in range(k):
tail = tail.next
if not tail:
return hair.next
nex = tail.next
head, tail = self.reverse(head, tail)
# 把子链表重新接回原链表
pre.next = head
tail.next = nex
pre = tail
head = tail.next
return hair.next
随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解：主要问题：当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建。使用回溯+哈希表（官方解法）.我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。
具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。
我们这里可以使用两次遍历 + 哈希表（非官方解法）。我们不是在创建节点的同时就复制 random，而是先把所有节点创建出来，再去连接 random。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
# old_node -> new_node
dic = {}
# 第一次遍历：创建复制节点
curr = head
while curr:
dic[curr] = Node(curr.val)
curr = curr.next
# 第二次遍历：连接 next 和 random
curr = head
while curr:
dic[curr].next = dic[curr.next] if curr.next else None
dic[curr].random = dic[curr.random] if curr.random else None
curr = curr.next
return dic[head]
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
解：链表最快的不是快速排序而是归并排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 0 个或 1 个节点，本身就是有序的
if not head or not head.next:
return head
# 1. 找中点
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. 从中间断开
right = slow.next
slow.next = None
# 3. 分别排序
left = self.sortList(head)
right = self.sortList(right)
# 4. 合并两个有序链表
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left
left = left.next
else:
curr.next = right
right = right.next
curr = curr.next
# 接上剩余部分
curr.next = left if left else right
return dummy.next
合并 K 个升序链表(困难)
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
解：将 k 个链表两两合并，直到只剩下一个链表，使用分治的思想，递归地合并链表。注意这里是“链表数组”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def mergeKLists(lists):
if not lists:
return None
if len(lists) == 1:
return lists[0]
# 最关键的就是这 3 行
mid = len(lists) // 2
left = mergeKLists(lists[:mid])
right = mergeKLists(lists[mid:])
return mergeTwoLists(left, right)
# 就是上一个的合并，即合并两个链表
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next
LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
解：主要还是一个 删除原位置 + 移动到头部 的两个函数的拼接实现get和put,还有一个删除尾部的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class DLinkNode:
def __init__(self, key = 0, value =0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = dict()
self.head =DLinkNode()
self.tail =DLinkNode()
# 在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
self.head.next = self.tail
self.tail.prev = self.head
self.capacity =capacity
self.size = 0
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.moveToHead(node) # 自己实现的移动到头部，实际上是删除原位置，在头部造一个一样的
return node.value
def put(self, key: int, value: int) -> None:
if key not in self.cache:
# 如果 key 不存在，创建一个新的节点
node = DLinkNode(key, value)
# 添加进哈希表
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量，删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)
# 再头部造一个一样的
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
# 删除原位置
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
# 移动到头部
def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)
def removeTail(self):
node = self.tail.prev # 找到伪尾节点的前一个真实尾节点
self.removeNode(node)
return node
二叉树
二叉树挺喜欢“递归”，但是实现时1.主要流程；2.递归终止条件；3.python递归自己要self（如果是class里面第一层而不是子def）
二叉树的中序遍历
递归和优先队列两种方法：
方法1：递归
- 先遍历左子树
- 访问根节点
- 再遍历右子树
方法2：迭代（使用栈）
- 使用栈模拟递归过程
- 先一直向左遍历，将节点入栈
- 当左子树遍历完后，弹出栈顶节点并访问
- 转向右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode | None) -> list[int]:
res = []
def dfe(node):
if node is None:
return
dfe(node.left)
res.append(node.val)
dfe(node.right)
dfe(root)
return res
# 迭代方法
class Solution:
def inorderTraversal(self, root: TreeNode | None) -> list[int]:
res = []
stack = []
curr = root
while curr or stack: # 只要还有“没处理完的节点”，就必须继续循环。
# 先一直向左遍历，将节点入栈
while curr:
stack.append(curr)
curr = curr.left
# 当左子树遍历完后，弹出栈顶节点并访问
curr = stack.pop()
res.append(curr.val)
# 转向右子树
curr = curr.right
return res
二叉树的最大深度
解：深度优先搜索（递归法），即
- 如果根节点为空，返回 0
- 否则，返回
max(左子树深度, 右子树深度) + 1
1
2
3
4
5
6
7
8
9
10
11
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: TreeNode | None) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1
翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。输入为层序遍历的数组。
解：一样递归。输入和输出虽然是看这要层序遍历，但是不需要实现直接返回root。主要递归流程就是交换就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: #终止条件
return None
# 主要实现的过程
root.left, root.right = root.right, root.left
self.invertTree(root.left)#这里的左右好像没关系
self.invertTree(root.right)
return root
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
解：一样递归。这里的对称实际上就是下一次的话要复制一个在右边，再加个根节点,这样子来看直接判断(left.right，right.left),(left.left,right.right),（left.val,right.val）是否相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root: TreeNode | None) -> bool:
def ismiror(left,right): #记得这道直接传左右指针
# 注意这两个判断顺序
if not left and not right:
return True
if not left or not right: # 一个又一个没有才不对称
return False
return (left.val == right.val and
ismiror(left.left,right.right) and
ismiror(left.right, right.left)) #注意这里的大括号
if not root: #传的是左右指针这里要额外判断
return True
return ismiror(root.left, root.right)
二叉树的直径（最大深度pro）
给你一棵二叉树的根节点，返回该树的 直径。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 root。
两节点之间路径的 长度 由它们之间边数表示。
解：深度优先搜索DFS：
- 对于每个节点，计算经过该节点的最长路径
- 路径长度 = 左子树最大深度 + 右子树最大深度
- 在递归过程中更新全局最大直径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
max_diameter = 0
def maxDepth(node):
# 设置全局变量
nonlocal max_diameter
if not node:
return 0
l_depth = maxDepth(node.left)
r_depth = maxDepth(node.right)
max_diameter = max(max_diameter, l_depth+r_depth)
return 1+ max(l_depth, r_depth) # 加上自己,注意深度和长度是两条线，自己的深度是左右子树最大加自己
maxDepth(root)
return max_diameter
1.加上自己,注意深度和长度是两条线
2.内部函数 ,要修改外层函数定义的变量
global：修改模块（全局）作用域的变量。
nonlocal：修改外层函数作用域的变量。
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
解：使用队列（BFS）：
- 将根节点入队
- 当队列不为空时：
- 记录当前层的节点数
- 遍历当前层的所有节点，将它们的值加入结果，并将它们的子节点入队
- 将当前层的结果加入最终结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: TreeNode | None) -> list[list[int]]:
if not root:
return []
res = []
queue = deque([root])
while queue:
levelsize = len(queue)
level = []
for _ in range(levelsize):
node = queue.popleft()
level.append(node.val)
# 左右子节点入队列
if node.left:
queue.append(node.left) # 队列存的是节点
if node.right:
queue.append(node.right)
res.append(level) # 每层的加进去
return res
将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
有效 二叉搜索树定义如下：(即按照中序遍历为升序的)
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。
解：给定二叉搜索树的中序遍历，是否可以唯一地确定二叉搜索树？答案是否定的。如果没有要求二叉搜索树的高度平衡，则任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。
如果增加一个限制条件，即要求二叉搜索树的高度平衡，是否可以唯一地确定二叉搜索树？答案仍然是否定的。
递归法：
- 选择数组中间的元素创建作为根节点（这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡，无论奇偶）
- 递归构建左子树（左半部分）和右子树（右半部分）
- 这样可以保证树的高度平衡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: list[int]) -> TreeNode | None:
def build(left,righat):
if left > right:
return None
mid = (left+right)//2
root = TreeNode(nums[mid]) # 创建根节点
root.left = build(left,mid-1) # 递归创建左右子树，记得这里边界是left和right
root.right = build(mid+1, right)
return root # 一次递归返回的是创建的节点
res = build(0,len(nums)-1)
return res
验证二叉搜索树(中序遍历pro)
给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。
解：中序遍历(递归)就行：
- 二叉搜索树的中序遍历结果是严格递增的
- 进行中序遍历，检查当前节点的值是否大于前一个节点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isValidBST(root):
prev = None
def inorder(self, node):
nonlocal prev
if not node:
return True
# 左 → 根 → 右
if not inorder(node.left): # 左子树如果一直是False回来的，就一直是False
return False
#根
if prev is not None and node.val <= prev: # 如果不是第一个且不大于上一个，则是回复F
return False
prev = node.val # 无论怎么样都要赋值prev更新
return inorder(node.right) # 如果之前的两个不成立，则是看右了
return inorder(root)
二叉搜索树中第 K 小的元素(中序遍历pro)
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
解：中序遍历（栈）：
- 二叉搜索树的中序遍历结果是严格递增的
- 进行中序遍历，找到第 k 个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k-=1
if k==0:
return curr.val
curr = curr.right # 不要忘记这个
二叉树的右视图（层序遍历pro）
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解：层序遍历：
- 使用层序遍历，记录每层最后一个节点
- 或者使用DFS，优先访问右子树，记录每层第一个访问到的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
queue = deque([root])
while queue:
levelsize = len(queue)
level = []
for _ in range(levelsize):
node = queue.popleft()
level.append(node.val)
# 左右子节点入队列
if node.left:
queue.append(node.left) # 队列存的是节点
if node.right:
queue.append(node.right)
res.append(level[-1]) # 每层最后一个的加进去!!!只改这里就行
return res
如果更好的空间复杂度，吧level[]删了，直接在循环里res进行append就行（在if i == level_size - 1时）
二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 (根左右)顺序相同。使用原地算法（
O(1)额外空间）展开这棵树
解：直接前序遍历当然可以但是那样就O(N)的栈空间了。这里额外技巧：
寻找前驱节点。对于当前节点 curr，如果它有左子树，就把 左子树最右边的节点 接到当前节点的右子树前面。
1.先找左子树的最右节点，将右子树接到其上作为其的右子树
2.根节点的右指针指向左子树
3.根节点的左指针
4.迭代下一轮，curr指向右指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode | None) -> None:
"""
Do not return anything, modify root in-place instead.
"""
curr = root
while curr:
if curr.left:
# 找左子树最右边的节点
pre = curr.left
while pre.right:
pre = pre.right
# 把原来的右子树接到 pre 后面
pre.right = curr.right
# 左子树搬到右边
curr.right = curr.left
curr.left = None
# 继续处理右边
curr = curr.right
1
2 /
3 4
5
6
从前序与中序遍历序列构造二叉树（将有序数组转换为二叉搜索树pro）
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
解：递归构造：实际上就是之前的中序遍历构造二叉树
- 前序遍历的第一个元素是根节点（中序遍历中对根节点进行定位要整体扫描复杂度较高），但是还要其索引
- 在中序遍历中找到根节点的位置(哈希表)，左边是左子树，右边是右子树
- 递归构造左子树和右子树
可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 O(1) 的时间对根节点进行定位了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
if not preorder or not inorder:
return None
inorder_map = {val: idx for idx, val in enumerate(inorder)} # 把中序遍历的值和索引放入哈希表
pre_idx = 0
def build(left, right):
nonlocal pre_idx
if left > right:
return None
root_val = preorder[pre_idx] # 一开始前序遍历中的第一个节点就是根节点，后面每次加1
#永远拿到的是当前应该创建的根节点
root = TreeNode(root_val) # 这是主要的构造，原来的
pre_idx += 1
root_index = inorder_map[root_val]
root.left = build(left, root_index - 1)
root.right = build(root_index + 1, right)
return root
return build(0, len(inorder) - 1)
中序构建时只负责把范围切开。前序决定“下一个造谁”，但它干好时根-》左-》右。所以说，”中序构建二叉树是前序的“
路径总和III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
解：前缀和 + 哈希表:哈希表key = 前缀和；value = 从当前 DFS 路径起点（根）到某个节点的“前缀和”出现了多少次。
1.先算当前前缀和
2.查差值 （减去对应值）
3.加入当前和
4.DFS （cout记得累加）
5.回溯（哈希表记得对应值处-1）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
，cout记得累加当我们从一个节点退回来，换到它的兄弟节点时，之前那条分支的信息必须删掉。class Solution:
def pathSum(self, root, targetSum):
prefix = {0: 1} # 初始化含有（0，1）对的哈希表，一开始前缀和为0的次数为1
def dfs(node, curr_sum):# 和作为参数传递
if not node:
return 0 # 返回的是个数，为0，如果是节点才是None,当然还是要看题目
# 计算当前前缀和(记得减去对应值)
curr_sum += node.val
# 查差值，看之前有没有前缀和 = curr_sum - targetSum
count = prefix.get(curr_sum - targetSum, 0) # 有就返回对应的数字
# 把当前前缀和加入哈希表
prefix[curr_sum] = prefix.get(curr_sum, 0) + 1 # 先看现在的哈希表里的有没有对应的和，有则加1就行
# DFS ，继续左右子树，cout记得累加
count += dfs(node.left, curr_sum)
count += dfs(node.right, curr_sum)
# 回溯，因为当前 DFS 这条路径上的前缀和。当我们从一个节点退回来，换到它的兄弟节点时，之前那条分支的信息必须删掉。
prefix[curr_sum] -= 1
return count
return dfs(root, 0)
和作为参数传递
前缀和加哈希表要记得初始化加（0，1）
记得回溯，因为当前 DFS 这条路径上的前缀和。当我们从一个节点退回来，换到它的兄弟节点时，之前那条分支的信息必须删掉。（举一个3节点的例子就行）
DFS时cout记得累加
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解：递归法：
- 如果当前节点为空或等于 p 或 q，返回当前节点
- 递归查找左子树和右子树
- 如果左右子树都找到了节点，说明当前节点是最近公共祖先
- 如果只有一边找到了，返回那一边的结果(直接return left if left else right就行)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root ==p or root ==q:
return root
left = self.lowestCommonAncestor(root.left, p,q)
right = self.lowestCommonAncestor(root.right, p,q)
if left and right:
return root
return left if left else right # dfs时隐含二叉树如果不处理终止条件最后要返回None的，这里可以作为对错判断（常见用 法）
二叉树中的最大路径和（困难）
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root，返回其 最大路径和。
解：递归法：
- 定义辅助函数
maxGain(node)返回以 node 为起点的最大路径和（最大贡献值） - 对于每个节点，计算：
- 经过该节点的最大路径和 =
node.val + left_gain + right_gain - 返回给父节点的最大增益 =
node.val + max(left_gain, right_gain)
- 经过该节点的最大路径和 =
- 在递归过程中更新全局最大路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxPathSum(root):
max_sum = float('-inf')
def maxGain(node):
nonlocal max_sum
if not node:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 0 时，才会选取对应子节点
left_gain = max(maxGain(node.left), 0)
right_gain = max(maxGain(node.right), 0)
# # 经过节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
current_path = node.val + left_gain + right_gain
max_sum = max(max_sum, current_path) #更新答案
# 返回节点的最大贡献值
return node.val + max(left_gain, right_gain)
maxGain(root)
return max_sum
计算当前节点的 最大路径和 可以包含左右节点，但最大贡献度不能同时包括左右节点。因为对于某节点，他的贡献只能带其中一个孩子（带大孩子走），整个路径才能向上延伸
图论
岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
深度优先搜索DFS或者广度优先搜索BFS，我们这里选前者。不过要保证计数过的岛屿的地盘要变
0。我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。最终岛屿的数量就是我们进行深度优先搜索的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private:
//负责置0,让计数过的岛屿不会被重复计算
void dft(vector<vector<char>>& grid, int r, int c){
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if(r -1 >=0 && grid[r-1][c] == '1') dft(grid, r-1, c);
if(r +1 <nr && grid[r+1][c] == '1') dft(grid, r+1, c);
if(c -1 >=0 && grid[r][c-1] == '1') dft(grid, r, c-1);
if(c +1 <nc && grid[r][c+1] == '1') dft(grid, r, c+1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if(!nr) return 0;
int nc = grid[0].size();
int numIslands =0;
for(int r =0; r< nr; ++r){
for(int c =0; c< nc; ++c){
if(grid[r][c] == '1'){
++numIslands;
dft(grid, r, c);
}
}
}
return numIslands;
}
};
腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
广度优先搜索BFS.队列实现 BFS 的方法相对固定，大致分三步：
初始化队列；
最开始的坏橘子全部入队，具体是橘子的坐标和 time；
循环：当队列不为空时，先弹出队首元素，然后将这个元素能够腐烂的橘子全部入队。
注意：这里的for是遍历整个队列才是一层，rotten标记是为了只有真的发生传播，时间才+1。同时腐烂”靠的是 BFS 分层（queue size 控制）
1
2
3
4
5
class Solution {
int dirt[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
public:
// ... 其他代码
};
课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
课程表问题可以抽象成一个图：
- 每门课是一个节点
- 先修关系是有向边：
b -> a（学 a 之前必须先学 b）👉 本质问题： 这个有向图有没有环？
- 有环 ❌ → 无法完成（死循环依赖）
- 无环 ✅ → 可以完成
每次只能选你能上的课 每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。 假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。 接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。 接着选 2，导致课 4 的入度变 0。 现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。
这很像 BFS 让入度为 0 的课入列，它们是能直接选的课。 然后逐个出列，出列代表着课被选，需要减小相关课的入度。 如果相关课的入度新变为 0，安排它入列、再出列……直到没有入度为 0 的课可入列。
BFS 前的准备工作 每门课的入度需要被记录，我们关心入度值的变化。 课程之间的依赖关系也要被记录，我们关心选当前课会减小哪些课的入度。 因此我们需要选择合适的数据结构，去存这些数据： 入度数组：课号 0 到 n - 1 作为索引，通过遍历先决条件表求出对应的初始入度。 邻接表：用哈希表记录依赖关系（也可以用二维矩阵，但有点大） key：课号 value：依赖这门课的后续课（数组） 怎么判断能否修完所有课？ BFS 结束时，如果仍有课的入度不为 0，无法被选，完成不了所有课。否则，能找到一种顺序把所有课上完。 或者：用一个变量 count 记录入列的顶点个数，最后判断 count 是否等于总课程数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> irate(numCourses , 0);
vector<vector<int>> rel(numCourses , vector<int>{});
for(auto &c : prerequisites){
irate[c[0]]++;
rel[c[1]].push_back(c[0]);
}
queue<int> q;
for(int i = 0;i < numCourses;++i){
if(irate[i] == 0)//入度为0，没有前置课程
q.push(i);
}
int lesson = 0;//学完的课程
while(!q.empty()){
++lesson;
int fin = q.front();//取出一门结束课程
q.pop();
for(auto c:rel[fin]){//解放关联课程
irate[c] -= 1;
if(irate[c] == 0)
q.push(c);
}
}
return lesson == numCourses;
}
};
实现 Trie (前缀树)
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
指向子节点的指针数组 children。对于本题而言，数组长度为 26，即小写英文字母的数量。此时 children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。 布尔字段 isEnd，表示该节点是否为字符串的结尾。
插入字符串
我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续处理下一个字符。 子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。 重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
查找前缀
我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续搜索下一个字符。 子节点不存在。说明字典树中不包含该前缀，返回空指针。 重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Trie {
private:
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string prefix) {
Trie* node = this;
for (char ch : prefix) {
ch -= 'a';
if (node->children[ch] == nullptr) {
return nullptr;
}
node = node->children[ch];
}
return node;
}
public:
Trie() : children(26), isEnd(false) {}
void insert(string word) {
Trie* node = this;
for (char ch : word) {
ch -= 'a';
if (node->children[ch] == nullptr) {
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
}
};
回溯
回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。一般流程为：
1.探索2.递归3.回溯（撤销探索）
1
2
3
4
5
6
7
8
9
10
res = []
def backtrack(当前索引，子列举):
# 全排的化要加判断len(nums)才res.append,且下面的循环看看要不要return
# 循环边界：
...主要探索(可无)
backtrack(...)
...回溯|撤销(可无)
backtrack(0,[])
return res
说白了，循环加递归回溯有点多线程的意味
还有就是其backtrack的参数要考虑实时状态性
全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
解：回溯算法：
- 使用回溯法，维护一个当前排列
path - 对于每个位置，尝试所有未使用的数字
- 选择一个数字后，递归处理下一个位置
- 回溯时撤销选择，尝试其他可能性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了，前面的 [0, first-1] 已经确定好了，现在只需要决定 first 位置放谁。
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def backtrack(first = 0):
# 前面的 [0, first-1] 已经确定好了，现在只需要决定 first 位置放谁。
# 终止时，所有数都填完了，填入res
if first == n:
res.append(nums[:])
for i in range(first, n): #每次从剩下的数挑一个数放到第first个位置，传统N！列举循环写法
# 动态维护数组,相当于每次从剩下的数挑一个数放到第first个位置
nums[first], nums[i] = nums[i], nums[first]
# 继续递归填下一个数
backtrack(first + 1)
# 撤销操作
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
res = []
backtrack()
return res
读取外层变量：不需要 nonlocal 修改外层变量本身：需要 nonlocal
而res指向一个 list 对象，修改这个 list 对象的内容也不用 nonlocal
子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解：这里是子集不是全排列，化为二进制选择/不选更快
对于一个长度为
n的数组：👉 一共有 2^n 个子集，因为每个元素都有两种状态：
- 选
- 不选
即：
0/1 序列 子集 0/1 序列对应的二进制数 000 {} 0 001 {9} 1 010 {2} 2 011 {2,9} 3 100 {5} 4 101 {5,9} 5 110 {5,2} 6 111 {5,2,9} 7
这里外面的循环： | mask（二进制） | 含义 | | ————– | ————————— | | 000 | 空集 | | 001 | 选 nums[0] → [1] | | 010 | 选 nums[1] → [2] | | 011 | 选 nums[0], nums[1] → [1,2] | | 100 | [3] | | 111 | [1,2,3] |
而内层循环检查 mask 的第 i 位是不是 1，mask & (1 « i)是取出 mask 的第 i 位
mask = 5 = 101（二进制）
i = 0 → 1 → 选 nums[0] i = 1 → 0 → 不选 i = 2 → 1 → 选 nums[2]
整体逻辑：
- 枚举所有 mask（0 → 2ⁿ-1）
- 对每个 mask：
- 检查每一位
- 决定是否加入对应元素
- 构造一个子集
t- 加入答案
ans注意：这里是1往左移动n位和i位，而不是n往左移动1位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
res = []
def backtrack(start, path):
res.append(path[:]) #加入结果
# 主要循环，从字符串看看选不选该位字符
for i in range(start, len(nums)):
path.append(nums[i]) # 探索
backtrack(i+1, path) # 递归
path.pop() # 回溯
backtrack(0, [])
return res
python逻辑
- 对于每个元素，有两种选择：包含或不包含
- 从第一个元素开始，逐个决定是否加入当前子集
- 当处理完所有元素时，将当前子集加入结果
加入顺序：[],[1], [1,2] [1,2,3] range(3, 3)没有元素开始回溯到[1]选择3于是接着[1, 3]接着回溯 [2] [2,3] [3]
注意这里跟全排列不同的是无需判别就可append
电话号码的字母组合（全排列pro）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解：一样回溯，加个哈希表来确定可以加入的字符就行
- 建立数字到字母的映射表
- 使用回溯法，对于每个数字，尝试所有可能的字母
- 当处理完所有数字时，将当前组合加入结果
- 回溯时撤销选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
if (digits.empty()) {
return combinations;
}
unordered_map<char, string> phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
backtrack(combinations, phoneMap, digits, 0, combination);
return combinations;
}
void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
if (index == digits.length()) {
combinations.push_back(combination);
} else {
char digit = digits[index];
const string& letters = phoneMap.at(digit);
for (const char& letter: letters) {
combination.push_back(letter);
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.pop_back();
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def letterCombinations(self, digits: str) -> list[str]:
if not digits:
return []
mapping = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
res = []
def backtrack(index, path):
if index == len(digits): # 对的，len比如索引刚好大1
res.append(path)
return #不然会进入下面“数组越界”
for letter in mapping[digits[index]]: #哈希表取出来是一个长3的字符串
backtrack(index + 1, path + letter) # path + letter是拼接
backtrack(0,'')
return res
记得res.apppend这里要return
组合总和（全排列pro）
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解：回溯+剪枝。
同全排列，只不过边界改为和为target
- 对数组排序，便于剪枝(「已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义)
- 从第一个元素开始，尝试所有可能的组合
- 如果当前和等于 target，加入结果
- 如果当前和小于 target，继续递归,记得回溯
- 剪枝：如果当前和大于 target，直接返回（逻辑在以上两者之前）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
if (idx == candidates.size()) {
return;
}
if (target == 0) {
ans.emplace_back(combine);
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> combine;
dfs(candidates, target, ans, combine, 0);
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
res = []
candidates.sort() #先对数组排序，便于剪枝
def backtrack(start, path, current_sum):
if current_sum == target: # 一样判断边界才加入
res.append(path[:])
return
for i in range(start, len(candidates)):
if current_sum + candidates[i] > target: # 如果当前和大于 target，直接返回
break
# 如果当前和等于 target，加入结果
path.append(candidates[i])
backtrack(i, path, current_sum+candidates[i])# 如果当前和小于 target，继续递归，累计和记得加上现在的值,且是i而不是start+1因为同一个数字可以复用
path.pop() # 回溯
backtrack(0, [], 0)
return res
如果当前和小于 target，继续递归，累计和记得加上现在的值,且是i而不是start+1因为同一个数字可以复用
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合如：
输入：n = 3 输出：[”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
暴力：我们可以生成所有 2n 个 ‘(’ 和 ‘)’ 字符构成的序列，然后我们检查每一个是否有效即可。为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n−1 的序列前加一个 ‘(’ 或 ‘)’。为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。
回溯：可以只在序列仍然保持有效时才添加 ‘(’ 或 ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def generateParenthesis(self, n: int) -> list[str]:
res = []
def backtrack(S, left, right): #子串，左右括号个数
if len(S)==2*n:
res.append(''.join(S))
return
if left<n:
S.append('(')
backtrack(S,left+1,right)
S.pop()
if right <left: #注意这里是小于left
S.append(')')
backtrack(S,left,right+1)
S.pop()
backtrack([],0,0)
return res
注意这里是小于left
这里是“优先走左边” 但≠ “只生成这一条“((()))”路径”它确实先深度优先地把左括号一路加满，但是 pop() 会把它恢复回来，然后再尝试右括号。
单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数 check(i,j,k) 的执行步骤如下：
如果 board[i][j] =word[k]，当前字符不匹配，直接返回 false。 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false。 这样，我们对每一个位置 (i,j) 都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置
python:回溯 + DFS：
- 遍历网格，找到与单词首字母匹配的位置
- 从该位置开始，使用 DFS 搜索
- 对于每个位置，检查上下左右四个方向
- 使用 visited 数组标记已访问的位置
- 如果找到完整路径，返回 true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {
if (board[i][j] != s[k]) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool result = false;
for (const auto& dir: directions) {
int newi = i + dir.first, newj = j + dir.second;
if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
if (!visited[newi][newj]) {
bool flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
bool exist(vector<vector<char>>& board, string word) {
int h = board.size(), w = board[0].size();
vector<vector<int>> visited(h, vector<int>(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
bool flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def exist(board, word):
m, n = len(board), len(board[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(i, j, index):
if index == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[index]: #这里和最后的return的区别在于这里的
return False #False表示当前这个位置立刻就不行。
temp = board[i][j] # 下面记录使用过要更改值，先记录下来后面回溯要用，每一层有自己的temp
board[i][j] = '#' #这个格子已经在当前路径使用过，这条路径里面不能再次使用它,这里更改了元素后面无需判断了
# 回溯
for dx, dy in directions: # 4个方向都要考虑
if dfs(i + dx, j + dy, index + 1): #记得index也要加1
return True
board[i][j] = temp # 回溯恢复，相当于之前的pop
return False #而最后的False表示当前这个位置本身没问题，但是从它出发的所有路都试过了，还是不行。
# 让每一个格子都作为起点尝试一次。
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
记得index也要加1
不是从0，0，0开始，让每一个格子都作为起点尝试一次。
分割回文串（子集pro）
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
由于需要求出字符串 s 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
假设我们当前搜索到字符串的第 i 个字符，且 s[0..i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i..j] 是一个回文串。
因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i..j] 是否为回文串：如果 s[i..j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i..j] 从 ans 中移除。
如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。
细节
当我们在判断 s[i..j] 是否为回文串时，常规的方法是使用双指针分别指向 i 和 j，每次判断两个指针指向的字符是否相同，直到两个指针相遇。然而这种方法会产生重复计算，例如下面这个例子：
当 s=aaba 时，对于前 2 个字符 aa，我们有 2 种分割方法 [aa] 和 [a,a]，当我们每一次搜索到字符串的第 i=2 个字符 b 时，都需要对于每个 s[i..j] 使用双指针判断其是否为回文串，这就产生了重复计算。
因此，我们可以将字符串 s 的每个子串 s[i..j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j) 表示 s[i..j] 是否为回文串，那么有状态转移方程：
f(i,j)={ True,i≥j f(i+1,j−1)∧(s[i]=s[j]),otherwise
因为一个字符串是回文 ⇔两头一样 + 中间也是回文，即f[i][j] = (s[i] == s[j]) && f[i + 1] [j - 1];。其中 ∧ 表示逻辑与运算，即 s[i..j] 为回文串，当且仅当其为空串（i>j），其长度为 1（i=j），或者首尾字符相同且 s[i+1..j−1] 为回文串。
预处理完成之后，我们只需要 O(1) 的时间就可以判断任意 s[i..j] 是否为回文串了。
python 回溯算法+双指针：
- 使用回溯法，尝试所有可能的分割方式
- 对于每个位置，检查从当前位置到字符串末尾的所有子串
- 如果子串是回文，加入当前路径，继续递归
- 回溯时撤销选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
vector<vector<int>> f;
vector<vector<string>> ret;
vector<string> ans;
int n;
public:
void dfs(const string& s, int i) {
if (i == n) {
ret.push_back(ans);
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.push_back(s.substr(i, j - i + 1));
dfs(s, j + 1);
ans.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
dfs(s, 0);
return ret;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def partition(self, s: str) -> list[list[str]]:
res = []
# 双指针判断是否是回文串
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# 子集改写为子串但是加入回文判断
def backtrack(start, path):
if start == len(s):
res.append(path[:]) #加入结果
return
# 主要循环，从字符串看看选不选该位字符
for i in range(start, len(s)):
if is_palindrome(start, i): # 注意范围
path.append(s[start:i+1]) # 探索，这里改为path加入子串故上面也给改为了要判断最终最终res.append
backtrack(i+1, path) # 递归
path.pop() # 回溯
backtrack(0, [])
return res
子集改为子串+双指针判断回文
这里改为path加入子串故上面也给改为了要判断最终最终res.append。因为子集的 path 在任意时刻都是一个合法答案；而字符串分割的 path 只有把整个字符串全部切完，才是一个合法答案。
二分查找
1.left<=right; 2.mid =(left +right)//2
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
二分查找的判别是左右指针顺序正确
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n= nums.size();
int left =0,right =n-1;
while(left <= right){ //记得是<=
int mid =(left +right)/2;
if(nums[mid] < target){
left = mid +1;
}
else if(nums[mid] > target) {
right = mid-1;
}
else{
return mid;
}
}
return left; //记得最终架构返回l,
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
n = len(nums)
left, right = 0, n-1
while left <= right:
mid = (left+right)//2
if nums[mid]<target:
left = mid+1
elif nums[mid]>target:
right = mid -1
else:
return mid
return left #记得最后都没有要插入当前left位置
记得最后都没有要插入当前left位置
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
mid//和%就行。记得矩阵的行和列不要搞混：int m = matrix.size()，n = matrix[0].size();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
int left =0, right = m*n-1;
while(left <=right){
int mid =(left +right)/2;
int mid_m =mid/n;
int mid_n =mid%n;
if(matrix[mid_m][mid_n] < target){
left = mid + 1;
}
else if(matrix[mid_m][mid_n] > target){
right = mid - 1;
}
else{
return true;
}
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
m, n = len(matrix),len(matrix[0])
left, right = 0, m*n-1
while left <= right:
mid = (left+right)//2
mid_m = mid//n
mid_n = mid%n
if matrix[mid_m][mid_n] >target:
right = mid -1
elif matrix[mid_m][mid_n] <target:
left = mid+1
else:
return True
return False
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
肯定不能直接二分查找然后向两边扩展，这样如果全是target就是O(n）了。实际上直接进行两次二分查找就行：寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标，然后将下标减一。第一个重点确保了即使找到目标值，也会继续向左搜索，以确保找到第一个出现的索引。第二个重点确保了即使找到目标值，也会继续向右搜索，以确保找到最后一个出现的索引。(下面是java写法)
主要就是在==的时候firt和last=mid的后面加上r=mid-1 和l = mid+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 两次二分查找，分开查找第一个和最后一个
// 时间复杂度 O(log n), 空间复杂度 O(1)
// [1,2,3,3,3,3,4,5,9]
public int[] searchRange2(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int first = -1;
int last = -1;
// 找第一个等于target的位置
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
first = middle;
right = middle - 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 最后一个等于target的位置
left = 0;
right = nums.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (nums[middle] == target) {
last = middle;
left = middle + 1; //重点
} else if (nums[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return new int[]{first, last};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
n = len(nums)
left, right, first, last = 0, n-1,-1,-1
# 进行两轮遍历
while left <= right:
mid = (left+right)//2
if nums[mid]<target:
left = mid+1
elif nums[mid]>target:
right = mid -1
else:
first = mid
right = mid -1 # 找到对应值后first应该继续往左边找
left, right = 0, n-1 # 还原初始边界
while left <= right:
mid = (left+right)//2
if nums[mid]<target:
left = mid+1
elif nums[mid]>target:
right = mid -1
else:
last = mid
left = mid +1 # 找到对应值后last应该继续往右边找
return first, last #不用判断是否为空可，因为应开始就赋值了-1，只有找到才赋值，而找到了哪怕右一个都行
1.说白了，如果有重复的话应该不是最后只剩一个的时候被找到，而是有左右冗余的中点，故可以在等于的时候继续mid-1向左+1向右作为右左边界去找。
2.最后return不用判断是否为空可，因为应开始就赋值了-1，只有找到才赋值，而找到了哪怕有一个都行
搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
解：二分，只多了一个判断哪边有序的步骤
将数组二分，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。通过比较边界和 mid 的大小确定那个是有序的，在对有序部分比较两端判断是否在此范围(正因为有序才可以这样做)，然后看target在不在有序的这边,不在的话可以排除该区间，在的话就取该区间，一直分下去，
相当于只多了一个判断哪边有序的步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
int search(vector<int>& nums, int target) {
// 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
// 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
int n = (int)nums.size();
if (!n) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right)/2;
if(nums[mid] == target) return mid;
if(nums[0] <= nums[mid]){ //右边是无序的部分，0~mid是有序的
// 一直找有序的部分，拿其边界来判断target是否在里面，这前面的判断受k判断影响，与target无关，没毛病
if(nums[0] <= target && target < nums[mid]){
//边界判断，在有序里面
right = mid - 1;
}else{ //不然就是在无序的部分了
left = mid + 1;
}
}
else{//左边是无序的，mid~n-1才有序
//同理找有序的部分看target在不在有序里面
if(nums[mid] < target && target <= nums[n-1]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def search(self, nums: list[int], target: int) -> int:
n = len(nums)
left, right = 0, n-1
# 这两个0和1个元素的别忘记了
if n == 0:
return -1
if n==1:
return 0 if nums[0]==target else -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target: return mid
if nums[0] <= nums[mid]: #左边有序,记得是<=
if nums[0] <=target and nums[mid]>target: #接着看是否target是否在有序部分
right = mid -1 #有则接着在该部分
else: #没有则考虑无序范围
left = mid+1
else: #右边有序
if nums[mid] <target and nums[n-1]>=target: #接着看是否target是否在有序部分
left = mid+1 #有则接着在该部分
else:
right = mid -1 #没有则考虑无序范围
return -1
记得nums[0]和nums[n-1]是<=和>=
寻找旋转排序数组的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
跟上一题思路差不多，将[l, r]从中间分开，一定一边有序，一边可能有序可能无序，只考虑有序的一边，考虑完排除这部分区间
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = 1e5;
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (r + l) / 2;
// 左边有序
if (nums[l] <= nums[mid]) {
ans = min(nums[l], ans); //#因为是有序从小达大，取最小nums[left]
l = mid + 1; //排除该区间
} else { //右边有序
ans = min(nums[mid], ans); //因为是有序从小达大，取最小nums[mid]
r = mid - 1;
}
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def findMin(self, nums: list[int]) -> int:
n = len(nums)
left, right = 0, n-1
ans = 5e3
while left <= right:
mid = (left+right)//2
# if nums[mid] == target: return mid
if nums[left] <= nums[mid]: #也可以这样判断左边有序
ans = min(nums[left],ans) # 左边有序部分肯定left最小嘛
left = mid+1 # 接着排除该区间
else: #右边有序
ans = min(nums[mid],ans) # 右边有序的话肯定右边最小嘛
right = mid -1
return ans
记得更新ans后是要排除该区间，”“左边有序更新左边界left,右边有序更新右边界right”
栈
先进后出,对应DPS和二叉树的中序遍历
python里面栈直接用stack = []作为栈,使用append()写入和pop()弹出，栈顶元素直接使用stack[-1]查看
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
用栈的先进后出，当遇到左括号，进行存入，遇到右括号，取出看看是否对应的左括号，非括号则不动栈
python: 栈+哈希表
- 遇到左括号，入栈
- 遇到右括号，检查栈顶是否是匹配的左括号
- 如果匹配，出栈；否则返回 false
- 最后检查栈是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if(n%2 ==1){
return false;
}
// 创建标量字符表pairs,注意键是右来查找
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for(char ch:s){
if(pairs.count(ch)){//右括号弹出栈查看
if(stk.empty() || stk.top() != pairs[ch]){
return false;
}
stk.pop();
}else{//左括号存入
stk.push(ch);
}
}
return stk.empty(); //栈是否空为最终判决,为了防止有没有右括号的
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mappinng = {'}':'{', ']':'[',')':'('} #注意哈希表右括号为键，左括号才为值
for char in s:
if char in mappinng: #右括号检验栈顶是否是左括号
if not stack or stack.pop() != mappinng[char]: # 如果匹配，出栈；否则返回 false
return False
else:
stack.append(char) # 左括号入栈
return not stack # 最后返回是否为空
注意哈希表右括号为键，左括号才为值
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
解：两个栈实现：主栈和辅助栈
说白了，比正常的栈多要求返回一个当前最小元素，我们加一个辅助栈，存储当前元素入栈时的最小值，它必是降序的：
- 主栈存储所有元素
- 辅助栈存储每个状态下的最小值
- 每次 push 时，同时更新最小值栈:如果比当前最小值(辅助栈最后一个)小，则加入
- 每次 pop 时，如果弹出的元素等于最小值(辅助栈最后一个)，才同时弹出最小值栈 （不然不影响辅助栈）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX); //初始化
}
void push(int val) {
x_stack.push(val);
min_stack.push(min(min_stack.top(),val));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, value: int) -> None:
self.stack.append(value)
if not self.min_stack or value <= self.min_stack[-1]:
self.min_stack.append(value)
def pop(self) -> None:
temp = self.stack.pop()
if temp == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(value)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 10^5。
解：栈+ 普通的滑动窗口
直接用栈来处理多个括号叠加的问题
python:
1.遇到
[就把当前状态(两个状态，包括左括号前的 （数字和 字符串 )保存起来 （因为要拼接，前面的字符串也很重要）2.遇到
]就恢复之前的状态：除了当前的cur还要数字之前的部分prev注意：数字字符串转化数字时记得考虑多位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
string decodeString(string s) {
stack<char> stk;
for (char c : s) {
if (c != ']') {
stk.push(c);
} else {
// 1. 取出字符串
string str = "";
while (stk.top() != '[') {
str = stk.top() + str;
stk.pop();
}
stk.pop(); // 弹出 '['
// 2. 取出数字（可能多位）
string numStr = "";
while (!stk.empty() && isdigit(stk.top())) {
numStr = stk.top() + numStr;
stk.pop();
}
int num = stoi(numStr);
// 3. 重复压栈
string temp = "";
while (num--) temp += str;
for (char ch : temp) {
stk.push(ch);
}
}
}
// 4. 构造结果
string res = "";
while (!stk.empty()) {
res = stk.top() + res;
stk.pop();
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def decodeString(self, s: str) -> str:
stack = [] # 保存进入 [] 之前的 (字符串, 数字)
num = 0 # 当前 [] 前面的数字
cur = "" # 当前这一层已经解析出的字符串
for c in s:
if c.isdigit():
num = num * 10 + int(c) # 数字字符串转化数字时记得考虑多位数
elif c == '[': #为左括号时，两个状态 数字 和 当前解析出的字符串 入栈
# 把当前的字符串和数字保存起来
stack.append((cur, num))
cur = "" # 进入下一层，更新 解析的字符串 的窗口
num = 0
elif c == ']': # 右括号取出栈顶元素 之前的内容 并拼接 当前层的解析curr
# 取出进入当前 [] 之前的状态
prev, k = stack.pop() # 不能是num不然如果现在num有值就丢失了，得是新的k
cur = prev + cur * k # 这时候curr为[]里的字符串
else:
cur += c # 正常字符直接加入当前解析窗口
return cur
curr是当前这一层已经解析出的字符串，stack保存的是保存进入 [] 之前的 (字符串, 数字)，重要的时之前的字符串因为要拼接
右括号出栈时记得时k,不能是num不然如果现在num有值就丢失了，得是新的k
每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
解：单调栈
维护一个存储下标的单调栈（单调递增），从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
- 使用栈存储温度的下标
- 遍历数组，对于每个温度，如果当前温度大于栈顶温度，则找到了下一个更高温度
- 计算天数差，更新结果数组
- 将当前下标入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n =temperatures.size();
vector<int> ans(n);
stack<int> s;
for(int i =0;i<n;++i){
while(!s.empty() && temperatures[i] >temperatures[s.top()]){
int previousIndex =s.top();
ans[previousIndex] = i-previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
n = len(temperatures)
res = [0]*n # 初始值为0
stack = []
for i in range(n): #后面需要下标
while stack and temperatures[i] > temperatures[stack[-1]]: #大于历史最大温度时为结果
prev = stack.pop() # 找到比当前最大历史温度高的会连续多少天
res[prev] = i-prev #计算天数差，更新结果数组(即当前位置)
stack.append(i) # 栈存的是下标
return res
栈存的是下标
堆
堆是一种完全二叉树，它可以用数组来表示。对于数组中索引为 i 的元素，其左子节点的索引为 2 * i + 1，右子节点的索引为 2 * i + 2，父节点的索引为 (i - 1) // 2。一般数组转化是层序搭建二叉树。
Python 的 heapq 模块提供了对堆操作的支持:
1.heapify(x)将列表 x 转换为堆，原地操作，时间复杂度为 $O(n)$;一般现在x就是堆，不用返回，后面直接度x操作
2.heappush(heap, item)将 item 插入到堆 heap 中，并保持堆的性质，时间复杂度为 $O(log n)$; heap即上面的x
3.heappop(heap)从堆 heap 中弹出并返回最小的元素，同时保持堆的性质，时间复杂度为 $O(log n)$。heap即上面的x
最大堆：heapq. 时数字取反取-1每个节点的值都大于或等于其子节点的值，根节点的值是堆中的最大值。
最小堆：**使用heapq.正常是小顶堆 **,每个节点的值都小于或等于其子节点的值，根节点的值是堆中的最小值。
说白了，一般只有heapq 是小顶堆 一种用法
数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
解：最小堆（维护大小为 k 的最小堆）
直接快速排序即可，当然这里用堆也行:建立一个大根堆，做 k−1 次删除操作后堆顶元素就是我们要找的答案。在很多语言中，都有优先队列或者堆的的容器可以直接使用，但是在面试中，面试官更倾向于让更面试者自己实现一个堆.建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，因为 k<n，故渐进时间复杂为 O(n+klogn)=O(nlogn)。
python默认的时小根堆更好做。每次加入一个数后，如果堆的大小超过
k，就把最小的那个弹出去。这样堆里永远保留的是“目前见过的最大的 k 个数”,而堆顶是这 k 个数里最小的，所以它就是整个数组中第 k 大的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums, k);
}
private:
int quickSelect(vector<int>& nums, int k) {
// 随机选择基准数
int pivot = nums[rand() % nums.size()];
// 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
vector<int> big, equal, small;
for (int num : nums) {
if (num > pivot)
big.push_back(num);
else if (num < pivot)
small.push_back(num);
else
equal.push_back(num);
}
// 第 k 大元素在 big 中，递归划分
if (k <= big.size())
return quickSelect(big, k);
// 第 k 大元素在 small 中，递归划分
if (nums.size() - small.size() < k)
return quickSelect(small, k - nums.size() + small.size());
// 第 k 大元素在 equal 中，直接返回 pivot
return pivot;
}
};
-------------------------------------------------堆排序------------------------------------------------------
class Solution {
public:
void maxHeapify(vector<int>& a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a[i], a[largest]);
maxHeapify(a, largest, heapSize);
}
}
void buildMaxHeap(vector<int>& a, int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
swap(nums[0], nums[i]);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
};
1
2
3
4
5
6
7
8
9
10
#------------------------------------------------堆排序------------------------------------------------------
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, num) # 放入栈
if len(heap) > k:
heapq.heappop(heap) # 这里的参数要求有堆不要忘记了
return heap[0] # 最后返回堆顶，最小堆第一个最小
前 K 个高频元素（数组中的第K个最大元素pro）
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
解：最小堆+ 哈希
借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率 维护一个元素数目为 k 的最小堆 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中 最终，堆中的 k 个元素即为前 k 个高频元素
或者 **桶排序 **也可以
- 统计每个元素的频率（直接用了Counter方法）
- 使用最小堆维护频率最高的 k 个元素
- 返回堆中的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// JAVA
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer,Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 遍历map，用最小堆保存频率最大的k个元素
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (Integer key : map.keySet()) {
if (pq.size() < k) {
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
// 取出最小堆中的元素
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
heap = []
for num,freq in count.items(): # 记得是items
heapq.heappush(heap, (freq,num)) # freq在前才可以排序，拍的是freq
if len(heap) >k:
heapq.heappop(heap)
return [num for freq, num in heap]
heapq 会默认按元组的第一个元素排序；如果第一个元素相同，才会比较第二个，以此类推。
贪心算法
在对问题求解时，总是做出在当前看来是最好的选择。
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解，得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。
一般另起一个维护数组空间
背包问题（非100）：
同类型老师给的行李箱问题：
目标：用最少的行李箱将行李装满 已知条件：①每个行李大小一样②每个行李箱都有不同的最大容量，已装的行李数也不同，但每个行李箱已装的行李数是小于其最大容量的③移动行李时，不需要一次性全部转移，每转移一件需要的时间是1秒 输入：行李箱的个数，每个行李箱的最大容量，每个行李箱已有的行李数 输出：需要的行李箱个数和时间
装满石头的背包的最大数量：现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往任意背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
解：可使用的石头数量是有限的,且多数背包存在一定的差值,那么就可以按照差值从小到大的顺序使用石头,这样可以保证缺少石头最少的背包首先被填满,于是就可以获得最多个被填满的背包的数量,这使用了贪心的思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
int size = capacity.size();
vector<int> diff(size,0);
for(int i =0l;i<size; i++){
diff[i] = capacity[i]-rocks[i];
}
sort(diff.begin(),diff.end());
int res = 0;
int i = 0;
while(i<size){
if(diff[i]>0 && additionalRocks >= diff[i]){
additionalRocks -= diff[i];
res++;
}else if(diff[i]==0){
res++;
}
i++;
}
return res;
}
};
买卖股票的最佳时机：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解：暴力：遍历全部和其对应之后的数组分别求插值，查找最大的插值既可；O(n^2)超时
一次遍历：每次都假设是今天卖出，然后求今天之前的历史最低点。而这个历史最低点并不需要额外遍历，而是每天考虑的时候顺带记录的。实际上只要求符合序列顺序的最大差值，模仿数组最大最小值的查找，我们只要记忆一次最大的值就行，有更大的则替换，当然，最小值也要记录。但是一开始的最小价格要等于题目边界最大值，否则第一次会错误地把 prices[0] 当成“利润”，实际上可能你还没买入。
- 维护两个变量：
min_price（到目前为止的最低价格）和max_profit（最大利润）- 遍历数组，对于每一天：
- 更新最低价格：
min_price = min(min_price, prices[i])- 更新最大利润：
max_profit = max(max_profit, prices[i] - min_price)
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minprice=1e9,maxprofit =0;
for (int price : prices){
maxprofit = max(maxprofit,price-minprice);
minprice = min(price,minprice);
}
return maxprofit;
}
};
1
2
3
4
5
6
7
8
9
10
class Solution:
def maxProfit(self, prices: list[int]) -> int:
res = 0
low = float('inf')
for price in prices:
low = min(low, price)
res = max(res, price - low)
return res
跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。我们不需要模拟跳到哪里，只需要知道是否跳到最后
解：贪心算法。注意这里不需要刚好，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 y，即 x+nums[x]≥y，那么位置 y 也可以到达。nums[i] 实际上表示的是站在位置 i 最多可以向右跳多少步，于是我们不管每一步到底要不要跳满而是从可以选择的起跳点选择看看到底最远能跳到哪，但这个选择反而收到最远起跳点影响，所以只需要在遍历一遍同时更新最远起跳点就行。
- 维护一个变量
max_reach，表示当前能到达的最远位置（在遍历到目前为止的这些位置中，我最远能够到达的位置。）- 遍历数组，更新
max_reach = max(max_reach, i + nums[i])，i已经代表你目前所达到的最大距离- 如果
max_reach >= len(nums) - 1，说明可以到达最后一个位置- 如果在某个位置
i > max_reach，说明无法继续前进
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def canJump(self, nums: list[int]) -> bool:
max_lenth = 0 # 可以达到的最大距离
for i in range(len(nums)):
if i > max_lenth: # 因为i是遍历递增，这意味着上一步就是最远距离，当前这里它无法到达了，而还没到循环边界，即终点
return False #故失败
max_lenth = max(max_lenth, i +nums[i]) #目前max_length以内的都可以作为现在的起跳点
if max_lenth >= len(nums)-1:
return True
return True
注意判断i > max_reach
跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i]且i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
解：贪心算法：相比上一道，这一道问的是 最少跳几次能到终点？
- 维护
end表示当前跳跃能到达的最远位置- 维护
max_pos表示在[start, end]范围内能到达的最远位置max_pos = max(max_pos, i + nums[i])- 当到达
end时，跳跃次数加1，更新end = max_pos- 继续遍历直到到达最后一个位置
1
2
3
4
5
6
7
8
9
10
11
12
def jump(nums):
jumps = 0 # 已经跳了几次
end = 0 # 当前这一次跳跃能够到达的最远边界
max_pos = 0 # 在当前范围内，再跳一次最远能到哪里
for i in range(len(nums) - 1): #这道题比上一道不同在于是次数，达到终点就结束了，不需要遍历终点，所以边界条件为n-1且
#无需判断i是否大于max_pos
max_pos = max(max_pos, i + nums[i])
if i == end: # “这一跳能到达的所有位置，我已经全部看完了，该结算一次跳跃，并进入下一层了。”
jumps += 1
end = max_pos
return jumps
这两道题主要就是更新维护最远位置，end表示 当前已经确定的一跳，最远能覆盖到哪里。max_pos表示在当前这一跳能够覆盖的范围里，继续寻找下一跳的话，最远能够到哪里，二者不一样。类似于BFS
这道II循环边界条件为n-1
划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
解：贪心算法:要求同一只在同一片段，只需得到每个字母的最后位置。而贪心在于一旦发现当前区间已经可以结束，就立刻结束。因为题目要求：尽可能多的片段
1.遍历一次，记录每个字符最后出现的位置
2.第二次遍历，更新当前区间所有字符所需的最后的一个位置(即区间右端确认)
3.一旦发现当前区间已经可以结束，就立刻结束，填入片段的长度并更新下一个片段的起点
start
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def partitionLabels(self, s: str) -> list[int]:
# 遍历一次，记录每个字符最后出现的位置
last = {} # 记得这是字典，list[]只能用数字作为下标，这里的键得为字符
for i,c in enumerate(s):
last[c] = i
# 第二次遍历
res = []
start = end =0
for i,c in enumerate(s):
# 更新区间所有字符最后的位置
end = max(end, last[c])
if i == end: #要尽可能多的片段，一旦发现当前区间已经可以结束，就立刻结束
res.append(end-start+1) #填入片段的长度
start = i+1 #去下一个片段
return res
记得一开始“记录每个字符最后出现的位置”要使用字典last = {}
动态规划
’拆分子问题，记住过往，减少重复计算‘。或者说’记住求过的解来节省时间’
动态规划问题通常具有以下三个核心要素：
- 重叠子问题：问题可以分解为相互重叠的子问题
- 最优子结构：问题的最优解包含子问题的最优解
- 无后效性：某阶段状态一旦确定，不受这个状态以后决策的影响
流程：
- 定义状态：确定用哪些变量表示问题的状态（一般以结果作为最终状态从0开始规律，数量也可以这样看看需要几个状态最少）
- 状态转移方程：找出状态之间的递推关系（一般还是理解领悟逻辑，自己列举观察难，而且要从前面i-1,i-2,…组成）
- 初始化：确定初始状态的值 (如果有默认的话其他初始赋值取n+1个)
- 计算顺序：确定状态的计算顺序
- 返回结果：根据计算结果返回最终答案
记得如果有原数组一般dp的对应位置比其索引多1
爬楼梯：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解：我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下斐波那契数列式子：f(x)=f(x−1)+f(x−2)，暴力求解适用于 n 比较小的情况，在 n 变大之后，O(n) 的时间复杂度会让这个算法看起来有些捉襟见肘。我们可以用「矩阵快速幂」的方法来优化这个过程可以用快速幂求解。即求解矩阵[[1,1] [1,0]]的n次方即可。最后乘上[f(1),f(0)]
临近递推DP
- 定义
dp[i]为到达第 i 阶的方法数- 状态转移方程：
dp[i] = dp[i-1] + dp[i-2]- 初始条件：
dp[1] = 1, dp[2] = 2- 可以优化空间复杂度，只使用两个变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
//2*2矩阵相乘
vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
vector<vector<long long>> c(2, vector<long long>(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
//快速幂
vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
vector<vector<long long>> ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) { //当前位数为1时，即与000...0001 做按位与（AND）运算结果是 n 的最低位（即第 0 位）
ret = multiply(ret, a);
}
n >>= 1; //右移
a = multiply(a, a);
}
return ret;
}
int climbStairs(int n) {
vector<vector<long long>> ret = {{1, 1}, {1, 0}};
vector<vector<long long>> res = matrixPow(ret, n);
return res[0][0];
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def climbStairs(self, n: int) -> int:
if n <=2 : # 如果为0级台阶，为0，一级为1种，二级为2种,前几种单独处理
return n
# 初始赋值
a , b = 1,2
for _ in range(3,n+1): # 记得这里是n+1，n要进循环的
a, b = b, a+b # 状态转移方程,经过了压缩空间复杂度为两个变量
return b
记得初始的n <=2的处理； 记得范围是n+1,n要进循环的
杨辉三角(爬楼梯pro)
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
解：邻近递推(二维)DP 或者直接数学
dp [i] [j] = dp [i-1] [j-1] + dp [i-1] [j]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def generate(self, numRows: int) -> list[list[int]]:
res = []
for i in range(numRows):
# 先创建当前行，长度为 i + 1
row = [1]*(i+1)
# 中间元素 = 左上 + 右上
for j in range(1,i): # python的循环的range(1,0)里这样子没问题
row[j] = res[i-1][j-1] + res[i-1][j]
res.append(row)
return res
打家劫舍(爬楼梯pro)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
解：临近递推DP，类似爬楼梯
- 定义
dp[i]为偷窃前 i 间房屋能获得的最大金额- 状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- 不偷第 i 间：
dp[i-1]- 偷第 i 间：
dp[i-2] + nums[i]- 可以优化空间复杂度，只使用两个变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
# if n ==2 : 这个不用单独讨论
# return max(nums[0], num[1])
prev1, prev2 = max(nums[0], nums[1]), nums[0]
for i in range(2,n):
curr = max(prev2+nums[i], prev1)
prev2 = prev1
prev1 = curr
return prev1 #因为这里curr没有循环外初始化，用prev1也行
完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
解：区间间隔DP（就是根据不同区间不同边界处理）
- 定义
dp[i]为组成数字 i 的完全平方数的最少数量- 状态转移方程：
dp[i] = min(dp[i], dp[i - j*j] + 1)，其中j*j <= i(记得加1，等于加上j*j这1个)- 初始条件：自己补充
dp[0] = 0
1
2
3
4
5
6
7
8
9
10
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n + 1) # 记得后面是返回dp[n]所以要创建n+1长度个
dp[0] = 0
for i in range(1,n+1): # 0自己补充，n要进循环
j=1 # 平方索引从1开始找就行，终点取i开方
while j*j <= i:
dp[i] = min(dp[i], dp[i-j*j]+1) # 只有后者才加1 ，指的是加上j*j这1个
j+=1
return dp[n]
初始是创建n+1长度INF
零钱兑换(完全平方数mini)
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
解：区间间隔DP
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1) #
dp[0] = 0
for i in range(1,amount+1): # 0自己补充，n要进循环
j=0 # 从conis的初始索引开始了这里为0
# while j< len(coins) and coins[j] <= i: # 记得加个数组coins边界判别，不要这样否则意味着默认coin是排序的，直接在coin里遍历寻找不比i大的吧
for coin in coins:
if coin <=i:
# dp[i] = min(dp[i], dp[i-coins[j]]+1) # 只有后者才加1 ，指的是加上j*j这1个（需要提前排序）
dp[i] = min(dp[i], dp[i-coin]+1) # 只有后者才加1 ，指的是加上j*j这1个
# j+=1（需要提前排序）
return dp[amount] if dp[amount] != float('inf') else -1 # 最后要加个判别
完全平方数mini版本，将j*j改为coins加个coins查询就行，以及最后return加个判别就行，区别于最后找不到的-1的return
最后判别记得判断是否存在解，不要直接这样会把dp[0]的情况也改掉 return dp[amount] if dp[amount] else -1 # 最后要加个判别,得是return dp[amount] if dp[amount] != float('inf') else -1因为以及初始化了
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
解：DP+哈希集合
- 定义
dp[i]表示字符串s的前 i 个字符是否可以被字典中的单词拼接，word用哈希集合存储- 状态转移方程：
dp[i] = dp[j] && s[j:i] in wordDict，其中0 <= j < i- 初始条件：
dp[0] = true（空字符串可以被拼接）
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
w_set = set(wordDict)
n = len(s)
dp = [False] *(n+1)
dp[0] = True
for i in range(1, n+1):
for j in range(i): #第二个循环范围为0~i
if dp[j] and s[j:i] in w_set: #不能直接写bool等式，in在python里不是判别
dp[i] =True
return dp[n]
最长递增子序列（最优非DF）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解：DP是O(n²)，最优方法是贪心 + 二分查找
DP类似杨辉三角，每个元素自己都可以单独构成一个长度为 1 的递增子序列。
- 定义
dp[i]为以nums[i]结尾的最长递增子序列的长度- 状态转移方程：
dp[i] = max(dp[j]) + 1，其中0 <= j < i且nums[j] < nums[i]优化方法：贪心 + 二分查找
维护一个数组
tails，其中tails[i]表示长度为 i+1 的递增子序列的最小末尾元素.比如nums = [10, 9, 2, 5, 3, 7, 101, 18]，一开始变成tails = [10],接着变成tails = [9]，表示的是长度为 1 的递增子序列，现在可以用更小的结尾9。毕竟长度为 1，结尾当然越小越好。接着变成tails = [2]，接着到5，5 比 2 大，所以可以接上tails = [2,5]接着回变成tails = [2,3]，因为相比前者，后者更有潜力更优秀更容易接数字。（这一步直接找第一个>= num 的位置替换为当前num就行而且tails一定是有序的所以用二分查找tails）- 使用二分查找tails找到第一个大于等于nums当前元素的位置
- 最后返回tails的长度就行
- 时间复杂度：O(n log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def lengthOfLIS(nums):
tails = []
for num in nums:
left, right = 0, len(tails) # r指针初始不-1
# 二分查找tails第一个 >= num 的位置。为了更有潜力
while left < right: ##注意这里的二分边界条件没有等于
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
# 更新tails
if left == len(tails): #现在的结尾都比现在这个num小，可以在每个递增序列继续加上这个num
tails.append(num)
else: # 找到>=num的第一个位置就更改，后面的不用改无法受益
tails[left] = num
return len(tails)
相当于“迭代nums时看看每个num是否可以作为某个长度的递增排列的结尾，最后返回维护tails的长度就行”
r指针初始不-1，是左闭右开区间（因为后面可以加的嘛，反正记住就对了）
这里的二分边界条件没有等于
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
解:
加法只需要管最大值；乘法因为负数会翻转大小关系，所以最大值和最小值都得记。
1.定义状态cur_max以当前这个位置结尾的子数组中乘积最大的值，cur_min为相应最小的值
2.状态转移方程：
dp_max[i] = max(x, dp_max[i-1]*x, dp_min[i-1]*x)
dp_min[i] = min(x, dp_max[i-1]*x, dp_min[i-1]*x)（最大乘积只可能来自自己(如果之前只有单独一个负数重新开始)，以前的最大值 × 当前数字，以前的最小值 × 当前数字）
3.返回
curr[n]注：记得优化空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxProduct(self, nums: list[int]) -> int:
cur_max = nums[0]
cur_min = nums[0]
ans = nums[0]
for num in nums[1:]:
new_max = max(num, cur_max * num, cur_min * num)
new_min = min(num, cur_max * num, cur_min * num)
cur_max = new_max
cur_min = new_min
ans = max(ans, cur_max)
return ans
分割等和子集
给你一个 只包含正整数 的 非空 数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
解：DP+0-1背包
- 如果总和为奇数，不可能分割
- 目标是找到子集，使其和为总和的一半
- 使用动态规划：
bool dp[i][j]表示已经遍历过的前 i 个元素能否组成和为 j,但实际上不用多维DP只使用d[j]表示当前num位置之前遍历的的前面元素能否组成和为 j,初始化d[0]=True，其他为False- 转移方程：dp[j] = dp[j] OR dp[j - num] 其实就是不选
num或者 选num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for j in range(target, num - 1, -1): #0/1 背包，每个 num 最多只能使用一次。所以从大到小遍历，正序会重复使用，
#target这里比num-1大
dp[j] = dp[j] or dp[j - num] # 这里的第二个dp[j]是必要的，代表不选这个num
return dp[target] #
记得是倒序才不会重复使用，比如j = 3 ，dp[3] = dp[3] or dp[0]而再到后面j = 6，dp[6] = dp[6] or dp[3]相当于3 + 3 = 6同一个 3 用了两次
最长有效括号（困难）
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
解：DP
dp[i]表示以 s[i] 结尾的最长有效括号长度- 如果
s[i] == ')'且s[i-1] == '('，dp[i] = dp[i-2] + 2- 如果
s[i] == ')'且s[i-1] == ')'且s[i-dp[i-1]-1] == '('，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
def longestValidParentheses(s):
n = len(s)
dp = [0] * n
max_len = 0
for i in range(1, n):
if s[i] == ')':
if s[i-1] == '(':
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
elif i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = dp[i-1] + (dp[i - dp[i-1] - 2] if i - dp[i-1] >= 2 else 0) + 2
max_len = max(max_len, dp[i])
return max_len
多维动态规划
主要还是要看能不能空间压缩变成一维的DP
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
解：DP+空间压缩
dp[i][j]表示到达位置 (i, j) 的路径数dp[i][j] = dp[i-1][j] + dp[i][j-1]- 边界条件：第一行和第一列都是1
可以空间优化为只用dp[j]表示“处理到当前这一格时，走到
(i,j)的最小路径和”。相当于沿着对角线撕开变成线性的？
1
2
3
4
5
6
7
8
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1]*n
for i in range(1,m): #记得有起点1
for j in range(1,n):
dp[j] += dp[j-1]
return dp[n-1] # 最后返回n-1
记得有起点1和最后返回n-1
最小路径和（不同路径pro但无压缩）
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
解：DP+空间压缩
dp[i][j]表示到达位置 (i, j) 的最小路径和dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]注意：这里的左上角，第一列都要单独考虑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def minPathSum(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = grid[0][0]
for i in range(m): #记得有起点1
for j in range(n):
if i ==0 and j ==0: #单独处理左上角，已经赋值跳过，之前是直接1开始循环
continue
if j>0:
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
else: #单独处理第一列
dp[j] = dp[j] + grid[i][j]
return dp[n-1]
这里得单独处理第一列，所以两个循环从0开始，于是额外单独跳过左上角，“第一列和左上角单独处理”
最长回文子串（最优非DP）
给你一个字符串 s，找到 s 中最长的 回文 子串。
解：DP，无法空间压缩（从514题进化过来的思路）
dp[i][j]表示 s[i:j+1] 是否是回文子串（之所以研究该区间是因为是否回文只看边界两个，且可以进一步缩小区间来得到方程右边项，即之前的前驱节点）- 如果
s[i] == s[j]，dp[i][j] = dp[i+1][j-1]#缩小一点区间的回文长度+2（现在的加入可以延长）最优是Manacher算法O(N),这里展示DP算法O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
# dp[i][j]：s[i:j+1] 是否是回文串
dp = [[False] * n for _ in range(n)]
# length = 1
for i in range(n):
dp[i][i] = True
# 记录最长回文子串的左右边界
start = 0
max_len = 1
# length = 2, 3, ..., n
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
# 长度 <= 2 时，中间没有需要判断的部分
if length <= 2:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j]:
if length > max_len:
max_len = length
start = i
return s[start:start + max_len]
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列，返回 0。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
解：DP，无法空间压缩
- 定义
dp[i][j]为text1的前 i 个字符和text2的前 j 个字符的最长公共子序列长度- 状态转移方程：
- 如果
text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1- 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)] # 记得初始就要+1怎么又忘记了
# 不用给第一行第一列和左上角单独处理了，就是默认0
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]: # 注意dp比原数组对应位置多1
dp[i][j] = dp[i-1][j-1] +1 # 如果相同则最大长度加一个
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # 否则也要考虑前面的收益传播过来（画个表格）
return dp[m][n] #最后返回的是mn不是nn
注意dp比原数组对应位置多1所以是text1[i-1] == text2[j-1]
编辑距离
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
解：DP，无法空间压缩
- 定义
dp[i][j]为将word1的前 i 个字符转换为word2的前 j 个字符所需的最少操作数- 状态转移方程：
- 如果
word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]- 否则：
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
dp[i-1][j]：删除 word1[i-1]dp[i][j-1]：在 word1 中插入 word2[j-1]dp[i-1][j-1]：替换 word1[i-1] 为 word2[j-1]- 初始化 dp第一行第一列为递增序列 （相当于“abc” -> “”，你只能不断删除，故不断加1步）
- 返回dp[m] [n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)] # 记得初始就要+1怎么又忘记了
# 初始化
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
for i in range(1,m+1): # 着两个循环边界怎么又写错了
for j in range(1,n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1])+1
return dp[m][n]
初始化 和 循环边界
技巧题
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
解：位运算
利用异或运算规律：
- 任何数与0异或等于它本身
- 任何数与自身异或等于0
- 异或运算满足交换律和结合律
- 将所有数字异或，结果就是只出现一次的数字
1
2
3
4
5
6
7
8
class Solution:
def singleNumber(self, nums: List[int]) -> int:
n = len(nums)
res =0
for i in range(n):
res ^= nums[i]
return res
初始结果赋值0才不影响
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解：Boyer-Moore 投票法（最优）
把“多数元素”视为“+1”，其他数字看成 “-1”，多数元素出现次数 超过 n/2，所以即使它和其他元素两两抵消，最后仍然会剩下它。
1.只需一个总和 和 候选数记录，接着开始遍历
2.当总和为0（包括了开始），记录为候选数
3.当为候选数，总和+1，否则总和-1
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def majorityElement(self, nums: list[int]) -> int:
count, candidate = 0, None
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count +=1
else:
count -= 1
return candidate
颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
解：荷兰国旗问题，使用三指针
- 使用三个指针：
left（指向0的右边界，初始为0）、curr（当前遍历位置，初始为0）、right（指向2的左边界，初始为数组右边界）- 当
nums[curr] == 0时，与nums[left]交换，left++，curr++- 当
nums[curr] == 1时，curr++- 当
nums[curr] == 2时，与nums[right]交换，right--（注意不移动curr，因为交换来的元素还未检查）- 边界条件为curr <= right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def sortColors(self, nums: list[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = curr = 0
r = len(nums)-1
while curr <= r:
if nums[curr] == 0:
nums[l], nums[curr] = nums[curr], nums[l]
l +=1
curr +=1 # 因为 l 一定不会在 curr 的右边，而且 l 之前的位置全部已经是 0，curr从开始过来的化意味着之前的我们已经全部验收过了
elif nums[curr] == 1:
curr += 1
else:
nums[r], nums[curr] = nums[curr], nums[r]
r -= 1
# curr不需要动因为还没验收交换过来的数字
return nums
下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须** 原地 **修改，只允许使用额外常数空间。
解：两遍扫描，从右到左，因为要让前面尽可能不变的范围尽可能长（尽可能从后面取交换的树，交换的位置尽可能右边），且最后结果改动的部分后面一定是升序的
- 从右向左找到第一个降序的位置
i（即nums[i] < nums[i+1]）- 如果找不到，说明整个数组是降序的，直接反转整个数组
- 从右向左找到第一个大于
nums[i]的位置j- 交换
nums[i]和nums[j]- 反转
i+1到末尾的部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def nextPermutation(self, nums: list[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = n - 2 #记得初始化n-2否则下面循环越界
# 找到nums里升序的最后一对(i,i+1)，保证[i+1,n)是降序的
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# 在[i+1,n)找第一个大于nums[i]的位置j
if i >=0: # 注意验收i是否存在，否则整个是降序数组,不用交换后面等待全部反转就行
j = n-1
while j>i and nums[j]<=nums[i]:
j -=1
# 找到了就交换
nums[i], nums[j] = nums[j], nums[i]
# 反转降序部分[i+1,n)
l,r =i+1, n-1
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
记得初始化n-2否则下面循环越界
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
解：快慢指针（最优）
同龟兔赛跑寻找入口。由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环
- 将数组视为链表，
nums[i]指向nums[nums[i]]- 使用快慢指针找到环的入口
- 环的入口就是重复的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def findDuplicate(self, nums: list[int]) -> int:
n = len(nums)
f = s = nums[0] # 注意初始化为nums[0]而不是0
# 找到相遇点
while 0 <= f < n :# 实际上不用因为已经保证必会有环了
f = nums[f]
f = nums[f]
s = nums[s]
if f == s:
break #找到相遇点了
# 一个从起点出发一个从相遇点出发同速度相遇点就是环入口
f = nums[0]
while s != f: #找的就是入口而不是入口的前一个
s = nums[s]
f = nums[f]
return s # 是入口的前一个
注意初始化为nums[0]而不是0，不然无法全部遍历
心得：
1.vector
2.string直接+就行 ，倒着插入就用元素+(原来的string)
3.
4.BFS广度优先搜索用队列，DFS深度优先搜索用栈（不过好像递归更好）
5.python的哈希表一般使用dict()来创建，defaultdict(list)，不存在的 key 会自动创建。Python 的 dict 要求 key 必须是可哈希（hashable）的，而 list 可变，因此不能作为 key。如第二题就要加个tuple。还有就是其查找用in就行
6.enumerate函数遍历二维数组时，可以同时获取元素的索引和值
7.双指针的话直接用left= right =0这样的一个变量来记住位置即可
8.python的哈希表用dict(),哈希集合直接用set()就行，不过哈希表的键要为定制如是list要改tuple
9.python的等于是要完全相等啊
10.python的最小值（Integer.MIN_VALUE;）为float(“-inf”)，最大值同理
11.python的sort() 提供了一个参数key告诉 Python：”比较的时候，请先把元素变成某个值，再比较这个值。”[合并区间]
12.lambda x: x[0]相当于
1
2
def func(x):
return x[0]
13.python的数组用-1从最后开始找
14.判断语句要变量为空则直接if not
15.python具有多重赋值，对于swap不用事先存储temp,其实际上直接：
1
nums[i], nums[j] = nums[j], nums[i]#先计算完右边再一起赋值给左边
16.二分查找必须维护两个值再让mid=(left+right)/2而不是单独一个right
17.c++的
1
pA = pA == nullptr ? headB : pA->next;
在python中是
1
pA = headB if pA is None else pA.next
18.新建链表：
1
2
3
4
5
6
7
8
9
10
dummy = ListNode(0)
curr = dummy # 要加节点的话后面加就行
最后返回的话直接dummy.next就行
# 如果要从已有链表新建
dummy = ListNode(0, head) # 新建虚拟头节点，后面是head链表
等同于
dummy = ListNode(0)
dummy.next = head
最后一样返回dummt.next
19.python的栈和队列的加入都是append只有pop和popleft不同，且append可以同时家多个或者一整个数组
华为机试刷题
REALHW235 小红的花圃抬高方案
描述
小红要用土把所有花圃的最低高度尽量抬高。每单位土的填埋成本为 UU；每车最多运 CC 单位土，每启用一车另付运输费 FF，一车土可分给多个花圃。预算为 BB。求预算内所有花圃最终最低高度的最大值。
输入描述：
依次输入预算 BB、每车容量 CC、运输费 FF、单位填埋费 UU、花圃数 nn，最后输入 nn 个初始高度。 保证 1≤B≤10111≤B≤1011，1≤C,F,U≤1001≤C,F,U≤100，1≤n≤1051≤n≤105，高度在 [0,106][0,106]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
示例1
输入：
100
10
5
2
5
1 2 5 3 4
复制
输出：
11
复制
说明：
抬高到 11 需要 40 单位土，填埋费 80、运输费 20。
示例2
输入：
50
10
10
1
10
1 2 5 3 4 5 4 1 1 1
复制
输出：
4
复制
说明：
抬高到 4 总成本 35，抬高到 5 总成本 53。
解：将其视为一个单调的二分解法即可.1. 填土量对于每个花圃高度 a[i]：
- 如果
a[i] >= H，不用填土 - 如果
a[i] < H，需要：H−a[i]H-a[i]单位土。
总填土量：S(H)=∑ai<H(H−ai)S(H)=\sum_{a_i<H}(H-a_i)而每车最多运输 C 单位土，因此需要的车辆数：
k=⌈S(H)C⌉k=\left\lceil\frac{S(H)}{C}\right\rceil
每辆车运输费为 F，所以运输费用：kFkF
填埋费用：S(H)US(H)U
总费用：cost(H)=S(H)U+⌈S(H)C⌉Fcost(H)=S(H)U+\left\lceil\frac{S(H)}{C}\right\rceil F
只要：cost(H)≤Bcost(H)\le B
说明最低高度 H 可以达到。这里用一个前缀和去计算更好更快，不过不用也能过啦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
from bisect import bisect_left
data = list(map(int, sys.stdin.buffer.read().split()))
B, C, F, U, n = data[:5]
height = data[5:5+n]
a = min(height)
def check(H):
soil = 0
for x in height:
if x < H:
soil += H - x
# 填土费用
cost = soil * U
# 运输费用
trucks = (soil + C - 1) // C
cost += trucks * F
return cost <= B
# 最低高度不可能低于 0
# 上界取 min(a) + B // U + 1，保证一定不可行
lo = 0
hi = a + B // U + 1
while lo < hi:
mid = (lo + hi + 1) // 2
if check(mid):
lo = mid
else:
hi = mid - 1
print(lo)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
from bisect import bisect_left
data = list(map(int, sys.stdin.buffer.read().split()))
B, C, F, U, n = data[:5]
height = data[5:5+n]
# 排序
height.sort()
# 前缀和
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + height[i]
def check(H):
# 找到所有 < H 的花圃数量
k = bisect_left(height, H)
# 这些花圃填到 H 所需要的土
soil = H * k - prefix[k]
# 总成本
cost = soil * U
# 运输车辆数，向上取整
trucks = (soil + C - 1) // C
cost += trucks * F
return cost <= B
# 二分答案
l = 0
r = height[0] + B // U + 1
while l < r:
mid = (l + r + 1) // 2
if check(mid):
l = mid
else:
r = mid - 1
print(l)
REALHW233 小红的动态专家路由
描述
有 NN 个任务和 EE 个专家。每个任务按分数选择前 KK 个专家，分数相同优先编号小者。随后按任务编号顺序调度：专家当前负载小于容量 CC 时分配生效，否则丢弃。最终输出各专家负载平方和以及负载数组。
输入描述：
第一行输入 N,E,K,CN,E,K,C，随后输入 N×EN×E 的整数评分矩阵。 保证 N×E≤5×105N×E≤5×105，1≤K≤E≤1001≤K≤E≤100，0≤C≤N0≤C≤N，评分在 [0,104][0,104]。
输出描述：
第一行输出负载平方和，第二行输出各专家最终负载。
解：关键是调度以及topk吧，这里记得是K个（topk）,还有不满足的判断在自定义exp数组赋值时
sorted函数参数：sorted(iterable, key=None, reverse=False)，iterable：要排序的数据，必须是一个可迭代对象，比如列表、元组、字符串等。key：按照什么规则排序 ，可以写lambda(如 lambdax :len(x) ,则是按照元素比如字符串大小)，reverse：是否倒序，否则为从小到大升序.
list(enumerate())将一个list变为（键，值）组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
line = list(map(int, sys.stdin.buffer.read().split()))
N, E, K, C = line[0], line[1], line[2], line[3]
# N × E 的评分矩阵
NE = line[4:]
matrix = [
NE[i * E:(i + 1) * E]
for i in range(N)
]
# exp[i]：专家 i 最终承担的任务数
exp = [0] * E
# 按任务编号顺序调度
for m in range(N):
# (专家编号, 分数)
indexed_row = list(enumerate(matrix[m]))
# 分数从高到低；分数相同编号小的优先
topk = sorted(
indexed_row,
key=lambda x: (-x[1], x[0])
)[:K]
# 依次尝试分配给 Top-K 专家
for idx, score in topk:
# 专家容量没满，分配生效
if exp[idx] < C:
exp[idx] += 1
# 负载平方和
ans = sum(x ** 2 for x in exp)
print(ans)
print(*exp)
REALHW236 小红的满减购物清单
每件商品最多买一件。购物原价每满 200 减 20；若所选商品包含至少 3 个不同类别，则改为每满 200 减 30，两种优惠不叠加。给定预算，求折后价不超过预算时的最大满意度总和。
输入描述：第一行输入预算，第二行输入商品数 nn，随后 nn 行输入唯一编号、类别、价格、满意度。 保证预算在 [10,1000][10,1000]，1≤n≤201≤n≤20，类别在 [1,10][1,10]，价格在 [1,200][1,200]，满意度在 [1,240][1,240]。
输出描述：输出最大满意度总和。
解：这道题本质上是一个 带特殊折扣规则的 0/1 背包问题。关键点在于：优惠金额不仅取决于总价格，还取决于选择了多少种不同类别。因为 n ≤ 20，直接枚举所有商品子集即可：
一共最多
2^20 ≈ 1048576个子集，可以接受。对每个子集计算：
- 原价总和
sum_price - 满意度总和
sum_satisfaction - 不同类别数量
category_count - 根据优惠规则计算折后价格
- 如果折后价格
<= budget，更新最大满意度。
优惠规则：
- 不足 200：没有优惠
- 如果不同类别
< 3：discount = (sum_price // 200) * 20 - 如果不同类别
>= 3：discount = (sum_price // 200) * 30 - 两种优惠不叠加
注意优惠是按照原价每满 200计算，所以：折后价 = 原价 - floor(原价 / 200) * 优惠额度
但是这种方法智能通过18/20
- 原价总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
budget = int(input())
n = int(input())
goods = []
# 先把所有商品读进来
for _ in range(n):
id_, category, price, satisfaction = map(int, input().split())
goods.append((category, price, satisfaction))
# 所有商品读取完毕之后，再初始化答案
ans = 0
# 枚举所有商品子集
for mask in range(1 << n):
total_price = 0
total_satisfaction = 0
categories = set()
# 枚举当前子集中的商品
for i in range(n):
if mask & (1 << i):
category, price, satisfaction = goods[i]
total_price += price
total_satisfaction += satisfaction
categories.add(category)
# 根据不同类别数量确定优惠
if len(categories) >= 3:
discount = (total_price // 200) * 30
else:
discount = (total_price // 200) * 20
final_price = total_price - discount
if final_price <= budget:
ans = max(ans, total_satisfaction)
print(ans)
完美的DP（”1“+”1+1+1+1+!“ 直接=”6“，因为之前你算过后项为5并记住了）解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
普通DP：如果没有“不同类别 ≥ 3”这个条件，普通 0/1 背包就很简单。假设有三个商品：
商品 价格 满意度
A 100 90
B 200 150
C 300 220 ，我们定义：dp[p]表示：总价格不超过 p 时，能够获得的最大满意度。例如dp[100] = 90表示预算/容量是 100，最多买 A，所以满意度 90。在普通 0/1 背包里，最后判断一个方案是否可行，只看总价格 ≤ 预算，而目标只看总满意度，所以一个状态只需要知道：当前用了多少容量，即price即可，至于之前具体买了什么商品，不重要（DP）。参考这种DP思想，例如有两种方案：
方案 A：
价格 = 300
满意度 = 200
方案 B：
价格 = 300
满意度 = 250
对于后续决策来说，方案 A 完全没必要保留。因为它们：价格一样，方案 B 满意度更高，所以我们只保留dp[300] = 250（只保留对于未来决策有用的信息。）
然而这道题是不同类别 < 3：每满 200 减 20不同类别 >= 3：每满 200 减 30，现在假设有两个方案：方案 A：
原价 = 400
满意度 = 300
类别 = {1, 2}
方案 B：
原价 = 400
满意度 = 280
类别 = {1, 2, 3}
如果我们还是只定义：dp[400]那么：dp[400] = 300因为方案 A 满意度更高。但是问题来了A的折后价 = 360，B的折后价 = 340假设：预算 = 350
方案 A：360 > 350 ❌
方案 B：340 <= 350 ✅
虽然方案 A 在相同原价下满意度更高，但它不可行；方案 B 满意度稍低，却因为类别更多而可以购买。
这就是为什么要增加一个类别维度mask变为dp[mask][price]，这里为什么不加类别数量，因为新类别来了要知道是不是新类别，即DP“为了决定下一步，我必须知道前面的什么信息？”的思想
流程图：
商品
↓
┌───────────────┐
│ 0/1 背包转移 │
└───────┬───────┘
↓
dp[类别集合][原价]
↓
判断类别集合大小
↙ ↘
< 3类 ≥ 3类
↓ ↓
每200减20 每200减30
↘ ↙
↓
折后价格 ≤ 预算
↓
最大满意度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
budget = int(input())
n = int(input())
goods = []
for _ in range(n):
_, category, price, satisfaction = map(int, input().split())
goods.append((category, price, satisfaction))
ans = 0
total_price = 0
total_satisfaction = 0
# category_count[c]：
# 当前购物方案中，类别 c 有多少件商品
category_count = [0] * 11
distinct_categories = 0
# 加上个格雷码的思想gray(s) = s ^ (s >> 1)，从 s-1 到 s，只会改变一个商品。
prev_gray = 0
for s in range(1 << n):
gray = s ^ (s >> 1)
if s > 0:
# 找到 Gray Code 中发生变化的那一位
changed = gray ^ prev_gray
# changed 只有一个 bit 为 1
i = changed.bit_length() - 1
category, price, satisfaction = goods[i]
if gray & changed:
# 这个商品被加入
total_price += price
total_satisfaction += satisfaction
if category_count[category] == 0:
distinct_categories += 1
category_count[category] += 1
else:
# 这个商品被删除
total_price -= price
total_satisfaction -= satisfaction
category_count[category] -= 1
if category_count[category] == 0:
distinct_categories -= 1
prev_gray = gray
# 空集跳过
if s == 0:
continue
if distinct_categories >= 3:
discount_rate = 30
else:
discount_rate = 20
final_price = (
total_price
- (total_price // 200) * discount_rate
)
if final_price <= budget:
ans = max(ans, total_satisfaction)
print(ans)
REALHW234 小红的流水线阶段划分
解：理解题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
n = 5
p = 3
T = 10
每层时间：
2 4 6 3 7
通信开销：
1 1 1 1
5 层模型就是：
第1层 第2层 第3层 第4层 第5层
2 4 6 3 7
通信开销：
第1层 | 第2层 | 第3层 | 第4层 | 第5层
1 1 1 1
这里：
comm1 = 1
表示：如果在第 1 层和第 2 层之间切一刀，需要通信开销 1。
同理：comm2 = 1
表示在第 2、3 层之间切，花费 1。
什么叫“划分为 p 个非空连续阶段”？
这里最重要。n = 5，要求：p = 3
也就是说：5 层 → 分成 3 段
而且每段必须连续。比如：[2,4] [6,3] [7]就是合法的。
对应：
第1层 第2层 | 第3层 第4层 | 第5层
第一段 | 第二段 | 第三段
为什么会产生通信开销？
因为你切了一刀。
上面的：
[2,4] [6,3] [7]
实际上切了两刀：
2 4 | 6 3 | 7
↑ ↑
comm2 comm4
注意这里非常容易搞错：
[2,4] 后面切 → 在第 2 层后切 → comm2
[6,3] 后面切 → 在第 4 层后切 → comm4
所以：
总通信开销 = comm2 + comm4
= 1 + 1
= 2
因此答案是：2
但是不是随便切都行？
不是。还必须满足：
每一段的计算时间总和 ≤ T
这里：T = 10我们的划分：[2,4] [6,3] [7]
检查：
第一段：
2 + 4 = 6 ≤ 10
第二段：
6 + 3 = 9 ≤ 10
第三段：
7 ≤ 10全部满足。所以这个划分合法。
为什么要“恰好 p 段”？
题目说：恰好划分为 p 个非空连续阶段
不是：最多 p 段.也不是：至少 p 段.而是必须正好 p 段。
例如：
n = 5
p = 3
那么：[2,4,6] [3] [7]是 3 段。
但是：[2,4] [6,3,7]只有 2 段。不行。
[2] [4] [6] [3,7]是 4 段。也不行。
其实可以把它画成：
1 2 3 4 5
|-----|-----|-----|-----|
2 4 6 3 7
可以切的位置：
↓ ↓ ↓ ↓
1 2 3 4 5
|-----|-----|-----|-----|
c1 c2 c3 c4
你需要从这些切点：c1 c2 c3 c4里面选择：p - 1个切点。
因为：p 段 = p-1 刀。例如：p = 3
就必须切：2刀这其实就是一个“选择切刀”的问题例如：
[2,4,6,3,7]
要求 3 段。
所以需要选择两个切点。
假设：
↓ ↓
[2,4] | [6,3] | [7]
2刀
通信费用：
comm2 + comm4
= 1 + 1
= 2
如果通信费用不同，比如：
comm = [5, 1, 8, 2]
那么这个切法费用就是：
comm2 + comm4
= 1 + 2
= 3
我们真正要做的是：
在所有合法的切法中，找通信费用最小的那个。
直接贪心看看：注意读入的时字符串要转类型。list有什么好方法转吗map(int, input().split())
是一个DP问题，不是决定“现在能不能继续放下一层”。要解决的是：最后一段从哪里开始？定义 DP：dp[i][j]表示前 i 层，恰好分成 j 段时的最小通信开销。例如·dp [5] [3]表示前 5 层分成 3 段，最小通信开销是多少。dp = [[float(‘inf’)] * (p + 1) for _ in range(n + 1)]注意是n+1和p + 1
这里为了快速计算times[k] + … + times[i]，使用前缀和。
状态转移。dp[i] [j] 前 i 层分成 j 段。现在假设最后一段从第 k 层开始：
1
2
3
1 2 ... k-1 | k k+1 ... i
↑
最后一段
那么前面：1 … k-1必须分成j - 1,所以：dp[k - 1] [j - 1]就是前面的最小通信费用。写出转移：
1
2
3
4
dp[i][j] = min(
dp[i][j],
dp[k - 1][j - 1] + comm[k - 2]
)
最后一段是否合法?否则是返回-1的情况 prefix[i] - prefix[k - 1] <= T
通信开销。k - 1层后面切了一刀。增加comm[k - 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
n, p, T = map(int, input().split())
times = list(map(int, input().split()))
comm = list(map(int, input().split()))
# prefix[i] 表示前 i 层的总时间
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + times[i - 1]
# dp[i][j]
# 表示前 i 层恰好分成 j 段时的最小通信开销
INF = float('inf')
dp = [[INF] * (p + 1) for _ in range(n + 1)]
# 0 层分成 0 段，费用为 0
dp[0][0] = 0
# 枚举前 i 层
for i in range(1, n + 1):
# 枚举分成 j 段
for j in range(1, min(i, p) + 1):
# 假设最后一段从第 k 层开始
for k in range(1, i + 1):
# 最后一段 k...i 的时间
segment_time = prefix[i] - prefix[k - 1]
# 这一段超过 T，不合法
if segment_time > T:
continue
# 最后一段从第 1 层开始
if k == 1:
# 那么只能是整个区间只有 1 段
if j == 1:
dp[i][j] = 0
continue
# 前 k-1 层必须分成 j-1 段
if dp[k - 1][j - 1] == INF:
continue
# 在第 k-1 层后切一刀
cost = dp[k - 1][j - 1] + comm[k - 2]
dp[i][j] = min(dp[i][j], cost)
res = dp[n][p]
if res == INF:
res = -1
print(res)