哈希
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]提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
题解
简单题。直接枚举即可。
2. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
题解
用一个map<vector<int>, string>型的哈希表m来保存每一个字符串，其中键k为vector<int>型，长度为26，指示该字符串中每一个字符出现的次数，比如k[1]表示b出现的次数。依次遍历strs中每一个字符串str，将其加入m中。注意vector型变量可以直接用==进行判定，若两个字符串为异位词，那么它们对应的vector<int>型统计变量也完全相等。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
map<vector<int>, vector<string>> m;
for (string str: strs) {
vector<int> v(26);
for (char c: str) {
v[c-'a'] += 1;
}
if (m.count(v)) {
m[v].push_back(str);
} else {
vector<string> vs;
vs.push_back(str);
m[v] = vs;
}
}
vector<vector<string>> ans;
for (map<vector<int>, vector<string>>::iterator iter = m.begin(); iter != m.end(); iter++) {
ans.push_back(iter->second);
}
return ans;
}
};3. 最长连续子串
给定一个未排序的整数数组 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示例 3：
输入：nums = [1,0,1,2]
输出：3提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
题解
同样地，我们先用一个unordered_map<int, int>型变量m保存数组nums中元素出现的次数。然后遍历m中的键值对(k, v)。具体的，采取如下技巧：
- 对于每一个遍历到的
(k,v)，在此基础上，接着循环检测k+1,k+2,...是否存在，直至k+p不存在，该循环结束时将得到一个临时答案p，用其更新最终答案ans； - 另外注意，对于每一个遍历到的
(k,v)，若k-1存在，则直接跳过，因为按照上一步的策略我们已经考虑过这一段连续子串了。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> m;
for (int i: nums) {
m[i] += 1;
}
int ans = 0;
for (unordered_map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
int i = iter->first;
if (m.count(i-1)) {
continue;
} else {
int j = i+1;
while (m.count(j)) {
j++;
}
ans = max({ans, j - i});
}
}
return ans;
}
};双指针
4. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums = [0]
输出: [0]提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
题解
这道题非常简单。设置首尾双指针
- 指针
i，初始情况指向数组首部 - 指针
tail，初始情况指向数组尾部
若指针i指向了零元素，那么nums[i+1:tail+1]这部分应该左移、且nums[tail]应该置为零；否则i自增即可。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i, j;
int tail = nums.size() - 1;
i = 0;
while (i <= tail) {
if (nums[i]) i++;
else {
for (j=i; j<tail; j++) {
nums[j] = nums[j+1];
}
nums[tail] = 0;
tail--;
}
}
}
};5. 盛最多水的容器
给定一个长度为 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提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
题解
这道题需要先仔细分析一下，才能得出一个比较简洁的解法。首先我们也是设置首尾双指针left,right，初始情况分别指向数组头和数组尾部。关键在于每一步我们该如何移动双指针，才能确保得到最终的正确答案。
拿图中样例来分析，初始情况nums[left]=1, nums[right]=7即nums[left]<nums[right]，答案ans=(right - left) * min(height[left], height[right])；这种情况下，稍微深入分析会发现，如果我们选择向左移动right，答案一定不会比ans大！因为宽度right-left一定减小了，而高度
以此类推可以分析出nums[left]>=nums[right]的情况。
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int ans = (right - left) * min(height[left], height[right]);
while (left < right) {
if (height[left] < height[right]) {
left++;
} else {
right--;
}
int cnt = (right - left) * min(height[left], height[right]);
ans = max(ans, cnt);
}
return ans;
}
};6. 三数之和
给你一个整数数组 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 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
题解
三数之和，我们可以先固定住其中一个数，然后转化为去数组中用双指针找满足双数之和即可。于是，我们需要先对数组nums进行排序。尤其需要注意排除重复元素的情况，即三个指针i,j,k需要在遇到重复元素时进行移动。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
int i, j, k;
for (i=0; i<nums.size(); i++) {
j = i + 1, k = nums.size() - 1; // 确保三元组都是非递减排列的，避免重复
while (j < k) {
if (nums[j] + nums[k] == -nums[i]) {
vector<int> cnt;
cnt.push_back(nums[i]);
cnt.push_back(nums[j]);
cnt.push_back(nums[k]);
ans.push_back(cnt);
while (j < nums.size() - 1 && nums[j] == nums[j+1]) j++; // 排除指针j的重复情况
while (k > i + 1 && nums[k] == nums[k-1]) k--; // 排除指针k的重复情况
j++, k--;
} else if (nums[j] + nums[k] < -nums[i]) {
j++;
} else {
k--;
}
}
while (i < nums.size() - 1 && nums[i] == nums[i+1]) i++; // 排除指针i的重复情况
}
return ans;
}
};7. 接雨水
给定 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提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
题解
这一题和盛最多水的容器类似，都需要先仔细分析一下。我们不妨考虑计算每一个位置i处的雨水高度h[i]，然后总的雨水量为
具体地，我们先不考虑i处的容器高度height[i]，则i处能够容纳的雨水最大高度应为其左侧柱子最高者和右侧柱子最高者的较小者，进一步地，若该值不高于height[i]，则能够容纳的雨水最大高度h[i]就是0，否则应为该值减去height[i]。
有
class Solution {
public:
int trap(vector<int>& height) {
int leftH[200005];
int rightH[200005];
int n = height.size();
int i, j;
leftH[0] = height[0], rightH[n-1] = height[n-1];
int temp = height[0];
for (i=1; i<n; i++) {
if (height[i-1] > temp) {
temp = height[i-1];
}
leftH[i] = temp;
}
temp = height[n-1];
for (i=n-2; i>=0; i--) {
if (height[i+1] > temp) {
temp = height[i+1];
}
rightH[i] = temp;
}
int ans = 0;
for (i=0; i<n; i++) {
int vol = min(leftH[i], rightH[i]) - height[i];
ans += vol > 0 ? vol : 0;
}
return ans;
}
};滑动窗口
8. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
题解
我们有一个比较自然的想法：用双指针left,right共同维护一个滑动窗口，同时时刻维护一个记录子串s[left:right]中字符出现情况的哈希表unordered_map<char, int> m。整个过程包含扩张、收缩两个部分：
- 扩张。此时固定住左指针
left，不断地右移右指针right，要注意要同时更新m，即时刻将m[s[right]]置为1； - 收缩。在扩张至极限后，固定住右指针，将左指针
left右移一步，同时将m[s[left]]置为0。
注意扩张至极限后（循环结束），记录此时得到的答案，然后对全局答案ans进行更新即可。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int left, right;
left = 0, right = 0;
int n = s.size();
int ans = 0;
while (left < n && right < n) {
// 扩张
while (right < n && m[s[right]] == 0) {
m[s[right++]] = 1;
}
// 停止扩张,此时s[left:right]必定无重复字符
ans = max(ans, right - left);
m[s[left++]] = 0; // 收缩一个字符，即左指针往后移动一步
}
return ans;
}
};9. 找到字符串中的所有字母异位词
给定两个字符串 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 <= s.length, p.length <= 3 * 104s和p仅包含小写字母
题解
此题和“字母异位词分组”解法类似。同样地，我们用双指针left,right维护一个滑动窗口，再维护一个vector<int>型变量cnt维护子串s[left:right]（注意right指向滑动窗口末位字符的下一个）内字符出现的次数。我们在一开始就用label记录目标字符串p中各个字符的出险次数，然后在滑动窗口不断滑动（每次将left,right不断往后移动一步）时注意更新cnt，判定cnt==p是否成立，如果成立则将当前的左指针left索引记录下来。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
if (s.size() < p.size()) return ans;
vector<int> label(26, 0);
for (char c: p) {
label[c-'a']++;
}
vector<int> cnt(26, 0);
int left, right;
left = 0;
// 初始情况下的滑动窗口，左右指针就位，注意right指向当前滑动窗口的下一个字符
for (right=left; right<left+p.size(); right++) {
cnt[s[right]-'a']++;
}
while (true) {
if (cnt == label) {
ans.push_back(left);
}
if (right == s.size()) break;
// 左指针、右指针均右移
cnt[s[left++]-'a']--, cnt[s[right++]-'a']++;
}
return ans;
}
};子串
10. 和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
int n = nums.size();
int i, j;
int arr[20005];
for (i=0; i<n; i++) arr[i] = nums[i];
for (i=0; i<n; i++) {
// 起始索引 i
int sum = 0;
for (j=0; i+j<n; j++) {
// nums[i], nums[i+1], ...
sum += arr[i+j];
if (sum == k) {
ans++;
}
}
}
return ans;
}
};11. 滑动窗口最大值
给你一个整数数组 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 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
题解
此题需要一定技巧。我们时刻维护一个大小为k的大顶堆H（堆顶元素为当前最大值）。比如初始情况下，我们将数组前k个元素加入H中，堆顶元素即为当前初始的滑动窗口最大值。随着窗口往右滑动，将新元素加入H中，会更新当前的最大值。但是如此做，会出现一个问题：堆顶元素很可能不在滑动窗口范围内，即不是当前滑动窗口的最大值。
改进方法是，我们将堆中元素类型设计为pair<int, int>，第一个元素表示值，第二个元素表示其在nums中的索引，用于检测当前堆顶元素是否在滑动窗口范围内。如果不在该范围内，则将当前堆顶元素弹出，检测新的堆顶元素，以此反复直至堆顶元素（当前最大者）索引落在当前滑动窗口之中。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
auto comp = [](pair<int, int> p1, pair<int, int> p2) {
return p1.first < p2.first;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)>
pq;
vector<int> ans;
int i;
// 0 ~ k-1
for (i = 0; i < k; i++) {
pq.push({nums[i], i});
}
while (i <= nums.size()) {
// i-k ~ i-1
auto top = pq.top();
if (top.second >= i - k && top.second <= i - 1) {
ans.push_back(top.first);
} else {
while (!pq.empty()) {
auto top = pq.top();
if (top.second >= i - k && top.second <= i - 1) {
break;
} else {
pq.pop();
}
}
ans.push_back(pq.top().first);
}
if (i != nums.size()) {
pq.push({nums[i], i});
}
i++;
}
return ans;
}
};注意
需要额外留意C++自定义堆元素比较器的实现方式，参考上述代码中的相关代码块。
auto comp = [](pair<int, int> p1, pair<int, int> p2) {
return p1.first < p2.first; // < 表示大根堆（默认）；> 表示小根堆
};12. 最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在 O(m + n) 时间内解决此问题的算法吗？
题解
滑动窗口。通常来说，滑动窗口用两个指针表示，左指针l和右指针r。在窗口进行滑动时，只能移动其中一个指针而固定另一个。
- 固定左指针，移动右指针，此时为扩张
- 固定右指针，移动左指针，此时为收缩
为了检测滑动窗口是否覆盖字符串t，需要编写一个函数check，来判断是否覆盖：如果覆盖，且左指针不超过右指针，那么就进行收缩操作；而最外层的循环为扩展操作，内层循环为收缩操作。
class Solution {
public:
string minWindow(string s, string t) {
map<char, int> m;
map<char, int> label;
for (char ch: t) label[ch] += 1;
int i, j;
i = 0, j = 0;
int start = 0; // 最优子串起点
int len = INT_MAX; // 最优子串长度
int valid = 0; // 当前滑动窗口中匹配字符串t中的不同字符数量，valid==label.size()时完全匹配
while (j < s.size()) {
// 扩张，若不完全匹配valid != label.size()，则不断扩张，右移右指针j++
char ch = s[j];
j++;
if (label.count(ch)) {
m[ch]++;
if (m[ch] == label[ch]) {
valid++;
}
}
// 收缩，右移左指针，i++
while (valid == label.size()) {
if (j - i < len) {
start = i;
len = j - i;
}
char ch = s[i];
if (label.count(ch)) {
m[ch]--;
if (m[ch] < label[ch]) {
valid--;
}
}
i++;
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};普通数组
13. 最大子数组和
给你一个整数数组 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提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
题解
此题可以用动态规划求解。我们可以设置一个动态数组int dp[n]，其中dp[i]表示以nums[i]为结尾的连续子数组的最大和。考虑dp[i+1]，不难发现，
- 若
dp[i]>0，dp[i+1]=dp[i]+nums[i+1]； - 否则，此时必有
nums[i+1]+dp[i]<=nums[i+1]，于是有dp[i+1]=nums[i+1]。
最后遍历数组dp[0:n]即可。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int lastSum = ans;
int i, j;
for(i=1; i<nums.size(); i++) {
int newSum = 0;
if (lastSum <= 0) {
newSum = nums[i];
} else {
newSum = lastSum + nums[i];
}
lastSum = newSum;
ans = ans > newSum ? ans : newSum;
}
return ans;
}
};14. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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] 可被视为重叠区间。示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
题解
可以以第一个例子进行简要分析。我们的解法核心是对给出的数组intervals进行非递减排序，即按照区间开始值非递减排序。然后逐个进行分析。初始情况下，我们将intervals[0]直接添加到备选答案vector<vector<int>> ans中，然后逐个遍历取出intervals剩下的区间元素intervals[i], 1<=i<intervals.size()，记p=ans.size()-1，即考虑ans数组尾元素：
- 若
ans[p][1]>=intervals[i][1]，表示已经完全包含了目标区间； - 若
ans[p][1]>=intervals[i][0]，表示当前区间尾部和目标区间头有交集部分，则更新当前区间尾部即可。 - 若
ans[p][1]<intervals[i][0]，表示当前区间尾部和目标区间头没有交集部分，则直接添加目标区间。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> ans;
int i;
ans.push_back(intervals[0]);
for (i=1; i<intervals.size(); i++) {
int p = ans.size() - 1;
if (ans[p][1] >= intervals[i][1]) continue;
if (ans[p][1] >= intervals[i][0]) {
ans[p][1] = intervals[i][1];
} else {
ans.push_back(intervals[i]);
}
}
return ans;
}
};15. 轮转数组
给定一个整数数组 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 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
题解
一种比较简单的做法是，额外复制一份数组，然后基于该数组对原数组进行修改。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
vector<int> temp;
for (int n: nums) temp.push_back(n);
int i, j;
k = k % nums.size();
i = 0, j = nums.size()-k;
for (i=0; i<nums.size(); i++) {
nums[i] = temp[j%nums.size()];
j++;
}
}
};16. 除了自身以外数组的乘积
给你一个整数数组 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]提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
题解
此题因为要求出除开自身以外的全部元素之积，且不能使用除法，所以我们可以考虑用两个数组left[n],right[n]分别记录某元素左侧、右侧全部元素之积，随后取出对应值再做乘法即可。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int left[100005];
int right[100005];
left[0] = 1, left[1] = nums[0], right[nums.size()-1] = 1, right[nums.size()-2] = nums[nums.size()-1];
int i;
for (i=2; i<nums.size(); i++) left[i] = nums[i-1]*left[i-1];
for (i=nums.size()-3; i>=0; i--) right[i] = nums[i+1]*right[i+1];
vector<int> ans;
for (i=0; i<nums.size(); i++) ans.push_back(left[i]*right[i]);
return ans;
}
};17. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
题解
这个题由于题干要求只用O(1)额外存储空间，于是有一个比较自然的想法：能否利用输入的nums数组以节约存储空间？
事实上，若没有这项限制，我们会想到用一个哈希表存储每个正整数出现与否，然后从1开始逐个遍历即可，但是如此做的空间复杂度为O(n)。思考一下会发现，对于长度为N的输入数组nums，对应缺失的第一个正整数一定在[1,N+1]，绝不可能大于N+1。因此，我们可以遍历nums中的每一个元素x，然后将其视作数组下标，到nums[x-1]处打上标记以示x出现过。
打标记是本题的关键。因为原始的数组元素取值范围覆盖了整个INT类型，因此不能直接标记为某个int类型数字。但是考虑到答案范围一定在[1,N+1]，如果我们能够将非正整数（他们不会影响最后的答案）替换成某个也不会影响最后答案的正整数，那么就可以用任意一个负数（比如-1）来作为标记了。极端一点，我们可以先对nums进行一次遍历，将其中出现的所有的非正整数替换为INT_MAX。
对nums中的每一个元素x，我们即将标记nums[x-1]=-1，此时需要先存储nums[x-1]的值为temp，并在当前一步打标记后令x=temp循环处理。如果发现x>n或者x==-1，直接退出循环，表示当前一轮标记结束。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
int i;
for (i=0; i<n; i++) {
if (nums[i] <= 0) nums[i] = INT_MAX;
}
for (i=0; i<n; i++) {
int x = nums[i];
if (x == -1) continue;
while (x <= n && x != -1) {
int temp = nums[x-1];
nums[x-1] = -1;
x = temp;
}
}
for (i=0; i<n; i++) {
if (nums[i] != -1) return i + 1;
}
return i + 1;
}
};18. 矩阵置零
给定一个 *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]]提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
进阶：
- 一个直观的解决方案是使用
O(*m**n*)的额外空间，但这并不是一个好的解决方案。 - 一个简单的改进方案是使用
O(*m* + *n*)的额外空间，但这仍然不是最好的解决方案。 - 你能想出一个仅使用常量空间的解决方案吗？
题解
此题一个比较简单的做法是，维护两个集合rows,cols，分别记录原数组中每一个零出现过的行索引和列索引。然后根据rows,cols中的值对原数组进行修改。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
set<int> rows, cols;
int i, j;
int m = matrix.size(), n = matrix[0].size();
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
if (!matrix[i][j]) {
rows.insert(i);
cols.insert(j);
}
}
}
for (int r: rows) {
for (j=0; j<n; j++) {
matrix[r][j] = 0;
}
}
for (int c: cols) {
for (i=0; i<m; i++) {
matrix[i][c] = 0;
}
}
}
};19. 螺旋矩阵
给你一个 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]提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
题解
这道题的一个比较可行的思路是，将整个螺旋矩阵的打印顺序，看做不同层的矩阵，即分为若干圈，每一圈按照顺时针顺序返回元素即可。具体来说，可以单独实现一个接收(x1, y1, x2, y2)的函数，它实现按顺时针返回由(x1, y1)和(x2, y2)围成的矩形外圈元素，即依次取出四条边的元素即可。但是需要注意特殊情况：x1==x2以及y1==y2时，矩形退化为单条边。
class Solution {
public:
vector<int> ans;
void putVec(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2) {
int i;
if (x1 == x2) {
for (i=y1; i<=y2; i++) ans.push_back(matrix[i][x2]);
return;
}
if (y1 == y2) {
for (i=x1; i<=x2; i++) ans.push_back(matrix[y1][i]);
return;
}
for (i=x1; i<x2; i++) ans.push_back(matrix[y1][i]);
for (i=y1; i<y2; i++) ans.push_back(matrix[i][x2]);
for (i=x2; i>x1; i--) ans.push_back(matrix[y2][i]);
for (i=y2; i>y1; i--) ans.push_back(matrix[i][x1]);
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int x1 = 0, y1 = 0, x2 = n-1, y2 = m-1;
while (x1 <= x2 && y1 <= y2) {
putVec(matrix, x1, y1, x2, y2);
x1++, y1++, x2--, y2--;
}
return ans;
}
};20. 旋转图像
给定一个 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]]提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
题解
此题如果掌握一个技巧便非常简单：对矩阵A做顺时针旋转，等价于对矩阵A先做转置，再做水平翻转。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int i, j;
int n = matrix.size();
for (i=0; i<n; i++) {
for (j=i+1; j<n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
for (i=0; i<n; i++) {
for (j=0; j<n/2; j++) {
swap(matrix[i][j], matrix[i][n-1-j]);
}
}
}
};21. 搜索二维矩阵Ⅱ
编写一个高效的算法来搜索 *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提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109 <= target <= 109
题解
我们可以先实现一个二分搜索函数func(vec, target)，它可以对某个有序数组vec进行$\mathcal{O}(\log n)$级别的对元素target的搜索，然后我们对矩阵的每一行都调用func(matrix[i], target)即可。
class Solution {
public:
bool search(vector<int>& vec, int target) {
int lower = 0, upper = vec.size() - 1;
while (lower <= upper) {
int mid = lower + (upper - lower) / 2;
if (vec[mid] == target) return true;
else if (vec[mid] < target) lower = mid + 1;
else upper = mid - 1;
}
return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i;
for (i=0; i<matrix.size(); i++) {
if (matrix[i][0] > target) break;
if (search(matrix[i], target)) return true;
}
return false;
}
};22. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表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
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
题解一
一个非常简单的想法是，维护两个哈希表map<ListNode*, int> mapA, mapB，分别记录两个链表的结点出现情况，然后到两张表中查询，判定是否出现重复的键即可。
/**
* 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) {
map<ListNode*, int> mapA, mapB;
while(headA && headB) {
mapA[headA] = 1, mapB[headB] = 1;
if (mapA[headB]) return headB;
if (mapB[headA]) return headA;
headA = headA->next, headB = headB->next;
}
while(headA) {
if(mapB[headA]) return headA;
headA = headA->next;
}
while(headB) {
if(mapA[headB]) return headB;
headB = headB->next;
}
return NULL;
}
};题解二
使用双指针的方法，可以将空间复杂度降至 O(1)。
只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
每步操作需要同时更新指针 pA 和 pB。
如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
证明
下面提供双指针方法的正确性证明。考虑两种情况，第一种情况是两个链表相交，第二种情况是两个链表不相交。
情况一：两个链表相交
链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。
如果 a=b，则两个指针会同时到达两个链表相交的节点，此时返回相交的节点；
如果 $a\ne b$，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
情况二：两个链表不相交
链表 headA 和 headB 的长度分别是 m 和 n。考虑当 m=n 和 $m\ne n$ 时，两个指针分别会如何移动：
如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；
如果$m\ne n$，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};23. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
题解
我们的基本思路是，不断地遍历原链表中的每一个结点，将其加到链表头。具体而言，我们时刻维护一个指向当前链表头结点的指针head，当考虑的链表结点为p时，
- 首先我们需要获取它的下一个结点并存下来：
nextNode = p->next； - 然后将结点
p加到链表头部：p->next = head； - 别忘了更新指针
head：head = p； - 同时考虑下一个结点：
p = nextNode；
特别地，当p为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* reverseList(ListNode* head) {
if (head == NULL) return NULL;
ListNode* p = head;
head = NULL;
while (p) {
ListNode* nextNode = p->next;
p->next = head;
head = p;
p = nextNode;
}
return head;
}
};24. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true示例 2：
输入：head = [1,2]
输出：false提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
题解
一个非常简单的做法，将链表一次遍历，将读取到的全部元素存到数组中，利用数组随机访问的优势，可以快速实现回文判定。
/**
* 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) {
vector<int> v(100005);
int length = 0;
while (head) {
v[length++] = head->val;
head = head->next;
}
int i = 0, j = length - 1;
while (i < j) {
if (v[i] == v[j]) {
i++;
j--;
} else return false;
}
return true;
}
};题解二
先用快慢指针找到链表的中间结点，然后将后半段链表进行反转，将前半段链表和后半段反转后的链表进行对比，即可判定是否为回文链表。
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode* firstHalfEnd = endOfFirstHalf(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
ListNode* endOfFirstHalf(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};25. 环形链表1
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
题解
此题是经典的快慢指针做法。设置快指针fastPt和慢指针slowPt，前者每一次移动走两个结点，后者走一个结点，若两个结点出现了相遇（fastPt==slowPt），则判定有环。
/**
* 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 *fastPt, *slowPt;
fastPt = head, slowPt = head;
while (fastPt && slowPt) {
if (fastPt->next == NULL || fastPt->next->next == NULL) return false;
if (slowPt->next == NULL) return false;
fastPt = fastPt->next->next;
slowPt = slowPt->next;
if (fastPt == slowPt) return true;
}
return false;
}
};26. 环形链表2
给定一个链表的头节点 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
解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
题解
在环形链表1的快慢指针解法基础上，略做修改即可解出本题。具体而言，在fastPt和slowPt相遇时，我们此时再用一个新指针ptr指向链表头结点，随后ptr和慢指针同步移动，当两者相遇时，即为链表入口结点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};27. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = []
输出：[]示例 3：
输入：l1 = [], l2 = [0]
输出：[0]提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
题解
如果对归并排序有所了解，对此题做法应当不会陌生。在归并排序的合并阶段，我们会对两个有序数组进行合并；此处则是对两条有序链表进行合并，因此做法是类似的，唯独需要额外考虑链表的结点操作。
- 我们用新指针
head作为合并后链表（称之为新链表）的头结点 - 用两个指针
prev1, prev2分别指向两个链表，初始情况即两个链表的头结点 - 每次判定
prev1->val和prev2->val的大小关系，视情况将较小的结点剪切至新链表中，并移动对应的指针prev1或者prev2 - 最后需要将剩余的链表直接整体剪切至新链表尾部
/**
* 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* prev1 = list1;
ListNode* prev2 = list2;
ListNode* head = new ListNode();
ListNode* p = head;
while (prev1 && prev2) {
if (prev1->val < prev2->val) {
head->next = prev1;
prev1 = prev1->next;
} else {
head->next = prev2;
prev2 = prev2->next;
}
head = head->next;
}
while (prev1) {
head->next = prev1;
prev1 = prev1->next;
head = head->next;
}
while (prev2) {
head->next = prev2;
prev2 = prev2->next;
head = head->next;
}
return p->next;
}
};28. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
题解
/**
* 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) {
int c = 0;
ListNode* head = new ListNode(1);
ListNode* p = head;
while (l1 && l2) {
int sum = (l1->val + l2->val + c) % 10;
c = (l1->val + l2->val + c) / 10;
ListNode* newNode = new ListNode(sum);
newNode->next = NULL;
head->next = newNode;
head = head->next;
l1 = l1->next, l2 = l2->next;
}
while (l1) {
int sum = (l1->val + c) % 10;
c = (l1->val + c) / 10;
ListNode* newNode = new ListNode(sum);
newNode->next = NULL;
head->next = newNode;
head = head->next;
l1 = l1->next;
}
while (l2) {
int sum = (l2->val + c) % 10;
c = (l2->val + c) / 10;
ListNode* newNode = new ListNode(sum);
newNode->next = NULL;
head->next = newNode;
head = head->next;
l2 = l2->next;
}
if (c) {
ListNode* newNode = new ListNode(c);
newNode->next = NULL;
head->next = newNode;
head = head->next;
}
return p->next;
}
};29. 删除链表的倒数第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]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
题解
双指针实现。设置两个指针fast和slow，指针fast先往前移动n个结点，随后两个结点再不断地同步移动，直至fast==NULL，此时指针slow->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* removeNthFromEnd(ListNode* head, int n) {
ListNode* p = new ListNode();
p->next = head;
if (head->next == NULL) return NULL;
ListNode* slow, *fast;
slow = p, fast = p;
int i;
for (i=0; i<n; i++) fast = fast->next;
while (slow && fast) {
if (fast->next == NULL) break;
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return p->next;
}
};30. 两两交换链表中的结点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]示例 2：
输入：head = []
输出：[]示例 3：
输入：head = [1]
输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
题解
此题做法有点类似反转链表，对某一次操作做分析即可。详情见代码，我们设置了四个指针，来完成两两交换的过程。
/**
* 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 *p1, *p2, *p3, *p4;
p1 = new ListNode();
p1->next = head;
head = p1;
p2 = p1->next;
if (p2 == NULL) return head->next;
p3 = p2->next;
if (p3 == NULL) return head->next;
p4 = p3->next;
while(true) {
p1->next = p3;
p3->next = p2;
p2->next = p4;
if (p4 == NULL || p4->next == NULL) break;
p4 = p4->next->next;
p1 = p2;
p2 = p1->next;
p3 = p2->next;
}
return head->next;
}
};31. 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]提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
题解
此题难度虽大，但是可以化整为零进行求解。具体来说，我们可以先实现一个链表反转函数reverseList(ListNode* head)，这个函数实现起来比较简单。随后，我们将原先的链表按照每k个结点进行切分，存入一个数组vector<ListNode*> vm中，然后将vm中的每一条链表送入reverseList函数，得到反转后的链表，拼接起来即可。
/**
* 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) {
if (head == NULL) return NULL;
ListNode* p = head;
head = NULL;
while (p) {
ListNode* nextNode = p->next;
p->next = head;
head = p;
p = nextNode;
}
return head;
}
ListNode* reverseKGroup(ListNode* head, int k) {
vector<ListNode*> vm;
int n = 0;
ListNode* p = head;
while(p) {
n++;
p = p->next;
}
int c = n / k;
int i = 1;
p = head;
vm.push_back(p);
while (p) {
if (i % k == 0) {
ListNode* nextP = p->next;
p->next = NULL;
p = nextP;
vm.push_back(p);
} else {
p = p->next;
}
i++;
}
vector<ListNode*> ansvm;
for(i=0; i<vm.size(); i++) {
if (i != vm.size() - 1) ansvm.push_back(reverseList(vm[i]));
else {
if (n % k) ansvm.push_back(vm[i]);
else ansvm.push_back(reverseList(vm[i]));
}
}
ListNode* ans = ansvm[0];
for(i=0; i<ansvm.size()-1; i++) {
ListNode* p =ansvm[i];
while(p->next) p = p->next;
p->next = ansvm[i+1];
}
return ans;
}
};32. 随机链表的复制
给你一个长度为 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]]提示：
0 <= n <= 1000-104 <= Node.val <= 104Node.random为null或指向链表中的节点。
题解
此题非常关键的是需要实现“深拷贝”，也即完全创建新的结点。一个比较自然的想法是：
- 遍历旧链表，维护一个
unordered_map<Node*, Node*> randomMap，存储旧链表中旧结点和其随机指向结点的对应关系； - 再次遍历旧链表，同步地创建新链表（需要取出对应的结点值），然后同时维护一个
unordered_map<Node*, Node*> newMap，存储新结点和旧结点之间的对应关系； - 最后遍历一次新链表，根据
newMap, randomMap取到每个新结点应当指向的随机结点中的值即可，创建等值的结点作为Node.random。
/*
// 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) {
map<Node*, Node*> randomMap;
map<Node*, Node*> newMap;
if (!head) return head;
Node* p = head;
while(p) {
randomMap[p] = p->random;
p = p->next;
}
Node* newHead = new Node(head->val);
p = newHead;
newMap[head] = newHead;
Node* p1 = head->next;
while(p1) {
Node* temp = new Node(p1->val);
newMap[p1] = temp;
temp->next = NULL;
p->next = temp;
p = p->next;
p1 = p1->next;
}
newMap[NULL] = NULL;
p = newHead;
p1 = head;
while(p && p1) {
p->random = newMap[p1->random];
p = p->next;
p1 = p1->next;
}
return newHead;
}
};33. 排序链表[待求解]
给你链表的头结点 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 = []
输出：[]提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
题解
此题可以用链表式的归并排序解决。回顾数组的归并排序算法Merge：
- Divide：将数组尽可能均等地划分为前后各一半，递归地对各自两半数组进行
Merge； - Conquer：此时前后两半数组已经有序了，需要将这两个有序子数组合并为一个有序数组。
于是，在链表背景下，
- Divide阶段，可以用快慢指针获取前一半链表和后一半链表；
- Conquer阶段，将两部分的有序链表进行合并，参考“合并两个有序链表”求解方案。
/**
* 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* mergeSort(ListNode* head, ListNode* tail) {
if (!head) return head;
if (head->next == tail) {
head->next = NULL;
return head;
}
ListNode* slow;
ListNode* fast;
slow = fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* head1 = mergeSort(head, slow);
ListNode* head2 = mergeSort(slow, tail);
return merge(head1, head2);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode();
ListNode* p = head;
ListNode* p1 = l1;
ListNode* p2 = l2;
while (p1 && p2) {
if (p1->val < p2->val) {
p->next = p1;
p1 = p1->next;
} else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1) {
p->next = p1;
} else if (p2) {
p->next = p2;
}
return head->next;
}
ListNode* sortList(ListNode* head) {
return mergeSort(head, NULL);
}
};34. 合并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 = [[]]
输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
题解
此题有一个比较简单的求解方法。因为我们已经求解过“合并两个有序链表”，于是我们可以先实现一个函数mergeTwoList，它用来合并两个有序链表；随后我们初始化一个答案链表ListNode* ans = NULL;，不断地对链表数组lists中的每一个链表lists[i]和ans进行两两合并，并将结果更新ans。
/**
* 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* mergeTwoList(ListNode* head1, ListNode* head2) {
if (!head1) return head2;
if (!head2) return head1;
ListNode* p1 = head1;
ListNode* p2 = head2;
ListNode* head = new ListNode();
ListNode* p = head;
while (p1 && p2) {
if (p1->val > p2->val) {
head->next = p2;
p2 = p2->next;
} else {
head->next = p1;
p1 = p1->next;
}
head = head->next;
}
if (p1) head->next = p1;
if (p2) head->next = p2;
return p->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans = NULL;
if (lists.size() == 0) return ans;
for (ListNode* p: lists) {
ans = mergeTwoList(ans, p);
}
return ans;
}
};35. 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 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
题解
实现LRU，可以用哈希表+双向链表实现：
- 双向链表中，越靠近头结点的，便是越新的缓存；
- 越靠近尾结点的，则越旧。
具体而言，
- 我们时刻维护一个哈希表
unordered_map<int, ListNode*> m，用于记录每一个键和其对应结点的对应关系； - 随后，我们时刻维护一个双向链表
- 当调用
int get(int key)方法的同时，将结点m[key]移动至双向链表头部 - 当调用
void put(int key, int value)方法的同时，若结点不存在，则直接创建新结点并移动至链表头部（若链表满了则直接将尾结点删除，对应的更改哈希表）；若结点存在，则更新结点并将其移动至链表头部
- 当调用
class LRUCache {
public:
struct ListNode {
int val;
int key;
ListNode* prev;
ListNode* next;
ListNode() : key(0), val(0), prev(nullptr), next(nullptr) {}
ListNode(int x, int y) : key(x), val(y), prev(nullptr), next(nullptr) {}
ListNode(int x, ListNode* prev, ListNode* next)
: key(0), val(x), prev(prev), next(next) {}
};
int n;
int size = 0;
unordered_map<int, ListNode*> m;
ListNode* head;
ListNode* tail;
LRUCache(int capacity) {
head = new ListNode();
tail = new ListNode();
head->next = tail;
head->prev = NULL;
tail->prev = head;
tail->next = NULL;
n = capacity;
}
void moveToHead(ListNode* p) {
ListNode* pnext = p->next;
ListNode* pprev = p->prev;
pnext->prev = pprev;
pprev->next = pnext;
p->next = head->next;
p->prev = head;
head->next->prev = p;
head->next = p;
}
int get(int key) {
if (m.count(key)) {
ListNode* p = m[key];
moveToHead(p);
return p->val;
} else
return -1;
}
void put(int key, int value) {
if (m.count(key)) {
ListNode* p = m[key];
p->val = value;
moveToHead(p);
} else {
ListNode* node = new ListNode(key, value);
m[key] = node;
head->next->prev = node;
node->next = head->next;
node->prev = head;
head->next = node;
if (size == n) {
m.erase(tail->prev->key);
tail->prev->prev->next = tail;
tail->prev = tail->prev->prev;
} else {
size++;
}
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/二叉树
36. 中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解
/**
* 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:
void inorder(vector<int>& nums, TreeNode* root) {
if (root == NULL) {
return;
} else {
inorder(nums, root->left);
nums.push_back(root->val);
inorder(nums, root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
inorder(ans, root);
return ans;
}
};37. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3示例 2：
输入：root = [1,null,2]
输出：2提示：
- 树中节点的数量在
[0, 104]区间内。 -100 <= Node.val <= 100
题解
此题也是经典的二叉树递归求解。考虑一个函数int maxDepth(TreeNode* root)，它返回以root为根结点的子树的最大深度。不难发现，以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:
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDep = maxDepth(root->left);
int rightDep = maxDepth(root->right);
return 1 + (leftDep > rightDep ? leftDep : rightDep);
}
};38. 翻转二叉树
给你一棵二叉树的根节点 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 = []
输出：[]提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
题解
用递归方式实现。单独实现一个函数void invert(TreeNode* node)，原地对以node为根结点的子树进行翻转。用临时指针TreeNode* temp保存左子树或者右子树，进行交换即可。
/**
* 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:
void invert (TreeNode* node) {
if (node == NULL) return;
if (node->left) {
invert(node->left);
}
if (node->right) {
invert(node->right);
}
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
};39. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
题解
我们采取递归的方式解决此题。具体地，我们单独实现一个判定函数bool isTwoNodeSymmetric(TreeNode* node1, TreeNode* node2)，用于判定两个结点的值是否相等。另外需要注意若两个结点中只有一个为空时，直接返回false；若两个结点均为空，直接返回true。
/**
* 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 isTwoNodeSymmetric(TreeNode* node1, TreeNode* node2) {
if (node1 && !node2) return false;
if (node2 && !node1) return false;
if (!node1 && !node2) return true;
if (node1->val != node2->val) return false;
return isTwoNodeSymmetric(node1->left, node2->right) && isTwoNodeSymmetric(node1->right, node2->left);
}
bool isSymmetric(TreeNode* root) {
return isTwoNodeSymmetric(root, root);
}
};40. 二叉树的直径[待求解]
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。示例 2：
输入：root = [1,2]
输出：1提示：
- 树中节点数目在范围
[1, 104]内 -100 <= Node.val <= 100
题解
我们仍用递归方式求解。具体地，单独实现一个函数int depth(TreeNode* node, int &ans)，它用于计算以node为根结点的子树的深度，同时更新二叉树的直径ans。
- 递归求出左子树、右子树的深度
L,R后，当前子树的直径ans=max({L+R+1, ans})； - 当前子树的深度为
max({L, R})+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:
int depth(TreeNode* node, int &ans) {
if (node == NULL) return 0;
int L = depth(node->left, ans);
int R = depth(node->right, ans);
ans = max({L + R + 1, ans});
return max({L, R}) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
depth(root, ans);
return ans - 1;
}
};41. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
题解
此题用广度优先遍历即可，但是需要注意分层返回结点，要实现这点，我们可以将队列中的每一个元素改为vector<TreeNode*>而不是TreeNode*，即维护队列queue<vector<TreeNode*>> Q，其中每一个元素为二叉树的某一层的全部结点值组成的数组。
/**
* 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) {
vector<vector<int>> ans;
queue<vector<TreeNode*>> Q;
if (root == NULL) return ans;
vector<TreeNode*> v;
v.push_back(root);
Q.push(v);
while (!Q.empty()) {
vector<TreeNode*> top = Q.front();
Q.pop();
vector<int> subVec;
vector<TreeNode*> newItem;
for (TreeNode* node: top) {
subVec.push_back(node->val);
if (node->left) newItem.push_back(node->left);
if (node->right) newItem.push_back(node->right);
}
if (newItem.size()) Q.push(newItem); // 如果当前层有结点才入队，否则newItem只是一个空数组
ans.push_back(subVec);
}
return ans;
}
};42. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 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 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
题解
此题我们每次只需找数组的中间元素，将其作为待构建的结点，将其加到已构建的二叉搜索树中。具体而言，我们单独实现一个递归构建的函数void findRoot(vector<int>& nums, int left, int right, TreeNode*& p)，其中left,right分别表示原数组nums的左右指针范围，p则是待构建的二叉树结点，这里用传引用方式，方便原地修改（构建）。需要考虑三种情况：
left>right，此时不合法，令p=NULL；left==right，此时数组只含有一个元素，则直接创建值为nums[left]的新结点node，并令p=node；left<right，此时拿数组中间索引mid=(left+right)/2、对应元素即为nums[mid]，创建对应的新结点并赋给p。
/**
* 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:
void findRoot(vector<int>& nums, int left, int right, TreeNode*& p) {
if (left == right) {
TreeNode* node = new TreeNode(nums[left]);
node->left = NULL;
node->right = NULL;
p = node;
} else if (left > right) p = NULL;
else {
int mid = (left + right) / 2;
TreeNode* node = new TreeNode(nums[mid]);
p = node;
findRoot(nums, left, mid-1, node->left);
findRoot(nums, mid+1, right, node->right);
}
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
findRoot(nums, left, mid-1, root->left);
findRoot(nums, mid+1, right, root->right);
return root;
}
};43. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 严格小于 当前节点的数。
- 节点的右子树只包含 严格大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。提示：
- 树中节点数目范围在
[1, 104]内 -231 <= Node.val <= 231 - 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:
vector<int> v;
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left);
v.push_back(root->val);
inorder(root->right);
}
bool isValidBST(TreeNode* root) {
inorder(root);
int i;
for (i=1; i<v.size(); i++) {
if (v[i-1] >= v[i]) return false;
}
return true;
}
};44. 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 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提示：
- 树中的节点数为
n。 1 <= k <= n <= 1040 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
题解
和上题类似，做中序遍历、用数组保存中序遍历的结果，直接返回数组索引为k-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:
vector<int> v;
void inorder(TreeNode* node) {
if (node == NULL) return;
inorder(node->left);
v.push_back(node->val);
inorder(node->right);
}
int kthSmallest(TreeNode* root, int k) {
inorder(root);
return v[k-1];
}
};45. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1：
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入：root = [1,null,3]
输出：[1,3]
示例 4：
输入：root = []
输出：[]
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
题解
此题可以先用广度优先遍历求解出按层次遍历的结果，然后每次只取每一层遍历结果的最后一个即可。
/**
* 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) {
vector<int> ans;
queue<vector<TreeNode*>> Q;
if (root == NULL) return ans;
vector<TreeNode*> v;
v.push_back(root);
Q.push(v);
while (!Q.empty()) {
vector<TreeNode*> top = Q.front();
Q.pop();
TreeNode* lastNode = top[top.size()-1];
ans.push_back(lastNode->val);
vector<TreeNode*> newV;
for (TreeNode* node: top) {
if (node->left) newV.push_back(node->left);
if (node->right) newV.push_back(node->right);
}
if (newV.size()) {
Q.push(newV);
}
}
return ans;
}
};46. 二叉树展开为链表
给你二叉树的根结点 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]提示：
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
题解
采用分治算法divide and merge：divide(root): 将以root为根结点的子树展开，并返回头结点。
显然，一个比较自然的想法就是，先展开root的左子树，再展开root的右子树，然后将这两部分的结果拼接起来（merge）。要特别注意divide(root->left)为NULL的边界结果，此时跳过左子树展开结果即可。
/**
* 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* divide(TreeNode* root) {
if (!root) return NULL;
TreeNode* left = divide(root->left);
TreeNode* right = divide(root->right);
return merge(root, left, right);
}
TreeNode* merge(TreeNode* root, TreeNode* left, TreeNode* right) {
TreeNode* p = root;
if (left) {
p->right = left;
p->left = NULL;
while (p->right) {
p = p->right;
p->left = NULL;
}
}
p->right = right;
return root;
}
void flatten(TreeNode* root) {
divide(root);
}
};47. 从前序和中序遍历序列构造二叉树
给定两个整数数组 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 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
题解
同样地，采取分治算法。
观察给定的先序遍历和中序遍历数组：
- pre: 3, 9, 20, 15, 7
- in: 9, 3, 15, 20, 7
我们可以肯定以下几点：
- pre的第一个元素（记作root），一定是根结点（先序遍历性质决定）
- 到in中找root元素的索引，它左边一定是左子树的中序遍历、右边一定是右子树的中序遍历，同时也可以根据元素数量，回到pre数组确定左子树和右子树的先序遍历
结合以上两点，便可以写出递归程序实现分治算法。
注意，递归函数findRoot()还需要接收四个参数，pre1、pre2、in1、in2，它们分别代表当前先序遍历数组和中序遍历数组的起始结束索引位置，递归出口则是当pre1==pre2时，此时该子树仅有一个叶子结点，无需继续递归，直接返回即可。
/**
* 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* ans;
TreeNode* findRoot(vector<int>& preorder, vector<int>& inorder, int pre1, int pre2, int ord1, int ord2) {
// preorder[pre1]一定为根结点
TreeNode* root = new TreeNode(preorder[pre1]);
if (pre1 == 0) ans = root;
if (pre2 == pre1) {
root->left = root->right = NULL;
return root;
}
auto iter = find(inorder.begin()+ord1, inorder.end()+ord2+1, preorder[pre1]);
int ordMid = distance(inorder.begin(), iter); // inorder序号
if (ordMid == ord1) root->left = NULL;
else root->left = findRoot(preorder, inorder, pre1+1, pre1+ordMid-ord1, ord1, ordMid-1);
if (ordMid == ord2) root->right = NULL;
else root->right = findRoot(preorder, inorder, pre1+ordMid-ord1+1, pre2, ordMid+1, ord2);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
findRoot(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
return ans;
}
};48. 路径总和Ⅲ
给定一个二叉树的根节点 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提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
题解
实际上，这个题目也需要用到动态规划。定义一个函数rootSum(root, tgt)，他用来求解以root为根（包括root）、targetSum为tgt的路径数量，显然，有状态转移方程：
只需借助遍历（先序、中序或者后序均可），对每一个结点求解rootSum(root, tgt)，将它们的结果求和即可得到答案。
/**
* 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 k;
int rootSum(TreeNode* root, long long targetSum) {
if (!root) return 0;
int ans = 0;
if (root->val == targetSum) ans++;
ans += rootSum(root->left, targetSum - root->val);
ans += rootSum(root->right, targetSum - root->val);
return ans;
}
int pathSum(TreeNode* root, int targetSum) {
if (root == NULL) return 0;
return pathSum(root->left, targetSum) + pathSum(root->right, targetSum) + rootSum(root, targetSum);
}
};49. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。示例 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提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
题解
最直接的想法，使用广度优先遍历，搜索整棵树，可以得到每一个结点和其父结点的对应关系，将其存入哈希表；然后对于给定的结点p、q，先利用哈希表不断地找p的父结点，该路径上的结点标记访问过，然后再不断地找q的父结点，并返回第一个已经被标记访问过的结点。
时间复杂度：$O(n)$，n为树的边数
空间复杂度：$O(m+n)$，维护了两个哈希表，一个存放结点-父结点，另一个存放是否被访问过。
/**
* 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:
map<TreeNode*, TreeNode*> mps;
void BFS(TreeNode* root) {
queue<TreeNode*> Q;
Q.push(root);
// mps[root] = root;
while(!Q.empty()) {
TreeNode* top = Q.front();
Q.pop();
if(top->left) {
mps[top->left] = top;
Q.push(top->left);
}
if(top->right) {
mps[top->right] = top;
Q.push(top->right);
}
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
BFS(root);
map<int, bool> visit;
TreeNode* n1 = p;
while(mps.count(p)) {
visit[p->val] = 1;
p = mps[p];
}
visit[p->val] = 1;
while(mps.count(q)) {
if(visit[q->val]) return q;
q = mps[q];
}
return q;
}
};50. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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提示：
- 树中节点数目范围是
[1, 3 * 104] -1000 <= Node.val <= 1000
题解
我们可以先维护一个哈希表map<TreeNode*, int> mp，记录每一个结点的“贡献值”，即以该结点为根结点的子树中，寻找以该结点为起点的一条路径，使得该路径上的结点值之和最大。我们可以用动态规划思想，实现一个递归函数int rootSum(TreeNode* root)对哈希表进行填充。
随后，我们递归地求解最终答案，实现一个函数void recursion(TreeNode* root)求解root根结点的子树的最大路径和。我们检查左子树和右子树的贡献值，取出其中的正值加到root->val即可，同时对最终答案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:
map<TreeNode*, int> mp;
int ans = INT_MIN; // 答案，初始化为INT极小值
int rootSum(TreeNode* root) {
if (mp.count(root))
return mp[root];
if (root == NULL)
return 0;
int left = max(rootSum(root->left), 0);
int right = max(rootSum(root->right), 0);
return mp[root] = root->val + max(left, right);
}
void recursion(TreeNode* root) {
if (root == NULL) return ;
int temp = root->val; // 根结点必选
// 只取正值
if (mp[root->left] > 0)
temp += mp[root->left];
if (mp[root->right] > 0)
temp += mp[root->right];
if (temp > ans)
ans = temp; // 更新ans
recursion(root->left);
recursion(root->right);
}
int maxPathSum(TreeNode* root) {
mp[NULL] = 0;
rootSum(root);
recursion(root);
return ans;
}
};图论
51. 岛屿数量
给你一个由 '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提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
题解
DFS的经典原始题型。进行深度优先遍历，然后对每一个点调用DFS，能调用几次，答案就是几（即有几块陆地）。注意维护一个map二维矩阵，记录每一个位置是否访问过。
/*
深度优先遍历
遍历矩阵中的每一个位置，进行深度优先遍历，同时维护一个矩阵，标记每个位置是否访问过，避免重复搜索
深度优先遍历的次数，就是岛屿数量
*/
class Solution {
public:
int map[305][305];
int ans;
// 用深度优先遍历算法。最后的岛屿数量，就是深度优先遍历的次数
void dfs(vector<vector<char>>& grid, int x, int y) {
if (map[y][x]) return;
if (grid[y][x] == '0') return;
map[y][x] = 1; // 访问当前位置
if (y != grid.size() - 1) dfs(grid, x, y+1);
if (x != grid[0].size() - 1) dfs(grid, x+1, y);
if (y != 0) dfs(grid, x, y-1);
if (x != 0) dfs(grid, x-1, y);
}
int numIslands(vector<vector<char>>& grid) {
ans = 0;
int i, j;
for (i=0; i<grid.size(); i++) {
for (j=0; j<grid[0].size(); j++) {
if (map[i][j] == 0 && grid[i][j] == '1') ans++;
dfs(grid, j, i);
}
}
return ans;
}
};52. 腐烂的橘子
在给定的 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 。提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
题解
此题解法类似“二叉树的层次遍历”。我们用一个pair<int, int>型变量记录每一个位置的坐标，然后用vector<pair<int, int>>作为队列queue<vector<pair<int, int>>> Q的基本元素，它表示每一轮腐烂的橘子位置集合。我们进行广度优先遍历，每一轮遍历便往队列Q中添加一个非空数组，添加非空数组的次数变为此题答案。
另外，进行完毕广度优先遍历后，我们需要对整个网格grid进行遍历检查，若仍存在未腐烂的橘子，直接返回-1。
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<vector<pair<int, int>>> Q;
int i, j;
vector<pair<int, int>> vec;
for (i=0; i<grid.size(); i++) {
for (j=0; j<grid[0].size(); j++) {
if (grid[i][j] == 2) vec.push_back({i, j});
}
}
Q.push(vec);
int ans = 0;
while (!Q.empty()) {
vector<pair<int, int>> top = Q.front();
Q.pop();
vector<pair<int, int>> newVec;
for (pair<int, int> p: top) {
int y = p.first;
int x = p.second;
if (y != 0 && grid[y-1][x] == 1) grid[y-1][x] = 2, newVec.push_back({y-1, x});
if (y != grid.size()-1 && grid[y+1][x] == 1) grid[y+1][x] = 2, newVec.push_back({y+1, x});
if (x != 0 && grid[y][x-1] == 1) grid[y][x-1] = 2, newVec.push_back({y, x-1});
if (x != grid[0].size()-1 && grid[y][x+1] == 1) grid[y][x+1] = 2, newVec.push_back({y, x+1});
}
if (newVec.size()) {
Q.push(newVec);
ans++;
}
}
for (i=0; i<grid.size(); i++) {
for (j=0; j<grid[0].size(); j++) {
if (grid[i][j] == 1) return -1;
}
}
return ans;
}
};53. 课程表[待求解]
你这个学期必须选修 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 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
题解
此题需要用拓扑排序进行求解。所谓拓扑排序，即按照图结点的入度从小到大重新进行排序，比如第一次取出入度为零的结点，然后将其从原图中剔除、并更新其他结点的入度，接着以此类推每次取入度为零的结点即可；若某次迭代后发现不存在入度为零的结点，则可以判定图中有环。
具体而言，此题我们需要
- 根据先修课程矩阵
prerequisites构建一个邻接矩阵； - 同时维护一个入度矩阵
inDegree，记录每一个结点的入度。
此外，拓扑排序通常可以借助BFS来完成，此题只需要根据拓扑排序判定DFG中是否存在环。我们遍历图中的每一个结点，以它作为根结点来进行BFS。为了加快搜索，维护一个数组visit，来保存每一个结点的访问状态：
- 初始状态为0，表示完全没有被访问过
- 正在访问：-1，表示当前结点正在被BFS，处于递归访问状态
- 已经访问：1，表示当前结点已经被BFS，并且属于某一个连通分量
具体在遍历每一个结点时，如果visit[i]为1，则直接跳过，从下一个结点开始进行广度优先遍历，这样可以极大地减小搜索时间。而具体在BFS(i)内部：
- 首先必须置
visit[i]为-1，表示正在访问结点i - 找到结点i的全部后继，也就是课程i的所有先修课程
- 遍历每一个先修课程
preCourse，如果其状态为-1，直接返回false，而如果它没有被访问过，状态为0，则递归地搜索，调用BFS(preCourse)，一旦其返回结果为false，当前函数也返回false - 遍历结束，表示没有找到环，置当前结点状态为1，表示当前搜索路径不是环，这条连通分量中的每一个结点访问状态都置为1
/*
* @lc app=leetcode.cn id=207 lang=cpp
*
* [207] 课程表
*/
// @lc code=start
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int graph[2005][2005]; // 邻接矩阵
memset(graph, 0, sizeof(graph));
int inDegree[2005]; // 入度矩阵
memset(inDegree, 0, sizeof(inDegree));
// 更新邻接矩阵和入度矩阵
for (auto& p: prerequisites) {
graph[p[1]][p[0]] = 1;
inDegree[p[0]]++;
}
queue<int> q; // 广度优先遍历需要维护一个队列，每一个元素为课程编号
for (int i = 0; i < numCourses; i++) {
// 初始情况下，将任意一个入度为零的课程加入队列中
if (inDegree[i] == 0) {
q.push(i);
}
}
int visited = 0; // 记录访问过的课程数量
while (!q.empty()) {
int course = q.front();
q.pop();
visited++;
for (int next = 0; next < numCourses; next++) {
// 因为要去除当前队首课程结点，于是所有与之邻接的结点入度都要减一
if (graph[course][next]) { // 判定是否邻接
inDegree[next]--;
if (inDegree[next] == 0) {
// 将入度为零的课程结点入队
q.push(next);
}
}
}
}
// 广度优先遍历完成后，根据访问过的课程结点数量是否等于全部课程数量这一条件可以判定是否有环
return visited == numCourses;
}
};
// @lc code=end
54. 前缀树
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 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
题解
前缀树，需要明确树的每一个结点包含两个关键属性：
bool isEnd，表示当前结点是否为单词结束- 指针数组
Trie* pts[26]，分别指向26个字母
class Trie {
public:
Trie* pts[26]; // 26个Trie*指针
bool isEnd;
Trie() {
isEnd = false;
for (int i = 0; i < 26; i++) {
pts[i] = NULL;
}
}
void insert(string word) {
Trie* node = this;
for (char ch: word) {
// 如果当前word路径不存在，则构建新的结点，并指过去
if (node->pts[ch-'a'] == NULL) {
Trie* newNode = new Trie();
node->pts[ch-'a'] = newNode;
}
// 指针移动
node = node->pts[ch-'a'];
}
node->isEnd = true;
}
bool search(string word) {
// 沿着word路径搜索树，如果能到达终点，根据终点结点的isEnd属性判定即可；否则直接返回false
Trie* node = this;
for (char ch: word) {
if (node->pts[ch-'a'] == NULL) return false;
else node = node->pts[ch-'a'];
}
return node->isEnd;
}
bool startsWith(string prefix) {
// 和search很相似，只是如果能到达prefix路径终点，就返回true；否则返回false
Trie* node = this;
for (char ch: prefix) {
if (node->pts[ch-'a'] == NULL) return false;
else node = node->pts[ch-'a'];
}
return 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);
*/回溯
55. 全排列
给定一个不含重复数字的数组 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 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
题解
要用回溯算法求解，一个关键点便是鉴别出问题空间中的每一个状态结点该如何表示。比如此题我们可以用如下两个变量的组合表示当前状态：
vector<int> pm，表示当前已有的排列；vector<int> nums，表示当前剩余的、还未用上的数字集合。
在回溯判定时，
- 如果
nums.size()==0，表示已无剩余数字，全部数字已经加入组成了完整的排列，将当前的pm加入答案之中； - 否则，遍历
nums中的每一个元素nums[i]，将其加入pm、从nums剔除，迭代即可，注意当前一轮迭代完毕后需要还原状态，即恢复nums[i]、从pm中剔除nums[i]。
class Solution {
public:
vector<vector<int>> ans;
void search(vector<int> pm, vector<int> nums) {
// nums [2, 3] pm [1]
if (nums.size() == 0) {
ans.push_back(pm);
return;
}
int i;
for(i=0; i<nums.size(); i++) {
pm.push_back(nums[i]);
vector<int> nextNums = nums;
nextNums.erase(nextNums.begin()+i);
search(pm, nextNums);
pm.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> pm;
search(pm, nums);
return ans;
}
};56. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2：
输入：nums = [0]
输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
题解
我们用两个变量表示问题空间中的某个状态：
int k，表示当前考虑的元素在nums数组的下标；vector<int> subset，表示当前的子集。
回溯搜索时，
- 若
k==nums.size()，表示nums全部元素已经考虑完毕，直接将subset加入答案中； - 否则，需要考虑是否将
nums[k]加入subset子集，请注意，既可以加入、也可以不加，对应着两条分支。
class Solution {
public:
vector<vector<int>> ans;
void search(vector<int>& nums, vector<int> subset, int k) {
if (k >= nums.size()) {
ans.push_back(subset);
return;
}
search(nums, subset, k+1);
subset.push_back(nums[k]);
search(nums, subset, k+1);
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> subset;
search(nums, subset, 0);
return ans;
}
};57. 电话号码的组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = "2"
输出：["a","b","c"]提示：
1 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
题解
我们用两个变量记录状态结点：
string digits，表示当前剩余的数字字符串；string perm，表示当前已经做出的字母组合。
于是
- 若
digits.size()==0，已无剩余数字，将当前的perm加入答案中； - 否则，取出
digits[0]对应的所有字母，逐个加入perm中，同时将digits[0]从digits中剔除，注意每个字母加入perm、进行搜索后需要再从perm中剔除，才能考虑下一个字母。
class Solution {
public:
string arrs[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
void search(string perm, string digits) {
if (digits.size() == 0) {
ans.push_back(perm);
return;
}
char n = digits[0];
for (char ch: arrs[n-'0']) {
perm += ch;
search(perm, digits.substr(1));
perm.pop_back(); // 非常重要：将当前考虑完毕的字母剔除
}
}
vector<string> letterCombinations(string digits) {
string perm = "";
search(perm, digits);
return ans;
}
};58. 组合总和
给你一个 无重复元素 的整数数组 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 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
题解
DFS。和大多数深度优先遍历的题一样，此处，我们用
- 已经选取的数字组合done
- 已经凑出的总和sum
- 目前正在考虑的数字下标todo
来表示搜索到的状态。为了进行剪枝，首先对candidates数组进行非递减排序。
- 显然，当$sum = target$时，搜索到一个满足题意的状态，直接将当前的组合done保存下来；
- 当$todo = candidates.size()$时，也就是说，已经超出了原数组的范围，直接return（此时已经搜索到了一棵树的叶子）；
- 当$sum > target$或者$sum + candidates[todo] > target$时，此时不可能再凑出target了，直接return，相当于剪枝；
- 接下来进行状态搜索：
- 不选$candidates[todo]$，
DFS(done, sum, todo+1)； - 选$candidates[todo]$，但是仅选一次，
done.push_back(candidates[todo]); DFS(done, sum+candidates[todo], todo+1]； - 选$candidates[todo]$，选多次，
done.push_back(candidates[todo]); DFS(done, sum+candidates[todo], todo)
- 不选$candidates[todo]$，
如此，调用DFS(done, 0, 0)即可开始深度优先搜索。其中done为空数组。
class Solution {
public:
map<vector<int>, int> mp;
vector<vector<int>> ans;
void search(vector<int> ct, vector<int> candidates, int idx, int target) {
if (target == 0) {
if (!mp.count(ct)) {
mp[ct] = 1;
ans.push_back(ct);
}
return;
}
if (idx >= candidates.size() || candidates[idx] > target) return;
search(ct, candidates, idx+1, target); // 不选
ct.push_back(candidates[idx]);
search(ct, candidates, idx, target-candidates[idx]); // 选多次candidates[idx]
search(ct, candidates, idx+1, target-candidates[idx]); // 选一次candidates[idx]
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> ct;
search(ct, candidates, 0, target);
return ans;
}
};59. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1
输出：["()"]提示：
1 <= n <= 8
题解
我们可以用变量表示一个状态：
- 当前剩余的左括号数量
k - 当前剩余的右括号数量
r - 当前已经生成的括号组合
string str
我们利用k,r来考虑当前str的合法性。具体地，
- 若
r>k，表示当前剩余的右括号数量更多，str中左括号数量更多，此时不能再加左括号了，否则会出现非法括号组合，只能加右括号； - 否则，优先加左括号，防止出现非法情况。
class Solution {
public:
vector<string> ans;
void dfs(string str, int k, int r) {
if (k == 0 && r == 0) {
ans.push_back(str);
return;
}
if (k > 0) dfs(str+'(', k-1, r);
if (r > k) dfs(str+')', k, r-1);
}
vector<string> generateParenthesis(int n) {
string str = "";
dfs(str, n, n);
return ans;
}
};60. 单词搜索
给定一个 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提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
题解
我们用深度优先遍历DFS求解此题，对于搜索过程中的每一个状态，我们用两个变量进行记录：
- 当前检查的网格坐标
x,y - 当前检查的字符串单词字母下标
idx
我们考虑如何进行DFS。我们有四个方向可以搜索（上下左右），同时需要进行边界判定；
- 若
word[idx] != board[y][x]，直接返回false； - 否则，若
idx == word.size() - 1，表示已经检查到了字符串末尾，返回true
另外需要维护一个二维矩阵visits，指示每次DFS中每个位置是否检查过，避免上下左右搜索检查出现重复。
class Solution {
public:
int xs[4] = {-1, 1, 0, 0};
int ys[4] = {0, 0, -1, 1};
int visits[7][7];
bool dfs(vector<vector<char>>& board, int x, int y, string& word, int idx) {
if (word[idx] != board[y][x]) return false;
if (idx == word.size() - 1) return true;
else {
bool flag = false;
visits[y][x] = 1; // 访问了当前坐标，置一
int i;
for (i=0; i<4; i++) {
int newx = x + xs[i];
int newy = y + ys[i];
if (newx >= 0 && newx < board[0].size() && newy >= 0 && newy < board.size() && visits[newy][newx] == 0) {
bool isFind = dfs(board, newx, newy, word, idx+1);
if (isFind) return true;
}
}
}
visits[y][x] = 0; // 恢复到原始状态，置零
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
int i, j;
for (i=0; i<m; i++) {
for (j=0; j<n; j++) {
memset(visits, 0, sizeof(visits));
if (dfs(board, j, i, word, 0)) return true;
}
}
return false;
}
};61. 分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a"
输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
题解
此题有一个比较简单的做法。我们用两个变量表示一个状态：
vector<string> vec，表示当前已经分割的字符串结果；int idx，表示当前考虑字符串s的下标。
我们在每一次DFS搜索内部额外用一个循环，依次考虑当前切分的子串s[idx:i+1]，其中idx<=i<s.size()，若s[idx:i+1]为回文字符串，则将其加入vec中，并继续搜索。注意继续搜索完毕后需要将s[idx:i+1]剔除。
class Solution {
public:
vector<vector<string>> ans;
void dfs(vector<string> vec, string& s, int idx) {
if (idx == s.size()) ans.push_back(vec);
int i;
for (i=idx; i<s.size(); i++) {
string sub = s.substr(idx, i-idx+1);
string resub = sub;
reverse(sub.begin(), sub.end());
if (sub == resub) {
vec.push_back(sub);
dfs(vec, s, i+1);
vec.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<string> vec;
dfs(vec, s, 0);
return ans;
}
};62. 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 <= n <= 9
题解
此题的关键解法：用三个unordered_set集合来存储当前已经出现过的列和两条对角线，同时按照行号从上到下依次考虑每一行的放置位置。即
- 第一次，考虑将皇后放在第一行第几列？
- 第二次，考虑将皇后放在第二行第几列？（此时就需要考虑限制条件了）
- 如此反复即可
结点状态：
- 当前棋盘，用
vector<map>表示； - 当前考虑的行号，用
int k表示
当k == n时，到达一个叶子结点，将当前棋盘添加到答案数组中。
class Solution {
public:
unordered_set<int> cols;
unordered_set<int> dias1, dias2;
vector<vector<string>> ans;
void updateMap(vector<string>& map, int x, int y) {
map[y][x] = 'Q';
}
void backtrack(vector<string> map, int n, int k) {
if (k == n) {
ans.push_back(map);
return;
}
int i;
for (i=0; i<n; i++) {
if (cols.find(i) != cols.end()) {
continue;
}
int cnt1 = k - i;
int cnt2 = k + i;
if (dias1.find(cnt1) != dias1.end()) {
continue;
}
if (dias2.find(cnt2) != dias2.end()) {
continue;
}
cols.insert(i);
dias1.insert(cnt1);
dias2.insert(cnt2);
vector<string> newMap = map;
updateMap(newMap, i, k);
backtrack(newMap, n, k+1);
cols.erase(i);
dias1.erase(cnt1);
dias2.erase(cnt2);
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> map;
string str = "";
int i;
for (i=0; i<n; i++) {
str += ".";
}
for (i=0; i<n; i++) map.push_back(str);
backtrack(map, n, 0);
return ans;
}
};二分查找
63. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 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 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
题解
此题做法类似一个经典的二分搜索模板。注意这里的迭代停止条件和边界更新。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (target > nums[nums.size() - 1]) return nums.size();
int lower = 0, upper = nums.size() - 1;
while (lower < upper) {
int mid = (lower + upper) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) {
lower = mid + 1;
} else {
upper = mid;
}
}
return lower;
}
};64. 搜索二维矩阵
给你一个满足下述两条属性的 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提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
题解
此题也有一个简单做法。在“搜索插入位置”题中，我们已经实现了标准的一维二分搜索算法。此题我们只需对二维矩阵的每一行应用二分搜索算法即可。注意这里的迭代停止条件和边界更新方式。
class Solution {
public:
bool binarySearch(vector<int>& vec, int left, int right, int target) {
while (left <= right) {
int mid = (left + right) / 2;
if (vec[mid] == target) return true;
else if (vec[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i;
for (i=0; i<matrix.size(); i++) {
if (binarySearch(matrix[i], 0, matrix[i].size()-1, target)) {
return true;
}
}
return false;
}
};65. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 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]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
题解
第一感觉，二分，因为题目给的很明显，一是序列已经非递减排序；二是要求算法时间复杂度为$\mathcal{O}(\log n)$。设置两个指针：左指针和右指针，分别指向当前查找序列段的首尾。这样一来，中间指针mid=down + (up - down) / 2；比较nums[mid]和target的大小关系，调整down = mid + 1或者up = mid －1。循环终止条件为up > down。
如此二分法执行两遍，分别查找位序下界和上界，最后输出答案。
class Solution {
public:
int lower;
int higher;
vector<int> searchRange(vector<int>& nums, int target) {
lower = -1, higher = -1;
int down = 0;
int up = nums.size() - 1;
while (down <= up) {
int mid = (up + down) / 2;
if (nums[mid] == target) {
if (mid == 0 || nums[mid-1] != target) {
lower = mid;
break;
} else {
up = mid - 1;
}
} else if (nums[mid] < target) {
down = mid + 1;
} else {
up = mid - 1;
}
}
down = 0, up = nums.size() - 1;
while (down <= up) {
int mid = (up + down) / 2;
if (nums[mid] == target) {
if (mid == nums.size() - 1 || nums[mid+1] != target) {
higher = mid;
break;
} else {
down = mid + 1;
}
} else if (nums[mid] < target) {
down = mid + 1;
} else {
up = mid - 1;
}
}
vector<int> ans;
ans.push_back(lower);
ans.push_back(higher);
return ans;
}
};66. 搜索旋转排序数组
整数数组 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 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
题解
同样的道理，很自然会想到二分法查找元素，但是即使将数组排序，再进行二分法查找，得到的结果也不再是原数组中的位序了。但是却可以思考原数组和有序数组之间的关系：从某一个位置进行截断，然后进行循环移位，这样的话可以找到原数组和有序数组相同元素位序之间的1映射关系。原数组位序为a，有序数组位序为b，则有b=(a+p)%l，p为有序数组截断处位置，l为数组长度。
class Solution {
public:
int search(vector<int>& nums, int target) {
int lower = 0;
int upper = nums.size() - 1;
int ans = -1;
while (lower <= upper) {
int mid = (lower + upper) / 2;
if (nums[mid] == target) {
ans = mid;
break;
} else if (nums[mid] >= nums[lower]) {
if (target < nums[mid] && target >= nums[lower]) {
upper = mid - 1;
} else {
lower = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[upper]) {
lower = mid + 1;
} else {
upper = mid - 1;
}
}
}
return ans;
}
};67. 寻找旋转排序数组中的最小值
已知一个长度为 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 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
题解
同样进行二分搜索，我们设置首尾指针lower, higher，求出中间指针mid，关键是考虑如何更新边界指针lower, higher。
- 若
nums[lower] < nums[higher]，表示nums[lower:higher+1]这一段是升序排列的，仔细分析就会发现最小值就是nums[lower]； - 否则，若
nums[mid] > nums[higher]，最小值一定落在nums[mid+1:higher+1]中； - 否则，最小值一定落在
nums[lower:mid]中。
class Solution {
public:
int binarySearch(vector<int>& nums, int left, int right) {
int lower = left;
int higher = right;
while (lower < higher) {
int mid = (lower + higher) / 2;
if (nums[lower] < nums[higher]) return nums[lower];
if (nums[mid] > nums[higher]) {
lower = mid + 1;
} else {
higher = mid;
}
}
return nums[lower];
}
int findMin(vector<int>& nums) {
return binarySearch(nums, 0, nums.size()-1);
}
};68. 寻找两个正序数组的中位数
给定两个大小分别为 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提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
题解
class Solution {
public:
int getK(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size();
int n = nums2.size();
int index1 = 0;
int index2 = 0;
while (true) {
if (index1 == m) {
return nums2[index2+k-1];
}
if (index2 == n) {
return nums1[index1+k-1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int x = nums1[newIndex1];
int y = nums2[newIndex2];
if (x <= y) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int k = nums1.size() + nums2.size();
if (k % 2) {
return getK(nums1, nums2, k/2+1);
} else {
return (getK(nums1, nums2, k/2) + getK(nums1, nums2, k/2+1)) / 2.0;
}
}
};栈
69. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([])”
输出：true
示例 5：
输入：s = “([)]”
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
题解
堆栈模拟用法。遍历字符串s，当遇到右括号时，则查看当前栈顶元素，只有在栈不为空且栈顶元素与之对应时，证明当前匹配成功，将栈顶元素出栈；否则直接将当前字符入栈。遍历完毕后，如果当前栈中仍有元素，则表明字符串s不合法；否则，合法。
class Solution {
public:
bool isValid(string s) {
stack<char> S;
for (char ch: s) {
if (ch == '(' || ch == '{' || ch == '[') {
S.push(ch);
} else {
if (S.empty()) return false;
char top = S.top();
if (top == '(') {
if (ch == ')') {
S.pop();
} else {
return false;
}
} else if (top == '{') {
if (ch == '}') {
S.pop();
} else {
return false;
}
} else {
if (ch == ']') {
S.pop();
} else {
return false;
}
}
}
}
if (!S.empty()) return false;
return true;
}
};70. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
题解
此题需要充分考虑栈的特性。我们除了维护一个常规的栈之外，还维护一个存储每一次push之后当前最小值的栈minS即可。如此，在getMin操作时，直接返回minS.top()即可。
class MinStack {
public:
stack<int> S;
stack<int> minS;
MinStack() {
minS.push(INT_MAX);
}
void push(int val) {
S.push(val);
if (val < minS.top()) {
minS.push(val);
} else {
minS.push(minS.top());
}
}
void pop() {
S.pop();
minS.pop();
}
int top() {
return S.top();
}
int getMin() {
return minS.top();
}
};
/**
* 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();
*/71. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
题解
这是一道需要模拟出栈入栈的算法题。我们可以对给定的字符串中的每一个字符s进行考察遍历，同时维护一个存放当前处理结果的栈stack<string> ans：
- 如果s为数字，表示此时需要读取出数字，它表示字符串重复次数，将完整的数字读取出来，以string形式入栈；
- 如果s为字母或者
[，直接入栈； - 剩余情况就是s为
]了，于是将ans中的元素逐个出栈，直到[出栈，此部分字符串即为需要重复的子串sub，此时栈顶元素即为string形式的重复次数，将其转换为int类型，结合sub得到完整的子串str，再将str入栈。
class Solution {
public:
// 获取完整的数字
string getDigit(string &s, int k) {
string digit = "";
while (isdigit(s[k])) {
digit.push_back(s[k]);
k++;
}
return digit;
}
string decodeString(string s) {
stack<string> ans;
int i = 0;
while (i < s.size()) {
if (isdigit(s[i])) {
string digit = getDigit(s, i);
ans.push(digit);
i += digit.size();
} else if (isalpha(s[i]) || s[i] == '[') {
ans.push(string(1, s[i]));
i++;
} else {
// 此时取到了']'，栈顶元素依次取出
string sub = "";
while (true) {
string top = ans.top();
ans.pop();
if (top == string(1, '[')) break;
sub = top + sub;
}
// 栈中元素遇到'['，则退出循环，此时栈顶元素一定是一个数字
int k = stoi(ans.top());
ans.pop();
int j;
string str = "";
// 将sub重复k次
for (j=0; j<k; j++) {
str += sub;
}
ans.push(str);
i++;
}
}
string finalAns = "";
while (!ans.empty()) {
string top = ans.top();
ans.pop();
finalAns = top + finalAns;
}
return finalAns;
}
};72. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
题解
此题是非常经典的单调栈求解。我们维护一个（单调）栈，若当前温度高于栈顶元素，则弹出栈顶元素，然后再次比较栈顶元素和当前温度大小，直到不高于当前温度，再将当前温度入栈；否则，直接将当前温度入栈。如此，便可实现栈顶元素出栈时，便可以得到其下一个更高温度出现天数的答案。为了方便记录每一个温度所属天数，栈中元素类型设计为pair<int, int>，记录第几天和对应的温度。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans(temperatures.size()); // 待返回的答案
int i;
stack<pair<int, int>> S; // <温度，第x天>
S.push({temperatures[0], 0});
for (i=1; i<temperatures.size(); i++) {
while (!S.empty()) {
// 单调栈实现
auto top = S.top();
if (top.first < temperatures[i]) {
S.pop();
ans[top.second] = i - top.second;
} else {
break;
}
}
// 无论如何，入栈
S.push({temperatures[i], i});
}
return ans;
}
};73. 柱状图中最大的矩形[待求解]
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4提示：
1 <= heights.length <=1050 <= heights[i] <= 104
题解
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int cnts[100005];
stack<int> S;
int ans = 0;
int i;
heights.push_back(0);
heights.insert(heights.begin(), 0);
for (i=0; i<heights.size(); i++) {
if (S.empty()) S.push(i);
else {
int topIdx = S.top();
int height = heights[topIdx];
while (height > heights[i]) {
S.pop();
topIdx = S.top();
int width = i - topIdx - 1;
int area = width * height;
ans = ans > area ? ans : area;
height = heights[topIdx];
}
S.push(i);
}
}
return ans;
}
};堆
74. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
题解
我们维护一个小根堆priority_queue<int, vector<int>, greater<int>> pq，然后时刻控制堆大小为k。也就是说，
- 当
pq元素数量不满k时，我们直接将当前元素入堆； - 否则，则需要考虑是否弹出堆顶元素了：若当前元素大于堆顶元素，则弹出堆顶元素，加入当前元素，否则直接跳过即可。
如此，堆里始终存着当前看到的最大的k个数，故而（小根）堆顶元素就是这最大的k个数里面最小的，即第k大的元素。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 小根堆确保堆顶元素是最小的
priority_queue<int, vector<int>, greater<int>> pq;
for (int n: nums) {
if (pq.size() < k) {
pq.push(n);
} else {
if (pq.top() < n) {
// 确保存放前k个最大元素
pq.pop();
pq.push(n);
}
}
}
// 综合来看，小根堆顶元素是前k个最大元素中的最小者，即第k大者
return pq.top();
}
};75. 前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
题解
用堆排序解决。但是要注意，要维护的一定是一个小根堆，因为在后续遍历元素时，取出堆顶元素（确保它是最小的），如果它比当前新元素的频次更小，说明当前新元素的频次是前k大的，应该入堆。
小根堆的自定义比较器comp(a,b)结果应该为true，也要注意。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
auto comp = [](pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq;
map<int, int> mp; // 记录每个元素以及其出现频次
for (int x : nums) {
if (mp.count(x))
mp[x]++;
else
mp[x] = 1;
}
vector<pair<int, int>> data;
for (map<int, int>::iterator iter = mp.begin(); iter != mp.end();
iter++) {
data.push_back({iter->first, iter->second});
}
for (auto p : data) {
if (pq.size() < k)
pq.push(p);
else {
auto top = pq.top();
if (top.second < p.second) {
pq.pop();
pq.push(p);
}
}
}
vector<int> ans;
while (!pq.empty()) {
auto top = pq.top();
ans.push_back(top.first);
pq.pop();
}
return ans;
}
};76. 数据流的中位数[待求解]
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0提示:
-105 <= num <= 105- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 104次调用addNum和findMedian
题解
此题关键：维护两个堆，小顶堆和大顶堆，分别存储较大的一半higher（小顶堆）和较小的一半元素lower（大顶堆）。另外，时刻保证lower比higher中的元素最多多一个；故而需要根据两者元素数量进行调整。
- 如果
lower.size()>higher.size()+1，此时lower中元素太多，将lower堆顶元素取出来弹出，添加到higher堆顶 - 如果
higher.size()>lower.size()，此时higher中元素过多，将higher堆顶元素取出弹出，添加到lower堆顶
同时考虑addNum函数。
- 初始情况，
lower,higher均为空，addNum函数中，将num加入到lower中； - 若
lower.top() > num，表示待添加的元素比当前存储较小一半元素中的最大元素还小，则将其加入到lower中； - 否则，则表示待添加的元素比当前存储较小一半元素中的最大元素还大（或相等），则将
num添加到higher中
class MedianFinder {
public:
priority_queue<int, vector<int>, greater<int>> higher;
priority_queue<int> lower;
MedianFinder() {
}
void addNum(int num) {
// 正常考虑入堆
if (lower.empty() || lower.top() >= num) {
lower.push(num);
} else {
higher.push(num);
}
// 同时考虑平衡lower和higher两个堆元素
if (lower.size() > higher.size() + 1) {
higher.push(lower.top());
lower.pop();
} else if (higher.size() > lower.size()) {
lower.push(higher.top());
higher.pop();
}
}
double findMedian() {
if (lower.size() == higher.size()) {
return (lower.top() + higher.top()) / 2.0; // 取中间两数的平均值
} else {
return lower.top(); // 由于lower.size() == higher.size() + 1，返回lower堆顶元素
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/贪心算法
77. 买股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
题解
我们设计的贪心策略为，在股票价格最低时买入，然后在买入后的股票价格最高时卖出。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int i;
int ans = 0;
int minPrice = 100005;
for (i=0; i<prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
}
ans = max(prices[i] - minPrice, ans);
}
return ans;
}
};78. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
题解
设计贪心策略：每次根据能够跳跃最远的距离，选择跳跃步数。比如示例一中，
nums = [2, 3, 1, 1, 4]初始情况我们选择跳1步到下标1，因为此处可以跳3步，距离最远。
class Solution {
public:
bool canJump(vector<int>& nums) {
int i = 0;
int j;
while (i < nums.size()) {
int steps = nums[i];
int nextIdx = i;
for (j=i+1; j<=i+steps && j<nums.size(); j++) {
if (nums[j] + j > nextIdx + nums[nextIdx]) {
nextIdx = j;
}
}
if (nums[nextIdx] + nextIdx >= nums.size() - 1) return true;
if (nextIdx == i) return false;
i = nextIdx;
}
return true;
}
};79. 跳跃游戏Ⅱ
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i]且i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4]
输出: 2提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
n - 1
题解
用类似上题的解法，只不过需要额外考虑已经跳跃的次数。
class Solution {
public:
int jump(vector<int>& nums) {
int i = 0;
int j;
int ans = 0;
while (i < nums.size()) {
int steps = nums[i];
int nextIdx = i;
if (nextIdx == nums.size() - 1) return ans;
if (nextIdx + nums[nextIdx] >= nums.size() - 1) return ans + 1;
for (j=i+1; j<=i+steps && j<nums.size(); j++) {
if (nums[j] + j > nextIdx + nums[nextIdx]) {
nextIdx = j;
}
}
i = nextIdx;
ans++;
}
return ans;
}
};80. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 示例 2：
输入：s = "eccbbbbdec"
输出：[10]提示：
1 <= s.length <= 500s仅由小写英文字母组成
题解
维护一个hash表ends，记录字符串s中出现的每一个字符的最后索引位置。
然后从头遍历s中的每一个字符，并取出其出现的最后索引位置，并将其和当前片段的末尾位置end进行对比，更新最新的end。若当前位置等于最新的end，表示一个新的片段切割完毕，更新start=end+1。
class Solution {
public:
vector<int> partitionLabels(string s) {
int i;
map<char, int> ends; // 存储每一个字符出现的最后位置
for (i=s.size()-1; i>=0; i--) {
char ch = s[i];
if (!ends.count(ch)) {
ends[ch] = i;
}
}
vector<int> ans;
int start = 0;
int end = 0;
for (i=0; i<s.size(); i++) {
end = max(end, ends[s[i]]); // 不断地更新当前字符所需要切分的位置
if (end == i) {
ans.push_back(end - start + 1);
start = end + 1;
}
}
return ans;
}
};动态规划
81. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：
1 <= n <= 45
题解
非常经典的递推做法。dp[i] = dp[i-1] + dp[i-2]，因此每次可以爬1阶或者2阶。
class Solution {
public:
int climbStairs(int n) {
int dp[50];
dp[1] = 1;
dp[2] = 2;
int i;
for (i=3; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};82. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows = 1
输出: [[1]]提示:
1 <= numRows <= 30
题解
此题也很简单。只需明确，每一层的首个元素和末尾元素均为1，其余元素均为上一层对应相邻元素之和。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ans;
vector<int> v0 = {1};
ans.push_back(v0);
if (numRows == 1) return ans;
vector<int> v1 = {1, 1};
ans.push_back(v1);
if (numRows == 2) return ans;
int i = 1;
while (i < numRows - 1) {
vector<int> prev = ans[i];
vector<int> curr;
curr.push_back(1);
for (int j = 0; j<prev.size()-1; j++) {
curr.push_back(prev[j] + prev[j+1]);
}
curr.push_back(1);
ans.push_back(curr);
i++;
}
return ans;
}
};83. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
题解
我们维护一个动态规划数组dp[]，其中dp[i]表示最后偷取nums[i]（nums[i:]部分不考虑）的现金。接下来要考虑状态转移方程。稍微分析一下就会发现，如果选择偷取nums[i]，那么我们可以考虑选取dp[0:i-1]的最大者更新dp[i]；否则，若不偷取nums[i]，则dp[i]=dp[i-1]，维持和昨天的结果即可。这两种情况选取其中较大者。
class Solution {
public:
int rob(vector<int>& nums) {
int dp[105];
int i, j;
dp[0] = nums[0];
if (nums.size() == 1) return dp[0];
dp[1] = max(nums[0], nums[1]);
int ans = max(dp[0], dp[1]);
for (i=2; i<nums.size(); i++) {
int last = 0;
for (j=0; j<i-1; j++) {
last = max(last, dp[j]);
}
dp[i] = max(last + nums[i], dp[i-1]);
ans = max(ans, dp[i]);
}
return ans;
}
};84. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9提示：
1 <= n <= 104
题解
这个问题很明显具备最优子结构。换言之，要求出和为x的完全平方数的最少数量dp[x]，我们可以考虑将其不断地拆分为两数之和i+(x-i)，然后取出其中的最小者min{dp[i] + dp[x-i]}, 1<=i<=x/2更新dp[x]即可。
/*
* @lc app=leetcode.cn id=279 lang=cpp
*
* [279] 完全平方数
*/
// @lc code=start
class Solution {
public:
int numSquares(int n) {
int dp[10005];
int i, j;
for (i=0; i<=100; i++) {
dp[i*i] = 1;
}
for (i=0; i<=n; i++) {
if (!dp[i]) {
dp[i] = 10005;
for (j=1; j<=i/2; j++) {
dp[i] = min(dp[i], dp[j]+dp[i-j]);
}
}
}
return dp[n];
}
};
85. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1示例 2：
输入：coins = [2], amount = 3
输出：-1示例 3：
输入：coins = [1], amount = 0
输出：0提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
题解
这是一个背包问题。经典地，我们维护一个二维数组dp，其中dp[i][x]表示coins[0]~coins[i]凑出x的最少硬币数量。考虑状态转移，
- 对于
coins[i]，我们不选它，那么dp[i][x] = dp[i-1][x]； - 若我们选它，且只选一次，那么
dp[i][x] = dp[i-1][x-coins[i]] + 1； - 若我们选它，且选多次，那么有
dp[i][x] = dp[i][x-coins[i]] + 1。
我们选取三种情况的最小者即可。另外考虑初始情况也很关键。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
sort(coins.begin(), coins.end());
int nums = 0;
while (nums < coins.size()) {
if (coins[nums] > amount) break;
nums++;
}
int i, j;
int dp[15][10005];
int sum = 0;
const int INF = 1e9;
for (i=0; i<nums; i++) {
for (j=0; j<=amount; j++) {
dp[i][j] = INF;
}
}
// 初始情况
for (i=0; i<nums; i++) {
dp[i][coins[i]] = 1;
dp[i][0] = 0;
}
j = 0;
while (j * coins[0] <= amount) {
dp[0][j*coins[0]] = j;
j++;
}
for (i=1; i<nums; i++) {
for (j=0; j<=amount; j++) {
if (j < coins[i]) dp[i][j] = dp[i-1][j];
else {
dp[i][j] = min({dp[i][j-coins[i]]+1, dp[i-1][j-coins[i]]+1, dp[i-1][j]});
}
}
}
int ans = INF;
for (i=0; i<nums; i++) {
ans = min({dp[i][amount], ans});
}
if (ans == INF) ans = -1;
return ans;
}
};86. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
题解
我们可以用深度优先遍历解决此题。我们用变量string s来表示搜索过程中的每个状态，然后在单次DFS搜索过程中，循环遍历检查s首部是否存在wordDict中的单词。
/*
* @lc app=leetcode.cn id=139 lang=cpp
*
* [139] 单词拆分
*/
// @lc code=start
class Solution {
public:
map<string, bool> memo;
bool dfs(string s, vector<string>& wordDict) {
if (memo.count(s)) {
return memo[s];
}
for (string word: wordDict) {
if (s.substr(0, word.size()) == word) {
// 匹配上一个单词，则继续考虑子串
if (s.size() == word.size() || dfs(s.substr(word.size()), wordDict)) {
return memo[s] = true;
}
}
}
// 每一个匹配得上，直接返回false
return memo[s] = false;
}
bool wordBreak(string s, vector<string>& wordDict) {
return dfs(s, wordDict);
}
};
// @lc code=end
87. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
题解
同样地，我们维护一个数组dp，其中dp[i]表示以nums[i]结尾的最长递增子序列长度。此问题也是有最优子结构的，即有状态转移方程
最终取出dp数组中的最大值即可。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int dp[2501];
int i, j;
dp[0] = 1;
for (i=1; i<nums.size(); i++) {
j = i - 1;
int lastDp = 0;
for (j=i-1; j>=0; j--) {
if (nums[j] < nums[i]) {
lastDp = lastDp > dp[j] ? lastDp : dp[j];
}
}
dp[i] = lastDp + 1;
}
int ans = 0;
for (i=0; i<nums.size(); i++) {
ans = ans > dp[i] ? ans : dp[i];
}
return ans;
}
};88. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何子数组的乘积都 保证 是一个 32-位 整数
题解
用双一维动态规划数组实现。这道题和最大子数组和不同，不能直接用动态转移方程dp[i] = max{dp[i-1] + a[i], a[i]}实现，因为在乘积前提下，如此做法不符合最优子结构，因为存在负负得正的情况。因此
- 维护两个数组，dpMax、dpMin，分别存储以nums[i]结尾的最大乘积和最小乘积
- 而当nums[i+1]为正数时，更希望dpMax[i]是一个越大的正数；否则希望dpMin[i]是一个越小的负数
class Solution {
public:
int maxProduct(vector<int>& nums) {
int dpMax[20005], dpMin[20005];
int i;
dpMax[0] = nums[0], dpMin[0] = nums[0];
int ans = dpMax[0];
for (i=1; i<nums.size(); i++) {
// 更简洁的写法，将三种情况合并
dpMax[i] = max({dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]});
dpMin[i] = min({dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]});
ans = max(ans, dpMax[i]);
}
return ans;
}
};89. 分割等和子集[待求解]
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
题解
用二维动态规划，此题是一个典型的背包问题。
设置一个数组dp[i][j]表示前i+1个元素能否凑出和为j，记nums数组全元素之和为sum，则dp[nums.size()-1][sum/2]就是最终答案。
可以写一个带备忘录的动态规划，如果dp数组中已经存下某个位置的答案，直接返回，无需额外计算，节约时间。注意如果sum % 2 == 1，直接返回false。
对于dp[idx][sum]，也就是需要考虑nums[idx]是否需要选中：
- 若
nums[idx] == sum，直接令dp[idx][sum] = 1； - 若满足
nums[idx] < sum，则可以选nums[idx]也可以不选，即dp[idx][sum] = dp[idx-1][sum] || dp[idx-1][sum-nums[idx]]； 否则，只能不选之，则
dp[idx][sum] = dp[idx-1][sum]class Solution { public: int dp[205][20005]; int findDp(int idx, int sum, vector<int>& nums) { if (dp[idx][sum] != -1) return dp[idx][sum]; if (nums[idx] == sum) return dp[idx][sum] = 1; else if (nums[idx] < sum) return dp[idx][sum] = findDp(idx - 1, sum, nums) || findDp(idx - 1, sum - nums[idx], nums); else return dp[idx][sum] = findDp(idx - 1, sum, nums); } bool canPartition(vector<int>& nums) { memset(dp, -1, sizeof(dp)); int i, j; int sum = 0; for (i=0; i<nums.size(); i++) { sum += nums[i]; } if (sum % 2) return false; for (i=0; i<=sum/2; i++) dp[0][i] = 0; dp[0][nums[0]] = 1; return findDp(nums.size() - 1, sum / 2, nums); } };
90. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"示例 3：
输入：s = ""
输出：0提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
题解
动态规划。定义数组dp[n]，其中dp[i]表示以s[i]结尾的所有子串中，最长有效括号子串的长度。接下来考虑状态转移：
若s[i]=’(‘，此时必然有dp[i]=0；
若s[i]=’)’，此时继续考虑s[i-1]：
若s[i-1]=’(‘，显然s[i-1:i]完全匹配，需要查看以s[i-2]结尾的所有子串了，于是$dp[i]=dp[i-2]+2$；
若s[i-1]=’)’，此时末尾出现连续两个’)’，因此需要查看以s[i-1]结尾的所有子串了，并且，以s[i-1]结尾的最长有效子串（记作$\mathrm{sub}_1$）一定是以s[i]结尾的最长有效子串的子串（假设它们都存在），那么只需判断$\mathrm{sub}_1$[0]在原字符串中的左边那个字符是否为’(‘（与s[i]相匹配）即可，表述为
要判定某个括号字符串是否合法，可以用之前题目中的栈模拟方法快速实现。
class Solution {
public:
int longestValidParentheses(string s) {
int i;
int dp[30005];
dp[0] = 0;
for (i=1; i<s.size(); i++) {
if (s[i] == '(') dp[i] = 0;
else {
stack<char> st;
int j = i - 1;
st.push(s[i]);
while (j>=0 && !st.empty()) {
if (s[j] == '(') {
st.pop();
} else {
st.push(s[j]);
}
j--;
}
if (j == -1) {
// 此时字符串s[0:i]全部检查过了，若st为空表示这一部分合法，否则不合法
if (st.empty()) dp[i] = i - j;
else dp[i] = 0;
}
// 此时s[j+1:i]是合法的
else dp[i] = i - j + dp[j];
}
}
int ans = 0;
for (i=0; i<s.size(); i++) {
ans = ans > dp[i] ? ans : dp[i];
}
return ans;
}
};多维动态规划
91. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下示例 3：
输入：m = 7, n = 3
输出：28示例 4：
输入：m = 3, n = 3
输出：6提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
题解
此题是比较基础的多维动态规划。若用dp维护到达每一个位置的走法，则显然有动态转移方程
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[105][105];
int i, j;
for (i=0; i<m; i++) dp[i][0] = 1;
for (j=0; j<n; j++) dp[0][j] = 1;
for (i=1; i<m; i++) {
for (j=1; j<n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};92. 最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 200
题解
显然，状态转移方程为
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int i, j;
int m = grid.size();
int n = grid[0].size();
int dp[205][205];
dp[0][0] = grid[0][0];
for (i=1; i<m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (i=1; i<n; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for (i=1; i<m; i++) {
for (j=1; j<n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
};93. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
题解
我们维护一个二维数组dp，其中dp[i][j]为一个布尔值，指示s[i:j+1]是否为回文串。我们可以将这个问题进行拆分，即s[i] == s[j]以及dp[i+1][j-1]。由此，不难写出状态转移方程：
最后，我们只需遍历dp[i][j]，取出dp[i][j]==true中j-i+1的最大者即可。
class Solution {
public:
int dp[1005][1005];
int findDp(int i, int j, string& s) {
if (dp[i][j] != -1) return dp[i][j];
return dp[i][j] = s[i] == s[j] && findDp(i+1, j-1, s);
}
string longestPalindrome(string s) {
memset(dp, -1, sizeof(dp));
int i, j;
for (i=0; i<s.size(); i++) dp[i][i] = 1;
for (i=0; i<s.size()-1; i++) {
if (s[i] == s[i+1]) dp[i][i+1] = 1;
else dp[i][i+1] = 0;
}
string ans = "";
int maxLen = 0;
for (i=0; i<s.size(); i++) {
for (j=i; j<s.size(); j++) {
dp[i][j] = findDp(i, j, s);
if (dp[i][j] && j - i + 1 > maxLen) {
ans = s.substr(i, j - i + 1);
maxLen = j - i + 1;
}
}
}
return ans;
}
};94. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
题解
同样地，维护一个二维数组dp，其中dp[i][j]表示s1[0:i+1],s2[0:j+1]的最长公共子序列长度。接下来考虑状态转移dp[i][j]的递推公式。
- 若
s1[i]==s2[j]，则s1[i],s2[j]可以匹配成功（公共子序列长度加1），当然也可以选择不匹配，那么dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])； - 否则，
dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])。
class Solution {
public:
int dp[1005][1005];
int findDp(int i, int j, string& text1, string& text2) {
if (dp[i][j] != -1) return dp[i][j];
if (text1[i] == text2[j]) return dp[i][j] = max({findDp(i-1, j-1, text1, text2)+1, findDp(i-1, j, text1, text2), findDp(i, j-1, text1, text2)});
else return dp[i][j] = max({findDp(i-1, j-1, text1, text2), findDp(i-1, j, text1, text2), findDp(i, j-1, text1, text2)});
}
int longestCommonSubsequence(string text1, string text2) {
memset(dp, -1, sizeof(dp));
int i, j;
for (i=0; i<text2.size(); i++) {
if (text1[0] == text2[i]) break;
dp[0][i] = 0;
}
for (; i<text2.size(); i++) dp[0][i] = 1;
for (i=0; i<text1.size(); i++) {
if (text2[0] == text1[i]) break;
dp[i][0] = 0;
}
for (; i<text1.size(); i++) dp[i][0] = 1;
return findDp(text1.size()-1, text2.size()-1, text1, text2);
}
};95. 编辑距离[待求解]
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
题解
仔细分析一下，插入、删除、替换三种操作其实均等价于
- 在单词
A中插入一个字符； - 在单词
B中插入一个字符； - 修改单词
A的一个字符。
class Solution {
public:
int minDistance(string word1, string word2) {
if (!word1.size() || !word2.size()) return max(word1.size(), word2.size());
int i, j;
int dp[505][505];
for (i=0; i<word2.size(); i++) {
if (word1[0] == word2[i]) break;
dp[0][i] = i + 1;
}
for (; i<word2.size(); i++) dp[0][i] = i;
for (i=0; i<word1.size(); i++) {
if (word2[0] == word1[i]) break;
dp[i][0] = i + 1;
}
for (; i<word1.size(); i++) dp[i][0] = i;
for (i=1; i<word1.size(); i++) {
for (j=1; j<word2.size(); j++) {
if (word1[i] != word2[j]) dp[i][j] = min({dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1});
else dp[i][j] = min({dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1]});
}
}
return dp[word1.size()-1][word2.size()-1];
}
};#
96. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
题解
我们可以用位运算巧妙求解此题。考虑到只有某一个元素出现了一次，其余都出现两次，于是可以用异或操作。该运算（^）有重要性质：
- $a \oplus b = b \oplus a$，异或操作满足交换律、结合律
- $a\oplus 0 = a$，0是幺元
- $a \oplus a = 0$，任何数和自身做异或操作，均得零
我们将全部元素都做异或操作，那么出现两次的元素做完异或操作之后均得0，而多余的那个、只出现一次的元素和0做异或操作，得到它自己，即最终的答案。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int i;
int ans = 0;
for (i=0; i<nums.size(); i++) {
ans ^= nums[i];
}
return ans;
}
};97. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109- 输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
题解一
暴力解法，用一个哈希表存储每个元素出现的次数；随后遍历每一个键值对，取出值大于n/2的元素（键）即可。
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int> mp;
int n = nums.size();
int i;
for(i=0; i<n; i++) {
mp[nums[i]]++;
}
for(map<int,int>::iterator iter = mp.begin(); iter != mp.end(); iter++) {
int x = iter->first;
int counts = iter->second;
if (counts > n / 2) {
return x;
}
}
return 0;
}
};题解二
排序。对原数组进行排序，然后直接返回下标为$n/2$的元素（因为一定有某个元素出现次数大于$n/2$，无论该元素是哪个，都会包含中间元素）。
98. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
题解
最简单的思路：既然数组只会出现0、1、2三个数字，那么遍历一遍统计每一个数字出现次数，然后再遍历一遍nums，按照每一个数字出现次数分别赋值即可。
- 时间复杂度：$\mathcal{O}(n)$
- 空间复杂度：需要用到一个map表
class Solution {
public:
void sortColors(vector<int>& nums) {
map<int, int> mp;
for (int x: nums) {
mp[x]++;
}
int i = 0;
int j;
int colors[3] = {0, 1, 2};
for (int color: colors) {
for (j=0; j<mp[color]; j++) {
nums[i+j] = color;
}
i += mp[color];
}
}
};99. 下一个排列[待求解]
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。 - 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。 - 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
题解
寻找下一个字典序比当前序列大的序列，这个要寻找的序列跟当前的序列比起来，我们期望它的左边子序列保持不变的部分尽可能长。举个例子，比如当前序列为
1，4，3，2，7，5，1
我们根据直觉可以分析下一个序列应该是
1，4，3，5，1，2，7
具体的分析过程如下：
从当前序列末尾开始遍历，找到第一个非递减的元素，这里就是[3] = 2
再从末尾遍历，找到第一个大于该元素的元素，这里是[5] = 5
两者交换，得到序列 1，4，3，5，7，2，1
将第一个元素后部分的元素（这里是[4:6]）进行非递减排序，得到最终结果，即1，4，3，5，1，2，7
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
// 循环，找第一个非递减的元素
while (i>=0 && nums[i] >= nums[i+1]) {
// 如果一直递减就一直往前扫描
i--;
}
if (i >= 0) {
int j = nums.size() - 1;
// 然后再找第一个大于nums[i]的元素，将这俩交换
while (j >= 0) {
if (nums[j] > nums[i]) break;
j--;
}
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
}
};100. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2示例 2：
输入：nums = [3,1,3,4,2]
输出：3示例 3 :
输入：nums = [3,3,3,3,3]
输出：3提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
题解
我们建立一个索引i到数组元素nums[i]的映射：$f(i) = nums[i]$，我们来看看不断地嵌套映射会得到什么：
索引：0,1,2,3,4,5
数组元素：1,4,5,2,3,2
有：
- $f(0) = 1$
- $f(1) = 4$
- $f(4) = 3$
- $f(3) = 2$
- $f(2) = 5$
- $f(5) = 2$
可以发现得到的序列其实就是数组元素：1、4、3、2、5、2。如果将其看作链表，那么出现了2、5、2的环，2为环的起点，也正是我们要找的重复元素。
接下来使用弗洛伊德判圈法，设置快慢指针来进行判断。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 当slow==fast时，快慢指针相遇，此时将slow重置，同步移动，相遇处即为环入口
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
