Leetcode Hot 100
Tip力扣 JS 内置 lodash 和 队列 (datastructures-js/queue) / 优先队列 (datastructures-js/priority-queue) 库
梦开始的地方——
两数之和
核心思路就是哈希表一次遍历。在遍历数组 nums 的同时，利用哈希表记录已经访问过的数值及其下标。对于当前的元素 nums[i]，我们不需要二次遍历另一个数判断两数和是否为 target，而是寻找“目标差值”target - nums[i]。若目标差值已在哈希表中，说明找到了匹配对，直接返回其下标。若不在，则将当前 nums[i] 存入哈希表，继续向后扫描。
时间复杂度：O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); ++i) {
int x = target - nums[i];
if (mp.count(x))
return {mp[x], i};
mp[nums[i]] = i;
}
return {};
}
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; ++i) {
if (map.get(target - nums[i]) !== undefined)
return [i, map.get(target - nums[i])];
map.set(nums[i], i);
}
return [];
};
字母异位词分组
哈希表分组，将strs[i]排序后的值作为哈希表的键，其在结果数组里的下标作为哈希表的值。也可以不用索引映射，直接用vector<string>作为哈希表的值。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, int> mp;
for (int i = 0, j = 0; i < strs.size(); ++i) {
string t = strs[i];
ranges::sort(t);
if (!mp.count(t)) {
mp[t] = j++;
ans.push_back({strs[i]});
} else
ans[mp[t]].push_back(strs[i]);
}
return ans;
}
};
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
let ans = [];
const map = new Map();
for (let i = 0, j = 0; i < strs.length; ++i) {
let t = [...strs[i]].sort().join();
if (map.get(t) === undefined) {
map.set(t, j++);
ans.push([strs[i]]);
} else {
ans[map.get(t)].push(strs[i]);
}
}
return ans;
};
最长连续序列
要找出数组中数字连续的最长序列，那么从这个序列的起点开始找就行了，不需要从数组中每个数开始找一遍。我们怎么找到序列的起点？哈希表中如果不存在当前值x小1的数x-1，那么x就是起点。找到起点后通过哈希表找终点，数后面有多长。
时间复杂度：O(n)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> st(nums.begin(), nums.end());
int ans = 0;
for (auto start : st) {
if (!st.count(start - 1)) {
int end = start + 1;
while (st.count(end))
end++;
ans = max(ans, end - start);
}
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
let ans = 0;
const set = new Set(nums);
for (let start of set) {
if (!set.has(start - 1)) {
let end = start + 1;
while (set.has(end))
end++;
ans = Math.max(ans, end - start);
}
}
return ans;
};
移动零
双指针，把右边所有非零元素移到左边的空位（0）上。
时间复杂度：O(n)
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int l = 0, r = 0; r < nums.size(); ++r) {
if (nums[r]) {
swap(nums[l++], nums[r]);
}
}
}
};
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
for(let l = 0, r = 0; r < nums.length; ++r) {
if(nums[r]) {
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
}
}
};
盛最多水的容器
水量即容器的面积，面积=底*高，求最大水量也就是说要让底和高尽可能大，用双指针分别置于数组首尾，逐渐减小底，我们知道高是由左右指针对应的最小值决定的，如果左边的高小于右边的，就移动左指针（因为如果移动较高的一侧，新的高度即使超过原来高度，容器的高取的是最小值，还是左边的高，那么宽也减小的情况下，面积不可能会增大），否则移动右指针。
class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0, l = 0, r = height.size() - 1;
while (l < r) {
ans = max(ans, (r - l) * min(height[l], height[r]));
height[l] < height[r] ? l++ : r--;
}
return ans;
}
};
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let ans = 0, l = 0, r = height.length - 1;
while (l < r) {
ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
if (height[l] < height[r])
l++;
else
r--;
}
return ans;
};
三数之和
需要考虑如何避免重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
ranges::sort(nums);
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (i && nums[i] == nums[i - 1])
continue;
if (nums[i] + nums[i + 1] + nums[i + 2] > 0)
break;
if (nums[i] + nums[n - 2] + nums[n - 1] < 0)
continue;
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum < 0)
j++;
else if (sum > 0)
k--;
else {
if (j == i + 1 || nums[j] != nums[j - 1])
ans.push_back({nums[i], nums[j], nums[k]});
j++;
k--;
}
}
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
let ans = [], n = nums.length;
for (let i = 0; i < n - 2; ++i) {
if (i && nums[i] === nums[i - 1])
continue;
if (nums[i] + nums[i + 1] + nums[i + 2] > 0)
break;
if (nums[i] + nums[n - 2] + nums[n - 1] < 0)
continue;
let j = i + 1, k = n - 1;
while (j < k) {
let sum = nums[i] + nums[j] + nums[k];
if (sum < 0)
j++;
else if (sum > 0)
k--;
else {
if (j == i + 1 || nums[j] != nums[j - 1])
ans.push([nums[i], nums[j], nums[k]]);
j++;
k--;
}
}
}
return ans;
};
接雨水
双指针的做法就是维护两边最大的高度，哪边低哪边内部就接雨水。
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
vector<int> v;
for (int i = 0; i < height.size(); ++i) {
while (!v.empty() && height[i] >= height[v.back()]) {
int j = v.back();
v.pop_back();
if (!v.empty()) {
int k = v.back();
ans += (min(height[k], height[i]) - height[j]) * (i - k - 1);
}
}
v.push_back(i);
}
return ans;
}
};
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let ans = 0, preMax = 0, sufMax = 0, l = 0, r = height.length - 1;
while (l < r) {
preMax = Math.max(preMax, height[l]);
sufMax = Math.max(sufMax, height[r]);
if (preMax < sufMax)
ans += preMax - height[l++];
else
ans += sufMax - height[r--];
}
return ans;
};
无重复字符的最长子串
大体思路是哈希表/哈希集合+不定长滑动窗口，有重复字符就移动左指针。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
unordered_map<char, int> mp;
for (int i = 0, l = 0; i < s.size(); ++i) {
mp[s[i]]++;
while (mp[s[i]] > 1)
mp[s[l++]]--;
ans = max(ans, i - l + 1);
}
return ans;
}
};
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function (s) {
let ans = 0;
const set = new Set();
for (let i = 0, l = 0; i < s.length; ++i) {
while (set.has(s[i]))
set.delete(s[l++]);
set.add(s[i]);
ans = Math.max(ans, i - l + 1);
}
return ans;
};
找到字符串中所有字母异位词
定长滑动窗口，枚举s中所有与p等长的字串。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
unordered_map<char, int> mp_s, mp_p;
for (auto ch : p)
mp_p[ch]++;
int n = p.size();
for (int i = 0; i < s.size(); ++i) {
mp_s[s[i]]++;
int l = i - n + 1;
if (l < 0)
continue;
if (mp_p == mp_s)
ans.push_back(l);
mp_s[s[l]]--;
if (mp_s[s[l]] == 0)
mp_s.erase(s[l]);
}
return ans;
}
};
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
let ans = [];
const cntP = new Array(26).fill(0), cntS = new Array(26).fill(0);
for (const c of p)
cntP[c.charCodeAt() - 'a'.charCodeAt()]++;
for (let i = 0; i < s.length; ++i) {
cntS[s[i].charCodeAt() - 'a'.charCodeAt()]++;
let l = i - p.length + 1;
if (l < 0) continue;
if (_.isEqual(cntS, cntP)) ans.push(l);
cntS[s[l].charCodeAt() - 'a'.charCodeAt()]--;
}
return ans;
};
和为 K 的子数组
哈希表记录前缀和。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0, sum = 0;
unordered_map<int, int> mp;
mp[0] = 1;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
ans += mp[sum - k];
mp[sum]++;
}
return ans;
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function (nums, k) {
let ans = 0, sum = 0;
const map = new Map();
for (const num of nums) {
map.set(sum, (map.get(sum) ?? 0) + 1);
sum += num;
ans += map.get(sum - k) ?? 0;
}
return ans;
};
滑动窗口最大值
一种思路是用最大堆，堆顶是最大元素及其对应下标，需要滑出左边移出窗口的元素。
但这不是最好的做法，我们可以用单调队列，需要维护的是窗口内最大元素的下标，每次入队尾前，如果当前元素大于或等于队尾对应元素，就移出队尾这个元素，这样就保证了队列是单调递减的，也就是说队首是最大元素下标，是我们要记录的答案。那队首什么时候移出呢，队首下标如果与当前下标的距离不小于k了，说明队首对应元素离开窗口了，需要移出。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
priority_queue<pair<int, int>> heap;
for (int i = 0; i < nums.size(); ++i) {
heap.push({nums[i], i});
while (heap.top().second <= i - k)
heap.pop();
if (i >= k - 1)
ans.push_back(heap.top().first);
}
return ans;
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function (nums, k) {
let ans = [];
const q = new Deque();
for (let i = 0; i < nums.length; ++i) {
while (!q.isEmpty() && nums[i] >= nums[q.back()])
q.popBack();
q.pushBack(i);
let l = i - k + 1;
if (q.front() < l)
q.popFront();
if (l >= 0)
ans.push(nums[q.front()]);
}
return ans;
// let ans = [], dq = [];
// for (let i = 0; i < nums.length; ++i) {
// while (dq.length && nums[i] >= nums[dq.at(-1)])
// dq.pop();
// dq.push(i);
// if (i - dq[0] >= k)
// dq.shift(); // shift() 也能移除首位元素，但时间复杂度是 O(n)，最好用 Deque 数据结构
// if (i >= k - 1)
// ans.push(nums[dq[0]]);
// }
// return ans;
};
最小覆盖子串
考虑滑动窗口，什么时候需要滑动呢？当窗口内的子串满足覆盖 t 时，移动左值针，这里要记录指针的位置，直接更新答案会爆内存。
class Solution {
public:
string minWindow(string s, string t) {
int cnt_s[128]{}, cnt_t[128]{};
for(auto ch: t)
cnt_t[ch]++;
auto cover = [&]() -> bool {
for (int i = 'A'; i <= 'Z'; ++i) {
int j = i - 'A' + 'a';
if (cnt_t[i] > cnt_s[i] || cnt_t[j] > cnt_s[j])
return false;
}
return true;
};
int left = 0, right = -1;
for (int l = 0, r = 0; r < s.size(); ++r) {
cnt_s[s[r]]++;
while (cover()) {
if (right == -1 || r - l < right - left) {
left = l;
right = r;
}
cnt_s[s[l++]]--;
}
}
return s.substr(left, right - left + 1);
}
};
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
const cnt_s = new Array(128).fill(0), cnt_t = new Array(128).fill(0);
for (const ch of t)
cnt_t[ch.charCodeAt(0)]++;
function cover() {
for (let i = 65; i <= 90; ++i) {
let j = i + 32;
if (cnt_s[i] < cnt_t[i] || cnt_s[j] < cnt_t[j])
return false;
}
return true;
}
let left = 0, right = -1;
for (let l = 0, r = 0; r < s.length; ++r) {
cnt_s[s[r].charCodeAt(0)]++;
while (cover()) {
if (right == -1 || right - left > r - l) {
left = l;
right = r;
}
cnt_s[s[l].charCodeAt(0)]--;
l++;
}
}
return s.slice(left, right + 1);
};
最大子数组和
问题是找到最大和的连续子数组，可以用动态规划，那么就要想状态转移方程是什么：
定义 f[i] 为截至第i个元素的最大子数组和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = nums[0], ans = sum;
for (int i = 1; i < nums.size(); ++i) {
sum = max(sum, 0) + nums[i];
ans = max(ans, sum);
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let sum = nums[0], ans = sum;
for (let i = 1; i < nums.length; ++i) {
sum = Math.max(sum, 0) + nums[i];
ans = Math.max(ans, sum);
}
return ans;
};
合并区间
这题主要就是先排序，保证左端点是从小到大的。然后判断每个左端点在不在前一个元素区间里，更新右端点为两者右端点的最大值。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
ranges::sort(intervals);
vector<vector<int>> ans{intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] > ans.back()[1])
ans.push_back(intervals[i]);
else
ans.back()[1] = max(ans.back()[1], intervals[i][1]);
}
return ans;
}
};
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function (intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let ans = [intervals[0]];
for (let i = 1; i < intervals.length; ++i) {
if (ans.at(-1)[1] < intervals[i][0])
ans.push(intervals[i]);
else
ans.at(-1)[1] = Math.max(ans.at(-1)[1], intervals[i][1]);
}
return ans;
};
轮转数组
参考灵神的思路，先翻转整个数组，在翻转前k个和后n-k个。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
ranges::reverse(nums);
ranges::reverse(nums.begin(), nums.begin() + k);
ranges::reverse(nums.begin() + k, nums.end());
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function (nums, k) {
let n = nums.length;
k %= n;
function reverse(start, end) {
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start++;
end--
}
}
reverse(0, n - 1);
reverse(0, k - 1);
reverse(k, n - 1);
};
除了自身以外数组的乘积
简单来说就是前缀元素的乘积乘以后缀元素的乘积。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans, prefix{1}, suffix{1};
for (int i = 0; i < n; ++i) {
prefix.push_back(prefix.back() * nums[i]);
suffix.push_back(suffix.back() * nums[n - i - 1]);
}
for (int i = 0; i < n; ++i)
ans.push_back(prefix[i] * suffix[n - i - 1]);
return ans;
}
};
/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
let n = nums.length, ans = [], prefix = [1], suffix = [1];
for (let i = 0; i < n; ++i) {
prefix.push(prefix.at(-1) * nums[i]);
suffix.push(suffix.at(-1) * nums[n - i - 1]);
}
for (let i = 0; i < n; ++i)
ans.push(prefix[i] * suffix[n - i - 1]);
return ans;
};
缺失的第一个正数
问题是找出其中没有出现的最小的正整数，设n为数组长度 + 1，那么答案一定在 区间[1, n]中。先遍历数组，排除区间之外的数，可以将这些元素置0，再次遍历，将元素 nums[i] 对应到 nums[nums[i] -1] 上进行标记，加一个 n，说明可以排除这个下标。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size() + 1;
for (auto& num : nums) {
if (num < 0 || num >= n)
num = 0;
}
for (int i = 0; i < n - 1; ++i) {
if (nums[i] % n)
nums[nums[i] % n - 1] += n;
}
for (int i = 0; i < n - 1; ++i) {
if (nums[i] < n)
return i + 1;
}
return n;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function (nums) {
let n = nums.length + 1;
for (let i = 0; i < n - 1; ++i) {
if (nums[i] < 0 || nums[i] >= n)
nums[i] = 0;
}
for (let i = 0; i < n - 1; ++i) {
if (nums[i] % n) {
nums[nums[i] % n - 1] += n;
}
}
for (let i = 0; i < n - 1; ++i) {
if (nums[i] < n)
return i + 1;
}
return n;
};
矩阵置零
原地算法，遍历每个元素，如果是0，就标记当前行和列。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool first_row_has_zero = ranges::contains(matrix[0], 0);
bool first_col_has_zero =
ranges::any_of(matrix, [](auto& row) { return row[0] == 0; });
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
if (first_col_has_zero) {
for (int i = 0; i < m; ++i)
matrix[i][0] = 0;
}
if (first_row_has_zero) {
ranges::fill(matrix[0], 0);
}
}
};
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
const m = matrix.length, n = matrix[0].length;
let first_row_contains_zero = matrix[0].includes(0);
for (let i = 1; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (matrix[i][j] === 0)
matrix[i][0] = matrix[0][j] = 0;
}
}
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
if (matrix[i][0] === 0 || matrix[0][j] === 0)
matrix[i][j] = 0;
}
}
if(matrix[0][0] === 0) {
for(const row of matrix)
row[0] = 0;
}
if (first_row_contains_zero)
matrix[0].fill(0)
};
螺旋矩阵
从外到里遍历，只要考虑好方向变化就行。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.size() == 0)
return {};
int a = 0, b = (int)matrix[0].size(), c = 0, d = (int)matrix.size();
vector<int> res;
while (a < b && c < d) {
for (int i = a; i < b; ++i)
res.push_back(matrix[c][i]);
for (int i = c + 1; i < d; ++i)
res.push_back(matrix[i][b - 1]);
for (int i = b - 2; i >= a && d > c + 1; --i)
res.push_back(matrix[d - 1][i]);
for (int i = d - 2; i > c && d > c + 1 && b > a + 1; --i)
res.push_back(matrix[i][a]);
a += 1;
b -= 1;
c += 1;
d -= 1;
}
return res;
}
};
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function (matrix) {
let dir = 0, i = 0, j = 0, t = 0, ans = [];
const m = matrix.length, n = matrix[0].length, dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
while (ans.length < m * n) {
ans.push(matrix[i][j]);
dir %= 4;
i += dirs[dir][0];
j += dirs[dir][1];
if ((dir === 0 && j >= n - t) || (dir === 1 && i >= m - t) || (dir === 2 && j < t) || (dir === 3 && i < t)) {
dir++;
t += dir % 3 === 0;
i += dirs[dir % 4][0] - dirs[(dir - 1) % 4][0];
j += dirs[dir % 4][1] - dirs[(dir - 1) % 4][1];
}
}
return ans;
};
旋转图像
先按主对角线反转，再进行行翻转。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
swap(matrix[i][j], matrix[j][i]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n / 2; ++j)
swap(matrix[i][j], matrix[i][n - j - 1]);
}
};
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
const m = matrix.length, n = matrix[0].length;
for (let i = 0; i < m; ++i) {
for (let j = i; j < n; ++j)
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n / 2; ++j)
[matrix[i][j], matrix[i][n - j - 1]] = [matrix[i][n - j - 1], matrix[i][j]];
}
};
搜索二维矩阵 II
从右上角开始找，如果大于目标值，往左，如果小于目标值，往下。当然也可以从左下角开始。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target)
return true;
else if (matrix[i][j] > target)
--j;
else
++i;
}
return false;
}
};
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const m = matrix.length, n = matrix[0].length;
let i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target)
return true;
if (matrix[i][j] > target)
--j;
else
++i;
}
return false;
};
相交链表
假设两条链表长度分别为m和n，那么从距离表尾min(m, n)处开始找相同节点就行。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode *p = headA, *q = headB;
while (p && q) {
p = p->next;
q = q->next;
}
ListNode *a = headA, *b = headB;
while (p) {
p = p->next;
a = a->next;
}
while (q) {
q = q->next;
b = b->next;
}
while (a != b) {
a = a->next;
b = b->next;
}
return a;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
let p = headA, q = headB;
while (p && q) {
p = p.next;
q = q.next;
}
let a = headA, b = headB;
while (p) {
p = p.next;
a = a.next;
}
while (q) {
q = q.next;
b = b.next;
}
while (a != b) {
a = a.next;
b = b.next;
}
return a;
};
反转链表
用到pre、cur、nxt三个变量，分别指向前一个节点，当前节点，后一个节点。要翻转链表，更改当前节点next指向pre就行了，循环结束后pre表示新得到的链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr, *cur = head, *nxt = head;
while (nxt) {
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let pre = null, cur = head, nxt = head;
while(nxt) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
};
回文链表
这题可以利用上一题的翻转，回文嘛，把链表后半段翻转一下，然后分别从表头和链表中间开始遍历判断节点值是不是相等。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *p = head, *q = head;
while (q && q->next) {
p = p->next;
q = q->next->next;
}
ListNode *pre = nullptr, *cur = p, *nxt = p;
while (nxt) {
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
// 我这里没把后半段链表接上去
q = pre, p = head;
while (p && q) {
if(p->val != q->val)
return false;
p = p->next;
q = q->next;
}
return true;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
let p = head, q = head;
while (q && q.next) {
p = p.next;
q = q.next.next;
}
let pre = null, cur = p, nxt = p;
while (nxt) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
p = head, q = pre;
while (p && q) {
if (p.val != q.val)
return false;
p = p.next;
q = q.next;
}
return true;
};
环形链表
核心思路就是快慢指针，链表有环的话快指针和慢指针一定会相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode *p = head, *q = head;
while (q && q->next) {
p = p->next;
q = q->next->next;
if (p == q)
return true;
}
return false;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
let p = head, q = head;
while (q && q.next) {
p = p.next;
q = q.next.next;
if (p === q)
return true;
}
return false;
};
环形链表 II
同样利用快慢指针。假设头节点到环入口距离为l，环长为c，快慢指针相遇后，距离（顺时针）环入口为x，那么慢指针走过的距离可计算为l+x，快指针走过的距离为l+x+c（快指针实际就是比慢指针多走了一个环的距离），而快指针移动速度是慢指针的两倍，因此我们可以得到等式2(l+x) = l+x+c，化简得l = c-x，这说明什么呢？要找到环入口，继续移动慢指针就行了，另外从头移动另一个指针，他们必定会在环入口相遇，因为l = c-x。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode *p = head, *q = head;
while (q && q->next) {
p = p->next;
q = q->next->next;
if (p == q) {
ListNode* h = head;
while (h != p) {
h = h->next;
p = p->next;
}
return p;
}
}
return NULL;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let p = head, q = head;
while (q && q.next) {
p = p.next;
q = q.next.next;
if (p === q) {
let h = head;
while (h != p) {
p = p.next;
h = h.next;
}
return p;
}
}
return null;
};
合并两个有序链表
两两比较，哪个小哪个放前面。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *l = new ListNode(), *p = l;
while (list1 && list2) {
if (list1->val > list2->val) {
p->next = new ListNode(list2->val);
list2 = list2->next;
} else {
p->next = new ListNode(list1->val);
list1 = list1->next;
}
p = p->next;
}
p->next = list1 ? list1 : list2;
return l->next;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
let l = new ListNode(0), p = l;
while (list1 && list2) {
p.next = new ListNode(Math.min(list1.val, list2.val));
if (list1.val < list2.val)
list1 = list1.next;
else
list2 = list2.next;
p = p.next;
}
p.next = list1 ? list1 : list2;
return l.next;
};
两数相加
节点数值相加然后注意进位就行。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode(), *p = l1, *q = l2, *l = head;
int carry = 0;
while (p || q) {
int x = carry;
if (p) {
x += p->val;
p = p->next;
}
if (q) {
x += q->val;
q = q->next;
}
carry = x / 10;
l->next = new ListNode(x % 10);
l = l->next;
}
if (carry)
l->next = new ListNode(1);
return head->next;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
let head = new ListNode(0), l = head, carry = 0;
while (l1 || l2 || carry) {
let x = carry;
if (l1) {
x += l1.val;
l1 = l1.next;
}
if (l2) {
x += l2.val;
l2 = l2.next;
}
// C++ 写习惯了老是忘了加 Math.floor（T-T）
carry = Math.floor(x / 10);
l.next = new ListNode(x % 10);
l = l.next;
}
return head.next;
};
删除链表的倒数第 N 个结点
先找到倒数第N个节点的位置，删除就改变指针指向。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *p = head, *q = head;
for (int i = 0; i < n; ++i)
q = q->next;
if (q == nullptr)
return p->next;
q = q->next;
while (q) {
q = q->next;
p = p->next;
}
p->next = p->next->next;
return head;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
let p = head, q = head;
for (let i = 0; i < n; ++i)
p = p.next;
if(p === null)
return q.next;
while (p && p.next) {
p = p.next;
q = q.next;
}
q.next = q.next.next;
return head;
};
两两交换链表中的节点
假如链表是1->2->3->4，放一个哨兵节点变成0->1->2->3->4，从这个节点开始node1->0、node2->1，每次取node3为node2的下一个节点（这里是2），node2和node3是真正要交换的节点。更改node2下一个节点指向node3的下一个节点（1->3），而node3下一个节点指向node2（2->1），再修改node1下一个节点指向node3(0->2)，这样就连起来了0->2->1->3->4，成功交换了1 (node2)和2 (node3)的顺序，之后更新node1和node2为下一次循环做准备（node1移到1，node2移到3）。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(0, head), *node1 = dummy, *node2 = head;
while (node2 && node2->next) {
ListNode* node3 = node2->next;
node2->next = node3->next;
node3->next = node2;
node1->next = node3;
node1 = node2;
node2 = node2->next;
}
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function (head) {
let dummy = new ListNode(0, head), node1 = dummy, node2 = head;
while (node2 && node2.next) {
let node3 = node2.next;
node2.next = node3.next;
node3.next = node2;
node1.next = node3;
node1 = node2;
node2 = node2.next;
}
return dummy.next;
};
K 个一组翻转链表
主要思考的就是一组翻转后怎么前后连起来。我们需要用到的指针有，这组链表翻转前的前一个节点和后一个节点，以及这组链表翻转后的头节点和尾节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n = 0;
for (ListNode* cur = head; cur; cur = cur->next)
n++;
ListNode *dummy = new ListNode(0, head), *l = dummy, *pre = nullptr,
*cur = head;
for (; n >= k; n -= k) {
for (int i = 0; i < k; ++i) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
ListNode* nxt = l->next;
nxt->next = cur;
l->next = pre;
l = nxt;
}
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function (head, k) {
let i = 0, dummy = new ListNode(0, head), p = head, q = dummy, pre = null, cur = head, nxt = head;
while(p) {
i++;
p = p.next;
if(i % k == 0) {
while(nxt !== p) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
nxt = q.next;
nxt.next = cur;
q.next = pre;
q = nxt;
}
}
return dummy.next;
};
随机链表的复制
排序链表
合并 K 个升序链表
LRU 缓存
二叉树的中序遍历
深搜 dfs 啦，先遍历左子树，获取根节点值，再遍历右子树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
auto dfs = [&](this auto&& dfs, TreeNode* node) {
if(node == nullptr)
return;
dfs(node->left);
v.push_back(node->val);
dfs(node->right);
};
dfs(root);
return v;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function (root) {
let ans = [];
function dfs(node) {
if (node === null)
return;
dfs(node.left);
ans.push(node.val);
dfs(node.right);
}
dfs(root);
return ans;
};
二叉树的最大深度
就是递归思想，找二叉树最大深度的话取左右子树最大的那个就行。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr)
return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
if (root === null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};
翻转二叉树
同样是递归思想，互换左右子树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr)
return nullptr;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function (root) {
if (root === null)
return null;
let left = invertTree(root.left);
let right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
};
对称二叉树
对称说明左子树的左子树与右子树的右子树相同，左子树的右子树与右子树的左子树相同。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
auto dfs = [&](this auto&& dfs, TreeNode* l, TreeNode* r) -> bool {
if (l == nullptr)
return r == nullptr;
if (r == nullptr)
return l == nullptr;
if (l->val != r->val)
return false;
return dfs(l->left, r->right) && dfs(l->right, r->left);
};
return dfs(root->left, root->right);
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function (root) {
function dfs(l, r) {
if (l === null && r === null)
return true;
if (l === null || r === null || l.val !== r.val)
return false;
return dfs(l.left, r.right) && dfs(l.right, r.left);
}
return dfs(root.left, root.right);
};
二叉树的直径
二叉树的直径是指树中任意两个节点之间最长路径的长度，其实就是树中某个节点的左子树最大深度与右子树最大深度之和的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
auto dfs = [&](this auto&& dfs, TreeNode* node) -> int {
if (node == nullptr)
return -1;
int left = dfs(node->left) + 1;
int right = dfs(node->right) + 1;
ans = max(ans, left + right);
return max(left, right);
};
dfs(root);
return ans;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function (root) {
let ans = 0;
function dfs(node) {
if (node === null)
return -1;
let l = dfs(node.left) + 1, r = dfs(node.right) + 1;
ans = Math.max(ans, l + r);
return Math.max(l, r);
}
dfs(root);
return ans;
};
二叉树的层序遍历
广搜用队列。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
vector<int> v;
queue<TreeNode*> q, p;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
v.push_back(node->val);
q.pop();
if (node->left)
p.push(node->left);
if (node->right)
p.push(node->right);
if (q.empty() && !p.empty()) {
q = p;
ans.push_back(v);
v.clear();
p = queue<TreeNode*>();
}
}
ans.push_back(v);
return ans;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function (root) {
if (root === null)
return [];
let ans = [];
const q = new Queue();
q.enqueue(root);
while (!q.isEmpty()) {
let n = q.size(), level = [];
while (n--) {
let node = q.dequeue();
level.push(node.val);
if (node.left)
q.enqueue(node.left);
if (node.right)
q.enqueue(node.right);
}
ans.push(level);
}
return ans;
};
将有序数组转换为二叉搜索树
平衡二叉树就是树中任意节点的左右子树高度差绝对值不超过1，我们可以用分治法，左子树取数组前一半，右子树取数组后一半。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
auto helper = [&](this auto&& helper, int i, int j) -> TreeNode* {
if (i >= j)
return nullptr;
int mid = (i + j) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = helper(i, mid);
node->right = helper(mid + 1, j);
return node;
};
return helper(0, nums.size());
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function (nums) {
function arrayToBST(l, r) {
let len = r - l;
if (len === 0)
return null;
let mid = Math.floor(len / 2) + l;
return new TreeNode(nums[mid], sortedArrayToBST(nums.slice(l, mid)), sortedArrayToBST(nums.slice(mid + 1, r)));
}
return arrayToBST(0, nums.length);
};
验证二叉搜索树
二叉搜索数如果用中序遍历展开成数组，那么这个数组一定是从小到大的。要验证是否是BST，只要比较相邻两个元素的大小就行了，可以用一个变量保存前一个元素的值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root, long long l = LONG_MAX,
long long r = LONG_MIN) {
if (root == nullptr)
return true;
long long val = root->val;
if (val >= l || val <= r)
return false;
return isValidBST(root->left, val, r) &&
isValidBST(root->right, l, val);
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function (root) {
let pre = -Infinity;
function dfs(node) {
if (node === null)
return true;
if (!dfs(node.left))
return false;
if (node.val <= pre)
return false;
pre = node.val;
return dfs(node.right);
}
return dfs(root);
};
二叉搜索树中第 K 小的元素
中序遍历，先递归左子树，判断k值以决定是否返回当前节点值，再递归右子树。C++注意参数k要引用传递，这样所有递归层共享一个k，找到答案（k=0时）就返回。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int &k) {
if (root == nullptr)
return -1;
int l = kthSmallest(root->left, k);
if (l != -1)
return l;
if (--k == 0)
return root->val;
return kthSmallest(root->right, k);
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function (root, k) {
function dfs(node) {
if (node === null)
return -1;
let l = dfs(node.left, k);
if (l !== -1)
return l;
if (--k === 0)
return node.val;
return dfs(node.right, k);
}
return dfs(root);
};
二叉树的右视图
用队列实现层序遍历，保存每层最后一个元素就行。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if(root == nullptr)
return {};
vector<int> v;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; ++i) {
TreeNode* node = q.front();
q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
if (i == n - 1)
v.push_back(node->val);
}
}
return v;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function (root) {
let ans = [];
if (root === null)
return ans;
const q = new Queue();
q.enqueue(root);
while (!q.isEmpty()) {
let n = q.size();
while (n--) {
let node = q.dequeue();
if (n == 0)
ans.push(node.val);
if (node.left)
q.enqueue(node.left);
if (node.right)
q.enqueue(node.right);
}
}
return ans;
};
二叉树展开为链表
dfs，先递归右子树，再递归左子树，最后处理当前节点。用head记录已展开链表的前驱节点。处理每个节点时，将其right指向head，left置空，然后更新head为当前节点。这样从后往前构建，最终得到前序遍历顺序的链表。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
TreeNode* head;
public:
void flatten(TreeNode* root) {
if (root == nullptr)
return;
flatten(root->right);
flatten(root->left);
root->left = nullptr;
root->right = head;
head = root;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var flatten = function(root) {
let head = null;
function dfs(node) {
if(node === null)
return;
dfs(node.right);
dfs(node.left);
node.left = null;
node.right = head;
head = node;
}
dfs(root);
};
从前序与中序遍历序列构造二叉树
前序遍历是根-左-右，中序遍历是左-根-右，我们只要找到前序遍历的根在中序遍历数组里的位置，就知道了这个位置左边是左子树，右边是右子树，并且能够知道左右子树的大小，以在前序遍历数组进行划分，递归构建树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
unordered_map<int, int> index;
for (int i = 0; i < n; i++)
index[inorder[i]] = i;
function<TreeNode*(int, int, int, int)> dfs =
[&](int pre_l, int pre_r, int in_l, int in_r) -> TreeNode* {
if (pre_l == pre_r)
return nullptr;
int left_size = index[preorder[pre_l]] - in_l;
TreeNode* left =
dfs(pre_l + 1, pre_l + 1 + left_size, in_l, in_l + left_size);
TreeNode* right =
dfs(pre_l + 1 + left_size, pre_r, in_l + 1 + left_size, in_r);
return new TreeNode(preorder[pre_l], left, right);
};
return dfs(0, n, 0, n);
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function (preorder, inorder) {
function dfs(pre_l, pre_r, in_l, in_r) {
if (pre_l >= pre_r)
return null;
let pos = inorder.indexOf(preorder[pre_l]);
let root = new TreeNode(preorder[pre_l]);
root.left = dfs(pre_l + 1, pre_l + 1 + pos - in_l, in_l, pos);
root.right = dfs(pre_l + 1 + pos - in_l, pre_r, pos + 1, in_r);
return root;
}
return dfs(0, preorder.length, 0, inorder.length);
};
// var buildTree = function (preorder, inorder) {
// if (preorder.length === 0 || inorder.length === 0)
// return null;
// let root = new TreeNode(preorder[0]);
// let pos = inorder.indexOf(preorder[0]);
// root.left = buildTree(preorder.slice(1, pos + 1), inorder.slice(0, pos));
// root.right = buildTree(preorder.slice(pos + 1, preorder.length), inorder.slice(pos + 1, inorder.length));
// return root;
// };
路径总和 III
暴力做法是枚举所有路径的和。更好的做法是用哈希表保存前缀和（从根节点开始的路径），假如当前路径和是sum，每次答案加上哈希表里sum - targetSum的值就行了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
int ans = 0;
if(root == nullptr)
return 0;
auto dfs = [&](this auto&& dfs, TreeNode* node, long sum) {
if (node == nullptr)
return;
sum += node->val;
ans += sum == targetSum;
dfs(node->left, sum);
dfs(node->right, sum);
};
dfs(root, 0);
return ans + pathSum(root->left, targetSum) +
pathSum(root->right, targetSum);
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {number}
*/
var pathSum = function (root, targetSum) {
let ans = 0;
const cnt = new Map();
cnt.set(0, 1);
function dfs(node, sum) {
if (node === null)
return;
sum += node.val;
ans += cnt.get(sum - targetSum) ?? 0;
cnt.set(sum, (cnt.get(sum) ?? 0) + 1);
dfs(node.left, sum);
dfs(node.right, sum);
cnt.set(sum, cnt.get(sum) - 1);
}
dfs(root, 0);
return ans;
};
二叉树的最近公共祖先
深搜，递归边界条件是什么？节点为空这个容易想到，还有就是节点为p或q时，不用再往下找了，直接返回。递归左、右子树，如果都有返回，说明找到了公共祖先。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right)
return root;
if (left)
return left;
return right;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
if(root === null || root === p || root === q)
return root;
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if(left && right)
return root;
return left ?? right;
};
二叉树中的最大路径和
二叉树中的最大路径和就是任意节点左子树最大链和与右子树最大链和与当前节点值之和的最大值，如果左/右子树节点值之和是负数，就取0。递归返回当前子树最大链和，如果把左右子树链和都返回，路径会分叉，所以要取最大。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
auto dfs = [&](auto dfs, TreeNode* node) -> int {
if (node == nullptr)
return 0;
int left = max(0, dfs(dfs, node->left));
int right = max(0, dfs(dfs, node->right));
res = max(res, left + right + node->val);
return max(left, right) + node->val;
};
dfs(dfs, root);
return res;
}
};
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function (root) {
let ans = -Infinity;
function dfs(node) {
if (node === null)
return 0;
let l = Math.max(0, dfs(node.left));
let r = Math.max(0, dfs(node.right));
ans = Math.max(ans, l + r + node.val);
return Math.max(l, r) + node.val;
}
dfs(root);
return ans;
};
岛屿数量
dfs和bfs都可以，dfs写起来更简洁一些，主要就是标记访问已经访问过的陆地格子。
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = (int)grid.size(), n = (int)grid[0].size(), ans = 0;
auto dfs = [&](this auto&& dfs, int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != '1')
return;
grid[i][j] = '2';
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
dfs(i, j);
ans++;
}
}
}
return ans;
}
};
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function (grid) {
let m = grid.length, n = grid[0].length, ans = 0;
let visited = Array.from({ length: m }, () => new Array(n).fill(false));
let dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]];
function bfs(i, j) {
const q = new Queue();
q.enqueue({ x: i, y: j });
while (!q.isEmpty()) {
const { x, y } = q.dequeue();
visited[x][y] = true;
for (const dir of dirs) {
const a = dir[0] + x, b = dir[1] + y;
if (a >= 0 && b >= 0 && a < m && b < n && !visited[a][b] && grid[a][b] === '1') {
visited[a][b] = true;
q.enqueue({ x: a, y: b });
}
}
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === '1' && !visited[i][j]) {
bfs(i, j);
++ans;
}
}
}
return ans;
};
腐烂的橘子
bfs，初始将所有腐烂的橘子加入队列，模拟橘子腐烂的过程，如果四周有新鲜橘子，就把这些橘子腐烂掉，更新队列。
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
using pii = pair<int, int>;
int ans = 0, m = grid.size(), n = grid[0].size();
queue<pii> q, tmp;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2)
q.push({i, j});
}
}
vector<pii> dirs{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
grid[x][y] = 0;
q.pop();
for (int i = 0; i < 4; ++i) {
int nxt_x = dirs[i].first + x;
int nxt_y = dirs[i].second + y;
if (nxt_x >= 0 && nxt_x < m && nxt_y >= 0 && nxt_y < n &&
grid[nxt_x][nxt_y] == 1) {
grid[nxt_x][nxt_y] = 0;
tmp.push({nxt_x, nxt_y});
}
}
if (q.empty() && !tmp.empty()) {
++ans;
q = tmp;
tmp = queue<pii>();
}
}
for (auto v : grid) {
for (auto x : v) {
if (x)
return -1;
}
}
return ans;
}
};
/**
* @param {number[][]} grid
* @return {number}
*/
var orangesRotting = function (grid) {
let m = grid.length, n = grid[0].length;
let ans = 0, fresh = 0;
let dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]];
let q = [];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 2)
q.push([i, j]);
else if (grid[i][j] === 1)
fresh++;
}
}
while (q.length && fresh) {
++ans;
const tmp = q;
q = [];
for (const [x, y] of tmp) {
for (const dir of dirs) {
let i = x + dir[0], j = y + dir[1];
if (i >= 0 && j >= 0 && i < m && j < n && grid[i][j] === 1) {
fresh--;
grid[i][j] = 2;
q.push([i, j]);
}
}
}
}
return fresh ? -1 : ans;
};
课程表
实现 Trie (前缀树)
全排列
回溯需要思考的就是1. 递归边界条件，2. 哪些参数需要更新给子问题，3. 什么时候回退。深度优先搜索所有排列方案，枚举第1位元素一直到第n位，每次枚举的元素要保证没取过。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
int n = nums.size();
vector<int> path(n), on_path(n);
auto dfs = [&](this auto&& dfs, int i) {
if (i == n) {
ans.push_back(path);
return;
}
for (int j = 0; j < n; ++j) {
if (!on_path[j]) {
path[i] = nums[j];
on_path[j] = 1;
dfs(i + 1);
on_path[j] = 0;
}
}
};
dfs(0);
return ans;
}
};
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
const path = Array(n).fill(0);
const onPath = Array(n).fill(false);
const ans = [];
const dfs = (i) => {
if (i === n) {
ans.push(path.slice());
return;
}
for (let j = 0; j < n; ++j) {
if (!onPath[j]) {
path[i] = nums[j];
onPath[j] = true;
dfs(i + 1);
onPath[j] = false;
}
}
}
dfs(0);
return ans;
};
子集
选或不选，将当前元素加入路径递归结束后恢复现场。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> v;
auto dfs = [&](this auto&& dfs, int i) {
if (i == nums.size()) {
ans.push_back(v);
return;
}
v.push_back(nums[i]);
dfs(i + 1);
v.pop_back();
dfs(i + 1);
};
dfs(0);
return ans;
}
};
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
let ans = [], v = [];
function dfs(i) {
if (i === nums.length) {
ans.push([...v]);
return;
}
dfs(i + 1);
v.push(nums[i]);
dfs(i + 1);
v.pop();
}
dfs(0);
return ans;
};
电话号码的字母组合
回溯，每次加上一个字母，递归终止条件是字符串长度与按键长度相等。
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> v{"","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
auto dfs = [&](this auto&& dfs, string s, int i) {
if (i == digits.size()) {
ans.push_back(s);
return;
}
for (auto x : v[digits[i] - '1'])
dfs(s + x, i + 1);
};
dfs("", 0);
return ans;
}
};
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
const phone = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
let ans = [];
function dfs(i, s) {
if (i === digits.length) {
ans.push(s);
return;
}
for (const x of phone[digits[i]])
dfs(i + 1, s + x)
}
dfs(0, "");
return ans;
};
组合总和
如果不选candidates[i]，递归到dfs(i+1,sum)，如果选candidates[i]，递归到dfs(i,sum+candidates[i])。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> v;
auto dfs = [&](this auto&& dfs, int i, int sum) {
if (i >= candidates.size() || sum > target)
return;
if (sum == target) {
ans.push_back(v);
return;
}
v.push_back(candidates[i]);
dfs(i, sum + candidates[i]);
v.pop_back();
dfs(i + 1, sum);
};
dfs(0, 0);
return ans;
}
};
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let ans = [];
function dfs(i, sum, v) {
if (sum > target || i === candidates.length)
return;
if (sum === target) {
ans.push([...v]);
return;
}
v.push(candidates[i]);
dfs(i, sum + candidates[i], v);
v.pop();
dfs(i + 1, sum, v);
}
dfs(0, 0, []);
return ans;
};
括号生成
如果右括号数量少于左括号数量，加上右括号继续递归；如果左括号数量少于n，加上左括号继续递归。当字符串长度达到2*n时，递归终止。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
auto dfs = [&](this auto&& dfs, int l, int r, string s) {
if (s.size() == 2 * n) {
ans.push_back(s);
return;
}
if (r < l)
dfs(l, r + 1, s + ')');
if (l < n)
dfs(l + 1, r, s + '(');
};
dfs(0, 0, "");
return ans;
}
};
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
let ans = [];
function dfs(l, r, s) {
if (s.length === 2 * n) {
ans.push(s);
return;
}
if (l > r)
dfs(l, r + 1, s + ')');
if (l < n)
dfs(l + 1, r, s + '(');
}
dfs(0, 0, "");
return ans;
};
单词搜索
如果board[i][j]与word第一个字符相同，就进行深搜，枚举(i,j)周围的四个相邻格子(x,y)，如果(x,y)没有出界并且与word下一个字符匹配，就继续递归，递归边界条件是匹配到word最后一个字符。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
vector<pair<int, int>> dirs{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
auto dfs = [&](this auto&& dfs, int i, int j, int k) {
if (k == word.size() - 1)
return true;
board[i][j] = 0;
for (auto dir : dirs) {
int x = i + dir.first, y = j + dir.second;
if (x >= 0 && y >= 0 && x < m && y < n &&
board[x][y] == word[k + 1] && dfs(x, y, k + 1))
return true;
}
board[i][j] = word[k];
return false;
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == word[0] && dfs(i, j, 0))
return true;
}
}
return false;
}
};
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
let m = board.length, n = board[0].length;
let dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];
function dfs(i, j, k) {
if (k === word.length - 1)
return true;
let res = false;
board[i][j] = '0';
for (const dir of dirs) {
let x = dir[0] + i, y = dir[1] + j;
if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] === word[k + 1])
res |= dfs(x, y, k + 1);
}
board[i][j] = word[k];
return res;
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (board[i][j] === word[0] && dfs(i, j, 0))
return true;
}
}
return false;
};
分割回文串
回溯的基本思想：选或不选当前元素，s[i]作为当前子串的最后一个字符，s[i+1]作为下一个子串的第一个字符（在当前子串是回文串的前提下选，否则不选）。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
auto isPalindrome = [&](string t) {
for (int i = 0; i <= t.size() / 2; ++i)
if (t[i] != t[t.size() - 1 - i])
return false;
return true;
};
vector<string> v;
auto dfs = [&](this auto&& dfs, int i) {
if (i == s.size()) {
ans.push_back(v);
return;
}
for (int j = i; j < s.size(); ++j) {
string t = s.substr(i, j - i + 1);
if (isPalindrome(t)) {
v.push_back(t);
dfs(j + 1);
v.pop_back();
}
}
};
dfs(0);
return ans;
}
};
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function (s) {
let ans = [], v = [];
function isPalindrome(t) {
let left = 0, right = t.length - 1;
while (left < right) {
if (t[left] !== t[right])
return false;
left++;
right--;
}
return true;
}
function dfs(i, j) {
if (j === s.length) {
ans.push([...v]);
return;
}
if (j < s.length - 1)
dfs(i, j + 1);
let t = s.slice(i, j + 1);
if (isPalindrome(t)) {
v.push(t);
dfs(j + 1, j + 1);
v.pop();
}
}
dfs(0, 0);
return ans;
};
N 皇后
哈希集合记录某列/正对角线/副对角线是否放置过皇后，如果都没有，就递归下一行。
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
unordered_set<int> col, dia1, dia2;
vector<string> v;
auto dfs = [&](this auto&& dfs, int i) {
if (i == n) {
ans.push_back(v);
return;
}
for (int j = 0; j < n; ++j) {
if (col.count(j) || dia1.count(i - j) || dia2.count(i + j))
continue;
col.insert(j);
dia1.insert(i - j);
dia2.insert(i + j);
string s(n, '.');
s[j] = 'Q';
v.push_back(s);
dfs(i + 1);
col.erase(j);
dia1.erase(i - j);
dia2.erase(i + j);
v.pop_back();
}
};
dfs(0);
return ans;
}
};
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {
let ans = [], v = [];
const col = new Set(), diag1 = new Set(), diag2 = new Set();
function dfs(i) {
if (i === n) {
ans.push([...v]);
return;
}
for (let j = 0; j < n; ++j) {
if (!col.has(j) && !diag1.has(i + j) && !diag2.has(i - j)) {
col.add(j);
diag1.add(i + j);
diag2.add(i - j);
let s = ".".repeat(j) + "Q" + ".".repeat(n - j - 1);
v.push(s);
dfs(i + 1);
col.delete(j);
diag1.delete(i + j);
diag2.delete(i - j);
v.pop();
}
}
}
dfs(0);
return ans;
};
搜索插入位置
二分查找标准模版～
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = -1, right = nums.size();
while (left + 1 < right) {
int mid = left + (right - left) / 2;
nums[mid] < target ? left++ : right--;
}
return right;
}
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
let left = -1, right = nums.length;
while (left + 1 < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] < target)
left = mid;
else
right = mid;
}
return right;
};
搜索二维矩阵
已知这个二维矩阵每行中的整数从左到右按非严格递增顺序排列，每行的第一个整数大于前一行的最后一个整数。那么把它(m * n)展开成一维矩阵(1 * mn)，应该是严格递增的，直接二分查找，中间的值对应matrix[mid / n][mid % n]。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = -1, right = m * n;
while (left + 1 < right) {
int mid = (left + right) / 2;
int x = matrix[mid / n][mid % n];
if (x == target)
return true;
(x < target ? left : right) = mid;
}
return false;
}
};
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function (matrix, target) {
const m = matrix.length, n = matrix[0].length;
let left = -1, right = m * n;
while (left + 1 < right) {
let mid = Math.floor((left + right) / 2);
let x = matrix[Math.floor(mid / n)][mid % n];
if (x == target)
return true;
if (x < target)
left = mid;
else
right = mid;
}
return false;
};
在排序数组中查找元素的第一个和最后一个位置
二分查找返回数组里大于等于target的最小下标，这个下标对应元素的第一个位置。而最后一个位置是大于等于target+1的最小下标减一。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
auto lower_bound = [&](int k) {
int left = -1, right = n;
while (left + 1 < right) {
int mid = (left + right) / 2;
(nums[mid] < k ? left : right) = mid;
}
return right;
};
int i = lower_bound(target), j = lower_bound(target + 1);
if (i == n || nums[i] != target)
return {-1, -1};
return {i, j - 1};
}
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let n = nums.length;
function lowerBound(k) {
let left = -1, right = n;
while (left + 1 < right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] < k)
left = mid;
else
right = mid;
}
return right;
}
let i = lowerBound(target), j = lowerBound(target + 1);
if (i === n || nums[i] !== target)
return [-1, -1];
return [i, j - 1];
};
搜索旋转排序数组
寻找旋转排序数组中的最小值
寻找两个正序数组的中位数
有效的括号
如果是左括号就入栈，如果是右括号就判断是否和栈顶匹配，匹配就出栈，不匹配说明不是有效的括号。
class Solution {
public:
bool isValid(string s) {
string t;
for (auto ch : s) {
if (ch == '(' || ch == '[' || ch == '{')
t += ch;
else {
if (t == "")
return false;
char x = t.back();
if ((ch == ')' && x == '(') || (ch == ']' && x == '[') ||
(ch == '}' && x == '{'))
t.pop_back();
else
return false;
}
}
return t == "";
}
};
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
let t = "";
for (const ch of s) {
if (ch === '(' || ch === '{' || ch === '[')
t += ch;
else if (t.length === 0)
return false;
else {
let x = t.at(-1);
if ((ch == ')' && x == '(') || (ch === ']' && x === '[') || (ch === '}' && x === '{'))
t = t.slice(0, -1);
else
return false;
}
}
return t.length === 0;
};
最小栈
两个栈，一个保存添加的元素，一个维护每个前缀的最小值。
class MinStack {
public:
vector<int> v, v_min;
MinStack() {}
void push(int val) {
v.push_back(val);
v_min.push_back((v_min.empty() || v_min.back() > val) ? val
: v_min.back());
}
void pop() {
v.pop_back();
v_min.pop_back();
}
int top() { return v.back(); }
int getMin() { return v_min.back(); }
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
var MinStack = function () {
this.stack = [];
this.min_stack = [Infinity];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function (val) {
this.stack.push(val);
this.min_stack.push(Math.min(this.min_stack.at(-1), val));
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
this.stack.pop();
this.min_stack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack.at(-1);
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
return this.min_stack.at(-1);
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
字符串解码
不是右括号就入栈，是右括号就一直出栈直至碰到左括号，弹出左括号后如果栈不为空，再出栈记录重复次数直至碰到非数字，将解码后的字符串重新入栈。
class Solution {
public:
string decodeString(string s) {
string ans;
for (auto ch : s) {
if (ch == ']') {
string t;
while (!ans.empty() && ans.back() != '[') {
t += ans.back();
ans.pop_back();
}
ans.pop_back();
int k = 0, bit = 1;
while (!ans.empty() && isdigit(ans.back())) {
k += (ans.back() - '0') * bit;
bit *= 10;
ans.pop_back();
}
ranges::reverse(t);
for (int i = 0; i < k; ++i)
ans += t;
} else
ans += ch;
}
return ans;
}
};
/**
* @param {string} s
* @return {string}
*/
var decodeString = function (s) {
let ans = "";
function isLetter(ch) {
return /^[a-z]$/.test(ch);
}
function isNumber(ch) {
return /^[0-9]$/.test(ch);
}
for (const ch of s) {
if (ch != ']')
ans += ch;
else {
let t = "", r = 0, bit = 0;
while (ans.length) {
let x = ans.at(-1);
ans = ans.slice(0, -1);
if (x === '[') {
while (ans.length && isNumber(ans.at(-1))) {
r = r + Number(ans.at(-1)) * (10 ** bit++);
ans = ans.slice(0, -1);
}
break;
}
t += x;
}
t = [...t].reverse().join("").repeat(r);
ans += t;
}
}
return ans;
};
每日温度
单调栈（单调递减）保存下标，如果当前温度大于栈顶温度，就出栈。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> v, res(temperatures.size());
for (int i = 0; i < temperatures.size(); ++i) {
while (v.size() && temperatures[i] > temperatures[v.back()]) {
res[v.back()] = i - v.back();
v.pop_back();
}
v.push_back(i);
}
return res;
}
};
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function (temperatures) {
let ans = new Array(temperatures.length).fill(0), tmp = [];
for (let i = 0; i < temperatures.length; ++i) {
while (tmp.length && temperatures[i] > temperatures[tmp.at(-1)]) {
let j = tmp.at(-1);
ans[j] = i - j;
tmp.pop();
}
tmp.push(i);
}
return ans;
};
柱状图中最大的矩形
数组中的第K个最大元素
最小堆，保留最大的k个数，根节点是堆中的最小元素，如果堆大小小于k，就直接加入元素，否则比较根节点和当前元素的大小，如果比当前元素小，就移出队列。
但是堆的插入/删除操作的时间复杂度是O(logk)吗，因此上述算法时间复杂度为O(nlogk)，要做到O(n)，用快排更好。
快速排序的思想就是每次随机选一个基准元素，然后进行分区操作，最后所有比基准元素小的元素都移到基准的左边，所有比基准元素大的元素都移到基准的右边，基准元素的位置也被确定。数组中的第k个最大元素对应排序后nums[n-k]，只要基准元素的下标为n-k，说明就找到了。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> q;
for (auto num : nums) {
if (q.size() < k) {
q.push(num);
} else if (q.top() < num) {
q.pop();
q.push(num);
}
}
return q.top();
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function (nums, k) {
const n = nums.length, targetIndex = n - k;
let left = 0, right = n - 1;
function partition(l, r) {
const idx = l + Math.floor(Math.random() * (r - l + 1));
const pivot = nums[idx];
[nums[idx], nums[l]] = [nums[l], nums[idx]];
let i = l + 1, j = r;
while (1) {
while (i <= j && nums[i] < pivot)
++i;
while (i <= j && nums[j] > pivot)
--j;
if (i >= j)
break;
[nums[i], nums[j]] = [nums[j], nums[i]];
++i;
--j;
}
[nums[l], nums[j]] = [nums[j], nums[l]];
return j;
}
while (1) {
const i = partition(left, right);
if (i === targetIndex)
return nums[i];
if (i < targetIndex)
left = i + 1;
else
right = i - 1;
}
};
// var findKthLargest = function (nums, k) {
// const heap = new MinPriorityQueue();
// for (const num of nums) {
// if (heap.size() < k)
// heap.enqueue(num);
// else if (heap.front() < num) {
// heap.dequeue();
// heap.enqueue(num);
// }
// }
// return heap.front();
// };
前 K 个高频元素
最小堆记录元素以及元素出现次数，出现次数优先。
用堆做的话比较简单，更优的做法是桶排序，把出现次数相同的元素放入一个桶中，倒序遍历桶更新答案。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> v;
using pii = pair<int, int>;
unordered_map<int, int> mp;
for (auto num : nums)
++mp[num];
priority_queue<pii, vector<pii>, greater<pii>> heap;
for (auto [x, y] : mp) {
if (heap.size() < k)
heap.push({y, x});
else if (heap.top().first < y) {
heap.pop();
heap.push({y, x});
}
}
while (!heap.empty()) {
v.push_back(heap.top().second);
heap.pop();
}
return v;
}
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {
const map = new Map();
for (const num of nums)
map.set(num, (map.get(num) ?? 0) + 1);
const maxCnt = Math.max(...map.values())
let buckets = new Array(maxCnt + 1).fill().map(() => []);
for (const [key, val] of map)
buckets[val].push(key);
let ans = [];
for (let i = maxCnt; ans.length < k; --i)
ans.push(...buckets[i]);
return ans;
};
// var topKFrequent = function (nums, k) {
// const map = new Map();
// for (const num of nums)
// map.set(num, (map.get(num) ?? 0) + 1);
// const heap = new MinPriorityQueue({ compare: (a, b) => a.cnt - b.cnt });
// for (const [key, val] of map) {
// if (heap.size() < k)
// heap.enqueue({ cnt: val, num: key });
// else if (heap.front().cnt < val) {
// heap.dequeue();
// heap.enqueue({ cnt: val, num: key });
// }
// }
// let ans = [];
// while (!heap.isEmpty())
// ans.push(heap.dequeue().num);
// return ans;
// };
数据流的中位数
买卖股票的最佳时机
贪心，维护一个minVal为第i个元素之前的最小价格，我们要求的就是nums[i]-minVal的最大值。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0, pre = prices[0];
for (int i = 0; i < prices.size(); ++i) {
ans = max(ans, prices[i] - pre);
pre = min(pre, prices[i]);
}
return ans;
}
};
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let ans = 0, minVal = prices[0];
for (const price of prices) {
minVal = Math.min(minVal, price);
ans = Math.max(ans, price - minVal);
}
return ans;
};
跳跃游戏
维护最远可到达位置。
class Solution {
public:
bool canJump(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); ++i) {
if(i > j)
return false;
j = max(j, i + nums[i]);
}
return true;
}
};
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function (nums) {
for (let i = 0, j = 0; i < nums.length; ++i) {
if (i > j)
return false;
j = Math.max(j, i + nums[i]);
}
return true;
};
跳跃游戏 II
维护当前和下一次的最远可到达位置。当遍历到达当前边界时，说明必须进行一次跳跃，此时更新边界并增加步数。
class Solution {
public:
int jump(vector<int>& nums) {
int ans = 0, cur = 0, nxt = 0;
for (int i = 0; i + 1 < nums.size(); ++i) {
nxt = max(nxt, i + nums[i]);
if(i == cur) {
cur = nxt;
++ans;
}
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function (nums) {
let ans = 0, cur = 0, nxt = 0;
for (let i = 0; i + 1 < nums.length; ++i) {
nxt = Math.max(nxt, i + nums[i]);
if (i == cur) {
cur = nxt;
++ans;
}
}
return ans;
};
划分字母区间
维护每个字母出现的最远位置，初始化区间左右端点，更新右端点为区间内字母出现的最大下标，如果下标正好走到右端点时，说明区间合并完毕，加入答案并更新左端点。
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> cnt(26), ans;
for (int i = 0; i < s.size(); ++i)
cnt[s[i] - 'a'] = i;
for (int i = 0, l = 0, r = 0; i < s.size(); ++i) {
r = max(r, cnt[s[i] - 'a']);
if (i == r) {
ans.push_back(r - l + 1);
l = r + 1;
}
}
return ans;
}
};
/**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function (s) {
var last = Array(26), ans = [];
for (let i = 0; i < s.length; ++i)
last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
for (let i = 0, start = 0, end = 0; i < s.length; ++i) {
end = Math.max(end, last[s.charCodeAt(i) - 'a'.charCodeAt(0)]);
if (end === i) {
ans.push(end - start + 1);
start = i + 1;
}
}
return ans;
};
爬楼梯
状态转移方程为：
class Solution {
public:
int climbStairs(int n) {
int f1 = 1, f2 = 1, f = 1;
for (int i = 2; i <= n; ++i) {
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}
};
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let f1 = 1, f2 = 1, f = 1;
for(let i = 2; i <= n; ++i) {
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
};
杨辉三角
杨辉三角每行第一个数和最后一个数是1，中间的数nums[i][j] = nums[i-1][j-1] + nums[i-1][j]。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans{{1}};
for (int r = 2; r <= numRows; ++r) {
vector<int> cur{1}, pre = ans.back();
for(int i = 1; i < pre.size(); ++i)
cur.push_back(pre[i-1]+pre[i]);
cur.push_back(1);
ans.push_back(cur);
}
return ans;
}
};
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function (numRows) {
let ans = [[1]];
for (let i = 1; i < numRows; ++i) {
let level = [1];
for (let j = 1; j < i; ++j)
level.push(ans.at(-1)[j - 1] + ans.at(-1)[j]);
level.push(1);
ans.push(level);
}
return ans;
};
打家劫舍
状态转移方程为：
class Solution {
public:
int rob(vector<int>& nums) {
int f = nums[0], f1 = 0, f2 = 0;
for (int i = 0; i < nums.size(); ++i) {
f = max(f, f1 + nums[i]);
f1 = f2;
f2 = f;
}
return f;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
let f = nums[0], f1 = 0, f2 = 0;
for (let i = 0; i < nums.length; ++i) {
f = Math.max(f, f1 + nums[i]);
f1 = f2;
f2 = f;
}
return f;
};
完全平方数
状态转移方程为：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, 10001);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j * j <= i; ++j)
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
return dp[n];
}
};
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
var dp = Array(n + 1).fill(10001);
dp[0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j ** 2 <= i; ++j)
dp[i] = Math.min(dp[i], dp[i - j ** 2] + 1);
}
return dp[n];
};
零钱兑换
f(i)表示凑成总金额i需要的最少硬币个数，状态转移方程为：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 10001);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
if (i >= coin)
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
return dp.back() < 10001 ? dp.back() : -1;
}
};
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
coins.sort((a, b) => a - b);
let dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let i = 0; i <= amount; ++i) {
for (let j = 0; j < coins.length && i >= coins[j]; ++j)
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
return dp[amount] < amount + 1 ? dp[amount] : -1;
};
单词拆分
最长递增子序列
f(i)表示以 nums[i] 结尾的最长递增子序列的长度，状态转移方程为：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size() + 1, 1);
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
let n = nums.length, dp = new Array(n).fill(1);
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
return Math.max(...dp);
};
乘积最大子数组
数组里面有负数，我们需要保存以nums[i]结尾的最大和最小的子数组乘积，状态转移方程为：
class Solution {
public:
int maxProduct(vector<int>& nums) {
int ans = nums[0], f1 = 1, f2 = 1;
for (auto num : nums) {
int x = num * f1, y = num * f2;
f1 = max({num, x, y});
f2 = min({num, x, y});
ans = max({ans, f1, f2});
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function (nums) {
let maxVal = 1, minVal = 1, ans = nums[0];
for (const num of nums) {
let x = num * maxVal, y = num * minVal;
maxVal = Math.max(num, x, y);
minVal = Math.min(num, x, y);
ans = Math.max(ans, maxVal);
}
return ans;
};
分割等和子集
要分割成两个等和子集，那么每个子集的和一定是数组总和sum的一半，如果数组总和是奇数，那么一定不能等分两个子集。
问题目标转换成数组是否存在某个子集的和是sum/2，我们可以用动态规划，思考先遍历数组还是先遍历目标值？这个其实和0-1背包是一样的，我们知道应该先遍历物品再遍历容量，因为物品只能选一个（每次只处理一个物品，确保它只被考虑一次）。那么容量应该从小到大还是从大到小遍历呢？每次更新依赖的是上一轮的状态也就是物品还没被考虑时的情况，所以是从大到小。如果是从小到大，每次更新可能依赖本轮已更新的状态，就不兑了。状态转移方程为：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum / 2;
if (sum % 2)
return false;
vector<bool> dp(target + 1);
dp[0] = true;
for (auto num : nums)
for (int j = target; j >= num; j--)
dp[j] = dp[j] || dp[j - num];
return dp[target];
}
};
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
let sum = nums.reduce((pre, val) => pre + val);
if (sum % 2)
return false;
let target = Math.floor(sum / 2), dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let i = target; i >= num; --i)
dp[i] = dp[i] || dp[i - num];
}
return dp[target];
};
最长有效括号
不同路径
状态转移方程为：
class Solution {
public:
int uniquePaths(int m, int n) {
if (m == 1 || n == 1)
return 1;
vector<vector<int>> dp(m, vector<int>(n));
dp[0][1] = dp[1][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0)
dp[i][j] += dp[i - 1][j];
if (j > 0)
dp[i][j] += dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
if(m === 1 || n === 1)
return 1;
let dp = Array.from({ length: m }, () => new Array(n).fill(0));
dp[0][1] = dp[1][0] = 1;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i > 0)
dp[i][j] += dp[i - 1][j];
if (j > 0)
dp[i][j] += dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
};
最小路径和
状态转移方程为：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
dp[0][0] = grid[0][0];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i && j)
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
else
dp[i][j] = (i ? dp[i - 1][j] : (j ? dp[i][j - 1] : 0)) +
grid[i][j];
}
}
return dp[m - 1][n - 1];
}
};
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function (grid) {
let m = grid.length, n = grid[0].length;
let dp = Array.from({ length: m }, () => new Array(n).fill(Infinity));
dp[0][0] = grid[0][0];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i && j)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
else
dp[i][j] = (i ? dp[i - 1][j] : (j ? dp[i][j - 1] : 0)) +
grid[i][j];
}
}
return dp[m - 1][n - 1];
};
最长回文子串
最长公共子序列
状态转移方程为：
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (text1[i] == text2[j])
dp[i + 1][j + 1] = 1 + dp[i][j];
else
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
return dp[m][n];
}
};
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function (text1, text2) {
let m = text1.length, n = text2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (text1[i] == text2[j])
dp[i + 1][j + 1] = 1 + dp[i][j];
else
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
return dp[m][n];
};
编辑距离
只出现一次的数字
我们知道两个相同的数字异或的结果为0，那么只要遍历元素，用异或来消除所有出现两次的数字，剩下的一定是出现一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(auto num: nums)
ans ^= num;
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
let ans = 0;
for (const num of nums)
ans ^= num;
return ans;
};
多数元素
存在严格众数，在数组中出现次数大于⌊n/2⌋，说明比其他元素出现次数加起来还要多，因此可以把众数出现次数与其他元素出现次数进行抵消。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans = 0, hp = 0;
for (auto num : nums) {
if (hp)
hp += num == ans ? 1 : -1;
else {
ans = num;
hp = 1;
}
}
return ans;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function (nums) {
let ans = 0, hp = 0;
for (const num of nums) {
if (hp)
hp += num === ans ? 1 : -1;
else {
ans = num;
hp = 1;
}
}
return ans;
};
颜色分类
比较 tricky 的做法是维护数组中0和1的次数，分别记作c0和c1，那么只要把nums[c1]之前的数改成1，nums[c0]之前的数改成0，剩下的改成2就行。
class Solution {
public:
void sortColors(vector<int>& nums) {
int zero = 0, one = 0;
for (auto num : nums) {
zero += num == 0;
one += num == 1;
}
for (int i = 0; i < nums.size(); ++i) {
if (i < zero)
nums[i] = 0;
else if (i < zero + one)
nums[i] = 1;
else
nums[i] = 2;
}
}
};
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let c0 = 0, c1 = 0;
for (let i = 0; i < nums.length; ++i) {
const x = nums[i];
nums[i] = 2;
if(x <= 1)
nums[c1++] = 1;
if(x === 0)
nums[c0++] = 0;
}
};
下一个排列
找下一个排列，如果是单调递减的，那么下一个就是单调递增的排列。如果不是，那么就找比当前排列稍微大一点的。从后往前找，如果当前元素nums[i]大于前一个元素nums[i-1]，那么说明nums[i]开始一直到数组末尾的这一整段子序列是单调递减的，再从后往前找，找到第一个nums[j]>nums[i-1]并交换两个数，再把i之后的数从小到大排序，这就是下一个排列。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size(), k = 0;
for (int i = n - 1; i > 0; --i) {
if (nums[i] > nums[i - 1]) {
for (int j = n - 1; j >= i; --j) {
if (nums[j] > nums[i - 1]) {
swap(nums[j], nums[i - 1]);
break;
}
}
k = i;
break;
}
}
sort(nums.begin() + k, nums.end());
}
};
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
let n = nums.length, k = 0;
for (let i = n - 1; i > 0; --i) {
if (nums[i] > nums[i - 1]) {
for (let j = n - 1; j >= i; --j) {
if (nums[j] > nums[i - 1]) {
[nums[j], nums[i - 1]] = [nums[i - 1], nums[j]];
break;
}
}
k = i;
break;
}
}
nums = nums.splice(k, n - k, ...nums.slice(k).sort((a, b) => a - b));
};
寻找重复数
参考灵茶山艾府: 用基环树理解，做法同 142. 环形链表 II，和“判断链表是否有环”的原理一样。如果你在位置i，下一站就去位置nums[i]，从0出发，你永远跳不出这个数组，而且永远不会回到位置 0，重复数就是环入口。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
while(1) {
slow = nums[slow];
fast = nums[nums[fast]];
if(slow == fast)
break;
}
int head = 0;
while(slow != head) {
slow = nums[slow];
head = nums[head];
}
return head;
}
};
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
for (let i = 0; i < nums.length; ++i) {
while (nums[i] != i + 1) {
let j = nums[i] - 1;
if (nums[j] === nums[i])
return nums[i];
[nums[j], nums[i]] = [nums[i], nums[j]];
}
}
};