哈希
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：输入：nums = [3,3], target = 6 输出：[0,1]
分析:
1.遍历数组, 同时 hash 记录当前已经保存过的数字的索引, 遇到互补元素则可以找到两数之和;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num2idx;
for (int i = 0; i < nums.size(); ++i) {
if (num2idx.find(target - nums[i]) != num2idx.end()) {
return vector<int>{num2idx[target-nums[i]], i};
}
num2idx[nums[i]] = i;
}
return vector<int>{};
}
};
49.字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。
示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2: 输入: strs = [“”] 输出: [[“”]]
示例 3: 输入: strs = [“a”] 输出: [[“a”]]
分析:
1.按照每一类异位词进行分组哈希, 然后遍历哈希表, 哈希函数设计成什么呢?
2.一种简单的做法是 26 个字符出现的次数拼起来的字符串, 对于 abd 来说就是 “11010000..00” 这样, 但是一个词出现的次数大于 10 次造成冲突, 所以在每个位置之间增加一个分隔符, 比如 1#1#0#1..#0#
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> group2strs;
auto hash = [] (string s) {
vector<int> cnt(26, 0);
for (char c: s) {
cnt[c - 'a'] += 1;
}
string hashStr = "";
for (auto c: cnt) {
hashStr += to_string(c) + "#";
}
return hashStr;
};
for (auto s: strs) {
group2strs[hash(s)].push_back(s);
}
for (auto x: group2strs) {
ans.push_back(x.second);
}
return ans;
}
};
128.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
分析:
1.时间复杂度要求是 O(n), 排序之类的都不能用
2.这里关键是分析连续序列有什么特殊性? 对于连续的序列, 它的很多子序列对我们计算最长序列长度没有影响, 比如对 1,2,3,4 这个序列, 对于它的子序列, 例如 2,3,4 或者 3,4, 不会增加最大长度序列的可能性; 如果能想到研究对象缩短到研究, 当前的数字是否是某个最长序列的 [判断可能是一个最长连续序列的起点], 那么复杂度就不会增加; 也就是说, 我们对任意一个数字, 判断当前的数字是 [可能是一个最长连续序列的起点] 的时候, 才会进入内层统计长度, 因此时间复杂度是 O(n)
3.用一个 set 去保存元素, 然后遍历 set , 每个元素首先检查是否是第一个元素, 如果不是那么就不进入扫描最长连续长度
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
unordered_set<int> s(nums.begin(), nums.end());
int ans = 1;
for (auto x: s) {
// 判断可能是一个最长连续序列的起点
if (!s.count(x - 1)) {
int len = 1;
int cur = x;
// 进入里面开始逐个判断以它为起点的最长长度
while (s.count(cur + 1)) {
++len;
++cur;
}
ans = max(len, ans);
}
}
return ans;
}
};
双指针
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。
示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2: 输入: nums = [0] 输出: [0]
分析:
1.把所有的 0 移动到末尾, 等同于把所有的非0元素移动到最前面, 然后将后面的全部置为零; 要求就地复制元素实现, 维护快慢双指针, fast 检索所有非0的元素之后给到 slow
2.fast 检索完之后, 从 slow 开始后面的元素都设置成 0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int len = nums.size();
if (len <= 1) {
return;
}
int slow = 0;
int fast = 0;
// 快慢指针
// fast 给到 slow 将非 0 元素移动到最前面
while (fast < len) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
// 把 slow 之后的都设置为 0
while (slow < len) {
nums[slow] = 0;
++slow;
}
return;
}
};
11.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。
示例 1：输入：[1,8,6,2,5,4,8,3,7] 输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1] 输出：1
分析:
1.我们找出来两个左右两个端点, 然后计算最大的盛出来的水量, 假设我们已经有了这么两个最优的端点, 盛出来水的量是什么?
直接求面积, 面积的公式是什么? 假设我们确定了左右两个指针 left, right, 长就是 right - left, 宽是什么 ? 其实和木桶原理有点像, 承载的水是两边比较低的那头, 也就是 min(left, right);
curArea = min(left, right) * (right - left)
2.所以怎么搜索最大的面积呢 ? 一开始肯定是从最左边和最右边两个端点开始, 计算一个 curArea; 然后怎么更新呢? 每次是移动左边的指针还是移动右边的指针? 因为面积是取决于左右两边的最小值, 也就是说, 我们需要每次更新的是比当前下界更高的那个下界, 才能有机会找到更大的面积, 因此我们每次移动的是当前的 left 和 right 中间较小的一个指针
class Solution {
public:
int maxArea(vector<int>& height) {
int len = height.size();
int left = 0;
int right = len - 1;
int ans = 0;
while (left < right) {
int curArea = min(height[left], height[right]) * (right - left);
ans = max(ans, curArea);
if (height[left] < height[right]) {
++left;
} else {
--right;
}
}
return ans;
}
};
15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。
示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
分析:
1.因为只是判断存在性, 元素前后不存在先后顺序, 所以先排序
2.对所有的元素扫描, 固定住当前的第 i 个元素, 在后面的数组用双指针搜索 complement == nums[left] + nums[right] == - nums[i] 的情况
3.因为我们要的结果是不重复的三元组, 如果当前的元素和前面的一个元素相等, 就会多计算一次, 所以在找的时候直接过掉这一次; 在左右指针搜索的时候, 也要注意避免重复的结果 push
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
int len = nums.size();
if (len <= 2) {
return ans;
}
sort(nums.begin(), nums.end());
// 当前元素作为最小的元素
for (int i = 0; i < len - 2; ++i) {
// 最小的元素>0, 后面都不用搜索了
if (nums[i] > 0) {
break;
}
// 如果当前元素和前面元素相同, 不再重复判断, 否则会造成结果重复
if (i - 1 >= 0 && nums[i] == nums[i-1]) {
continue;
}
int complement = -nums[i];
int left = i + 1;
int right = len - 1;
while (left < right) {
if (nums[left] + nums[right] == complement) {
ans.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) {
++left;
}
while (left < right && nums[right] == nums[right-1]) {
--right;
}
++left;
--right;
} else if (nums[left] + nums[right] < complement) {
++left;
} else if (nums[left] + nums[right] > complement) {
--right;
}
}
}
return ans;
}
};
42.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：输入：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 个单位的雨水（蓝色部分表示雨水）。
示例 2：输入：height = [4,2,0,3,2,5] 输出：9
分析:
1.需要分析接到的水量是怎么计算的, 从直观感觉来算, 对于 (示例图里面) 出现的【凹槽里面水】, 要计算接到的雨水数量, 怎么累计全部凹槽的雨水量呢 ? 我们先考虑对于1个位置来说, 比如针对第i个位置上, 最大能接到的水怎么算?
2.对于最左边和最右边的位置, 不管多高或者多低, 题意背景下都是接不到水的, 所以我们考察的是 [1, n-1] 这些位置上的 i 的获得水量, 针对第i个位置上, 水量怎么计算呢?
3.类似木桶原理, 对于第i个位置上的接水量, 第一感觉上取决于左边和右边的较低的一方, 但是还有一种情况是考虑凹槽是 [T字型] 的这种情况, 所以就不可以仅考虑 i 位置相邻的 [i-1, i+1] 的情况, 而是要确定位置 i 左右两侧各自最高度的的情况, 然后再去取左右两侧所有最高度的最小高度; 同时, 对于 i 位置自己本身也是有高度的, 假设左边柱子最高的高度是比位置i还要低的, 那么计算一边的最低位置也要考虑算自己
4.总结: 对于位置 i, 能接雨水的量为: min(i左侧所有(含i)最高柱子, 右侧所有(含有i)最高柱子) - height[i]
water[i] = min(max(height[0..i]), max(height[i..n-1])) - height[i];
5.代码思路: 从左往右累加第 i 个位置上的雨水值; 对于第 i 个位置, 分别计算它左侧 (包括自己) 的最高值, 计算右侧的最高值, 然后取二者的最小值, 在减去自己位置 i 的高度, 得到的就是第 i 个位置上的接水量, 因此我们得到最 naive 的版本
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
int leftSideMax = 0;
int rightSideMax = 0;
for (int j = i; j >= 0; --j) {
leftSideMax = max(leftSideMax, height[j]);
}
for (int j = i; j < n; ++j) {
rightSideMax = max(rightSideMax, height[j]);
}
ans += min(leftSideMax, rightSideMax) - height[i];
}
return ans;
}
};
6.naive 版本显示超时, 超时的原因是第i个位置上计算时, 每次计算左边右边的最大值都会重复遍历一遍, 可以用备忘录把这个记下来, 其实就是记录下来了左边或者右边最大高度的状态转移关系 (将这道题当做动态规划来做); 状态初始条件是什么? 比如对于 leftMaxMemo[0] 记录的是第0个元素左边的最大, rightMaxMemo[0] 记录的是右边最后一个元素的最大, 为了后续结果计算不影响, 我们将左边最大和右边最大分别设置成最左边的1个元素高度和右边最后一个元素的高度;
vector<int> leftMaxMemo(n);
vector<int> rightMaxMemo(n);
// 初始条件
leftMaxMemo[0] = height[0];
rightMaxMemo[n-1] = height[n-1];
// 状态转移
for (int i = 1; i < n; ++i) {
leftMaxMemo[i] = max(height[i], leftMaxMemo[i-1]);
}
// 状态转移
for (int i = n - 2; i >= 0; --i) {
rightMaxMemo[i] = max(height[i], rightMaxMemo[i+1]);
}
7.有了状态转移的备忘录, solution 如下:
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int ans = 0;
vector<int> leftMaxMemo(len);
vector<int> rightMaxMemo(len);
// 初始条件: 设置第0位置元素左边最大为第 0 个元素的高度, 设置第 n-1 位置元素右边最大为第 n-1 个元素的高度
// 不影响状态转移计算的结果
leftMaxMemo[0] = height[0];
rightMaxMemo[len-1] = height[len-1];
// 构造左侧最大的 memo: 状态转移为 max(height[i], leftMaxMemo[i-1])
for (int i = 1; i <= len-1; ++i) {
leftMaxMemo[i] = max(height[i], leftMaxMemo[i-1]);
}
// 构造右侧侧最大的 memo 状态转移为 max(height[i], rightMaxMemo[i-1])
for (int i = len-2; i >= 0; --i) {
rightMaxMemo[i] = max(height[i], rightMaxMemo[i+1]);
}
for (int i = 1; i <= len-2; ++i) {
ans += min(leftMaxMemo[i], rightMaxMemo[i]) - height[i];
}
return ans;
}
};
8.左右双指针两边向中间逼近思路 (可以先参考下另一个问题 11.盛最多水的容器 再回来看这个问题)
在动态规划的方法中, 我们考察的是 左侧 [0..i] 区间 和右侧 [i..n-1] 区间的各自区间最大值, 但我们最终是关心 min(leftSideMax, rightSideMax), 也就是只关心两边各自最大中的 [最小的一个]
假如我们知道在 leftMax < rightMax 的情况下, 那么右边最大的是多少暂时不重要, 只需要关心 height[i] 和 已经被确认是较低的 leftMax 去运算
而且我们发现动态规划的时候, 左边指针单项往右扫, 右边指针单项向右扫, 扫完一个位置之后都是就不回来了, 每个位置上只扫一次, 在这种设定下, 实质上考察 左侧[0..left] 区间和 右侧[right..n-1] 区间, 且 left 指针始终向右扫, right始终向左扫
9.我们只对维护左边和右边两个指针去保存, 而不是按照整个数组去保存, 看下能否实现: 用左右两个指针去扫描, 判断哪个指针扫过的最高柱子更小, 就移动哪个指针, 同时累加当前的扫过的接水量
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
int leftMaxPtr = 0;
int rightMaxPtr = n - 1;
int leftMax = 0;
int rightMax = 0;
while (leftMaxPtr < rightMaxPtr) {
// 左右指针向中央逼近, 只找两边各自最大的里面更小的一个
leftMax = max(leftMax, height[leftMaxPtr]);
rightMax = max(rightMax, height[rightMaxPtr]);
// 哪边更小, 累加哪边的雨水, 同时也移动哪边的指针;
if (leftMax < rightMax) {
ans += leftMax - height[leftMaxPtr];
++leftMaxPtr;
} else {
ans += rightMax - height[rightMaxPtr];
--rightMaxPtr;
}
}
return ans;
}
};
滑动窗口
3.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2：输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3: 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
分析:
1.用滑动窗口对任何一个子串进行无重复判断, 维护窗口内我们搜的是最长的不重复子串
2.为了判断窗口内是无重复的, 我们引入一个 hash表 去记录窗口内每个字符出现的次数
3.如果当前右边指针指向字符发生了重复, 那么就移动左边的窗口
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
if (len <= 1) {
return len;
}
int l = 0;
int r = 0;
int ans = 1;
// 记录无重复窗口里面的字符出现次数
unordered_map<char, int> noRepeatWindowCharCnt;
while (r < len) {
char rc = s[r];
++r;
noRepeatWindowCharCnt[rc] += 1;
// 如果右边指针出现了重复元素, 窗口左侧持续收缩, 直到窗口里面完全无重复 (noRepeatWindowCharCnt[rc] == 1)
while (noRepeatWindowCharCnt[rc] > 1) {
char lc = s[l];
++l;
--noRepeatWindowCharCnt[lc];
}
ans = max(ans, r - l);
}
return ans;
}
};
438.找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:输入: s = “cbaebabacd”, p = “abc” 输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。示例 2: 输入: s = “abab”, p = “ab” 输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
分析:
1.先采用模板的方法: 用滑动窗口搜索每个窗口内是否每个字母出现的次数和需要的次数是一致的; 首先构建一个 hash table 将需要的次数统计一下
2.开始滑动, 每次滑动的时候记录一下当前窗口内每个字符出现的次数, 如何判定所有的次数和整体的次数相等? 一种简单的方法是再引入一个窗口内满足条件的总次数, 每次判定当前右边指针指向的那个字符和我们想要的这个字符出现次数是匹配的情况下, ++valid, 如果 validCnt = p.size(); 那么就推出去结果
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> need;
unordered_map<char, int> window;
for (char c: p)
++need[c];
int left = 0;
int right = 0;
int valid = 0;
vector<int> ans;
while (right < s.size()) {
char r = s[right];
++right;
if (need.count(r)) {
++window[r];
if (need[r] == window[r])
++valid;
}
while (right - left >= p.size()) {
if (valid == need.size()) {
ans.push_back(left);
}
char l = s[left];
++left;
if (need.count(l)) {
if (need[l] == window[l]) {
--valid;
}
--window[l];
}
}
}
return ans;
}
};
滑动窗口的方法可以采用更简单的方式, 用 vector
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sLen = s.size();
int pLen = p.size();
vector<int> ans;
if (pLen > sLen) {
return ans;
}
vector<int> sCnt(26, 0);
vector<int> pCnt(26, 0);
for (int i = 0; i < pLen; ++i) {
++pCnt[p[i] - 'a'];
++sCnt[s[i] - 'a'];
}
if (sCnt == pCnt) {
ans.push_back(0);
}
for (int i = 1; i < sLen - pLen + 1; ++i) {
sCnt[s[i-1] - 'a'] -= 1;
sCnt[s[i + pLen - 1] - 'a'] += 1;
if (sCnt == pCnt) {
ans.push_back(i);
}
}
return ans;
}
};
子串
560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：输入：nums = [1,1,1], k = 2 输出：2
示例 2：输入：nums = [1,2,3], k = 3 输出：2
分析:
1.题目中要求的是计算数组中连续子数组的求和 == k的情况, 我们看到连续子数组求和马上联想到前缀和数组看看能不能加快计算, 因为要求的是连续子数组和 == k, 那么其实转化到前缀和数组上就是问两个前缀和的差 == k的情况
2.我们用带包含的定义 preSum[i] 是包含第 i 个元素的前缀和, 也就是
preSum[i] = preSum[i - 1] + num[i]
3.对于任意的两个下标 i 和 j（i < j），如果 prefixSum[j] - prefixSum[i] = k，即从第 i 个位置到第 j 个位置的元素之和等于 k, 那么说明从第 i+1 个位置到第 j 个位置的连续子数组的和为 k
先遍历 1 次数组, 得到前缀和数组, 开一个哈希表来存储每种前缀和出现的次数. 在遍历的过程中, 我们检查是否存在 prefixSum[j] - k的前缀和, 如果存在，说明从某个位置到当前位置的连续子数组的和为 k, 我们将对应的次数累加到结果中
再遍历一次数组，累加出和为 k 的连续子数组的个数，最终时间复杂度为 O(n)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = 0;
// 构建包含i的前缀数组
vector<long> preSum(n, 0);
preSum[0] = nums[0];
for (int i = 1; i < n; ++i) {
preSum[i] = preSum[i-1] + nums[i];
}
// preSum2Cnt 记录每一种前缀和出现的次数
unordered_map<long, int> preSum2Cnt;
preSum2Cnt[0] = 1;
for (int i = 0; i < n; ++i) {
// 如果 preSum[i] - k 这种前缀和是存在的, 那么答案累加这种前缀和的次数, 同时累加这种前缀和出现的次数
if (preSum2Cnt.find(preSum[i] - k) != preSum2Cnt.end()) {
ans += preSum2Cnt[preSum[i] - k];
}
// 累加前缀和出现的次数
preSum2Cnt[preSum[i]] += 1;
}
return ans;
}
};
对每个位置 i, 计算前缀和只需用 1 次, 因此前缀和计算和累加前缀和是可以同时进行, 不需要开数组, 只维护当前那个前缀和出现的次数
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0;
if (n == 0) {
return 0;
}
long preSum = 0;
unordered_map<long, int> preSum2Cnt;
preSum2Cnt[0] = 1;
for (int i = 0; i < n; ++i) {
preSum += nums[i];
if (preSum2Cnt.find(preSum - k) != preSum2Cnt.end()) {
ans += preSum2Cnt[preSum - k];
}
preSum2Cnt[preSum] += 1;
}
return ans;
}
};
239.滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。
示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7示例 2：输入：nums = [1], k = 1 输出：[1]
分析:
1.核心思路是如果有一个数据结构能模拟窗口滑动的移动, 那么问题就解决了, 有没有这样的一个数据结构呢? 既要随时取出来最大的元素, 同时满足一个窗口大小是固定的; 为了满足取出来最大的元素, 想到可以持续用大顶堆取顶部元素 pq.top(), 依次取出来最大的那个元素
2.但是怎么模拟窗口大小固定的呢? 可以持续往大顶堆加入元素, 但是保存我们要的结果的时候需要判断一下是否在固定长度的窗口内; 也就是说, 在移动过程中, 队列持续加入元素, 但是最大元素可能不在窗口里面, 需要移除出去最大的元素, 需要注意是要持续移动直到不在窗口内的所有最大元素都移除出去
3.判断不在窗口内方法是队列元素增加一个维度是 index , 如果判断当前窗口添加元素后最大元素应该排除出去, 这时候有 窗口的维护是 [i-k+1, i] 这么 k 个元素, 也就是说窗口元素包含的下界是 [i-k+1], 所以 q.top().second < i - k + 1 都要移除出去
4.举个例子 [9,10,9,-7,-4,-8,2,-6] 窗口大小是 5
移动方法是:
[9,10,9,-7,-4,-8,2,-6] [9,10,9,-7,-4] max = 10
[9,10,9,-7,-4,-8,2,-6] i = 5 队列放入-8 [9,10,9,-7,-4,-8] max=10
[9,10,9,-7,-4,-8,2,-6] i = 6 队列放入2 [9,10,9,-7,-4,-8,2] 最大元素 10 不应该在窗口里面, 删掉10, 变成 [9,9,-7,-4,-8,2], 最大元素9从队列删除, 变成 [9,-7,-4,-8,2] max = 9
[9,10,9,-7,-4,-8,2,-6] i = 7 放入-6 [9,-7,-4,-8,2,-6], 删除最左边的9, max=2
所以最后是 [10,10,9,2]
typedef pair<int, int> pii;
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int len = nums.size();
auto cmp = [] (const pii& a, const pii& b) {
return a.first < b.first;
};
// 建一个 pii 类型大顶堆, 维护 <元素值, index> pair
priority_queue<pii, vector<pii>, decltype(cmp)> pq;
for (int i = 0; i < k; ++i) {
pq.push({nums[i], i});
}
vector<int> ans{pq.top().first};
for (int i = k; i < len; ++i) {
// 开始滑动窗口, 放入元素
pq.push({nums[i], i});
// 当最大元素已经不在窗口内, 持续将最大元素赶出队列
// [i-k+1, i] 是当前的窗口 索引搜索的边界是 idx < i - k + 1
while (pq.top().second < i - k + 1) {
pq.pop();
}
ans.push_back(pq.top().first);
}
return ans;
}
};
76.最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = “ADOBECODEBANC”, t = “ABC” 输出：”BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。
示例 2：输入：s = “a”, t = “a” 输出：”a” 解释：整个字符串 s 是最小覆盖子串。
示例 3: 输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
分析:
1.我们用滑动窗口处理这个最小覆盖子串的搜索问题, 初始化左右指针 left/right 都是起始位置, 对于判定子串是否覆盖, 我们先建立一个 unordered_map
2.因为我们需要记录下来最小的覆盖子串的字符串, 最简单的方法是记录下来满足条件的时候的位置, 以及是当前覆盖子串长度; 然后不断更新这个长度;
3.我们再理一下思路: 先对 t 字符扫描进 need 统计需要的情况; 左右指针从 0 处初始化, 右边指针持续向右扫, 如果存在在当前的字符里面, 满足在 need 中需要, 那么就对 window[rc] += 1, 然后再判断是否满足覆盖的条件, valid == need.size(), 如果满足那么就尝试更新长度, 并且判断左边界缩减, 左边界缩减的条件是什么? 左指针所在的字符是需要的字符中的, —valid, 且窗口中 —window[lc]
class Solution {
public:
string minWindow(string s, string t) {
int l = 0;
int r = 0;
unordered_map<char, int> need;
unordered_map<char, int> window;
for (auto c: t) {
++need[c];
}
int valid = 0; // valid 记录有多少个独立的字符是满足计数条件的
int len = s.size();
int ansStart = 0;
int ansLen = s.size() + 1; // 初始化默认按照最长长度 + 1来
while (r < len) {
char rc = s[r];
++r;
if (need.count(rc)) {
++window[rc];
if (window[rc] == need[rc]) {
++valid;
}
}
while (valid == need.size()) {
if (r - l < ansLen) {
ansStart = l;
ansLen = r - l;
}
char lc = s[l];
++l;
if (need.count(lc)) {
if (window[lc] == need[lc]) {
--valid;
}
--window[lc];
}
}
}
return ansLen == s.size() + 1 ? "" : s.substr(ansStart, ansLen);
}
};
普通数组
53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：输入：nums = [1] 输出：1
示例 3：输入：nums = [5,4,-1,7,8] 输出：23
分析:
因为数组是有正有负的, 这里定义的状态是, 以 nums[i] 为结尾的最大子数组和为dp[i], 那么dp [i] 怎么做选择
1.nums[i] 自成一派 dp[i] = nums[i]
2.nums[i] 和之前的数组 dp[i-1] 合并起来, 即 dp[i] = dp[i-1] + nums[i]
状态转移汇总: dp[i] = max(nums[i], dp[i-1] + nums[i])
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if (len <= 0) {
return 0;
}
vector<int> dp(len, INT_MIN);
dp[0] = nums[0];
int ans = dp[0];
for (int i = 1; i < len; ++i) {
// dp[i], 表示以 i 为结尾的最大连续子数组和
// 状态转移: 要么是和前面的加起来最大, 要么自成一派最大
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ans = max(dp[i], ans);
}
return ans;
}
};
56.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
分析:
1.对所有的区间的左端点先排序
2.新增一个 merged 空数组, 然后遍历排序后的数组, 逐个加入到数组里面, 怎么依次往里面 merge 呢?
(i). 如果当前区间 cur 的左边的端点比 merged 数组中最后一个区间的右端点还大, 那么我们直接放入到 merged 末尾
(ii). 如果当前区间 cur 的左边端点比 merged 数组最后一个 区间 的右端点小, 那么更新最后一个数组的右端点更新成 max(cur_右端点, last_右端点)
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int len = intervals.size();
vector<vector<int>> merged;
if (len <= 0) {
return merged;
}
auto cmp = [] (const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
};
sort(intervals.begin(), intervals.end(), cmp);
merged.push_back(intervals[0]);
for (int i = 1; i < len; ++i) {
int l = intervals[i][0];
int r = intervals[i][1];
int lastR = merged.back()[1];
// 如果当前区间的左端点 比 最后一个区间的右端点还大, 直接放到最后一个, 没有重合无需合并
if (l > lastR) {
merged.push_back({l, r});
// 否则将 cur区间 和最后一个区间合并
} else {
merged.back()[1] = max(merged.back()[1], r);
}
}
return merged;
}
};
189.轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]示例 2: 输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
分析:
1.向右旋转有个 k 个位置的效果有个先分步反转然后整体反转的等效作用方式, 把反转过程分解成分开2个部分反转结果的反转
2.理解过程如下:
数组是 ——->—> k = 3 (1)
翻转完成的效果是 —>——-> (2)
这个可以怎么从效果 (1) 到效果 (2) 呢? 我们可以分别将整个数组分成两个部分分别反转j
——-> 反转后得到 <——-
—> 反转后得到 <—
然后我们现在得到的是 <——-<— (3)
我们发现我们要的 (2) 和 现在得到的(3) 是个对称图形, 如果对 (3) 整体翻转一下, 就得到了我们要的 (2) 的效果
3.一开始额外判断一下 k 是否是 nums.size() 的倍数, 可以直接取模, 化简运算
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
if (len <= 0) {
return;
}
k %= len;
if (k == 0) {
return;
}
reverse(nums.begin(), nums.end() - k); // 反转 k 之前的
reverse(nums.end() - k, nums.end()); // 反转 k 之后的
reverse(nums.begin(), nums.end());
return;
}
};
238.除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1: 输入: nums = [1,2,3,4] 输出: [24,12,8,6]
示例 2: 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
分析:
1.我们不妨想一下出题人想考我们什么, 想要 [除自身以外数组的乘积] 可以直接全部乘起来然后除以 [自身], 但是这种直觉的想法有个问题是无法处理自身为 0 的问题, 所以提示了不要使用除法
2.思路上很类似于接雨水的思路, 我们首先构造一个左侧乘积数组, 对于某个元素 i 来说, lProduct[i] 是它严格左侧所有的乘积; 同理右侧侧乘积数组 rProduct[i] 是它严格右侧所有的乘积, 然后遍历取 lProduct[i] * rProduct[i]; 对于边界条件设定 lProduct[0] = 1 = rProduct[len - 1]
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> lProduct(len, 1); // 存储左侧所有元素乘积
vector<int> rProduct(len, 1); // 存储右侧所有元素乘积
vector<int> ans(len, 0);
for (int i = 1; i < len; ++i) {
lProduct[i] = lProduct[i-1] * nums[i-1];
}
for (int i = len - 2; i >= 0; --i) {
rProduct[i] = rProduct[i+1] * nums[i+1];
}
for (int i = 0; i < len; ++i) {
ans[i] = lProduct[i] * rProduct[i];
}
return ans;
}
};
41.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：输入：nums = [1,2,0] 输出：3
示例 2：输入：nums = [3,4,-1,1] 输出：2
示例 3：输入：nums = [7,8,9,11,12] 输出：1
分析:
1.题目要求 O(n) 时间 和 O(1) 空间; 如果没有限制这个我们估计怎么做, 遍历放哈希表, 然后从1开始枚举看哪个不存在在哈希表, 但是会引入到 O(n) 空间
2.这个题目需要引入一种原地哈希的思路, 在原始的数组中修改, 这样才能不引入额外的空间
3.对于一个长度为 N 的数组, 未出现的最小正数的范围在 [1, N+1], 如果 [1,N] 都出现了, 那么第一个没出现的正数就是 N+1; 否则就是在 [1, N] 中没有出现的最小正整数; 所以我们想对 [1, N] 范围的数放入哈希表
4.怎么把 [1, N] 范围的数放入哈希表, 但是有不建立新的哈希表呢? 放在原始的数组里面: 我们对数组进行遍历, 对于遍历到的数字 x, 如果它在 [1, N] 范围内, 那么就将 x - 1 这个[位置] 打上 [某种标记], 因此遍历结束之后, 如果所有 [位置] 都有标记, 那么缺失的就是 N+1 这个数字; 否则就是没有打上标记的的位置 + 1 这个数字就是第一个缺失的正数
5.举个例子, 数组长度是 5, 我们对于数字 1, 我们对 0 位置上打标记, 全打完所有标记之后, 没打上标记的位置就是 + 1, 就是缺失的数字: 比如我们发现, 我们在 2 位置没有标记, 那么就说明 3 这个数字缺失了
6.到此为止, 我们只需要设计某种标记的规则, 就能完成上面的操作; 对于负数, 这种不在我们考虑的范围内, 只需要排除它对我们后续的干扰就行, 这里一种设计方法是打一个较大的正数 N + 2, 这样数组里面的数字就都是正数了, 遍历数字的时候, 如果绝对值 超出 N 的一律不考虑
7.我们可以将 [标记] 的产生, 设置成 打了[负号] 的 [负数], 也称为 [负数标记]; 比如一个数字 3, 我们让它在 nums[2] 位置上的负数 -nums[2]
8.举个完整的例子:
3,4,-1, 1, 9,-5 第一步, n = 6 将负数替换成 n + 2 = 8
3,4, 8, 1, 9, 8 第二步, 做完上一步所有数字都是正数了, 对所有不大于 6 的数字, 标记为负数, 标记的方法是 nums[num - 1] = - 原始数字的绝对值
-3,4,-8,-1, 9, 8 第三步, 做完上一步已经标记好正数了, 如果现在还有正数就是缺失的那个数字, 缺失数字对应的是 i + 1
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
// 把负数都标记成 len + 2, 至少是标记为 len + 1
for (int& x: nums) {
if (x <= 0) {
x = len + 2;
}
}
for (int i = 0; i < len; ++i) {
int num = abs(nums[i]); // 先取出来绝对值, 用于下面判断这个数之前不是负数
// 对剩下的真正的正数 (之前的负数不需要再考虑), 也就是 num <= len 的数, 搞上 [负数标记]
if (num <= len) {
nums[num - 1] = -abs(nums[num - 1]); // 打上负数标记, 直接对这个数字取一个负数;
}
}
// 遍历已经打好标记的结果, 找第1个剩下的正数, 找到了, 那么就返回 i + 1
// 第一个大于 0 的数 index + 1 就是缺失正数
for (int i = 0; i < len; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
// 如果遍历完找不到, 那么第 1 个缺失的正数就是 len + 1
return len + 1;
}
};
矩阵
73.矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：输入：matrix = [
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：[
[1,0,1],
[0,0,0],
[1,0,1]
]示例 2：输入：matrix = [
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
分析:
1.如果扫描每个位置, 扫到 0 之后再去动所在的行和列, 每个位置和其他位置置为零的过程有较多重复操作
2.采用空间换时间的思想, 开一个数组标记哪一行哪一列是有 0 的, 全标记完再开始根据标记结果去设置 0
(i). 我们先扫描一遍矩阵, 并用引入两个额外的数组去标记, 这行和这列是否存在过 0
(ii). 然后再扫描一遍矩阵, 如果存在这行或者这列为 0 的情况, 那么全部标记为 0
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<bool> rowHasZeroFlag(m, false);
vector<bool> colHasZeroFlag(n, false);
for (int i = 0; i < m; ++i) {
for (int j = 0 ; j < n; ++j) {
if (matrix[i][j] == 0) {
rowHasZeroFlag[i] = true;
colHasZeroFlag[j] = true;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0 ; j < n; ++j) {
if (rowHasZeroFlag[i] || colHasZeroFlag[j]) {
matrix[i][j] = 0;
}
}
}
return;
}
};
54.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：输入：
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
] 输出：[1,2,3,6,9,8,7,4,5]示例 2：输入：
matrix = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
分析:
1.模拟旋转的过程, 维护上下左右四个终极边界, left, right, top, bottom, 然后在旋转过程中缩小边界, 直到边界发生某种重合; 向右和向下是必有的, 但是有时候向左和向上不是必须的, 因此需要一个判断; 判断可以回转的情况是两个边界不重合, 也就是 left < right && top < bottom
2.每次单项移动的时候, 都是卡着一个边界去移动
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if (matrix.size() == 0 || matrix[0].size() == 0) {
return ans;
}
int rowNum = matrix.size();
int colNum = matrix[0].size();
// left/right/top/bottom 模拟当前可执行螺旋的四个方向的边界
int left = 0;
int right = colNum - 1;
int top = 0;
int bottom = rowNum - 1;
while (left <= right && top <= bottom) {
for (int c = left; c <= right; ++c) {
ans.push_back(matrix[top][c]);
}
for (int r = top + 1; r <= bottom; ++r) {
ans.push_back(matrix[r][right]);
}
// 在需要缩小的情况下
if (left < right && top < bottom) {
// 先往左缩小
for (int c = right - 1; c > left; --c) {
ans.push_back(matrix[bottom][c]);
}
// 再向上缩小
for (int r = bottom; r > top; --r) {
ans.push_back(matrix[r][left]);
}
}
// 缩小一圈边界
++left;
--right;
++top;
--bottom;
}
return ans;
}
};
48.旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2： 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
分析:
1.图像是顺时针旋转了90度, 不太好直接看出来旋转后的对应关系, 可以尝试水平翻转, 垂直翻转，或者转置等操作的组合; 看一下翻转一步之后，距离目标状态还能怎么操作一下就能达到同样的效果
2.
[
[1,2,3],
[4,5,6],
[7,8,9]
]
先以中间一行为轴, 上下对称做个翻转
[
[7,8,9],
[4,5,6]
[1,2,3],
]
然后做一个转置
[
[7,4,1],
[8,5,2],
[9,6,3]
]
3.总结翻转的公式
水平线上下翻转: matrix[row][col] => matrix[n-row-1][col]
转置操作: matrix[row][col] => matrix[col][row]
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// 沿着水平线上下翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
swap(matrix[i][j], matrix[n - i - 1][j]);
}
}
// 矩阵转置操作
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
return;
}
};
240.搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。每列的元素从上到下升序排列
示例 1：输入：matrix = [
[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]
], target = 5 输出：true示例 2：输入：matrix = [
[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]
], target = 20 输出：false
分析:
1.二维矩阵搜索, 其实这个搜索也是有序的, 从上到下, 从左往右有序, 最小的永远在左上角, 最大的永远在右下角, 但是右上角和左下角哪个更大我们不知道
2.最基础的方法可以对逐行进行二分搜索, 每一行是 logn复杂度, 总时间复杂度 nlogn
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rowNum = matrix.size();
for (int row = 0; row < rowNum; ++row) {
if (binary_search(matrix[row].begin(), matrix[row].end(), target)) {
return true;
}
}
return false;
}
};
3.这个矩阵的特点我们得充分利用下, 因为右边总比左边大, 下边总比上边大, 我们可以先卡一个最大的子坐标, 另一个从 0 开始搜索, 比如从右上角 (0, n - 1) 元素开始搜索, 如果当前搜索元素比目标元素小, 那么就往下搜索, 纵坐标不动; 如果当前搜索元素比目标元素大, 那么就缩小右边界
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rowNum = matrix.size();
int colNum = matrix[0].size();
int x = 0;
int y = colNum - 1;
while (x < rowNum && y >= 0) {
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] < target) {
++x;
} else if (matrix[x][y] > target) {
--y;
}
}
return false;
}
};
链表
160.相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
分析:
1.这个题如果看了答案只能感觉很巧妙, 但是不看答案又想不出来这个巧妙的答案, 先用比较基础的方法: 用一个 hashset 保存 headA 下的所有节点, 然后和另一个链表逐个对比就能找到公共节点, 但是需要额外的空间
2.需要充分利用”相交”这个信息, 一种解决的方式是, 将两条链表按照前后两种不同的顺序拼接在一起, 例如如下的两条链表公共节点是c1
a1->a2->c1->c2
b1->b2->b3->c1->c2
拼接之后得到两条长度相同的链表
a1->a2->c1->c2->b1->b2->b3->c1->c2
b1->b2->b3->c1->c2->a1->a2->c1->c2
这样我们同时遍历这两个链表, 找到的第一个相同的节点就是 c1 就是链表交点
3.在实际遍历的时候, 可以想象这两个链表已经被拼接起来, 但不实际地去开辟额外空间, 只在原来的两条链表上面走
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* pa = headA;
ListNode* pb = headB;
while (pa != pb) {
if (pa) {
pa = pa -> next;
} else {
// 将pa链接在b的开头
pa = headB;
}
if (pb) {
pb = pb -> next;
} else {
// 将pb链接在b的开头
pb = headA;
}
}
return pa;
}
};
206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：输入：head = [1,2] 输出：[2,1]
示例 3：输入：head = [] 输出：[]
分析:
1.迭代:
反转的核心操作, 是要把当前的节点指向它前一个节点, 但是我们得迭代, 所以需要先记下来它前一个是谁和后一个是谁, 然后执行迭代操作更新, 因此就是用三个指针 pre, cur, next 这3个就能完成
原始状态 1 -> 2 -> 3 -> nullptr
目标状态 nullptr <- 1 <- 2 <- 3, 假设我们要操作 2 这个节点的反转 1 -> 2 -> 3 得到 1 <- 2 -> 3, 关键操作是将当前的节点反向指向它的前一个节点, 也就是cur -> next = pre, 同时为了能迭代我们首先要记下来下一个节点, 然后再实施关键翻转操作
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* next = nullptr;
while (cur != nullptr) {
next = cur->next; // 先记下来它下一个是谁, 不然反转完当前之后, 没法走到下一个反转流程
cur->next = pre; // 执行核心的反转操作
pre = cur; // 执行迭代
cur = next; // 执行迭代
}
return pre;
}
};
2.递归操作
想一下假设只有一个节点需要反转, 后面的都已经反转好了, 就差一步大功告成, 应该怎么反转?
1 -> [2 -> 3 -> 4 -> nullptr]
1 -> [nullptr <- 2 <- 3 <- 4] 此时 newHead 指向4 让 1->next->next 指向1
1 <- [2 <- 3 <- 4] 得到左边的结果, 但还差一步 1->next = nullptr
nullptr <- 1 <- [2 <- 3 <- 4]
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
234.回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：输入：head = [1,2,2,1] 输出：true
示例 2：输入：head = [1,2] 输出：false
分析:
1.找到链表的中点, 然后反转后半部分, 用半部分和后半部分遍历, 先准备个反转链表和找到中点的操作, 反转链表写递归的更快, 找到中点用快慢指针一次遍历
class Solution {
public:
ListNode* reverse(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverse(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
ListNode* findMidNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* mid = findMidNode(head);
ListNode* p1 = head;
ListNode* p2 = reverse(mid);
while (p1 != nullptr & p2 != nullptr) {
if (p1->val != p2->val) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}
};
141.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
分析:
1.快慢指针, 相遇就有环, 否则没环
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
142.环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。示例 1：输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
分析:
1.需要分析下相遇点有什么特点, 我们仍然采用快慢指针的方式来看, 起点快慢指针都指向非空的 head, 假设 slow 走了 k 步之后, fast 和 slow 相遇了, slow 走 k 步, 那么 fast 走 2k 步; fast 比 slow 多走出的 k 步是在环里面转圈, 所以这个相遇时候慢指针走过的 k 步的 k 的值正好就是环长度的 [整数倍]
2.假设 [相遇点] 距离 [环起点] 为 m , 原始头节点距离 [环起点] 为 k - m , fast 如果继续往前走 k - m 步到达环的起点, 但是我们不知道这个 m 是多少; 这里我们知道, 相遇之后原始头结点距离 [环起点] 距离 == [相遇点] 距离 [环起点] 继续走距离都是 k - m; 所以我们让快慢指针第一次相遇的时候, 让快慢指针的任意一个重新指向 head, 比如 slow 重新指向 head, 然后 slow 和 fast 指针同速前进 (每次走1步), (经过 k - m 步) 然后它俩一定相遇, 相遇的地方就是环的起点
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
// 假设 [相遇点] 距离 [环起点] 为 m , 原始头节点距离 [环起点] 为 k - m , fast 如果继续往前走 k - m 步到达环的起点, 我们不知道这个 m 是多少;
// 相遇之后原始头结点距离 [环起点] 距离 == [相遇点] 距离 [环起点] 继续走距离都是 k - m;
// 我们让快慢指针第一次相遇的时候, 让快慢指针的任意一个重新指向 head, 比如 slow 重新指向 head, 然后 slow 和 fast 指针同速前进 (每次走1步), (经过 k - m 步) 然后他俩一定相遇, 相遇的地方就是环的起点;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
21.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：输入：l1 = [], l2 = [] 输出：[]
示例 3：输入：l1 = [], l2 = [0] 输出：[0]
分析:
1.合并有序链表的操作关键操作是分别用两个指针维护当前列表 list1/list2 的指针 p1 和 p2, 然后再用一个指针维护合并的指针, 这个合并指针好像一个针线头一样, 把两条线穿起来
2.先处理 p1 和 p2 同时非空的场景, 然后再处理剩下的唯一的链表有剩余的场景
3.为了方便处理有链表为空的情况, 额外设置一个 dummy 节点, 返回 dummy->next
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 && p2) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
if (p1) {
cur->next = p1;
}
if (p2) {
cur->next = p2;
}
return dummy->next;
}
};
2.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例 1：输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
分析:
1.纯模拟实现, 注意各种进位的判断, 可以先处理两个链表同时有节点的情况, 再单独处理一个链表有节点的情况, 然后再处理最后的一个进位的情况
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = l1;
ListNode* p2 = l2;
int sum = 0;
int data = 0;
int carry = 0;
while (p1 && p2) {
sum = p1->val + p2->val + carry;
data = sum % 10;
carry = sum / 10;
ListNode* tmp = new ListNode(data);
cur->next = tmp;
p1 = p1->next;
p2 = p2->next;
cur = cur->next;
}
ListNode* p = (p1) ? p1 : p2;
while (p) {
sum = p->val + carry;
data = sum % 10;
carry = sum / 10;
p->val = data;
cur->next = p;
cur = cur->next;
p = p->next;
}
if (carry > 0) {
ListNode* finalNode = new ListNode(carry);
cur->next = finalNode;
cur = cur->next;
}
return dummy->next;
}
};
19.删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：输入：head = [1], n = 1 输出：[]
示例 3：输入：head = [1,2], n = 1 输出：[1]
分析:
1.如果要删除倒数第 N 个节点, 也就是删除正数 nums-N+1 个节点, 为了删除 nums-N+1 的节点, 我们需要指针指向删除目标节点的前一个节点, 即正数 nums-N 个节点, 也就是倒数 N+1 个节点
2.一种方法是遍历一遍找到 N 等于几, 然后再遍历一遍执行删除操作
3.更方便的一种方式是先让 fast 先正好走到我们想要 slow 停下来的节点, 也就是待删除的节点的前一个节点, 然后再快慢同速度一起走, 直到 fast 为空, 这时候 slow 停下来的节点就是正数 nums-N 个节点; 其实我们脑洞开一点, 就好比等价于有另一个指针 (fast) 先执行倒着走一样, 它能先帮我们找到那个前一个节点
4.假设 [1,2,3,4,5], n=2, 为了防止空指针出现, 比如 5 个节点删除倒数第 5 个, 要用 dummy 去避免空指针; fast 指针可以从 head 开始, 然后 slow 指针多走一步从 dummy 开始, 这样就能直接达到走到待删除节点的下一个节点的效果; 增加 dummy 得到 [d,1,2,3,4,5], 所以, fast 从 1 出发走 2 步到 3, 然后走 3 步到空指针, slow 从 dummy 出发走 3 步到 3, 也就是 4 的前1个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1, head);
// 举例 [d,1,2,3,4,5], n=2, fast 停在3, slow 最终停在3
ListNode* slow = dummy; // slow 从 dummy 出发, 能够多走一步, 保证 slow 最终停在待删除节点前面
ListNode* fast = head; // fast 从 head 出发
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：输入：head = [] 输出：[]
示例 3：输入：head = [1] 输出：[1]
分析:
1.这个题意是想让我们按照每两个一组交换节点, 需要画图在纸上才能看清楚指针的变动顺序;
2.先设置一个 dummy, dummy->next = head:
3.我们尝试反转第一组, 因为需要一个前置节点才能开始连接, 因此声明一个 pre, 一开始pre = dummy;
先取出来 node1 和 node2
pre->next = node2;
node1->next = node2->next;
node2->next = node1;
pre = node1;
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1, head);
ListNode* pre = dummy;
while (pre->next != nullptr && pre->next->next != nullptr) {
ListNode* node1 = pre->next;
ListNode* node2 = pre->next->next;
pre->next = node2;
node1->next = node2->next;
node2->next = node1;
pre = node1;
}
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
25.K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。示例 1：输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
分析:
1.如果我们对链表内任意一个区间 [left, right] 可以实施反转, 我们只需要对所有的区间实施相同的反转; 如何对链表内任意一个区间实施反转 ? 采用 [区间内头插法反转]
// 移动 pre 到指向区间前一个节点
for (int i = 0; i < left - 1; ++i) {
pre = pre->next;
}
ListNode* cur = pre->next; // cur 节点是反转区域第1个节点, 也是反转区域最后一个节点, 始终不动
ListNode* next; // next 是要执行头插的节点, 每次移动到反转区域的第1个元素, 并一直迭代
for (int i = 0; i < right - left; ++i) {
next = cur->next; // 找到头插节点
cur->next = next->next; // 隔过去待头插入的节点
next->next = pre->next; // 执行头插: 插入头节点到区间第1个节点
pre->next = next; // 链接 pre -> 头插元素
}
2.应用 [区间内头插法反转] 的操作可以对任意区间进行反转, 我们只需要对多个区间采取相同的操作; 每个[区间内头插法反转] 操作完成之后, 我们将 pre 和 cur 顺序往下移动一个区间, 再下一个区间进行 [区间内头插法]
3.先求出来区间的总长度; 然后一个区间一个区间地做 [区间内头插法反转]
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* dummy = new ListNode(-1, head);
ListNode* t = head;
int len = 0;
// 先求出来链表的长度
while (t) {
++len;
t = t->next;
}
ListNode* pre = dummy;
ListNode* cur = pre->next;
ListNode* next;
while (len >= k) {
// 执行区间内头插法反转
for (int i = 1; i < k; ++i) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = cur; // 下一个 pre 指向 cur 也就是区间内的最后1个元素
cur = pre->next; // cur 进入到新区间的第1个元素
len -= k;
}
return dummy->next;
}
};
138.随机链表的复制
给你一个长度为 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 作为传入参数。示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2： 输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3： 输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
分析:
1.如果没有随机指针, 我们遍历复制就行, 因为有随机指针的存在, 当我们想复制某个节点的时候, 它的随机指针指向的那个节点可能还没创建, 因此不太好复制
2.这里有个非常巧妙的办法, 先复制在拆分, 对于链表 a->b->c, 我们可以在每个元素之后先建一个a->a’->b->b’->c->c’, 然后我们对所有a’和b’和c’找到随机指针指向的节点是它原来节点的随机指针指向的节点对应的后继节点, 然后重新遍历一遍, 按照 [原来节点] 和 [复制节点] 拆分出来; 因为随机指针可以指向空值, 给复制节点找随机指针指向的结点的时候, 需要判断一下能否指向一个节点
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
Node* p = head;
// 先复制串联镜像节点 a->a'->b->b'->c->c
while (p != nullptr) {
Node* node = new Node(p->val);
node->next = p->next;
p->next = node;
p = node->next;
}
p = head;
Node* cp = nullptr;
// 给复制节点们找到对应的随机指针的正确指向
while (p != nullptr) {
cp = p->next;
if (p->random != nullptr) {
cp->random = p->random->next;
}
p = cp->next;
}
p = head;
cp = head->next;
Node* newHead = cp;
// p 和 cp 各自串自己的糖葫芦
while (cp->next != nullptr) {
p->next = cp->next;
p = p->next;
cp->next = p->next;
cp = cp->next;
}
p->next = nullptr;
return newHead;
}
};
148.排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：输入：head = [] 输出：[]
分析:
1.采用分治 (归并) 的方法, 每次先找到链表的中点, 强行断开, 然后执行归并排序
2.每次找中点的时候, 用快慢指针找中点, 注意这里的中点是偏小的那一个, 也就是 slow 前面的 pre 指针, 这样比较适合前后断开的操作
3.合并的时候, 执行的是两个有序链表的合并操作
4.归并排序的思路 + 快慢指针找中点 + 有序链表合并之后可以完成该操作
class Solution {
public:
ListNode* findMidNode(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre;
while (fast != nullptr && fast->next != nullptr) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
return pre;
}
ListNode* mergeSortedList(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
cur->next = (p1 != nullptr) ? p1 : p2;
ListNode* ret = dummy->next;
delete dummy;
return ret;
}
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p1 = head;
ListNode* mid = findMidNode(head);
ListNode* p2 = mid->next;
mid->next = nullptr;
p1 = sortList(p1);
p2 = sortList(p2);
ListNode* ans = mergeSortedList(p1, p2);
return ans;
}
};
23.合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6示例 2：输入：lists = [] 输出：[]
示例 3：输入：lists = [[]] 输出：[]
分析:
1.如果是合并 2 个升序链表, 我们可以维护两个指针去比较, 如果是 k 个链表, 则不太好比较
2.如果想维护 k 个链表里面的最小值, 那么需要引入一个小顶堆去找到最小节点, 来多少个链表我们都不管, 我们每次都取最小的那个节点: 每次取出来最小的那个节点, 然后链接到生成的链表的末尾, 看下后续还有无其他的节点, 有的话放入队列一起比较, 直到最后队列元素为空
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [] (ListNode* p1, ListNode* p2) {
return p2->val < p1->val;
};
// 采用一个按照值排序的有限队列
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
for (auto head: lists) {
if (head != nullptr) {
pq.push(head);
}
}
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (!pq.empty()) {
cur->next = pq.top();
pq.pop();
cur = cur->next;
if (cur->next != nullptr) {
pq.push(cur->next);
}
}
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
146.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) 的平均时间复杂度运行。示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
分析:
1.我们回忆一下 LRU cache 要实现什么, 首先考虑是构造一个队列, 用于模拟的访问 cache 的时间顺序关系; 另外, 因为要 O(1) 实现查找, 所以需要一个哈希表指向节点; 因为还要 O(1) 的复杂度实现插入和删除, 就需要搞一个双端链表去模拟加入的时序关系; 构造一个双端链表的中间结构
struct DLinkedListNode {
int key;
int value;
DLinkedListNode* pre;
DLinkedListNode* next;
DLinkedListNode(): key(0), value(0) {}
DLinkedListNode(int _key, int _value): key(_key), value(_value), pre(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int size;
int totalCapacity;
DLinkedListNode* dummyHead;
DLinkedListNode* dummyTail;
unordered_map<int, DLinkedListNode*> key2node;
public:
LRUCache(int capacity) {
size = 0;
totalCapacity = capacity;
dummyHead = new DLinkedListNode();
dummyTail = new DLinkedListNode();
dummyHead->next = dummyTail;
dummyTail->pre = dummyHead;
}
// 如果待查询 key 不存在, 是个无效的查询, 直接返回 -1
// 如果存在, 移动 key 所在的 node 到开头
int get(int key) {
if (!key2node.count(key)) {
return -1;
}
DLinkedListNode* node = key2node[key];
moveNodeToHead(node);
return node->value;
}
// 如果待添加的 key 不存在, 加入哈希表
// 如果已经存在了, 移动在链表头, 重写 value
void put(int key, int value) {
if (!key2node.count(key)) {
DLinkedListNode* node = new DLinkedListNode(key, value);
key2node[key] = node;
addNodeToHead(node);
++size;
if (size > totalCapacity) {
// 返回待删除的节点的指针
DLinkedListNode* node = removeNodeTailNode();
key2node.erase(node->key);
delete node;
--size;
}
} else {
DLinkedListNode* node = key2node[key];
node->value = value;
moveNodeToHead(node);
}
}
void moveNodeToHead(DLinkedListNode* node) {
removeNode(node);
addNodeToHead(node);
}
// 双端操作: 先把 node 向 前后节点建立联系, 然后前后节点和 node 向 前后节点建立联系
void addNodeToHead(DLinkedListNode* node) {
node->pre = dummyHead;
node->next = dummyHead->next;
dummyHead->next->pre = node;
dummyHead->next = node;
}
void removeNode(DLinkedListNode* node) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
DLinkedListNode* removeNodeTailNode() {
DLinkedListNode* node = dummyTail->pre;
removeNode(node);
return node;
}
};
二叉树
94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
分析:
1.递归方法比较简单, 这里用迭代方法
2.迭代方法的本质是需要记录下来 [上一个访问的根节点], 因为二叉树这个结构只有向下遍历操作没法直接往回回溯, 所以需要引入栈去记录下来最近一次上一个根节点是哪个节点
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> preRoot;
while (root != nullptr || !preRoot.empty()) {
while (root != nullptr) {
preRoot.push(root);
root = root->left;
}
root = preRoot.top();
preRoot.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};
104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：输入：root = [1,null,2] 输出：2
3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
分析:
1.采用分解问题的思维, 当前 root 节点最大深度, 等于它的左子树最大深度和右子树最大深度之间的最大值 + 1, 因此可以写出递归代码
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int lMaxDepth = maxDepth(root->left);
int rMaxDepth = maxDepth(root->right);
return max(lMaxDepth, rMaxDepth) + 1;
}
};
226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：输入：root = [2,1,3] 输出：[2,3,1]
示例 3：输入：root = [] 输出：[]
分析:
1.采用分解问题的思维, 原问题翻转之后的效果等于左子树翻转完, 右子树翻转完之后再左右翻转
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return root;
}
TreeNode* lInverted = invertTree(root->left);
TreeNode* rInverted = invertTree(root->right);
root->left = rInverted;
root->right = lInverted;
return root;
}
};
101.对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：输入：root = [1,2,2,null,3,null,3] 输出：false
分析:
1.采用分解的思维: 对于原问题来说, 给定一个根节点, 需要判定左子树和右子树是对称的, 怎么判定左子树和右子树是对称的
2.要想判定左子树和右子树对称性, 需要生成两个指针来同时遍历, 一个向左一个向右, 然后1生2, 2生4, 4生成8…
class Solution {
public:
// p 和 q 是两个同时遍历具有对称性的指针
bool check(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p == nullptr || q == nullptr) {
return false;
}
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
543.二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。1 / \ 2 3 / \ 4 5示例 1：输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：输入：root = [1,2] 输出：1
分析:
1.具体到一个根节点, 它所在的直径等于最大深度等于什么?
2.如果能想到对于一个根节点, 它的直径等于 [左子树数的最大深度] 和 [右子树的最大深度] 之和
3.我们写一个最大深度的函数, 然后不断更新这个最大深度
4.一个二叉树的的最大深度是怎么来的 ? 是另一个可以用分解的思维去思考的问题, 对于一个根节点来说, 它的最大深度等于 max(左子树的最大深度, 右子树的最大深度) + 1
class Solution {
private:
int ans = 0;
public:
// 写一个求最大深度的函数
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int lMaxDepth = maxDepth(root->left);
int rMaxDepth = maxDepth(root->right);
// 对于一个根节点而言, 它的直径等于 [左子树数的最大深度] 和 [右子树的最大深度] 之和;
int diameter = lMaxDepth + rMaxDepth;
ans = max(ans, diameter);
// 对于一个根节点而言, 最大深度等于 max(lMaxDepth, rMaxDepth) + 1;
return max(lMaxDepth, rMaxDepth) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
maxDepth(root);
return ans;
}
};
102.二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
3 / \ 9 20 / \ 15 7示例 2：输入：root = [1] 输出：[[1]]
示例 3：输入：root = [] 输出：[]
分析:
1.层序遍历用队列模拟
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> ans;
if (root == nullptr) {
return ans;
}
q.push(root);
while (!q.empty()) {
int len = q.size();
vector<int> levelVec;
while (len > 0) {
TreeNode* node = q.front();
int val = node->val;
q.pop();
levelVec.push_back(val);
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
--len;
}
ans.push_back(levelVec);
}
return ans;
}
};
108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。示例 1：输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
分析:
1.BST 的中序遍历正好是有序序列, 给定中序遍历, 能否唯一确定一个二叉搜索树? 不能, 在没限制平衡的设定下, 任何一个数字都可以作为二叉搜索树的根节点
2.如果我们要求二叉搜索树平衡, 是否可以确定唯一一个二叉搜索树? 也不能. 举个反例是一个节点下面各两个子树, 但是每个子树下面2个唯一分支节点, 左孩子或者右孩子各种换位置都可以满足需求
3.那怎么能能确定根节点, 然后保证构造出来的一定是平衡的呢? 如果数组长度是奇数, 那么中间的节点是唯一可行的根节点, 如果偶数, 那么中间位置左边或者右边都能做根节点
4.中间位置是 int mid = l + (r - l) / 2
class Solution {
public:
TreeNode* construct(vector<int>& nums, int l, int r) {
if (l > r) {
return nullptr;
}
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = construct(nums, l, mid - 1);
root->right = construct(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return construct(nums, 0, nums.size()-1);
}
};
98.验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。示例 1：输入：root = [2,1,3] 输出：true
示例 2：输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
分析:
1.BST 的中序遍历是完全有序的, 我们利用这个性质, 中序迭代遍历二叉树, 然后发现前一个元素和后一个元素是违反有序关系的, 那么一定非BST;
2.迭代中序遍历, 并额外维护一个 preNode 指针, 遍历过程中每次比较 preNode 和 cur 的关系是不满足 < 情况判定非BST
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* preNode = nullptr;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (preNode != nullptr && preNode->val >= root->val) {
return false;
}
preNode = root;
root = root->right;
}
return true;
}
};
230.二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root， 和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
分析:
1.BST中序遍历正好是有序的, 因此采用中序遍历, 找到遍历数 == k 的时候, 返回, 先用递归版本
class Solution {
private:
int ans = 0;
int rank = 0;
public:
void traverse(TreeNode* root, int k) {
if (root == nullptr) {
return;
}
// 前序位置
traverse(root->left, k);
// 搜到中序位置
++rank;
if (k == rank) {
ans = root->val;
return;
}
// 后序位置
traverse(root->right, k);
}
int kthSmallest(TreeNode* root, int k) {
traverse(root, k);
return ans;
}
};
同时顺便写一下迭代版本的中序遍历搜索
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
--k;
if (k == 0) {
return root->val;
}
root = root->right;
}
return 0;
}
};
2.假如我们频繁地查找第 k 小的值, 有没有优化方法? 我们每次采用重新中序遍历的一个前提是不知道每个根节点的子树的节点总数, 假设我们已经知道了每个根节点的左子树的以某个节点的子树节点总数为 nodeNum, 可以先用左子树的节点数和我们要找的 k 进行比较, 判定是否在左子树里面, 或者在右子树里面, 还是直接就是当前根节点就是第 k 小的树
3.令 node 为当前根节点开始搜索, 也就是说一开始指针指向 root,
如果 node 的左子树的节点数 leftNodeNum < k-1, 那么第 k 小的元素在 node 的右子树中, 指针搜向右边的子树 node=node->right, 搜索的空间可以直接减去 (leftNodeNums + 1), 然后继续搜索
如果 node 的左子树的节点数 leftNodeNum == k-1, 那么第 k 小的元素就是 node 直接返回 node
如果 node 的左子树的节点数 leftNodeNum > k-1, 那么第 k 小的元素在node的左子树里面, 指针走向左子树里面搜索 node=node->left, 继续搜索
3.为实现上述的逻辑, 先将每个根节点数保存在哈希表中
class Solution {
public:
unordered_map<TreeNode*, int> nodeNum;
// 记录以 node 为根节点的树的节点总数
int countNodesNum(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int num = 1 + countNodesNum(root->left) + countNodesNum(root->right);
nodeNum[root] = num;
return num;
}
int kthSmallest(TreeNode* root, int k) {
if (root == nullptr) {
return 0;
}
countNodesNum(root);
while (root != nullptr) {
int leftNodeNum = nodeNum[root->left];
if (leftNodeNum < k - 1) {
root = root->right;
k -= leftNodeNum + 1;
} else if (leftNodeNum == k - 1) {
return root->val;
} else if (leftNodeNum > k - 1) {
root = root->left;
}
}
return root->val;
}
};
199.二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2: 输入: [1,null,3] 输出: [1,3]
示例 3: 输入: [] 输出: []
分析:
1.层序遍历
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
queue<TreeNode*> q;
if (root == nullptr) {
return ans;
}
q.push(root);
while (!q.empty()) {
int qlen = q.size();
while (qlen > 0) {
root = q.front();
q.pop();
if (root->left != nullptr) {
q.push(root->left);
}
if (root->right != nullptr) {
q.push(root->right);
}
if (qlen == 1) {
ans.push_back(root->val);
}
--qlen;
}
}
return ans;
}
};
114.二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1：输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [0] 输出：[0]
1 1 1
/ \ / \ \
2 5 2 5 2
/ \ \ \ \ \
3 4 6 3 6 3
\ \
4 4
\
5
\
6
分析:
1.先理解一下二叉树转换为链表是什么意思 ? 链表本质上就是只有一个子树的二叉树, 二叉树就是链表的第一个节点多开出来一条链表的链表
2.可以用递归/非递归先序遍历, 遍历过程中把元素存储到数组里面, 然后再遍历这个数组构建一个二叉树
class Solution {
private:
vector<TreeNode*> list;
public:
// 先序转数组
void preorderTraverse(TreeNode* root) {
if (root == nullptr) {
return;
}
list.push_back(root);
preorderTraverse(root->left);
preorderTraverse(root->right);
return;
}
void flatten(TreeNode* root) {
preorderTraverse(root);
int len = list.size();
// 迭代构建树: 左孩子置空指针, 右孩子链接起来
for (int i = 1; i < len; ++i) {
TreeNode* pre = list[i-1];
TreeNode* cur = list[i];
pre->left = nullptr;
pre->right = cur;
}
return;
}
};
2.思考能否用分解的思路递归实现, 那么就要看看怎么去实现 flatten 这种操作, 也就是找 flatten 子树和当前根节点的关系
3.如下所示 一个flatten操作可以分解为 3 步, 先把左右子树分别做 flatten, 然后将右子树接在左子树的最下面, 然后把左子树换到右子树
1 1 1
/ \ / \ \
2 5 2 5 2
/ \ \ \ \ \
3 4 6 3 6 3
\ \
4 4
\
5
\
6
将三步都写出来, 得到完整答案
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr) {
return;
}
flatten(root->left);
flatten(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
root->right = left;
TreeNode* p = root;
while (p ->right != nullptr) {
p = p->right;
}
p->right = right;
return;
}
};
105.从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1: 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2: 输入: preorder = [-1], inorder = [-1] 输出: [-1]
分析:
1.先拿一个例子看,
1
/ \
2 3
/ \ / \
5 4 8 9
/ \
6 7
preorder
1,[2,5,4,6,7],[3,8,9]
inorder
[5,2,6,4,7],1,[8,3,9]
根节点把 inorder 可以划分成两半, 然后继续递归建立树, 每次建立树在先序数组里面维护起点和终点, 在中序里面也要维护起点和终点; 所以思路是先找根节点 => 左右子树递归建树, 建树的过程需要算各种长度, 我们先写个代码框架:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLow, int preHigh, int inLow, int inHigh) {
if (preLow > preHigh) {
return nullptr;
}
// 找到先序的第一个就是根节点
int rootVal = preorder[preLow];
int rootInorderIdx;
for (int i = inLow; i <= inHigh; ++i) {
if (inorder[i] == rootVal) {
rootInorderIdx = i;
break;
}
}
TreeNode* root = newTreeNode(rootVal);
root->left = build(preorder, inorder, ?, ?, ?, ?);
root->right = build(preorder, inorder, ?, ?, ?, ?);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, preorder.size()-1, inorder.size()-1)
}
现在需要明确上面递归构建子树的时候 index 填什么, 如果能填对相应的 4 个index, 那么就完成了; 我们发现在中序序列里面是比较好填的, 无非就是左侧给到左子树, 右侧给到右子树
TreeNode* root = newTreeNode(rootval);
root->left = build(preorder, inorder, ?, ?, inlow, rootInorderIdx-1);
root->right = build(preorder, inorder, ?, ?, rootInorderIdx+1, inHigh);
那么先序的左边起止点怎么填?
先序左边的起点是 preLow+1, 先序的终点呢? 其实是要找到先序左侧对应的 size 有多大, 然后 preLow + leftSize
先序右边的终点是 preHigh, 先序的起点呢? 顺着上面的结论, 其实就是左侧那个区间的后一个节点, 可以得到preLow + leftSize + 1
leftSize = rootInorderIdx - inLow
把这些起止点都梳理清楚后, 然后就能递归的建树了
int leftSize = rootInorderIdx - inLow;
root->left = build(preorder, inorder, preLow+1, preLow+leftSize, inlow, rootInorderIdx-1);
root->right = build(preorder, inorder, preLow+leftSize+1, preHigh, rootInorderIdx+1, inHigh);
完整代码如下
class Solution {
private:
unordered_map<int, int> inorderValue2indx;
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int prel, int preh, int inl, int inh) {
if (prel > preh) {
return nullptr;
}
// 找到根节点
int rootVal = preorder[prel];
int rootInorderIdx = inorderValue2indx[rootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootInorderIdx - inl;
root->left = build(preorder, inorder, prel + 1, prel + leftSize, inl, rootInorderIdx - 1);
root->right = build(preorder, inorder, prel + leftSize + 1, preh, rootInorderIdx + 1, inh);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
inorderValue2indx[inorder[i]] = i;
}
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size()-1);
}
};
这里有个优化点, 因为数组中不存在重复元素, 那么可以提前把中序遍历的根节点对应的index 提前保存在 hash 表中, 找 index 的时间复杂度降低为 O(1)
class Solution {
private:
// 记录下来中序遍历中每个值对应的index
unordered_map<int, int> inorderValue2indx;
public:
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int prel, int preh, int inl, int inh) {
if (prel > preh) {
return nullptr;
}
// 找到根节点
int rootVal = preorder[prel];
int rootInorderIdx = inorderValue2indx[rootVal];
TreeNode* root = new TreeNode(rootVal);
int leftSize = rootInorderIdx - inl;
root->left = build(preorder, inorder, prel + 1, prel + leftSize, inl, rootInorderIdx - 1);
root->right = build(preorder, inorder, prel + leftSize + 1, preh, rootInorderIdx + 1, inh);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); ++i) {
inorderValue2indx[inorder[i]] = i;
}
return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size()-1);
}
};
437.路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）
示例 1：输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
分析:
1.这个题中提到的路径不需要从根节点开始, 而是累计以根节点为根节点包含下的所有 (经过或者不经过根节点) 的路径. 因此用分解问题的思维, 以根节点为根节点的所有路径总和, 等于左子树包含的路径总和 + 右子树包含的路径总和 + 以根节点为必经节点下的路径总和; 写成代码就是 pathSum(root->left) + pathSum(root->right) + rootViaSum(root), 其中 rootViaSum(root) 以根节点为必经节点下的路径总和
2.所以我们思考如何计算 rootViaSum(root) , 也就是以某个具体的根节点为根节点, 然后必须经过这个根节点的路径总和; 这里又要采用另一个分解思维: 当前的这个求和为 targetSum 的话, 可以有 3 种方式, 一种是一开始根节点就能满足路径总和, 另外两种是根节点和下面左子树凑出来路径总和, 以及根节点和右子树凑出来路径总和
class Solution {
public:
// rootViaSum 计算必须经过这个根节点的路径总和
int rootViaSum(TreeNode* root, long long targetSum) {
if (root == nullptr) {
return 0;
}
// 计算必须经过这个根节点的路径总和 = 可能的根节点值等于 target的情况=1/否则0 + 根节点和下面左子树凑出来路径总和 + 根节点和下面右子树凑出来的路径总和
return ((root->val == targetSum) ? 1 : 0) + rootViaSum(root->left, targetSum - root->val) + rootViaSum(root->right, targetSum - root->val);
}
int pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return 0;
}
// 以根节点为根节点的所有路径总和 = 左子树包含的路径总和 + 右子树包含的路径总和 + 以根节点为必经节点下的路径总和
return rootViaSum(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
};
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 .
3 / \ 5 1 / \ / \ 6 2 0 3 / \ 7 4示例 2：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：输入：root = [1,2], p = 1, q = 2 输出：1
分析:
1.给定一个根节点, 然后给定树里面任意两个节点, 让我们找这两个任意节点的最低公共祖先
2.先可以判定一些非常简单的情况, 假设 p 和 q 之间本身有一个祖先关系, 也就是说 root == p || root = q 那么就说明这时候的 root 就是最近公共祖先
3.然后我们处理一些相对复杂的情况, 根节点在上面, 然后 p 和 q 在根节点的下面分布着, 下一步怎么搜索呢 ? 根节点的搜索指针可以向下移动, 可以从根节点左子树搜索 p 和 q, 也可以从根节点的右子树搜索 p 和 q; 这里有 3 种可能的情况,
(i). p 和 q 都在左子树, 那么我们就在 左子树里面递归找最低公共祖先
(ii). p 和 q 都在右子树, 那么我们就在 右子树里面递归找最低公共祖先
(iii). p 和 q 左右子树各一个, 最低公共祖先就是 root
class Solution {
public:
bool nodeInSubTree(TreeNode* root, TreeNode* c) {
if (root == nullptr) {
return false;
}
if (root == c) {
return true;
}
return nodeInSubTree(root->left, c) || nodeInSubTree(root->left, c);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
if (nodeInSubTree(root->left, p) && nodeInSubTree(root->right, q)) {
return lowestCommonAncestor(root->left, p, q);
}
if (nodeInSubTree(root->right, p) && nodeInSubTree(root->right, q)) {
return lowestCommonAncestor(root->right, p, q);
}
return root
}
};
4.我们再想一下, 既然总共就 以上 3 种情况, 这里我们也不用非要判断 p 和 q 具体要在哪个子树里面: 情况还是如上三种, 我们逐次判断 2 种情况的存在性就可以
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
TreeNode* lRes = lowestCommonAncestor(root->left, p, q);
TreeNode* rRes = lowestCommonAncestor(root->right, p, q);
if (lRes != nullptr && rRes != nullptr) {
return root;
} else if (lRes == nullptr) {
return rRes;
} else {
return lRes;
}
}
};
124.二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
-10
/ \
9 20
/ \ / \
-2 15 7
分析:
1.因为最大路径和可以不包含根节点, 所以我们要遍历出来以每个根节点为根节点的二叉树的最大路径和, 然后迭代出来最大的, 所以我们分析下以某个根节点为根节点的二叉树的最大路径和怎么来的?
2.以当前根节点为根节点的二叉树的最大路径和 = 根节点的值 + 左子树的最大路径和 + 右子树的最大路径和; 左子树的最大路径和是什么 ? 这里每个节点是有正有负的, 如果左子树最大路径和是个负数, 那么我们把左子树的负增益要砍掉, 反而是最大的; 所以准确地说, 我们考虑的左子树的最大路径和, 考虑的是经过左孩子为根节点的向下路径求和增益 (右子树同理); 以当前根节点为根节点的二叉树的最大路径和 = 根节点的值 + 经过左孩子为根节点的向下路径求和增益 + 经过右孩子为根节点的向下路径求和增益, 其中, 增益表示的是至少是个 >= 0 的值
经过左孩子为根节点的向下路径求和增益 = max(viaRootPathSumGain(root->left), 0)
经过左孩子为根节点的向下路径求和增益 = max(viaRootPathSumGain(root->right), 0)
3.所以, 我们要写的函数是 viaRootPathSumGain(), 代表了经过 root 为根节点的向下路径的求和增益, 这个路径上的增益是什么? 根节点的值加左右增益路径中最大的一边的值: 经过 root 为根节点的向下路径的下求和增益 = root->val + max(经过左孩子为根节点的向下路径求和增益, 经过右孩子为根节点的向下路径求和增益)
class Solution {
private:
int ans = INT_MIN;
public:
// viaRootPathSumGain 返回经过 root 为根节点的向下路径的求和增益
int viaRootPathSumGain(TreeNode* root) {
if (root == nullptr) {
return 0;
}
// 经过左/右孩子节点的向下陆景求和增益, 增益表示限制下界是0, 路径和为负数一律不考虑
int lPathSumGain = max(viaRootPathSumGain(root->left), 0);
int rPathSumGain = max(viaRootPathSumGain(root->right), 0);
// 后序位置迭代: 求经过 root 的二叉树的最大路径和
// 经过 root 的二叉树的最大路径和 = root 的值 + 经过左孩子为根节点的向下路径求和增益 + 经过右孩子为根节点的向下路径求和增益
int curPathSum = root->val + lPathSumGain + rPathSumGain;
ans = max(ans, curPathSum);
// 经过 root 为根节点的向下路径的求和增益 = root->val + max(经过左孩子为根节点的向下路径求和增益, 经过右孩子为根节点的向下路径求和增益)
return root->val + max(lPathSumGain, rPathSumGain);
}
int maxPathSum(TreeNode* root) {
viaRootPathSumGain(root);
return ans;
}
};
图论
200.岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。示例 1：
输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1示例 2：
输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3
分析:
1.遍历岛屿, 然后遇到1的情况下累加岛屿个数, 然后 dfs 四个方向把链接的地方都标注成水
class Solution {
private:
int ans = 0;
public:
const vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
return;
}
if (grid[i][j] == '0') {
return;
}
if (grid[i][j] == '1') {
grid[i][j] = '0';
for (int k = 0; k < 4; ++k) {
int nx = i + dirs[k][0];
int ny = j + dirs[k][1];
dfs(grid, nx, ny);
}
}
return;
}
int numIslands(vector<vector<char>>& grid) {
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++ans;
dfs(grid, i, j);
}
}
}
return ans;
}
};
994.腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。示例 1：输入：grid =
[
[2,1,1],
[1,1,0],
[0,1,1]
] 输出：4示例 2：输入：grid =
[
[2,1,1],
[0,1,1],
[1,0,1]
]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。示例 3：输入：grid =
[
[0,2]
] 输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
分析:
1.模拟腐烂的过程, 对腐烂的橘子做广度优先搜索, 每一层数量分钟数增加1 , 然后模拟新鲜的橘子变成了腐烂的橘子
2.在模拟腐烂进行 BFS 的过程中, 持续判断新鲜的橘子 > 0的, 如果新鲜橘子数量 == 0 了, 那么就停下来模拟, 返回结果
3.一开始遍历一下计数有多少个新鲜的橘子, 并将腐烂的橘子入队
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
typedef pair<int, int> pii;
queue<pii> q;
const vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int freshCnt = 0;
// 维护新鲜橘子的个数
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 1) {
++freshCnt;
} else if (grid[i][j] == 2) {
q.push(make_pair(i, j));
}
}
}
int minute = 0;
// 模拟腐烂的过程, bfs 实现
while (freshCnt > 0 && !q.empty()) {
++minute;
int len = q.size();
while (len > 0) {
pii cur = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = cur.first + dirs[k][0];
int ny = cur.second + dirs[k][1];
// 如果是个新鲜的橘子, 腐烂掉
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
grid[nx][ny] = 2;
--freshCnt;
q.push(make_pair(nx, ny));
}
}
--len;
}
}
if (freshCnt > 0) {
return -1;
} else {
return minute;
}
}
};
207.课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。示例 1：输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的.
示例 2：输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
分析:
1.课程之间的关系可以抽象为图结构的依赖关系, 返回可行的结果就是给出一种拓扑排序的结果; 我们尝试对课程图进行拓扑排序, 如果检测到环, 直接停止下来返回 false
2.给出 bfs 和 dfs 的两种实现
// bfs 实现
class Solution {
private:
vector<vector<int>> edges;
vector<int> indegree;
queue<int> q;
int cnt = 0;
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses, vector<int>());
indegree.resize(numCourses);
for (auto x : prerequisites) {
edges[x[1]].push_back(x[0]);
++indegree[x[0]];
}
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int c = q.front();
q.pop();
++cnt;
for (auto n : edges[c]) {
--indegree[n];
if (indegree[n] == 0) {
q.push(n);
}
}
}
return cnt == numCourses;
}
};
然后写下 dfs 实现
// dfs 实现
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
bool hasCycle;
public:
void dfs(int c) {
if (hasCycle) {
return;
}
visited[c] = 1;
for (auto n : edges[c]) {
if (visited[n] == 0) {
dfs(n);
} else if (visited[n] == 1) {
hasCycle = true;
return;
}
}
visited[c] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses, vector<int>());
visited.resize(numCourses);
for (auto x : prerequisites) {
edges[x[1]].push_back(x[0]);
}
for (int i = 0; i < numCourses; ++i) {
if (hasCycle) {
break;
}
if (visited[i] == 0) {
dfs(i);
}
}
return !hasCycle;
}
};
208.实现 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”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True
分析:
1.Trie 实现, 开一个指向 Trie 的数组 vector
class Trie {
private:
vector<Trie*> children; // 子节点指针, 指向的是 Trie 类型的孩子节点, 用一个数组
bool isEnd; // 标记已经是末尾
public:
Trie() {
children = vector<Trie*>(26, nullptr);
isEnd = false;
}
// 搜索前缀的函数: 实现核心搜索前缀的功能
// 如果前缀完全匹配, 返回非空的指针;
// 如果前缀匹配过程中没有匹配到, 直接返回空指针;
Trie* searchPrefix(string word) {
Trie* node = this;
for (char c: word) {
if (node->children[c - 'a'] == nullptr) {
return nullptr;
}
node = node->children[c - 'a'];
}
return node;
}
// 插入字符串的函数
// 遍历字符串
// 如果当前 children[ch] 已经开了指针, node 沿着指针搜索 node = node->children[c - 'a'];
// 如果当前 children[ch] 没有开指针, 那么 new 一个 Trie();
void insert(string word) {
Trie* node = this;
for (char c: word) {
if (node->children[c - 'a'] == nullptr) {
node->children[c - 'a'] = new Trie();
}
node = node->children[c - 'a'];
}
node->isEnd = true;
}
// 匹配前缀函数: 能搜到前缀
bool startsWith(string prefix) {
return searchPrefix(prefix) != nullptr;
}
// 匹配单词函数: 能搜到前缀, 且 idEnd 标记为 true
bool search(string word) {
Trie* node = searchPrefix(word);
return node != nullptr && node->isEnd == true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
回溯
46.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：输入：nums = [1] 输出：[[1]]
分析:
1.因为数组中的元素已经不重复, 我们 dfs + 回溯依次放入相应的元素, 直到判断元素个数已经达到目标元素个数
2.放入的时候判断重复的元素不能放入
class Solution {
public:
void dfs(vector<int>& nums, vector<int>& cur, vector<vector<int>>& ans) {
if (cur.size() == nums.size()) {
ans.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i) {
// 检测到数组中已经存在该元素不执行放入
if (find(cur.begin(), cur.end(), nums[i]) != cur.end()) {
continue;
}
cur.push_back(nums[i]);
dfs(nums, cur, ans);
cur.pop_back();
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> cur;
dfs(nums, cur, ans);
return ans;
}
};
78.子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：输入：nums = [0] 输出：[[],[0]]
分析:
1.采用 dfs+回溯的方式, 回溯完之后, 可以不选元素加入且继续路径向前+1 进行 dfs
class Solution {
public:
void dfs(int pos, vector<vector<int>>& ans, vector<int>& cur, vector<int>& nums) {
if (pos == nums.size()) {
ans.push_back(cur);
return;
}
cur.push_back(nums[pos]);
dfs(pos+1, ans, cur, nums);
cur.pop_back();
// 在不加入元素的情况下继续 dfs
dfs(pos+1, ans, cur, nums);
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> cur;
dfs(0, ans, cur, nums);
return ans;
}
};
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：输入：digits = “” 输出：[]
示例 3：输入：digits = “2” 输出：[“a”,”b”,”c”]
分析:
1.先把所有的从数字到字母的字符串放在一个 map 里面, 然后对数字进行回溯搜索
2.回溯的对应关系为
unrorderd_map<int, char> {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
}
3.采用回溯的思想逐个加入
class Solution {
private:
vector<string> ans;
unordered_map<char, string> num2letter{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
public:
void dfs(int idx, string& cur, string& target) {
if (idx == target.size()) {
ans.push_back(cur);
return;
}
string candidates = num2letter[target[idx]];
for (int i = 0; i < candidates.size(); ++i) {
cur.push_back(candidates[i]);
dfs(idx+1, cur, target);
cur.pop_back();
}
return;
}
vector<string> letterCombinations(string digits) {
if (digits.empty()) {
return ans;
}
string cur = "";
dfs(0, cur, digits);
return ans;
}
};
39.组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。示例 1：输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。示例 2：输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：输入: candidates = [2], target = 1 输出: []
分析:
1.想一下我们的搜索空间是什么, 为了保证不重复不遗漏, 先对元素进行排序, 每次搜索的时候, 要从当前的位置开始搜索, 之前搜过的元素不去搜索, 因此除了维护求和之外, 还得维护一个当前的搜索位置
class Solution {
private:
vector<vector<int>> ans;
public:
void dfs(int sum, int startIdx, int target, vector<int>& cur, vector<int>& candidates) {
if (sum == target) {
ans.push_back(cur);
return;
}
if (sum > target) {
return;
}
for (int i = startIdx; i < candidates.size(); ++i) {
cur.push_back(candidates[i]);
dfs(sum + candidates[i], i, target, cur, candidates);
cur.pop_back();
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if (candidates.empty()) {
return ans;
}
vector<int> cur;
// 必须先排序
sort(candidates.begin(), candidates.end());
// dfs 的时候带上搜索的位置, 才能确定候选集合
dfs(0, 0, target, cur, candidates);
return ans;
}
};
22.括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：输入：n = 1 输出：[“()”]
分析:
1.我们总共有 n 对括号需要增加, 只需要判定清楚什么情况下括号需要增加, 什么情况下括号不能增加, 搜索的时候采取回溯
2.左括号可以任意加入, 只要有就可以加; 右括号在什么情况下是合法的? 左括号数右括号数多的情况下, 可以通过加入右括号, 配置成合法的括号
class Solution {
private:
vector<string> ans;
public:
void dfs(int lCnt, int rCnt, string& cur) {
// 都填完
if (lCnt == 0 && rCnt == 0) {
ans.push_back(cur);
return;
}
// 左括号可以任意加入, 只要有就可以加
if (lCnt > 0) {
cur.push_back('(');
dfs(lCnt - 1, rCnt, cur);
cur.pop_back();
}
// 右括号在什么情况下是合法的? 左括号数右括号数多的情况下, 可以通过加入右括号, 配置成合法的括号
if (rCnt > lCnt) {
cur.push_back(')');
dfs(lCnt, rCnt - 1, cur);
cur.pop_back();
}
return;
}
vector<string> generateParenthesis(int n) {
string cur = "";
dfs(n, n, cur);
return ans;
}
};
79.单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true
示例 2：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE” 输出：true
示例 3：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB” 输出：false
分析:
1.dfs 回溯搜索, 搜索过的地方标记成 visited
2.用分解问题的思维, 当前位置和下个位置的搜索问题是一个问题, 当前位置搜索成功 = 周围四个方向中任意一个搜索成功
class Solution {
private:
vector<vector<bool>> visited;
int rows;
int cols;
public:
bool dfs(int i, int j, int idx, vector<vector<char>>& board, string& word) {
if (idx == word.size()) {
return true;
}
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
if (visited[i][j]) {
return false;
}
if (board[i][j] != word[idx]) {
return false;
}
visited[i][j] = true;
int ret = dfs(i + 1, j, idx + 1, board, word)
|| dfs(i - 1, j, idx + 1, board, word)
|| dfs(i, j + 1, idx + 1, board, word)
|| dfs(i, j - 1, idx + 1, board, word);
visited[i][j] = false;
return ret;
}
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) {
return false;
}
rows = board.size();
cols = board[0].size();
visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (dfs(i, j, 0, board, word)) {
return true;
}
}
}
return false;
}
};
131.分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
示例 1： 输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2： 输入：s = “a” 输出：[[“a”]]
分析:
1.这道题可以这么想, 比如给的是 aaaa, 可以 a,a,a,a, 可以 aa,a,a, 可以 aa,aa, 可以 aaa,a, 可以 aaaa, 所以每次都要判断以某一个起点为起点的某一段 [startPos, i] 是否是回文的, 如果是那么再后面的区间内尝试继续往后搜索, 然后再回溯到起点搜索, 回溯的点是字符串的某个起点位置
2.单独写一个判断区间是回文的函数 isPali(string s, int l, int r)
class Solution {
private:
vector<vector<string>> ans;
public:
bool isPali(string& s, int l, int h) {
while (l < h && s[l] == s[h]) {
++l;
--h;
}
return l >= h;
}
void dfs(int startPos, string& s, vector<string>& cur){
if (startPos == s.size()) {
ans.push_back(cur);
return;
}
for (int i = startPos; i < s.size(); ++i) {
// 如果 [pos, i] 之间是个回文串, 直接截取这个回文串存进去, 然后往后搜索
if (isPali(s, startPos, i)) {
cur.push_back(s.substr(startPos, i - startPos + 1));
// 向后搜索到 i + 1 这个位置
dfs(i+1, s, cur);
cur.pop_back();
}
}
return;
}
vector<vector<string>> partition(string s) {
vector<string> cur;
dfs(0, s, cur);
return ans;
}
};
51.N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。示例 1： 输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：输入：n = 1 输出：[[“Q”]]
分析:
1.初始化一个默认的棋盘, 因为根据规则, 每行至多放 1 个皇后, 所以在 dfs 放置的时候, 对 [行] 这个维度进行 dfs(row), 放完了直接进入下一行; dfs(row) 的内部, 对所有的列的位置 (row, col) 进行模拟放置并回溯
2.放置的时候, 需要检查放置的位置 [i,j] 是满足合法性的, 因此需要在放置之前先检查放置是合法的, 写一个 checkLegality()
3.checkLegality() 需要依次检查面的行之前不能放过, 左上方之前不能放过, 右上方之前不能放过
class Solution {
private:
vector<vector<string>> ans;
public:
bool checkLegality(int r, int c, int n, vector<string>& board) {
// 上面的行之前不能放过
for (int i = 0; i < r; ++i) {
if (board[i][c] == 'Q') {
return false;
}
}
// 左上方之前不能放过
for (int i = r-1, j = c-1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') {
return false;
}
}
// 右上方之前不能放过
for (int i = r-1, j = c+1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
void dfs(int row, int n, vector<string>& board) {
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (checkLegality(row, col, n, board)) {
board[row][col] = 'Q';
dfs(row+1, n, board);
board[row][col] = '.';
}
}
return;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
dfs(0, n, board);
return ans;
}
};
二分查找
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。nums 为 无重复元素 的 升序 排列数组.示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2: 输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3: 输入: nums = [1,3,5,6], target = 7 输出: 4
分析:
1.搜索左边界的二分搜索
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0;
int h = nums.size() - 1;
if (target < nums[l]) {
return 0;
}
if (target > nums[h]) {
return h + 1;
}
while (l <= h) {
int mid = l + (h - l) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
h = mid - 1;
}
}
return l;
}
};
74.搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。示例 1：输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
分析:
1.二分搜索的二维版本, 我们可以用行列关系建立二维和一维之间的映射关系, 然后就能退化到一维的二分搜索了, 假设有 row 行, col 列,
2.二维转一维 l = 0, high = row * col - 1
3.一维转二维 (i, j) 坐标之间关系为 (i / col , j % col) 这么个关系
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = matrix[0].size();
int l = 0;
int h = row * col - 1;
// 二维转一维映射 l = 0, h = row * col -1
while (l <= h) {
int mid = l + (h - l) / 2;
// 一维转二维映射 m[mid / col][mid % col]
int midNum = matrix[mid / col][mid % col];
if (midNum == target) {
return true;
} else if (midNum > target) {
h = mid - 1;
} else if (midNum < target) {
l = mid + 1;
}
}
return false;
}
};
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。示例 1：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
示例 2：输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
示例 3：输入：nums = [], target = 0 输出：[-1,-1]
分析:
1.写一个找左边边界的二分搜索, 以及另一个找右边边界的二分搜索, 两个函数分开写
class Solution {
public:
int lBinarySearch(vector<int>& nums, int target) {
int l = 0;
int h = nums.size() - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int midNum = nums[mid];
if (midNum == target) {
h = mid - 1;
} else if (midNum < target) {
l = mid + 1;
} else if (midNum > target) {
h = mid - 1;
}
}
if (l >= nums.size() || nums[l] != target) {
return -1;
}
return l;
}
int rBinarySearch(vector<int>& nums, int target) {
int l = 0;
int h = nums.size() - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int midNum = nums[mid];
if (midNum == target) {
l = mid + 1;
} else if (midNum < target) {
l = mid + 1;
} else if (midNum > target) {
h = mid - 1;
}
}
if (h < 0 || nums[h] != target) {
return -1;
}
return h;
}
vector<int> searchRange(vector<int>& nums, int target) {
return vector<int>{lBinarySearch(nums, target), rBinarySearch(nums, target)};
}
};
33.搜索旋转排序数组
整数数组 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) 的算法解决此问题。示例 1：输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：输入：nums = [1], target = 0 输出：-1
分析:
1.旋转数组的特点是: 以旋转点作为界限, 两边的区间仍然保持单调的性质, 比如 [4,5,6,7,0,1,2] 和 [6,7,0,1,2,3,4]; 但是以搜索点作为界限: 左右两边的区间只存在一边必然单调, 一边可能不单调的性质; 在搜索的时候, 我们先判断以 nums[mid] 的一遍是否存在单调性, 比如我们去判断 nums[mid] 的右边是否存在单调性: 判断右边是否存在单调性的依据是最右边的元素是否大于当前元素, 如果是最最右侧的元素是更大的, 说明旋转点不在右边, 右边是单调的; 如果右边存在单调性, 我们再判断在 target 是否在右边的区间里面, 也就是增加判断 target 是介于 nums[mid] 和 nums[r]之间的值, 如果是那么就很方便地进行二分搜索; 如果不存在在右边边界, 那么只要递归地搜索左边的区间, 右边不需要再投入考虑
2.旋转数组的二分搜索相对与普通的二分搜索相当于多加了两层判断, 一层判断是当前搜索区间是否单调, 以及再判断当前元素是否再里面
3.旋转数组的二分搜索如果进入一个不单调的区间里面搜索, 该子问题的结构和原问题的结构是完全相同的, 继续递归的去搜索一个子数组, 这个数组也是一个旋转数组, 直到两边不再有任何旋转数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size()-1;
while (l <= r) {
int mid = l + (r - l) / 2;
int midNum = nums[mid];
if (midNum == target) {
return mid;
}
// 判断一侧是否是单调的: 例如判断右边如果是单调的
if (nums[mid] < nums[r]) {
// 判断 target 是否在右边区间
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
// 不在就去左边区间搜索
} else {
r = mid - 1;
}
// 判断另一侧左边的单调性也已知了, 因为旋转数组必然一边单调一边不单调
} else {
// 判断 target 是否在左边区间
if (nums[mid] > target && target >= nums[l]) {
r = mid - 1;
// 不在就去右边区间搜索
} else {
l = mid + 1;
}
}
}
return -1;
}
};
153.寻找旋转排序数组中的最小值
已知一个长度为 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) 的算法解决此问题。示例 1：输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
分析:
1.旋转数组满足中点二分之后, 一边单调, 一边不单调的性质
2.我们二分搜一次, 可以找到一边的单调区间, 更新当前的最小值为单调区间的最左侧; 然后再去另一个不单调的区间里面去尝试找更小的元素, 直到两边都是单调的情况, 不断迭代找到整个数组的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = INT_MAX;
int l = 0;
int h = nums.size() - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
int midNum = nums[mid];
// 如果左边单调, 最左侧可尝试更新最小元素
if (midNum >= nums[l]) {
ans = min(ans, nums[l]);
l = mid + 1;
// 如果右边单调, midNum可尝试更新最小元素
} else {
ans = min(ans, midNum);
h = mid - 1;
}
}
return ans;
}
};
4.寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
示例 1: 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
分析:
1.找两个数组中的中位数: 两个数组中的中位数是怎么定义的 ?
(i). 如果两个数组长度 一个奇数一个偶数, 因为奇+偶=奇, 那么就是正好中间这个数
(ii). 如果两个数组长度 一个偶数一个偶数, 因为偶+偶=偶, 那么正好就是合并排序后中间这两个数的平均数
(iii). 如果两个数组长度 一个奇数一个奇数, 因为奇+奇=偶, 那么正好就是合并排序后中间这两个数的平均数
2.怎么忽略数组长度为奇数和数组长度为偶数的分类讨论? 总长度是 m + n. 找两个有序数组中的中位数, 相当于找 [两个数组合并且排序后第(m + n + 1) / 2 小的数] 和 [两个数组合并且排序后第 (m + n + 2)/2 小的数] 这2个结果的平均数, 无论总长度 (m + n) 是奇数还是偶数; 注意一个数组中第 k 小的数的下标是 k - 1
我们举 3个 例子理解一下
[如果总长度奇数] [1, 2, 3] 和 [4, 5, 6, 7] :(total[4 - 1]+total[4 - 1])/2 = 4
[如果总长度偶数] [1, 2, 3] 和 [4, 5, 6] :(total[3 - 1]+total[4 - 1])/2 = 3.5
[如果总长度偶数] [1, 2, 3, 4] 和 [5, 6, 7, 8] :(total[4 - 1]+total[5 - 1])/2 = 3.5
3.需要想办法找 [两个数组合并且排序] 中第x小的数
具体地，我们每次在两个数组中比较第 k/2 小的数，合并总数中找中位数, 可以通过比较子数组中找 k/2 分位数的数谁大谁小去缩小搜索空间
如果数组1的第 k/2 小的数 小于数组2的第 k/2 小的数，则数组1的前 k/2 个数可以舍弃，同时 k 要减去 k/2
如果数组2的第 k/2 小的数 小于数组1的第 k/2 小的数，则数组2的前 k/2 个数可以舍弃，同时 k 要减去 k/2
通过不断舍弃前 k/2 个数，最终我们可以得到第 k 小数.
4.我们就可以在O(log(m+n))的时间内查找到中位数
class Solution {
public:
// getKth 目标找到 nums1 和 nums2 合并排序后的第 k 小的数
int getKth(vector<int> nums1, vector<int> nums2, int k) {
int len1 = nums1.size();
int len2 = nums2.size();
// 保证 nums1 数组长度是较短的一个
if (len1 > len2) {
return getKth(nums2, nums1, k);
}
// 如果 len1 为空, 直接返回 nums2 中第 k 小的数, 下标是 k - 1
if (len1 == 0) {
return nums2[k - 1];
}
// 如果是找最小的数, 可以直接比这两个数组中的最小的数, 取二者的最小的
if (k == 1) {
return min(nums1[0], nums2[0]);
}
// 如果 num1 中 第k/2小的 元素的 index 比 len1 还大, 在 nums1 中至多找到 第 len1 小的数
int i = min(len1, k / 2);
int j = min(len2, k / 2);
// 比较 num1 的第 k/2 小的数 和 num2 的 k/2 的数的大小
// 如果 nums1的 k/2 分位数比, nums2 的 k/2 分位数大, nums2 舍弃前一半元素
if (nums1[i - 1] > nums2[j - 1]) {
vector<int> tmp = vector<int>(nums2.begin() + j, nums2.end());
return getKth(nums1, tmp, k - j);
// 如果 nums2的 k/2 分位数比, nums1 的 k/2 分位数大, nums1 舍弃前一半元素
} else {
vector<int> tmp = vector<int>(nums1.begin() + i, nums1.end());
return getKth(tmp, nums2, k - i);
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size();
int len2 = nums2.size();
// 两个有序数组中的中位数等于
// median = ((合并数组后 [len1 + len2 + 1] / 2 小的数) + (合并数组后 [len1 + len2 + 2] / 2 小的数)) / 2
return (getKth(nums1, nums2, (len1 + len2 + 1) / 2) + getKth(nums1, nums2, (len1 + len2 + 2) / 2)) / 2.0;
}
};
栈
20.有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。示例 1：输入：s = “()” 输出：true
示例 2：输入：s = “()[]{}” 输出：true
示例 3：输入：s = “(]” 输出：false
分析:
1.总共有 3 种类型的括号, 合法的括号都是成对的出现的, 举几个合法的例子
(([[]]))
[()]
{}[[(())]]
2.再举几个不合法的例子
``` sh
{[}]
)[{
转载请注明来源, from goldandrabbit.github.io
