C优选算法精选100道编程题附有图解和源码
目录
C++优选算法精选100道编程题（附有图解和源码）
C++优选算法精选100道编程题（附有图解和源码）
专题一：双指针
双指针介绍
1. 移动零（easy）
代码如下（示例）：
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
int cur = 0;
int dest = -1;
int n = nums.size();
while (cur < n)
{
if (nums[cur] != 0)
{
swap(nums[dest + 1], nums[cur]);
cur++;
dest++;
}
else
{
cur++;
}
}
}
};
// 简便版
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
for (int cur = 0, dest = -1; cur < nums.size(); cur++)
if (nums[cur]) // 处理⾮零元素
swap(nums[++dest], nums[cur]);
}
};2. 复写零（easy）
这里不能从前向后进行复写，会覆盖一些数字！
代码如下（示例）：
class Solution
{
public:
void duplicateZeros(vector<int>& arr)
{
// 1. 先找到最后⼀个数
int cur = 0, dest = -1, n = arr.size();
while (cur < n)
{
if (arr[cur]) dest++;
else dest += 2;
if (dest >= n - 1) break;
cur++;
}
// 2. 处理⼀下边界情况
if (dest == n)
{
arr[n - 1] = 0;
cur--; dest -= 2;
}
// 3. 从后向前完成复写操作
while (cur >= 0)
{
if (arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};3. 快乐数（medium）
代码如下（示例）：
class Solution
{
public:
int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和{
int sum = 0;
while(n)
{
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n, fast = bitSum(n);
while(slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
};4. 盛⽔最多的容器（medium）
代码如下（示例）：
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0, right = height.size() - 1, ret = 0;
while (left < right)
{
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
// 移动指针
if (height[left] < height[right]) left++;
else right--;
}
return ret;
}
};5. 有效三⻆形的个数（medium）
代码如下（示例）：
class Solution
{
public int triangleNumber(int[] nums)
{
// 1. 优化：排序
Arrays.sort(nums);
// 2. 利⽤双指针解决问题
int ret = 0, n = nums.length;
for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
{
// 利⽤双指针快速统计出符合要求的三元组的个数
int left = 0, right = i - 1;
while (left < right)
{
if (nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else
{
left++;
}
}
}
return ret;
}
}6. 和为 s 的两个数字（easy）
代码如下（示例）：
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
int left = 0, right = price.size() - 1;
while (left < right)
{
int sum = price[left] + price[right];
if (sum > target) right--;
else if (sum < target) left++;
else
{
return { price[left] , price[right] };
}
}
return { -1 , -1 };
}
};7. 三数之和（medium）
代码如下（示例）：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> net;
// 第一步：先排序
sort(nums.begin(), nums.end());
// 第二步：先固定一个数 a <= 0
int i = 0, n = nums.size();
for (i = 0; i < n;)
{
if (nums[i] > 0) break;
else
{
// 区间右边用双指针算法
int left = i + 1, right = n - 1, ret = -(nums[i]);
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum < ret) left++;
else if (sum > ret) right--;
else
{
net.push_back({ nums[i] , nums[left] , nums[right] });
left++; right--;
// 去重操作
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
i++;
while (i < n && nums[i] == nums[i - 1]) i++;
}
}
return net;
}
};
// 测试代码如下
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> net;
// 第一步：先排序
sort(nums.begin(), nums.end());
// 第二步：先固定一个数 a <= 0
int i = 0, n = nums.size();
for (i = 0; i < n;)
{
if (nums[i] > 0) break;
else
{
// 区间右边用双指针算法
int left = i + 1, right = n - 1, ret = -(nums[i]);
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum < ret) left++;
else if (sum > ret) right--;
else
{
net.push_back({ nums[i] , nums[left] , nums[right] });
left++; right--;
// 去重操作
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
i++;
while (i < n && nums[i] == nums[i - 1]) i++;
}
}
return net;
}
};
int main()
{
vector<int> v = { -1,0,1,2,-1,-4 };
Solution s;
s.threeSum(v);
return 0;
}8. 四数之和（medium）
写完三数取中之后再写四数取中就会很简单!!!
代码如下（示例）：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
// 先排序
sort(nums.begin() , nums.end());
// 再依次固定一个数 a
int n = nums.size();
for(int i = 0; i < n; )
{
// 三数字取和
for(int j=i+1;j<n;)
{
// 两个数字取和
int left = j+1 , right = n-1 ;
long long sum = (long long)target - nums[i] - nums[j];
while(left < right)
{
int mysum = nums[left] + nums[right];
if(mysum < sum) left++;
else if(mysum > sum) right--;
else
{
ret.push_back({nums[i],nums[j],nums[left],nums[right]});
left++,right--;
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
}
}
j++;
while(j<n && nums[j]==nums[j-1]) j++;
}
i++;
while(i<n && nums[i] == nums[i-1]) i++;
}
return ret;
}
};专题二：滑动窗口
滑动窗口介绍
9. 长度最小的子数组（medium）
代码如下（示例）：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, ret = INT_MAX;
for (int left = 0, right = 0; right < nums.size(); ++right)
{
sum += nums[right];
while (sum >= target)
{
ret = min(ret, right - left + 1);
sum -= nums[left];
left++;
}
}
return ret == INT_MAX ? 0 : ret;
}
};10. 无重复字符的最长子串（medium）
代码如下（示例）：
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int left = 0, right = 0, n = s.size();
int ret = 0;
int hash[128] = { 0 };
while (right < n)
{
hash[s[right]]++;
while (hash[s[right]] > 1) hash[s[left++]]--;
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};11. 最⼤连续 1 的个数 III（medium）
代码如下（示例）：
class Solution {
public:
int longestOnes(vector<int>& nums, int k)
{
int ret = 0;
int left = 0, right = 0, zero = 0;
int n = nums.size();
while (right < n)
{
if (nums[right] == 0) zero++; // 进窗口
while (zero > k)
{
if (nums[left++] == 0) zero--; // 出窗口
}
ret = max(ret, right - left + 1);// 更新结果
right++;
}
return ret;
}
};12. 将 x 减到 0 的最⼩操作数 (medium)
代码如下（示例）：
class Solution
{
public:
int minOperations(vector<int>& nums, int x)
{
int sum = 0;
for (int a : nums) sum += a;
int target = sum - x;
// 细节问题
if (target < 0) return -1;
int ret = -1;
for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
{
tmp += nums[right]; // 进窗⼝
while (tmp > target) // 判断
tmp -= nums[left++]; // 出窗⼝
if (tmp == target) // 更新结果
ret = max(ret, right - left + 1);
}
if (ret == -1) return ret;
else return nums.size() - ret;
}
};13. ⽔果成篮（medium）
代码如下（示例）：
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
int ret = 0;
unordered_map<int, int> hash;
for (int left = 0, right = 0; right < fruits.size(); right++)
{
// 进窗口
hash[fruits[right]]++;
// 判断+出窗口
while (hash.size() > 2)
{
hash[fruits[left]]--;
if (hash[fruits[left]] == 0) hash.erase(fruits[left]);
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
// 数组优化版本
class Solution
{
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
int ret = 0;
for (int left = 0, right = 0, kinds = 0; right < f.size(); right++)
{
if (hash[f[right]] == 0) kinds++; // 维护⽔果的种类
hash[f[right]]++; // 进窗⼝
while (kinds > 2) // 判断
{
// 出窗⼝
hash[f[left]]--;
if (hash[f[left]] == 0) kinds--;
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};14. 找到字符串中所有字⺟异位词（medium）
代码如下（示例）：
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
for (auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
int m = p.size();
for (int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
// 进窗⼝ + 维护 count
hash2[in - 'a']++;
if (hash2[in - 'a'] <= hash1[in - 'a']) count++;
if (right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if (hash2[out - 'a'] <= hash1[out - 'a']) count--;
hash2[out - 'a']--;
}
// 更新结果
if (count == m) ret.push_back(left);
}
return ret;
}
};15. 串联所有单词的⼦串（hard）
代码如下（示例）：
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret;
unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
for(auto& s : words) hash1[s]++;
int len = words[0].size(), m = words.size();
for(int i = 0; i < len; i++) // 执⾏ len 次
{
unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
for(int left = i, right = i, count = 0; right + len <= s.size();
right += len)
{
// 进窗⼝ + 维护 count
string in = s.substr(right, len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判断
if(right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
string out = s.substr(left, len);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
// 更新结果
if(count == m) ret.push_back(left);
}
}
return ret;
}
};16. 最⼩覆盖⼦串（hard）
代码如下（示例）：
class Solution
{
public:
string minWindow(string s, string t)
{
int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for (auto ch : t)
if (hash1[ch]++ == 0) kinds++;
int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
int minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while (count == kinds) // 判断条件
{
if (right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
}
}
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};专题三：二分查找算法
二分查找介绍
17. ⼆分查找（easy）
代码如下（示例）：
class Solution {
public:
int search(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
};18. 在排序数组中查找元素的第⼀个和最后⼀个位置
代码如下（示例）：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
if (nums.size() == 0) return { -1,-1 };
// 先查左端点
int begin = 0;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (nums[left] != target) return { -1,-1 };
else begin = left;
// 再查右端点
left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) left = mid;
else right = mid - 1;
}
return { begin,right };
}
};19. 搜索插⼊位置（easy）
代码如下（示例）：
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (nums[left] < target) return left + 1;
return left;
}
};20. x 的平⽅根（easy）
代码如下（示例）：
// 方法一：暴力枚举
class Solution {
public:
int mySqrt(int x) {
// 由于两个较⼤的数相乘可能会超过 int 最⼤范围
// 因此⽤ long long
long long i = 0;
for (i = 0; i <= x; i++)
{
// 如果两个数相乘正好等于 x，直接返回 i
if (i * i == x) return i;
// 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数
if (i * i > x) return i - 1;
}
// 为了处理oj题需要控制所有路径都有返回值
return -1;
}
};
// 方法二：二分
class Solution
{
public:
int mySqrt(int x)
{
if (x < 1) return 0; // 处理边界情况
int left = 1, right = x;
while (left < right)
{
long long mid = left + (right - left + 1) / 2; // 防溢出
if (mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
};21. 山峰数组的峰顶（easy）
代码如下（示例）：
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
// 第一个和最后一个一定不是山峰
int left = 1, right = arr.size() - 2;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (arr[mid] < arr[mid - 1]) right = mid - 1;
else left = mid;
}
return left;
}
};22. 寻找峰值（medium）
代码如下（示例）：
class Solution {
public:
int findPeakElement(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
};23. 搜索旋转排序数组中的最⼩值（medium）
代码如下（示例）：
class Solution {
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
int x = nums[right];
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < x) right = mid;
else left = mid + 1;
}
return nums[left];
}
};24. 0〜n-1 中缺失的数字（easy）
代码如下（示例）：
class Solution {
public:
int takeAttendance(vector<int>& records)
{
int left = 0, right = records.size()-1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(records[mid] == mid) left = mid + 1;
else right = mid;
}
return records[left] == left ? left+1 : left;
}
};专题四：前缀和
前缀和介绍
25. 【模板】⼀维前缀和（easy）
代码如下（示例）：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
// 1. 读入数据
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
// 2.预处理出来一个前缀和数组
vector<long long> dp(n + 1);
for (int i = 0; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
// 3.使用前缀和数组
int left = 0, right = 0;
while (q--)
{
cin >> left >> right;
cout << dp[right] - dp[left - 1] << endl;
}
return 0;
}26. 【模板】⼆维前缀和（medium）
代码如下（示例）：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
// 1. 读入数据
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> arr[i][j];
// 2. 预处理前缀和矩阵
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
// 3. 使用前缀和矩阵
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
while (q--)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
}
}27. 寻找数组的中心下标（easy）
代码如下（示例）：
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
int n = nums.size();
vector<int> f(n), g(n);
// 1.预处理前缀和两个数组
for (int i = 1; i < n; i++)
f[i] = f[i - 1] + nums[i - 1];
for (int i = n - 2; i >= 0; i--)
g[i] = g[i + 1] + nums[i + 1];
// 2.判断两个数组是否相同
for (int i = 0; i < n; i++)
if (f[i] == g[i])
return i;
return -1;
}
};28. 除⾃⾝以外数组的乘积（medium）
代码如下（示例）：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
int n = nums.size();
vector<int> f(n), g(n);
// 1.先预处理一下前缀积两个数组
f[0] = g[n - 1] = 1;
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--)
g[i] = g[i + 1] * nums[i + 1];
// 2.判断并且使用
vector<int> ret(n);
for (int i = 0; i < n; i++)
{
ret[i] = f[i] * g[i];
}
return ret;
}
};29. 和为 k 的子数组（medium）
代码如下（示例）：
class Solution {
public:
int subarraySum(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
hash[0] = 1;
int sum = 0, ret = 0;
for (auto x : nums)
{
sum += x;
if (hash.count(sum - k))
ret += hash[sum - k]; // 统计个数
hash[sum]++;
}
return ret;
}
};30. 和可被 K 整除的⼦数组（medium）
代码如下（示例）：
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
hash[0 % k] = 1; // 0 这个数的余数
int sum = 0, ret = 0;
for (auto x : nums)
{
sum += x; // 算出当前位置的前缀和
int r = (sum % k + k) % k; // 修正后的余数
if (hash.count(r))
ret += hash[r]; // 统计结果
hash[r]++;
}
return ret;
}
};31. 连续数组（medium）
代码如下（示例）：
class Solution
{
public:
int findMaxLength(vector<int>& nums)
{
unordered_map<int, int> hash;
hash[0] = -1; // 默认有⼀个前缀和为 0 的情况
int sum = 0, ret = 0;
for (int i = 0; i < nums.size(); i++)
{
sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
if (hash.count(sum)) ret = max(ret, i - hash[sum]);
else hash[sum] = i;
}
return ret;
}
};32. 矩阵区域和（medium）
代码如下（示例）：
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 1. 预处理前缀和矩阵
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
mat[i - 1][j - 1];
// 2. 使⽤
vector<vector<int>> ret(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +
dp[x1 - 1][y1 - 1];
}
return ret;
}
};专题五：位运算
位运算介绍
33. 判断字符是否唯⼀（easy）
代码如下（示例）：
class Solution {
public:
bool isUnique(string astr) {
// 鹊巢原理优化
if (astr.size() > 26)
return false;
// 利用位图的思想求解
int bitMap = 0;
for (auto ch : astr)
{
int i = ch - 'a';
// 先判断字符是否已经出现过
if (((bitMap >> i) & 1) == 1)
return false;
// 把当前字符加⼊到位图中
bitMap |= 1 << i;
}
return true;
}
};34. 丢失的数字（easy）
代码如下（示例）：
class Solution
{
public:
int missingNumber(vector<int>& nums)
{
int ret = 0;
for (auto x : nums) ret ^= x;
for (int i = 0; i <= nums.size(); i++) ret ^= i;
return ret;
}
};–
35. 两整数之和（medium）
代码如下（示例）：
class Solution
{
public:
int getSum(int a, int b)
{
while (b != 0)
{
int x = a ^ b; // 先算出⽆进位相加的结果
unsigned int carry = (unsigned int)(a & b) << 1; // 算出进位
a = x;
b = carry;
}
return a;
}
};36. 只出现⼀次的数字 II（medium）
代码如下（示例）：
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
int ret = 0;
for (int i = 0; i < 32; i++) // 依次去修改 ret 中的每⼀位
{
int sum = 0;
for (int x : nums) // 计算nums中所有的数的第 i 位的和
if (((x >> i) & 1) == 1)
sum++;
sum %= 3;
if (sum == 1) ret |= 1 << i;
}
return ret;
}
};37. 消失的两个数字（hard）
代码如下（示例）：
class Solution
{
public:
vector<int> missingTwo(vector<int>& nums)
{
// 1. 将所有的数异或在⼀起
int tmp = 0;
for (auto x : nums) tmp ^= x;
for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// 2. 找出 a，b 中⽐特位不同的那⼀位
int diff = 0;
while (1)
{
if (((tmp >> diff) & 1) == 1) break;
else diff++;
}
// 3. 根据 diff 位的不同，将所有的数划分为两类来异或
int a = 0, b = 0;
for (int x : nums)
if (((x >> diff) & 1) == 1) b ^= x;
else a ^= x;
for (int i = 1; i <= nums.size() + 2; i++)
if (((i >> diff) & 1) == 1) b ^= i;
else a ^= i;
return { a, b };
}
};专题六：模拟
模拟介绍
38. 替换所有的问号（easy）
代码如下（示例）：
class Solution
{
public:
string modifyString(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
{
if (s[i] == '?') // 替换
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i+ 1]))
{
s[i] = ch;
break;
}
}
}
}
return s;
}
};39. 提莫攻击（easy）
代码如下（示例）：
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
int ret = 0;
for (int i = 1; i < timeSeries.size(); i++)
{
int x = timeSeries[i] - timeSeries[i - 1];
if (x >= duration) ret += duration;
else ret += x;
}
return ret + duration;
}
};40. N 字形变换（medium）
代码如下（示例）：
class Solution
{
public:
string convert(string s, int numRows)
{
// 处理边界情况
if (numRows == 1) return s;
string ret;
int d = 2 * numRows - 2, n = s.size();
// 1. 先处理第⼀⾏
for (int i = 0; i < n; i += d)
ret += s[i];
// 2. 处理中间⾏
for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
{
for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
{
if (i < n) ret += s[i];
if (j < n) ret += s[j];
}
}
// 3. 处理最后⼀⾏
for (int i = numRows - 1; i < n; i += d)
ret += s[i];
return ret;
}
};41. 外观数列 (medium)
代码如下（示例）：
class Solution
{
public:
string countAndSay(int n)
{
string ret = "1";
for (int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可
{
string tmp;
int len = ret.size();
for (int left = 0, right = 0; right < len; )
{
while (right < len && ret[left] == ret[right]) right++;
tmp += to_string(right - left) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};42. 数⻘蛙（medium）
代码如下（示例）：
class Solution
{
public:
int minNumberOfFrogs(string croakOfFrogs)
{
string t = "croak";
int n = t.size();
vector<int> hash(n); // ⽤数组来模拟哈希表
unordered_map<char, int> index; //[x, x这个字符对应的下标]
for (int i = 0; i < n; i++)
index[t[i]] = i;
for (auto ch : croakOfFrogs)
{
if (ch == 'c')
{
if (hash[n - 1] != 0) hash[n - 1]--;
hash[0]++;
}
else
{
int i = index[ch];
if (hash[i - 1] == 0) return -1;
hash[i - 1]--; hash[i]++;
}
}
for (int i = 0; i < n - 1; i++)
if (hash[i] != 0)
return -1;
return hash[n - 1];
}
};专题七：分治快排
分治快排介绍
43. 颜色分类（medium）
代码如下（示例）：
class Solution {
public:
void sortColors(vector<int>& nums)
{
int left = -1, right = nums.size(), i = 0;
while (i < right)
{
if (nums[i] == 0) swap(nums[++left], nums[i++]);
else if (nums[i] == 2) swap(nums[--right], nums[i]);
else i++;
}
}
};44. 快速排序（medium）
代码如下（示例）：
class Solution
{
public:
vector<int> sortArray(vector<int>& nums)
{
srand(time(NULL)); // 种下⼀个随机数种⼦
qsort(nums, 0, nums.size() - 1);
return nums;
}
// 快排
void qsort(vector<int>& nums, int l, int r)
{
if (l >= r) return;
// 数组分三块
int key = getRandom(nums, l, r);
int i = l, left = l - 1, right = r + 1;
while (i < right)
{
if (nums[i] < key) swap(nums[++left], nums[i++]);
else if (nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
// [l, left] [left + 1, right - 1] [right, r]
qsort(nums, l, left);
qsort(nums, right, r);
}
int getRandom(vector<int>& nums, int left, int right)
{
int r = rand();
return nums[r % (right - left + 1) + left];
}
};45. 快速选择算法（medium）
代码如下（示例）：
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
srand(time(NULL));
return qsort(nums, 0, nums.size() - 1, k);
}
int qsort(vector<int>& nums, int l, int r, int k)
{
if (l == r) return nums[l];
// 1. 随机选择基准元素
int key = getRandom(nums, l, r);
// 2. 根据基准元素将数组分三块
int left = l - 1, right = r + 1, i = l;
while (i < right)
{
if (nums[i] < key) swap(nums[++left], nums[i++]);
else if (nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
// 3. 分情况讨论
int c = r - right + 1, b = right - left - 1;
if (c >= k) return qsort(nums, right, r, k);
else if (b + c >= k) return key;
else return qsort(nums, l, left, k - b - c);
}
int getRandom(vector<int>& nums, int left, int right)
{
return nums[rand() % (right - left + 1) + left];
}
};
46. 最⼩的 k 个数（medium）
代码如下（示例）：
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& nums, int k)
{
srand(time(NULL));
qsort(nums, 0, nums.size() - 1, k);
return { nums.begin(), nums.begin() + k };
}
void qsort(vector<int>& nums, int l, int r, int k)
{
if (l >= r) return;
// 1. 随机选择⼀个基准元素 + 数组分三块
int key = getRandom(nums, l, r);
int left = l - 1, right = r + 1, i = l;
while (i < right)
{
if (nums[i] < key) swap(nums[++left], nums[i++]);
else if (nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
// [l, left][left + 1, right - 1] [right, r]
// 2. 分情况讨论
int a = left - l + 1, b = right - left - 1;
if (a > k) qsort(nums, l, left, k);
else if (a + b >= k) return;
else qsort(nums, right, r, k - a - b);
}
int getRandom(vector<int>& nums, int l, int r)
{
return nums[rand() % (r - l + 1) + l];
}
};专题八：分治归并
分治归并介绍
47. 归并排序（medium）
代码如下（示例）：
class Solution
{
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return;
// 1. 选择中间点划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 把左右区间排序
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 合并两个有序数组
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] :
nums[cur2++];
// 处理没有遍历完的数组
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
// 4. 还原
for (int i = left; i <= right; i++)
nums[i] = tmp[i - left];
}
};48. 数组中的逆序对（hard）
代码如下（示例）：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 找中间点，将数组分成两部分
int mid = (left + right) >> 1;
// [left, mid][mid + 1, right]
// 2. 左边的个数 + 排序 + 右边的个数 + 排序
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. ⼀左⼀右的个数
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) // 升序的时候
{
if (nums[cur1] <= nums[cur2])
{
tmp[i++] = nums[cur1++];
}
else
{
ret += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
// 4. 处理⼀下排序
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++)
nums[j] = tmp[j - left];
return ret;
}
};49. 计算右侧⼩于当前元素的个数（hard）
代码如下（示例）：
class Solution
{
vector<int> ret;
vector<int> index; // 记录 nums 中当前元素的原始下标
int tmpNums[500010];
int tmpIndex[500010];
public:
vector<int> countSmaller(vector<int>& nums)
{
int n = nums.size();
ret.resize(n);
index.resize(n);
// 初始化⼀下 index 数组
for (int i = 0; i < n; i++)
index[i] = i;
mergeSort(nums, 0, n - 1);
return ret;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return;
// 1. 根据中间元素，划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先处理左右两部分
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右的情况
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) // 降序
{
if (nums[cur1] <= nums[cur2])
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
else
{
ret[index[cur1]] += right - cur2 + 1; // 重点
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
// 4. 处理剩下的排序过程
while (cur1 <= mid)
{
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right)
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for (int j = left; j <= right; j++)
{
nums[j] = tmpNums[j - left];
index[j] = tmpIndex[j - left];
}
}
};50. 翻转对（hard）
代码如下（示例）：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if (left >= right) return 0;
int ret = 0;
// 1. 先根据中间元素划分区间
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
// 2. 先计算左右两侧的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 先计算翻转对的数量
int cur1 = left, cur2 = mid + 1, i = left;
while (cur1 <= mid) // 降序的情况
{
while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
if (cur2 > right)
break;
ret += right - cur2 + 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left, cur2 = mid + 1;
while (cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++)
nums[j] = tmp[j];
return ret;
}
};专题九：链表
链表常用技巧和操作总结
51. 两数相加（medium）
代码如下（示例）：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* cur1 = l1, * cur2 = l2;
ListNode* newhead = new ListNode(0);//创建虚拟头节点，记录最终结果
ListNode* prev = newhead;// 尾指针
int t = 0;// 进位
while (cur1 || cur2 || t)
{
if (cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if (cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
prev->next = new ListNode(t % 10);
prev = prev->next;
t /= 10;
}
prev = newhead->next;
delete newhead;
return prev;
}
};52. 两两交换链表中的节点（medium）
代码如下（示例）：
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
if (head == nullptr || head->next == nullptr) return head;
ListNode* newHead = new ListNode(0);
newHead->next = head;
ListNode* prev = newHead, * cur = prev->next, * next = cur->next, * nnext
= next->next;
while (cur && next)
{
// 交换结点
prev->next = next;
next->next = cur;
cur->next = nnext;
// 修改指针
prev = cur; // 注意顺序
cur = nnext;
if (cur) next = cur->next;
if (next) nnext = next->next;
}
cur = newHead->next;
delete newHead;
return cur;
}
};53. 重排链表（medium）
代码如下（示例）：
class Solution
{
public:
void reorderList(ListNode* head)
{
// 处理边界情况
if (head == nullptr || head->next == nullptr || head->next->next ==
nullptr) return;
// 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥）
ListNode* slow = head, * fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
// 2. 把 slow 后⾯的部分给逆序 - 头插法
ListNode* head2 = new ListNode(0);
ListNode* cur = slow->next;
slow->next = nullptr; // 注意把两个链表给断开
while (cur)
{
ListNode* next = cur->next;
cur->next = head2->next;
head2->next = cur;
cur = next;
}
// 3. 合并两个链表 - 双指针
ListNode* ret = new ListNode(0);
ListNode* prev = ret;
ListNode* cur1 = head, * cur2 = head2->next;
while (cur1)
{
// 先放第⼀个链表
prev->next = cur1;
cur1 = cur1->next;
prev = prev->next;
// 再放第⼆个链表
if (cur2)
{
prev->next = cur2;
prev = prev->next;
cur2 = cur2->next;
}
}
delete head2;
delete ret;
}
};54. 合并 K 个升序链表（hard）
代码如下（示例）：
class Solution
{
struct cmp
{
bool operator()(const ListNode* l1, const ListNode* l2)
{
return l1->val > l2->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
// 创建⼀个⼩根堆
priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
// 让所有的头结点进⼊⼩根堆
for (auto l : lists)
if (l) heap.push(l);
// 合并 k 个有序链表
ListNode* ret = new ListNode(0);
ListNode* prev = ret;
while (!heap.empty())
{
ListNode* t = heap.top();
heap.pop();
prev->next = t;
prev = t;
if (t->next) heap.push(t->next);
}
prev = ret->next;
delete ret;
return prev;
}
};
// 递归
class Solution
{
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
return merge(lists, 0, lists.size() - 1);
}
ListNode* merge(vector<ListNode*>& lists, int left, int right)
{
if (left > right) return nullptr;
if (left == right) return lists[left];
// 1. 平分数组
int mid = left + right >> 1;
// [left, mid] [mid + 1, right]
// 2. 递归处理左右区间
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
// 3. 合并两个有序链表
return mergeTowList(l1, l2);
}
ListNode* mergeTowList(ListNode* l1, ListNode* l2)
{
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
// 合并两个有序链表
ListNode head;
ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
head.next = nullptr;
while (cur1 && cur2)
{
if (cur1->val <= cur2->val)
{
prev = prev->next = cur1;
cur1 = cur1->next;
}
else
{
prev = prev->next = cur2;
cur2 = cur2->next;
}
}
if (cur1) prev->next = cur1;
if (cur2) prev->next = cur2;
return head.next;
}
};55. K个⼀组翻转链表（hard）
代码如下（示例）：
class Solution
{
public:
ListNode* reverseKGroup(ListNode* head, int k)
{
// 1. 先求出需要逆序多少组
int n = 0;
ListNode* cur = head;
while (cur)
{
cur = cur->next;
n++;
}
n /= k;
// 2. 重复 n 次：⻓度为 k 的链表的逆序即可
ListNode* newHead = new ListNode(0);
ListNode* prev = newHead;
cur = head;
for (int i = 0; i < n; i++)
{
ListNode* tmp = cur;
for (int j = 0; j < k; j++)
{
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
}
prev = tmp;
}
// 把不需要翻转的接上
prev->next = cur;
cur = newHead->next;
delete newHead;
return cur;
}
};专题十：哈希表
哈希表简介
56. 两数之和（easy）
代码如下（示例）：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
for (int i = 0; i < nums.size(); i++)
{
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] + nums[j] == target) return { i , j };
}
}
return { -1 , -1 };
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hash; // <nums[i], i>
for (int i = 0; i < nums.size(); i++)
{
int x = target - nums[i];
if (hash.count(x)) return { hash[x] , i };
hash[nums[i]] = i;
}
return { -1 , -1 };
}
};57. 判断是否互为字符重排（easy）
代码如下（示例）：
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if (s1.size() != s2.size()) return false;
int hash[26] = { 0 };
// 先统计第一个字符串的信息
for (auto x : s1) hash[x - 'a']++;
// 再扫描第二个字符串，看看是否能重排
for (auto x : s2)
{
hash[x - 'a']--;
if (hash[x - 'a'] < 0) return false;
}
return true;
}
};58. 存在重复元素 I（easy）
代码如下（示例）：
class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash;
for (auto x : nums)
{
if (hash.count(x)) return true;
else hash.insert(x);
}
return false;
}
};59. 存在重复元素 II（easy）
代码如下（示例）：
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++)
{
if (hash.count(nums[i]))
{
if (i - hash[nums[i]] <= k) return true;
}
hash[nums[i]] = i;
}
return false;
}
};60. 字⺟异位词分组（medium）
代码如下（示例）：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> hash;
// 1.把所有的字母异位词分组
for (auto& s : strs)
{
string tmp = s;
sort(tmp.begin(), tmp.end());
hash[tmp].push_back(s);
}
// 2.结果提取出来
vector<vector<string>> ret;
for (auto& [x, y] : hash)
{
ret.push_back(y);
}
return ret;
}
};专题十一：字符串
61. 最⻓公共前缀（easy）
代码如下（示例）：
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
// 解法⼀：两两⽐较
string ret = strs[0];
for (int i = 1; i < strs.size(); i++)
ret = findCommon(ret, strs[i]);
return ret;
}
string findCommon(string& s1, string& s2)
{
int i = 0;
while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
return s1.substr(0, i);
}
};
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
// 解法⼆：统⼀⽐较
for (int i = 0; i < strs[0].size(); i++)
{
char tmp = strs[0][i];
for (int j = 1; j < strs.size(); j++)
if (i == strs[j].size() || tmp != strs[j][i])
return strs[0].substr(0, i);
}
return strs[0];
}
};62. 最⻓回⽂⼦串 (medium)
代码如下（示例）：
class Solution
{
public:
string longestPalindrome(string s)
{
// 中⼼扩展算法
int begin = 0, len = 0, n = s.size();
for (int i = 0; i < n; i++) // 依次枚举所有的中点
{
// 先做⼀次奇数⻓度的扩展
int left = i, right = i;
while (left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if (right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
// 偶数⻓度的扩展
left = i, right = i + 1;
while (left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if (right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
}
return s.substr(begin, len);
}
};63. ⼆进制求和（easy）
代码如下（示例）：
class Solution {
public:
string addBinary(string a, string b)
{
string str;
int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
while (cur1 >= 0 || cur2 >= 0 || t)
{
if (cur1 >= 0) t += a[cur1--] - '0';
if (cur2 >= 0) t += b[cur2--] - '0';
str += t % 2 + '0';
t /= 2;
}
reverse(str.begin(), str.end());
return str;
}
};64. 字符串相乘（medium）
代码如下（示例）：
class Solution
{
public:
string multiply(string n1, string n2)
{
// 解法：⽆进位相乘后相加，然后处理进位
int m = n1.size(), n = n2.size();
reverse(n1.begin(), n1.end());
reverse(n2.begin(), n2.end());
vector<int> tmp(m + n - 1);
// 1. ⽆进位相乘后相加
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
// 2. 处理进位
int cur = 0, t = 0;
string ret;
while (cur < m + n - 1 || t)
{
if (cur < m + n - 1) t += tmp[cur++];
ret += t % 10 + '0';
t /= 10;
}
// 3. 处理前导零
while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};专题十二：栈
65. 删除字符中的所有相邻重复项（easy）
代码如下（示例）：
class Solution
{
public:
string removeDuplicates(string s)
{
string ret; // 搞⼀个数组，模拟栈结构即可
for (auto ch : s)
{
if (ret.size() && ch == ret.back()) ret.pop_back(); // 出栈
else ret += ch; // ⼊栈
}
return ret;
}
};66. ⽐较含退格的字符串（easy）
代码如下（示例）：
class Solution
{
public:
bool backspaceCompare(string s, string t)
{
return changeStr(s) == changeStr(t);
}
string changeStr(string& s)
{
string ret; // ⽤数组模拟栈结构
for (char ch : s)
{
if (ch != '#') ret += ch;
else
{
if (ret.size()) ret.pop_back();
}
}
return ret;
}
};
class Solution {
public:
bool backspaceCompare(string s, string t)
{
string str1, str2;
for (auto x : s)
{
if (str1.size() && x == '#') str1.pop_back();
else {
if (x != '#') str1 += x;
}
}
for (auto x : t)
{
if (str2.size() && x == '#') str2.pop_back();
else {
if (x != '#') str2 += x;
}
}
return strcmp(str1.c_str(), str2.c_str()) == 0;
}
};67. 基本计算器 II（medium）
代码如下（示例）：
class Solution
{
public:
int calculate(string s)
{
vector<int> st; // ⽤数组来模拟栈结构
int i = 0, n = s.size();
char op = '+';
while (i < n)
{
if (s[i] == ' ') i++;
else if (s[i] >= '0' && s[i] <= '9')
{
// 先把这个数字给提取出来
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9')
tmp = tmp * 10 + (s[i++] - '0');
if (op == '+') st.push_back(tmp);
else if (op == '-') st.push_back(-tmp);
else if (op == '*') st.back() *= tmp;
else st.back() /= tmp;
}
else
{
op = s[i];
i++;
}
}
int ret = 0;
for (auto x : st) ret += x;
return ret;
}
};68. 字符串解码（medium）
代码如下（示例）：
class Solution
{
public:
string decodeString(string s)
{
stack<int> nums;
stack<string> st;
st.push("");
int i = 0, n = s.size();
while (i < n)
{
if (s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while (s[i] >= '0' && s[i] <= '9')
{
tmp = tmp * 10 + (s[i] - '0');
i++;
}
nums.push(tmp);
}
else if (s[i] == '[')
{
i++; // 把括号后⾯的字符串提取出来
string tmp = "";
while (s[i] >= 'a' && s[i] <= 'z')
{
tmp += s[i];
i++;
}
st.push(tmp);
}
else if (s[i] == ']')
{
string tmp = st.top();
st.pop();
int k = nums.top();
nums.pop();
while (k--)
{
st.top() += tmp;
}
i++; // 跳过这个右括号
}
else
{
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z')
{
tmp += s[i];
i++;
}
st.top() += tmp;
}
}
return st.top();
}
};69. 验证栈序列（medium）
代码如下（示例）：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int> st;
int i = 0, n = pushed.size();
for (auto x : pushed)
{
st.push(x);
while (st.size() && st.top() == popped[i])
{
st.pop();
i++;
}
}
return i == n;
}
};专题十三：队列 + 宽搜 (BFS)
70. N 叉树的层序遍历（medium）
代码如下（示例）：
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
vector<vector<int>> levelOrder(Node* root)
{
vector<vector<int>> ret;// 记录最终结果
queue<Node*> q; // 层序遍历需要的队列
if (root == nullptr) return ret;
q.push(root);
while (q.size())
{
int sz = q.size(); // 求出本层元素的个数
vector<int> tmp; //统计本层的节点
for (int i = 0; i < sz; i++)
{
Node* t = q.front(); // 取出对头
q.pop();
tmp.push_back(t->val);
for (Node* child : t->children) //让下一层节点入队列
{
if (child != nullptr) q.push(child);
}
}
ret.push_back(tmp);
}
return ret;
}
};71. ⼆叉树的锯⻮形层序遍历（medium）
代码如下（示例）：
/**
* 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>> zigzagLevelOrder(TreeNode* root)
{
vector<vector<int>> ret;
if(root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
int level = 1;
while(q.size())
{
int sz = q.size();
vector<int> tmp;
for(int i = 0 ; i < sz ; i++)
{
auto t = q.front();
q.pop();
tmp.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
// 判断是否逆序
if(level % 2 == 0) reverse(tmp.begin() , tmp.end());
ret.push_back(tmp);
level++;
}
return ret;
}
};72. ⼆叉树的最⼤宽度（medium）
代码如下（示例）：
/**
* 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 widthOfBinaryTree(TreeNode* root)
{
vector<pair<TreeNode*, unsigned int>> q;//用数组模拟队列
q.push_back({ root , 1 });
unsigned int ret = 0;
while (q.size())
{
// 先更新这一层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
// 让下一层进队列
vector<pair<TreeNode*, unsigned int>> tmp;//让下一层进入这个队列
for (auto& [x, y] : q)
{
if (x->left) tmp.push_back({ x->left, y * 2 });
if (x->right) tmp.push_back({ x->right, y * 2 + 1 });
}
q = tmp;
}
return ret;
}
};73. 在每个树⾏中找最⼤值（medium）
代码如下（示例）：
class Solution
{
public:
vector<int> largestValues(TreeNode* root)
{
vector<int> ret;
if (root == nullptr) return ret;
queue<TreeNode*> q;
q.push(root);
while (q.size())
{
int sz = q.size();
int tmp = INT_MIN;
for (int i = 0; i < sz; i++)
{
auto t = q.front();
q.pop();
tmp = max(tmp, t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
ret.push_back(tmp);
}
return ret;
}
};专题十四：优先级队列 (堆)
74. 最后⼀块石头的重量（easy）
代码如下（示例）：
class Solution
{
public:
int lastStoneWeight(vector<int>& stones)
{
// 1. 创建⼀个⼤根堆
priority_queue<int> heap;
// 2. 将所有元素丢进这个堆⾥⾯
for (auto x : stones) heap.push(x);
// 3. 模拟这个过程
while (heap.size() > 1)
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
if (a > b) heap.push(a - b);
}
return heap.size() ? heap.top() : 0;
}
};75. 数据流中的第 K ⼤元素（easy）
代码如下（示例）：
class KthLargest
{
// 创建⼀个⼤⼩为 k 的⼩跟堆
priority_queue<int, vector<int>, greater<int>> heap;
int _k;
public:
KthLargest(int k, vector<int>& nums)
{
_k = k;
for (auto x : nums)
{
heap.push(x);
if (heap.size() > _k) heap.pop();
}
}
int add(int val)
{
heap.push(val);
if (heap.size() > _k) heap.pop();
return heap.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/76. 前 K 个⾼频单词 （medium）
代码如下（示例）：
class Solution
{
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& a, const PSI& b)
{
if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列
{
return a.first < b.first;
}
return a.second > b.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k)
{
// 1. 统计⼀下每⼀个单词的频次
unordered_map<string, int> hash;
for (auto& s : words) hash[s]++;
// 2. 创建⼀个⼤⼩为 k 的堆
priority_queue<PSI, vector<PSI>, cmp> heap;
// 3. TopK 的主逻辑
for (auto& psi : hash)
{
heap.push(psi);
if (heap.size() > k) heap.pop();
}
// 4. 提取结果
vector<string> ret(k);
for (int i = k - 1; i >= 0; i--)
{
ret[i] = heap.top().first;
heap.pop();
}
return ret;
}
};77. 数据流的中位数（hard）
代码如下（示例）：
class MedianFinder
{
priority_queue<int> left; // ⼤根堆
priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:
MedianFinder()
{}
void addNum(int num)
{
// 分类讨论即可
if (left.size() == right.size()) // 左右两个堆的元素个数相同
{
if (left.empty() || num <= left.top()) // 放 left ⾥⾯
{
left.push(num);
}
else
{
right.push(num);
left.push(right.top());
right.pop();
}
}
else
{
if (num <= left.top())
{
left.push(num);
right.push(left.top());
left.pop();
}
else
{
right.push(num);
}
}
}
double findMedian()
{
if (left.size() == right.size()) return (left.top() + right.top()) /
2.0;
else return left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/专题十五：BFS解决FloodFill算法
BFS和FloodFill介绍
78. 图像渲染（medium）
代码如下（示例）：
class Solution {
public:
typedef pair<int, int> PII;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{
int prev = image[sr][sc];
if (prev == color) return image;
int m = image.size(), n = image[0].size();
queue<PII> q;
q.push({ sr,sc });
while (!q.empty())
{
auto [a, b] = q.front();
image[a][b] = color;
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
{
q.push({ x,y });
}
}
}
return image;
}
};79. 岛屿数量（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
bool vis[301][301];
int m, n;
public:
int numIslands(vector<vector<char>>& grid)
{
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && !vis[i][j])
{
ret++;
bfs(grid, i, j); // 把这块陆地全部标记⼀下
}
}
}
return ret;
}
void bfs(vector<vector<char>>& grid, int i, int j)
{
queue<pair<int, int>> q;
q.push({ i, j });
vis[i][j] = true;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' &&
!vis[x][y])
{
q.push({ x, y });
vis[x][y] = true;
}
}
}
}
};80. 岛屿的最大面积（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
bool vis[51][51];
int m, n;
public:
int maxAreaOfIsland(vector<vector<int>>& grid)
{
m = grid.size(), n = grid[0].size();
int ret = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1 && !vis[i][j])
{
ret = max(ret, bfs(grid, i, j));
}
}
}
return ret;
}
int bfs(vector<vector<int>>& grid, int i, int j)
{
int count = 0;
queue<pair<int, int>> q;
q.push({ i, j });
vis[i][j] = true;
count++;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
!vis[x][y])
{
q.push({ x, y });
vis[x][y] = true;
count++;
}
}
}
return count;
}
};81. 被围绕的区域（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int m, n;
public:
void solve(vector<vector<char>>& board)
{
m = board.size(), n = board[0].size();
// 1. 先处理边界上的 'O' 联通块，全部修改成 '.'
for (int j = 0; j < n; j++)
{
if (board[0][j] == 'O') bfs(board, 0, j);
if (board[m - 1][j] == 'O') bfs(board, m - 1, j);
}
for (int i = 0; i < m; i++)
{
if (board[i][0] == 'O') bfs(board, i, 0);
if (board[i][n - 1] == 'O') bfs(board, i, n - 1);
}
// 2. 还原
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == '.') board[i][j] = 'O';
}
void bfs(vector<vector<char>>& board, int i, int j)
{
queue<pair<int, int>> q;
q.push({ i, j });
board[i][j] = '.';
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
{
q.push({ x, y });
board[x][y] = '.';
}
}
}
}
};专题十六：BFS解决最短路径问题
最短路径问题介绍
82. 迷宫中离入口最近的出口（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& e)
{
int m = maze.size(), n = maze[0].size();
bool vis[m][n];
memset(vis, 0, sizeof vis);
queue<pair<int, int>> q;
q.push({ e[0], e[1] });
vis[e[0]][e[1]] = true;
int step = 0;
while (q.size())
{
step++;
int sz = q.size();
for (int i = 0; i < sz; i++)
{
auto [a, b] = q.front();
q.pop();
for (int j = 0; j < 4; j++)
{
int x = a + dx[j], y = b + dy[j];
if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.'
&& !vis[x][y])
{
// 判断是否已经到达出⼝
if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return
step;
q.push({ x, y });
vis[x][y] = true;
}
}
}
}
return -1;
}
};83. 最⼩基因变化（medium）
代码如下（示例）：
class Solution
{
public:
int minMutation(string startGene, string endGene, vector<string>& bank)
{
unordered_set<string> vis; // ⽤来标记已经搜索过的状态
unordered_set<string> hash(bank.begin(), bank.end()); // 存储基因库⾥⾯的字符串
string change = "ACGT";
if (startGene == endGene) return 0;
if (!hash.count(endGene)) return -1;
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret = 0;
while (q.size())
{
ret++;
int sz = q.size();
while (sz--)
{
string t = q.front();
q.pop();
for (int i = 0; i < 8; i++)
{
string tmp = t; // 细节问题
for (int j = 0; j < 4; j++)
{
tmp[i] = change[j];
if (hash.count(tmp) && !vis.count(tmp))
{
if (tmp == endGene) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};84. 单词接⻰（hard）
代码如下（示例）：
class Solution
{
public:
int ladderLength(string beginWord, string endWord, vector<string>&
wordList)
{
unordered_set<string> hash(wordList.begin(), wordList.end());
unordered_set<string> vis; // 标记已经搜索过的单词
if (!hash.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
vis.insert(beginWord);
int ret = 1;
while (q.size())
{
ret++;
int sz = q.size();
while (sz--)
{
string t = q.front();
q.pop();
for (int i = 0; i < t.size(); i++)
{
string tmp = t;
for (char ch = 'a'; ch <= 'z'; ch++)
{
tmp[i] = ch;
if (hash.count(tmp) && !vis.count(tmp))
{
if (tmp == endWord) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};85. 为高尔夫比赛砍树（hard）
代码如下（示例）：
class Solution
{
int m, n;
public:
int cutOffTree(vector<vector<int>>& f)
{
m = f.size(), n = f[0].size();
// 1. 准备⼯作：找出砍树的顺序
vector<pair<int, int>> trees;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (f[i][j] > 1) trees.push_back({ i, j });
sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const
pair<int, int>& p2)
{
return f[p1.first][p1.second] < f[p2.first][p2.second];
});
// 2. 按照顺序砍树
int bx = 0, by = 0;
int ret = 0;
for (auto& [a, b] : trees)
{
int step = bfs(f, bx, by, a, b);
if (step == -1) return -1;
ret += step;
bx = a, by = b;
}
return ret;
}
bool vis[51][51];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
{
if (bx == ex && by == ey) return 0;
queue<pair<int, int>> q;
memset(vis, 0, sizeof vis); // 清空之前的数据
q.push({ bx, by });
vis[bx][by] = true;
int step = 0;
while (q.size())
{
step++;
int sz = q.size();
while (sz--)
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] && !vis[x]
[y])
{
if (x == ex && y == ey) return step;
q.push({ x, y });
vis[x][y] = true;
}
}
}
}
return -1;
}
};专题十七：多源BFS
多源最短路径问题介绍
86. 01 矩阵（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
int m = mat.size(), n = mat[0].size();
// dist[i][j] == -1 表⽰：没有搜索过
// dist[i][j] != -1 表⽰：最短距离
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
// 1. 把所有的源点加⼊到队列中
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == 0)
{
q.push({ i, j });
dist[i][j] = 0;
}
// 2. ⼀层⼀层的往外扩
while (q.size())
{
auto [a, b] = q.front(); q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.push({ x, y });
}
}
}
return dist;
}
};87. ⻜地的数量（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
public:
int numEnclaves(vector<vector<int>>& grid)
{
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> vis(m, vector<bool>(n));
queue<pair<int, int>> q;
// 1. 把边上的 1 加⼊到队列中
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
{
if (grid[i][j] == 1)
{
q.push({ i, j });
vis[i][j] = true;
}
}
// 2. 多源 bfs
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
!vis[x][y])
{
vis[x][y] = true;
q.push({ x, y });
}
}
}
// 3. 统计结果
int ret = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1 && !vis[i][j])
ret++;
return ret;
}
};88. 地图中的最⾼点（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
{
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
// 1. 把所有的源点加⼊到队列⾥⾯
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (isWater[i][j])
{
dist[i][j] = 0;
q.push({ i, j });
}
// 2. 多源 bfs
while (q.size())
{
auto [a, b] = q.front(); q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.push({ x, y });
}
}
}
return dist;
}
};89. 地图分析（medium）
代码如下（示例）：
class Solution
{
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
public:
int maxDistance(vector<vector<int>>& grid)
{
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j])
{
dist[i][j] = 0;
q.push({ i, j });
}
int ret = -1;
while (q.size())
{
auto [a, b] = q.front(); q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.push({ x, y });
ret = max(ret, dist[x][y]);
}
}
}
return ret;
}
};专题十八：BFS解决拓扑排序
拓扑排序介绍
90. 课程表（medium）
代码如下（示例）：
class Solution
{
public:
bool canFinish(int n, vector<vector<int>>& p)
{
unordered_map<int, vector<int>> edges; // 邻接表
vector<int> in(n); // 存储每⼀个结点的⼊度
// 1. 建图
for (auto& e : p)
{
int a = e[0], b = e[1];
edges[b].push_back(a);
in[a]++;
}
// 2. 拓扑排序 - bfs
queue<int> q;
// 把所有⼊度为 0 的点加⼊到队列中
for (int i = 0; i < n; i++)
{
if (in[i] == 0) q.push(i);
}
// 层序遍历
while (!q.empty())
{
int t = q.front();
q.pop();
// 修改相连的边
for (int e : edges[t])
{
in[e]--;
if (in[e] == 0) q.push(e);
}
}
// 3. 判断是否有环
for (int i : in)
if (i)
return false;
return true;
}
};91. 课程表II（medium）
代码如下（示例）：
class Solution
{
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
{
// 1. 准备⼯作
vector<vector<int>> edges(numCourses); // 邻接表存储图
vector<int> in(numCourses); // 存储每⼀个点的⼊度
// 2. 建图
for (auto& p : prerequisites)
{
int a = p[0], b = p[1]; // b -> a
edges[b].push_back(a);
in[a]++;
}
// 3. 拓扑排序
vector<int> ret; // 统计排序后的结果
queue<int> q;
for (int i = 0; i < numCourses; i++)
{
if (in[i] == 0) q.push(i);
}
while (q.size())
{
int t = q.front(); q.pop();
ret.push_back(t);
for (int a : edges[t])
{
in[a]--;
if (in[a] == 0) q.push(a);
}
}
if (ret.size() == numCourses) return ret;
else return {};
}
};92. 火星词典（hard）
代码如下（示例）：
class Solution
{
unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
unordered_map<char, int> in; // 统计⼊度
bool cheak; // 处理边界情况
public:
string alienOrder(vector<string>& words)
{
// 1. 建图 + 初始化⼊度哈希表
for (auto& s : words)
{
for (auto ch : s)
{
in[ch] = 0;
}
}
int n = words.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
add(words[i], words[j]);
if (cheak) return "";
}
}
// 2. 拓扑排序
queue<char> q;
for (auto& [a, b] : in)
{
if (b == 0) q.push(a);
}
string ret;
while (q.size())
{
char t = q.front(); q.pop();
ret += t;
for (char ch : edges[t])
{
if (--in[ch] == 0) q.push(ch);
}
}
// 3. 判断
for (auto& [a, b] : in)
if (b != 0) return "";
return ret;
}
void add(string& s1, string& s2)
{
int n = min(s1.size(), s2.size());
int i = 0;
for (; i < n; i++)
{
if (s1[i] != s2[i])
{
char a = s1[i], b = s2[i]; // a -> b
if (!edges.count(a) || !edges[a].count(b))
{
edges[a].insert(b);
in[b]++;
}
break;
}
}
if (i == s2.size() && i < s1.size()) cheak = true;
}
};专题十九：位运算加练
位运算复习
96. 位1的个数（easy）
代码如下（示例）：
class Solution {
public:
int hammingWeight(int n)
{
int sum = 0;
int i = 0;
for (int i = 0; i < 32; i++)
{
if ((n >> i) & 1 == 1)
{
sum++;
}
}
return sum;
}
};97. 比特位计数（easy）
代码如下（示例）：
class Solution {
public:
vector<int> countBits(int n)
{
vector<int> nums(n + 1);
for (int i = 0; i <= n; i++)
{
int sum = 0;
for (int j = 0; j < 32; j++)
{
if ((i >> j) & 1 == 1)
sum++;
}
nums[i] = sum;
}
return nums;
}
};98. 汉明距离（easy）
代码如下（示例）：
class Solution {
public:
int hammingDistance(int x, int y)
{
int sum = 0;
for (int i = 0; i < 32; i++)
{
if (((x >> i) & 1) ^ ((y >> i) & 1) == 1)
sum++;
}
return sum;
}
};99. 只出现一次的数字（easy）
代码如下（示例）：
class Solution {
public:
int singleNumber(vector<int>& nums)
{
int ret = 0;
for (int i = 0; i < nums.size(); i++)
{
ret ^= nums[i];
}
return ret;
}
};100. 只出现一次的数字 III（medium）
代码如下（示例）：
int* singleNumber(int* nums, int numsSize, int* returnSize)
{
int* ans = (int*)calloc(2, sizeof(int));
int ret = 0;
int i = 0;
//计算数组中所有数异或起来的结果ret
for (i = 0; i < numsSize; i++) {
ret ^= nums[i];
}
//从低位往⾼位遍历计算ret的⼆进制中哪⼀位是1
int pos = 0;
for (i = 0; i < 32; i++) {
if (((ret >> i) & 1) == 1) {
pos = i;
break;
}
}
//3. 分组异或
for (i = 0; i < numsSize; i++) {
//若当前数pos位为1，作为其中⼀组对ans[0]进⾏异或操作
if (((nums[i] >> pos) & 1) == 1) {
ans[0] ^= nums[i];
}
//否则，作为另⼀组对ans[1]进⾏异或操作。
else {
ans[1] ^= nums[i];
}
}
//ans[1]另⼀种计算⽅法
//ans[1]=ret^ans[0];
//更新数组⻓度
*returnSize = 2;
//返回答案数组
return ans;
}整体源代码
代码如下（示例）：
using namespace std;
#include<iostream>
#include<vector>
// 双指针问题第一题
//class Solution
//{
//public:
// void moveZeroes(vector<int>& nums)
// {
// int cur = 0;
// int dest = -1;
// int n = nums.size();
// while (cur < n)
// {
// if (nums[cur] != 0)
// {
// swap(nums[dest + 1], nums[cur]);
// cur++;
// dest++;
// }
// else
// {
// cur++;
// }
// }
// }
//};
//
//
//// 简便版
//class Solution
//{
//public:
// void moveZeroes(vector<int>& nums)
// {
// for (int cur = 0, dest = -1; cur < nums.size(); cur++)
// if (nums[cur]) // 处理⾮零元素
// swap(nums[++dest], nums[cur]);
// }
//};
//class Solution
//{
//public:
// void duplicateZeros(vector<int>& arr)
// {
// // 1. 先找到最后⼀个数
// int cur = 0, dest = -1, n = arr.size();
// while (cur < n)
// {
// if (arr[cur]) dest++;
// else dest += 2;
// if (dest >= n - 1) break;
// cur++;
// }
// // 2. 处理⼀下边界情况
// if (dest == n)
// {
// arr[n - 1] = 0;
// cur--; dest -= 2;
// }
// // 3. 从后向前完成复写操作
// while (cur >= 0)
// {
// if (arr[cur]) arr[dest--] = arr[cur--];
// else
// {
// arr[dest--] = 0;
// arr[dest--] = 0;
// cur--;
// }
// }
// }
//};
//class Solution
//{
//public:
// int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和{
// int sum = 0;
// while (n)
// {
// int t = n % 10;
// sum += t * t;
// n /= 10;
// }
// return sum;
//}
//bool isHappy(int n)
//{
// int slow = n, fast = bitSum(n);
// while (slow != fast)
// {
// slow = bitSum(slow);
// fast = bitSum(bitSum(fast));
// }
// return slow == 1;
//}
//};
//class Solution
//{
//public:
// int maxArea(vector<int>& height)
// {
// int left = 0, right = height.size() - 1, ret = 0;
// while (left < right)
// {
// int v = min(height[left], height[right]) * (right - left);
// ret = max(ret, v);
// // 移动指针
// if (height[left] < height[right]) left++;
// else right--;
// }
// return ret;
// }
//};
//class Solution
//{
// public int triangleNumber(int[] nums)
// {
// // 1. 优化：排序
// Arrays.sort(nums);
// // 2. 利⽤双指针解决问题
// int ret = 0, n = nums.length;
// for (int i = n - 1; i >= 2; i--) // 先固定最⼤的数
// {
// // 利⽤双指针快速统计出符合要求的三元组的个数
// int left = 0, right = i - 1;
// while (left < right)
// {
// if (nums[left] + nums[right] > nums[i])
// {
// ret += right - left;
// right--;
// }
// else
// {
// left++;
// }
// }
// }
// return ret;
// }
//}
//class Solution {
//public:
// vector<int> twoSum(vector<int>& price, int target)
// {
// int left = 0, right = price.size() - 1;
// while (left < right)
// {
// int sum = price[left] + price[right];
// if (sum > target) right--;
// else if (sum < target) left++;
// else
// {
// return { price[left] , price[right] };
// }
// }
// return { -1 , -1 };
// }
//};
//class Solution {
//public:
// vector<vector<int>> threeSum(vector<int>& nums)
// {
// vector<vector<int>> net;
// // 第一步：先排序
// sort(nums.begin(), nums.end());
// // 第二步：先固定一个数 a <= 0
// int i = 0, n = nums.size();
// for (i = 0; i < n;)
// {
// if (nums[i] > 0) break;
// else
// {
// // 区间右边用双指针算法
// int left = i + 1, right = n - 1, ret = -(nums[i]);
// while (left < right)
// {
// int sum = nums[left] + nums[right];
// if (sum < ret) left++;
// else if (sum > ret) right--;
// else
// {
// net.push_back({ nums[i] , nums[left] , nums[right] });
// left++; right--;
// // 去重操作
// while (left < right && nums[left] == nums[left - 1]) left++;
// while (left < right && nums[right] == nums[right + 1]) right--;
// }
// }
// i++;
// while (i < n && nums[i] == nums[i - 1]) i++;
// }
// }
// return net;
// }
//};
//#include <vector>
//using namespace std;
//
//class Solution {
//public:
// vector<vector<int>> threeSum(vector<int>& nums)
// {
// vector<vector<int>> net;
// // 第一步：先排序
// sort(nums.begin(), nums.end());
// // 第二步：先固定一个数 a <= 0
// int i = 0, n = nums.size();
// for (i = 0; i < n;)
// {
// if (nums[i] > 0) break;
// else
// {
// // 区间右边用双指针算法
// int left = i + 1, right = n - 1, ret = -(nums[i]);
// while (left < right)
// {
// int sum = nums[left] + nums[right];
// if (sum < ret) left++;
// else if (sum > ret) right--;
// else
// {
// net.push_back({ nums[i] , nums[left] , nums[right] });
// left++; right--;
// // 去重操作
// while (left < right && nums[left] == nums[left - 1]) left++;
// while (left < right && nums[right] == nums[right + 1]) right--;
// }
// }
//
// i++;
// while (i < n && nums[i] == nums[i - 1]) i++;
// }
//
// }
// return net;
// }
//};
//
//
//int main()
//{
// vector<int> v = { -1,0,1,2,-1,-4 };
// Solution s;
// s.threeSum(v);
// return 0;
//}
//class Solution {
//public:
// vector<vector<int>> fourSum(vector<int>& nums, int target)
// {
// vector<vector<int>> ret;
// // 先排序
// sort(nums.begin(), nums.end());
// // 再依次固定一个数 a
// int n = nums.size();
// for (int i = 0; i < n; )
// {
// // 三数字取和
// for (int j = i + 1; j < n;)
// {
// // 两个数字取和
// int left = j + 1, right = n - 1;
// long long sum = (long long)target - nums[i] - nums[j];
// while (left < right)
// {
// int mysum = nums[left] + nums[right];
// if (mysum < sum) left++;
// else if (mysum > sum) right--;
// else
// {
// ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
// left++, right--;
// while (left < right && nums[left] == nums[left - 1]) left++;
// while (left < right && nums[right] == nums[right + 1]) right--;
// }
// }
// j++;
// while (j < n && nums[j] == nums[j - 1]) j++;
// }
// i++;
// while (i < n && nums[i] == nums[i - 1]) i++;
// }
// return ret;
// }
//};
//class Solution {
//public:
// int minSubArrayLen(int target, vector<int>& nums) {
// int sum = 0, ret = INT_MAX;
// for (int left = 0, right = 0; right < nums.size(); ++right)
// {
// sum += nums[right];
// while (sum >= target)
// {
// ret = min(ret, right - left + 1);
// sum -= nums[left];
// left++;
// }
// }
// return ret == INT_MAX ? 0 : ret;
// }
//};
//class Solution
//{
//public:
// int lengthOfLongestSubstring(string s)
// {
// int hash[128] = { 0 }; // 使⽤数组来模拟哈希表
// int left = 0, right = 0, n = s.size();
// int ret = 0;
// while (right < n)
// {
// hash[s[right]]++; // 进⼊窗⼝
// while (hash[s[right]] > 1) // 判断
// hash[s[left++]]--; // 出窗⼝
// ret = max(ret, right - left + 1); // 更新结果
// right++; // 让下⼀个元素进⼊窗⼝
// }
// return ret;
// }
//};
//int main()
//{
// string s = "deabcabca";
// Solution ret;
// cout << ret.lengthOfLongestSubstring(s) << endl;
//}
//class Solution {
//public:
// int lengthOfLongestSubstring(string s)
// {
// int left = 0, right = 0, n = s.size();
// int ret = 0;
// int hash[128] = { 0 };
// while (right < n)
// {
// hash[s[right]]++;
// while (hash[s[right]] > 1) hash[s[left++]]--;
// ret = max(ret, right - left + 1);
// right++;
// }
// return ret;
// }
//};
//class Solution {
//public:
// int longestOnes(vector<int>& nums, int k)
// {
// int ret = 0;
// int left = 0, right = 0, zero = 0;
// int n = nums.size();
// while (right < n)
// {
// if (nums[right] == 0) zero++; // 进窗口
// while (zero > k)
// {
// if (nums[left++] == 0) zero--; // 出窗口
// }
// ret = max(ret, right - left + 1);// 更新结果
// right++;
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// int minOperations(vector<int>& nums, int x)
// {
// int sum = 0;
// for (int a : nums) sum += a;
// int target = sum - x;
// // 细节问题
// if (target < 0) return -1;
// int ret = -1;
// for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
// {
// tmp += nums[right]; // 进窗⼝
// while (tmp > target) // 判断
// tmp -= nums[left++]; // 出窗⼝
// if (tmp == target) // 更新结果
// ret = max(ret, right - left + 1);
// }
// if (ret == -1) return ret;
// else return nums.size() - ret;
// }
//};
#include<unordered_map>
//class Solution {
//public:
// int totalFruit(vector<int>& fruits)
// {
// int ret = 0;
// unordered_map<int, int> hash;
// for (int left = 0, right = 0; right < fruits.size(); right++)
// {
// // 进窗口
// hash[fruits[right]]++;
// // 判断+出窗口
// while (hash.size() > 2)
// {
// hash[fruits[left]]--;
// if (hash[fruits[left]] == 0) hash.erase(fruits[left]);
// left++;
// }
// ret = max(ret, right - left + 1);
// }
// return ret;
// }
//};
//
//
//// 数组优化版本
//class Solution
//{
//public:
// int totalFruit(vector<int>& f)
// {
// int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
// int ret = 0;
// for (int left = 0, right = 0, kinds = 0; right < f.size(); right++)
// {
// if (hash[f[right]] == 0) kinds++; // 维护⽔果的种类
// hash[f[right]]++; // 进窗⼝
// while (kinds > 2) // 判断
// {
// // 出窗⼝
// hash[f[left]]--;
// if (hash[f[left]] == 0) kinds--;
// left++;
// }
// ret = max(ret, right - left + 1);
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// vector<int> findAnagrams(string s, string p)
// {
// vector<int> ret;
// int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
// for (auto ch : p) hash1[ch - 'a']++;
// int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
// int m = p.size();
// for (int left = 0, right = 0, count = 0; right < s.size(); right++)
// {
// char in = s[right];
// // 进窗⼝ + 维护 count
// hash2[in - 'a']++;
// if (hash2[in - 'a'] <= hash1[in - 'a']) count++;
// if (right - left + 1 > m) // 判断
// {
// char out = s[left++];
// // 出窗⼝ + 维护 count
// if (hash2[out - 'a'] <= hash1[out - 'a']) count--;
// hash2[out - 'a']--;
// }
// // 更新结果
// if (count == m) ret.push_back(left);
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// vector<int> findSubstring(string s, vector<string>& words)
// {
// vector<int> ret;
// unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
// for (auto& s : words) hash1[s]++;
// int len = words[0].size(), m = words.size();
// for (int i = 0; i < len; i++) // 执⾏ len 次
// {
// unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
// for (int left = i, right = i, count = 0; right + len <= s.size();
// right += len)
// {
// // 进窗⼝ + 维护 count
// string in = s.substr(right, len);
// hash2[in]++;
// if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
// // 判断
// if (right - left + 1 > len * m)
// {
// // 出窗⼝ + 维护 count
// string out = s.substr(left, len);
// if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
// hash2[out]--;
// left += len;
// }
// // 更新结果
// if (count == m) ret.push_back(left);
// }
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// string minWindow(string s, string t)
// {
// int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
// int kinds = 0; // 统计有效字符有多少种
// for (auto ch : t)
// if (hash1[ch]++ == 0) kinds++;
// int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
// int minlen = INT_MAX, begin = -1;
// for (int left = 0, right = 0, count = 0; right < s.size(); right++)
// {
// char in = s[right];
// if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
// while (count == kinds) // 判断条件
// {
// if (right - left + 1 < minlen) // 更新结果
// {
// minlen = right - left + 1;
// begin = left;
// }
// char out = s[left++];
// if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
// }
// }
// if (begin == -1) return "";
// else return s.substr(begin, minlen);
// }
//};
#include<algorithm>
//class Solution {
//public:
// int search(vector<int>& nums, int target)
// {
// sort(nums.begin(), nums.end());
// int left = 0, right = nums.size() - 1;
// while (left <= right)
// {
// int mid = left + (right - left) / 2;
// if (nums[mid] < target) left = mid + 1;
// else if (nums[mid] > target) right = mid - 1;
// else return mid;
// }
// return -1;
// }
//};
//class Solution {
//public:
// vector<int> searchRange(vector<int>& nums, int target)
// {
// int left = 0, right = nums.size() - 1;
// if (nums.size() == 0) return { -1,-1 };
// // 先查左端点
// int begin = 0;
// while (left < right)
// {
// int mid = left + (right - left) / 2;
// if (nums[mid] < target) left = mid + 1;
// else right = mid;
// }
// if (nums[left] != target) return { -1,-1 };
// else begin = left;
// // 再查右端点
// left = 0, right = nums.size() - 1;
// while (left < right)
// {
// int mid = left + (right - left + 1) / 2;
// if (nums[mid] <= target) left = mid;
// else right = mid - 1;
// }
// return { begin,right };
// }
//};
//// 方法一：暴力枚举
//class Solution {
//public:
// int mySqrt(int x) {
// // 由于两个较⼤的数相乘可能会超过 int 最⼤范围
// // 因此⽤ long long
// long long i = 0;
// for (i = 0; i <= x; i++)
// {
// // 如果两个数相乘正好等于 x，直接返回 i
// if (i * i == x) return i;
// // 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数
// if (i * i > x) return i - 1;
// }
// // 为了处理oj题需要控制所有路径都有返回值
// return -1;
// }
//};
//
//
//
//// 方法二：二分
//class Solution
//{
//public:
// int mySqrt(int x)
// {
// if (x < 1) return 0; // 处理边界情况
// int left = 1, right = x;
// while (left < right)
// {
// long long mid = left + (right - left + 1) / 2; // 防溢出
// if (mid * mid <= x) left = mid;
// else right = mid - 1;
// }
// return left;
// }
//};
//class Solution {
//public:
// int searchInsert(vector<int>& nums, int target)
// {
// int left = 0, right = nums.size() - 1;
// while (left < right)
// {
// int mid = left + (right - left) / 2;
// if (nums[mid] < target) left = mid + 1;
// else right = mid;
// }
// if (nums[left] < target) return left + 1;
// return left;
// }
//};
//class Solution {
//public:
// int peakIndexInMountainArray(vector<int>& arr)
// {
// // 第一个和最后一个一定不是山峰
// int left = 1, right = arr.size() - 2;
// while (left < right)
// {
// int mid = left + (right - left + 1) / 2;
// if (arr[mid] < arr[mid - 1]) right = mid - 1;
// else left = mid;
// }
// return left;
// }
//};
//class Solution {
//public:
// int findPeakElement(vector<int>& nums)
// {
// int left = 0, right = nums.size() - 1;
// while (left < right)
// {
// int mid = left + (right - left) / 2;
// if (nums[mid] > nums[mid + 1]) right = mid;
// else left = mid + 1;
// }
// return left;
// }
//};
//class Solution {
//public:
// int findMin(vector<int>& nums)
// {
// int left = 0, right = nums.size() - 1;
// int x = nums[right];
// while (left < right)
// {
// int mid = left + (right - left) / 2;
// if (nums[mid] < x) right = mid;
// else left = mid + 1;
// }
// return nums[left];
// }
//};
//class Solution {
//public:
// int takeAttendance(vector<int>& records)
// {
// int left = 0, right = records.size() - 1;
// while (left < right)
// {
// int mid = left + (right - left) / 2;
// if (records[mid] == mid) left = mid + 1;
// else right = mid;
// }
// return records[left] == left ? left + 1 : left;
// }
//};
//int main()
//{
// Solution s;
// vector<int> ret = { 0,1,3,4,5 };
// cout << s.takeAttendance(ret) << endl;
// return 0;
//}
//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
// int n, q;
// cin >> n >> q;
// // 1. 读入数据
// vector<int> arr(n + 1);
// for (int i = 1; i <= n; i++)
// {
// cin >> arr[i];
// }
// // 2.预处理出来一个前缀和数组
// vector<long long> dp(n + 1);
// for (int i = 0; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
//
// // 3.使用前缀和数组
// int left = 0, right = 0;
// while (q--)
// {
// cin >> left >> right;
// cout << dp[right] - dp[left - 1] << endl;
// }
// return 0;
//}
//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
// // 1. 读入数据
// int n = 0, m = 0, q = 0;
// cin >> n >> m >> q;
// vector<vector<int>> arr(n + 1, vector<int>(m + 1));
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= m; j++)
// cin >> arr[i][j];
// // 2. 预处理前缀和矩阵
// vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= m; j++)
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
// // 3. 使用前缀和矩阵
// int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
// while (q--)
// {
// cin >> x1 >> y1 >> x2 >> y2;
// cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
// }
//}
//class Solution {
//public:
// int pivotIndex(vector<int>& nums)
// {
// int n = nums.size();
// vector<int> f(n), g(n);
// // 1.预处理前缀和两个数组
// for (int i = 1; i < n; i++)
// f[i] = f[i - 1] + nums[i - 1];
// for (int i = n - 2; i >= 0; i--)
// g[i] = g[i + 1] + nums[i + 1];
// // 2.判断两个数组是否相同
// for (int i = 0; i < n; i++)
// if (f[i] == g[i])
// return i;
// return -1;
// }
//};
//class Solution {
//public:
// vector<int> productExceptSelf(vector<int>& nums)
// {
// int n = nums.size();
// vector<int> f(n), g(n);
// // 1.先预处理一下前缀积两个数组
// f[0] = g[n - 1] = 1;
// for (int i = 1; i < n; i++)
// f[i] = f[i - 1] * nums[i - 1];
// for (int i = n - 2; i >= 0; i--)
// g[i] = g[i + 1] * nums[i + 1];
// // 2.判断并且使用
// vector<int> ret(n);
// for (int i = 0; i < n; i++)
// {
// ret[i] = f[i] * g[i];
// }
// return ret;
// }
//};
//class Solution {
//public:
// int subarraySum(vector<int>& nums, int k)
// {
// unordered_map<int, int> hash;
// hash[0] = 1;
// int sum = 0, ret = 0;
// for (auto x : nums)
// {
// sum += x;
// if (hash.count(sum - k))
// ret += hash[sum - k]; // 统计个数
// hash[sum]++;
// }
// return ret;
// }
//};
//class Solution {
//public:
// int subarraysDivByK(vector<int>& nums, int k)
// {
// unordered_map<int, int> hash;
// hash[0 % k] = 1; // 0 这个数的余数
// int sum = 0, ret = 0;
// for (auto x : nums)
// {
// sum += x; // 算出当前位置的前缀和
// int r = (sum % k + k) % k; // 修正后的余数
// if (hash.count(r))
// ret += hash[r]; // 统计结果
// hash[r]++;
// }
// return ret;
// }
//};
//
//
//class Solution
//{
//public:
// int findMaxLength(vector<int>& nums)
// {
// unordered_map<int, int> hash;
// hash[0] = -1; // 默认有⼀个前缀和为 0 的情况
// int sum = 0, ret = 0;
// for (int i = 0; i < nums.size(); i++)
// {
// sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
// if (hash.count(sum)) ret = max(ret, i - hash[sum]);
// else hash[sum] = i;
// }
// return ret;
// }
//};
//class Solution {
//public:
// vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
// int m = mat.size(), n = mat[0].size();
// vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// // 1. 预处理前缀和矩阵
// for (int i = 1; i <= m; i++)
// for (int j = 1; j <= n; j++)
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] +
// mat[i - 1][j - 1];
//
// // 2. 使⽤
// vector<vector<int>> ret(m, vector<int>(n));
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// {
// int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
// int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
// ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] +
// dp[x1 - 1][y1 - 1];
// }
//
// return ret;
// }
//};
//class Solution {
//public:
// bool isUnique(string astr) {
// // 鹊巢原理优化
// if (astr.size() > 26)
// return false;
// // 利用位图的思想求解
// int bitMap = 0;
// for (auto ch : astr)
// {
// int i = ch - 'a';
// // 先判断字符是否已经出现过
// if (((bitMap >> i) & 1) == 1)
// return false;
// // 把当前字符加⼊到位图中
// bitMap |= 1 << i;
// }
// return true;
// }
//};
//class Solution
//{
//public:
// int missingNumber(vector<int>& nums)
// {
// int ret = 0;
// for (auto x : nums) ret ^= x;
// for (int i = 0; i <= nums.size(); i++) ret ^= i;
// return ret;
// }
//};
//int main()
//{
// vector<int> ret = { 3,0,1 };
// Solution s;
// cout << s.missingNumber(ret) << endl;
//}
//
//
//class Solution
//{
//public:
// int getSum(int a, int b)
// {
// while (b != 0)
// {
// int x = a ^ b; // 先算出⽆进位相加的结果
// unsigned int carry = (unsigned int)(a & b) << 1; // 算出进位
// a = x;
// b = carry;
// }
// return a;
// }
//};
//class Solution
//{
//public:
// int singleNumber(vector<int>& nums)
// {
// int ret = 0;
// for (int i = 0; i < 32; i++) // 依次去修改 ret 中的每⼀位
// {
// int sum = 0;
// for (int x : nums) // 计算nums中所有的数的第 i 位的和
// if (((x >> i) & 1) == 1)
// sum++;
// sum %= 3;
// if (sum == 1) ret |= 1 << i;
// }
// return ret;
// }
//};
//
//class Solution
//{
//public:
// vector<int> missingTwo(vector<int>& nums)
// {
// // 1. 将所有的数异或在⼀起
// int tmp = 0;
// for (auto x : nums) tmp ^= x;
// for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// // 2. 找出 a，b 中⽐特位不同的那⼀位
// int diff = 0;
// while (1)
// {
// if (((tmp >> diff) & 1) == 1) break;
// else diff++;
// }
// // 3. 根据 diff 位的不同，将所有的数划分为两类来异或
// int a = 0, b = 0;
// for (int x : nums)
// if (((x >> diff) & 1) == 1) b ^= x;
// else a ^= x;
// for (int i = 1; i <= nums.size() + 2; i++)
// if (((i >> diff) & 1) == 1) b ^= i;
// else a ^= i;
// return { a, b };
// }
//};
//class Solution
//{
//public:
// string modifyString(string s)
// {
// int n = s.size();
// for (int i = 0; i < n; i++)
// {
// if (s[i] == '?') // 替换
// {
// for (char ch = 'a'; ch <= 'z'; ch++)
// {
// if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i+ 1]))
// {
// s[i] = ch;
// break;
// }
// }
// }
// }
// return s;
// }
//};
//class Solution {
//public:
// int findPoisonedDuration(vector<int>& timeSeries, int duration)
// {
// int ret = 0;
// for (int i = 1; i < timeSeries.size(); i++)
// {
// int x = timeSeries[i] - timeSeries[i - 1];
// if (x >= duration) ret += duration;
// else ret += x;
// }
// return ret + duration;
// }
//};
//class Solution
//{
//public:
// string convert(string s, int numRows)
// {
// // 处理边界情况
// if (numRows == 1) return s;
// string ret;
// int d = 2 * numRows - 2, n = s.size();
// // 1. 先处理第⼀⾏
// for (int i = 0; i < n; i += d)
// ret += s[i];
// // 2. 处理中间⾏
// for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
// {
// for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
// {
// if (i < n) ret += s[i];
// if (j < n) ret += s[j];
// }
// }
// // 3. 处理最后⼀⾏
// for (int i = numRows - 1; i < n; i += d)
// ret += s[i];
// return ret;
// }
//};
//class Solution
//{
//public:
// string countAndSay(int n)
// {
// string ret = "1";
// for (int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可
// {
// string tmp;
// int len = ret.size();
// for (int left = 0, right = 0; right < len; )
// {
// while (right < len && ret[left] == ret[right]) right++;
// tmp += to_string(right - left) + ret[left];
// left = right;
// }
// ret = tmp;
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// int minNumberOfFrogs(string croakOfFrogs)
// {
// string t = "croak";
// int n = t.size();
// vector<int> hash(n); // ⽤数组来模拟哈希表
// unordered_map<char, int> index; //[x, x这个字符对应的下标]
// for (int i = 0; i < n; i++)
// index[t[i]] = i;
//
// for (auto ch : croakOfFrogs)
// {
// if (ch == 'c')
// {
// if (hash[n - 1] != 0) hash[n - 1]--;
// hash[0]++;
// }
// else
// {
// int i = index[ch];
// if (hash[i - 1] == 0) return -1;
// hash[i - 1]--; hash[i]++;
// }
// }
// for (int i = 0; i < n - 1; i++)
// if (hash[i] != 0)
// return -1;
// return hash[n - 1];
// }
//};
//class Solution {
//public:
// void sortColors(vector<int>& nums)
// {
// int left = -1, right = nums.size(), i = 0;
// while (i < right)
// {
// if (nums[i] == 0) swap(nums[++left], nums[i++]);
// else if (nums[i] == 2) swap(nums[--right], nums[i]);
// else i++;
// }
// }
//};
//class Solution
//{
//public:
// vector<int> sortArray(vector<int>& nums)
// {
// srand(time(NULL)); // 种下⼀个随机数种⼦
// qsort(nums, 0, nums.size() - 1);
// return nums;
// }
// // 快排
// void qsort(vector<int>& nums, int l, int r)
// {
// if (l >= r) return;
// // 数组分三块
// int key = getRandom(nums, l, r);
// int i = l, left = l - 1, right = r + 1;
// while (i < right)
// {
// if (nums[i] < key) swap(nums[++left], nums[i++]);
// else if (nums[i] == key) i++;
// else swap(nums[--right], nums[i]);
// }
// // [l, left] [left + 1, right - 1] [right, r]
// qsort(nums, l, left);
// qsort(nums, right, r);
// }
// int getRandom(vector<int>& nums, int left, int right)
// {
// int r = rand();
// return nums[r % (right - left + 1) + left];
// }
//};
//class Solution
//{
//public:
// int findKthLargest(vector<int>& nums, int k)
// {
// srand(time(NULL));
// return qsort(nums, 0, nums.size() - 1, k);
// }
// int qsort(vector<int>& nums, int l, int r, int k)
// {
// if (l == r) return nums[l];
// // 1. 随机选择基准元素
// int key = getRandom(nums, l, r);
// // 2. 根据基准元素将数组分三块
// int left = l - 1, right = r + 1, i = l;
// while (i < right)
// {
// if (nums[i] < key) swap(nums[++left], nums[i++]);
// else if (nums[i] == key) i++;
// else swap(nums[--right], nums[i]);
// }
// // 3. 分情况讨论
// int c = r - right + 1, b = right - left - 1;
// if (c >= k) return qsort(nums, right, r, k);
// else if (b + c >= k) return key;
// else return qsort(nums, l, left, k - b - c);
// }
// int getRandom(vector<int>& nums, int left, int right)
// {
// return nums[rand() % (right - left + 1) + left];
// }
//};
//class Solution {
//public:
// vector<int> getLeastNumbers(vector<int>& nums, int k)
// {
// srand(time(NULL));
// qsort(nums, 0, nums.size() - 1, k);
// return { nums.begin(), nums.begin() + k };
// }
// void qsort(vector<int>& nums, int l, int r, int k)
// {
// if (l >= r) return;
// // 1. 随机选择⼀个基准元素 + 数组分三块
// int key = getRandom(nums, l, r);
// int left = l - 1, right = r + 1, i = l;
// while (i < right)
// {
// if (nums[i] < key) swap(nums[++left], nums[i++]);
// else if (nums[i] == key) i++;
// else swap(nums[--right], nums[i]);
// }
// // [l, left][left + 1, right - 1] [right, r]
// // 2. 分情况讨论
// int a = left - l + 1, b = right - left - 1;
// if (a > k) qsort(nums, l, left, k);
// else if (a + b >= k) return;
// else qsort(nums, right, r, k - a - b);
// }
// int getRandom(vector<int>& nums, int l, int r)
// {
// return nums[rand() % (r - l + 1) + l];
// }
//};
//class Solution
//{
// vector<int> tmp;
//public:
// vector<int> sortArray(vector<int>& nums)
// {
// tmp.resize(nums.size());
// mergeSort(nums, 0, nums.size() - 1);
// return nums;
// }
// void mergeSort(vector<int>& nums, int left, int right)
// {
// if (left >= right) return;
// // 1. 选择中间点划分区间
// int mid = (left + right) >> 1;
// // [left, mid] [mid + 1, right]
// // 2. 把左右区间排序
// mergeSort(nums, left, mid);
// mergeSort(nums, mid + 1, right);
// // 3. 合并两个有序数组
// int cur1 = left, cur2 = mid + 1, i = 0;
// while (cur1 <= mid && cur2 <= right)
// tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] :
// nums[cur2++];
// // 处理没有遍历完的数组
// while (cur1 <= mid) tmp[i++] = nums[cur1++];
// while (cur2 <= right) tmp[i++] = nums[cur2++];
// // 4. 还原
// for (int i = left; i <= right; i++)
// nums[i] = tmp[i - left];
// }
//};
//class Solution
//{
// int tmp[50010];
//public:
// int reversePairs(vector<int>& nums)
// {
// return mergeSort(nums, 0, nums.size() - 1);
// }
// int mergeSort(vector<int>& nums, int left, int right)
// {
// if (left >= right) return 0;
// int ret = 0;
// // 1. 找中间点，将数组分成两部分
// int mid = (left + right) >> 1;
// // [left, mid][mid + 1, right]
// // 2. 左边的个数 + 排序 + 右边的个数 + 排序
// ret += mergeSort(nums, left, mid);
// ret += mergeSort(nums, mid + 1, right);
// // 3. ⼀左⼀右的个数
// int cur1 = left, cur2 = mid + 1, i = 0;
// while (cur1 <= mid && cur2 <= right) // 升序的时候
// {
// if (nums[cur1] <= nums[cur2])
// {
// tmp[i++] = nums[cur1++];
// }
// else
// {
// ret += mid - cur1 + 1;
// tmp[i++] = nums[cur2++];
// }
// }
// // 4. 处理⼀下排序
// while (cur1 <= mid) tmp[i++] = nums[cur1++];
// while (cur2 <= right) tmp[i++] = nums[cur2++];
// for (int j = left; j <= right; j++)
// nums[j] = tmp[j - left];
// return ret;
// }
//};
//class Solution
//{
// vector<int> ret;
// vector<int> index; // 记录 nums 中当前元素的原始下标
// int tmpNums[500010];
// int tmpIndex[500010];
//public:
// vector<int> countSmaller(vector<int>& nums)
// {
// int n = nums.size();
// ret.resize(n);
// index.resize(n);
// // 初始化⼀下 index 数组
// for (int i = 0; i < n; i++)
// index[i] = i;
// mergeSort(nums, 0, n - 1);
// return ret;
// }
//
// void mergeSort(vector<int>& nums, int left, int right)
// {
// if (left >= right) return;
// // 1. 根据中间元素，划分区间
// int mid = (left + right) >> 1;
// // [left, mid] [mid + 1, right]
// // 2. 先处理左右两部分
// mergeSort(nums, left, mid);
// mergeSort(nums, mid + 1, right);
// // 3. 处理⼀左⼀右的情况
// int cur1 = left, cur2 = mid + 1, i = 0;
// while (cur1 <= mid && cur2 <= right) // 降序
// {
// if (nums[cur1] <= nums[cur2])
// {
// tmpNums[i] = nums[cur2];
// tmpIndex[i++] = index[cur2++];
// }
// else
// {
// ret[index[cur1]] += right - cur2 + 1; // 重点
// tmpNums[i] = nums[cur1];
// tmpIndex[i++] = index[cur1++];
// }
// }
// // 4. 处理剩下的排序过程
// while (cur1 <= mid)
// {
// tmpNums[i] = nums[cur1];
// tmpIndex[i++] = index[cur1++];
// }
// while (cur2 <= right)
// {
// tmpNums[i] = nums[cur2];
// tmpIndex[i++] = index[cur2++];
// }
// for (int j = left; j <= right; j++)
// {
// nums[j] = tmpNums[j - left];
// index[j] = tmpIndex[j - left];
// }
// }
//};
//class Solution
//{
// int tmp[50010];
//public:
// int reversePairs(vector<int>& nums)
// {
// return mergeSort(nums, 0, nums.size() - 1);
// }
// int mergeSort(vector<int>& nums, int left, int right)
// {
// if (left >= right) return 0;
// int ret = 0;
// // 1. 先根据中间元素划分区间
// int mid = (left + right) >> 1;
// // [left, mid] [mid + 1, right]
// // 2. 先计算左右两侧的翻转对
// ret += mergeSort(nums, left, mid);
// ret += mergeSort(nums, mid + 1, right);
// // 3. 先计算翻转对的数量
// int cur1 = left, cur2 = mid + 1, i = left;
// while (cur1 <= mid) // 降序的情况
// {
// while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
// if (cur2 > right)
// break;
// ret += right - cur2 + 1;
// cur1++;
// }
// // 4. 合并两个有序数组
// cur1 = left, cur2 = mid + 1;
// while (cur1 <= mid && cur2 <= right)
// tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
// while (cur1 <= mid) tmp[i++] = nums[cur1++];
// while (cur2 <= right) tmp[i++] = nums[cur2++];
// for (int j = left; j <= right; j++)
// nums[j] = tmp[j];
//
// return ret;
// }
//};
//struct ListNode
//{
// int val;
// ListNode* next;
//};
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//class Solution {
//public:
// ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
// {
// ListNode* cur1 = l1, * cur2 = l2;
// ListNode* newhead = new ListNode(0);//创建虚拟头节点，记录最终结果
// ListNode* prev = newhead;// 尾指针
// int t = 0;// 进位
// while (cur1 || cur2 || t)
// {
// if (cur1)
// {
// t += cur1->val;
// cur1 = cur1->next;
// }
// if (cur2)
// {
// t += cur2->val;
// cur2 = cur2->next;
// }
// prev->next = new ListNode(t % 10);
// prev = prev->next;
// t /= 10;
// }
// prev = newhead->next;
// delete newhead;
// return prev;
// }
//};
//class Solution
//{
//public:
// ListNode* swapPairs(ListNode* head)
// {
// if (head == nullptr || head->next == nullptr) return head;
// ListNode* newHead = new ListNode(0);
// newHead->next = head;
// ListNode* prev = newHead, * cur = prev->next, * next = cur->next, * nnext
// = next->next;
// while (cur && next)
// {
// // 交换结点
// prev->next = next;
// next->next = cur;
// cur->next = nnext;
// // 修改指针
// prev = cur; // 注意顺序
// cur = nnext;
// if (cur) next = cur->next;
// if (next) nnext = next->next;
// }
// cur = newHead->next;
// delete newHead;
// return cur;
// }
//};
/**
* 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:
// void reorderList(ListNode* head)
// {
// // 处理边界情况
// if (head == nullptr || head->next == nullptr || head->next->next ==
// nullptr) return;
// // 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥）
// ListNode* slow = head, * fast = head;
// while (fast && fast->next)
// {
// slow = slow->next;
// fast = fast->next->next;
// }
// // 2. 把 slow 后⾯的部分给逆序 - 头插法
// ListNode* head2 = new ListNode(0);
// ListNode* cur = slow->next;
// slow->next = nullptr; // 注意把两个链表给断开
// while (cur)
// {
// ListNode* next = cur->next;
// cur->next = head2->next;
// head2->next = cur;
// cur = next;
// }
// // 3. 合并两个链表 - 双指针
// ListNode* ret = new ListNode(0);
// ListNode* prev = ret;
// ListNode* cur1 = head, * cur2 = head2->next;
// while (cur1)
// {
// // 先放第⼀个链表
// prev->next = cur1;
// cur1 = cur1->next;
// prev = prev->next;
// // 再放第⼆个链表
// if (cur2)
// {
// prev->next = cur2;
// prev = prev->next;
// cur2 = cur2->next;
// }
// }
// delete head2;
// delete ret;
// }
//};
#include <queue>
/**
* 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
//{
// struct cmp
// {
// bool operator()(const ListNode* l1, const ListNode* l2)
// {
// return l1->val > l2->val;
// }
// };
//public:
// ListNode* mergeKLists(vector<ListNode*>& lists)
// {
// // 创建⼀个⼩根堆
// priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
// // 让所有的头结点进⼊⼩根堆
// for (auto l : lists)
// if (l) heap.push(l);
//
// // 合并 k 个有序链表
// ListNode* ret = new ListNode(0);
// ListNode* prev = ret;
// while (!heap.empty())
// {
// ListNode* t = heap.top();
// heap.pop();
// prev->next = t;
// prev = t;
// if (t->next) heap.push(t->next);
// }
// prev = ret->next;
// delete ret;
// return prev;
// }
//};
//// 递归
//class Solution
//{
//public:
// ListNode* mergeKLists(vector<ListNode*>& lists)
// {
// return merge(lists, 0, lists.size() - 1);
// }
// ListNode* merge(vector<ListNode*>& lists, int left, int right)
// {
// if (left > right) return nullptr;
// if (left == right) return lists[left];
// // 1. 平分数组
// int mid = left + right >> 1;
// // [left, mid] [mid + 1, right]
// // 2. 递归处理左右区间
// ListNode* l1 = merge(lists, left, mid);
// ListNode* l2 = merge(lists, mid + 1, right);
// // 3. 合并两个有序链表
// return mergeTowList(l1, l2);
// }
// ListNode* mergeTowList(ListNode* l1, ListNode* l2)
// {
// if (l1 == nullptr) return l2;
// if (l2 == nullptr) return l1;
// // 合并两个有序链表
// ListNode head;
// ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
// head.next = nullptr;
// while (cur1 && cur2)
// {
// if (cur1->val <= cur2->val)
// {
// prev = prev->next = cur1;
// cur1 = cur1->next;
// }
// else
// {
// prev = prev->next = cur2;
// cur2 = cur2->next;
// }
// }
// if (cur1) prev->next = cur1;
// if (cur2) prev->next = cur2;
// return head.next;
// }
//};
//class Solution
//{
//public:
// ListNode* reverseKGroup(ListNode* head, int k)
// {
// // 1. 先求出需要逆序多少组
// int n = 0;
// ListNode* cur = head;
// while (cur)
// {
// cur = cur->next;
// n++;
// }
// n /= k;
// // 2. 重复 n 次：⻓度为 k 的链表的逆序即可
// ListNode* newHead = new ListNode(0);
// ListNode* prev = newHead;
// cur = head;
// for (int i = 0; i < n; i++)
// {
// ListNode* tmp = cur;
// for (int j = 0; j < k; j++)
// {
// ListNode* next = cur->next;
// cur->next = prev->next;
// prev->next = cur;
// cur = next;
// }
// prev = tmp;
// }
// // 把不需要翻转的接上
// prev->next = cur;
// cur = newHead->next;
// delete newHead;
// return cur;
// }
//};
//class Solution {
//public:
// vector<int> twoSum(vector<int>& nums, int target)
// {
// for (int i = 0; i < nums.size(); i++)
// {
// for (int j = i + 1; j < nums.size(); j++)
// {
// if (nums[i] + nums[j] == target) return { i , j };
// }
// }
// return { -1 , -1 };
// }
//};
//
//class Solution {
//public:
// vector<int> twoSum(vector<int>& nums, int target)
// {
// unordered_map<int, int> hash; // <nums[i], i>
// for (int i = 0; i < nums.size(); i++)
// {
// int x = target - nums[i];
// if (hash.count(x)) return { hash[x] , i };
// hash[nums[i]] = i;
// }
// return { -1 , -1 };
// }
//};
//class Solution {
//public:
// bool CheckPermutation(string s1, string s2)
// {
// if (s1.size() != s2.size()) return false;
// int hash[26] = { 0 };
// // 先统计第一个字符串的信息
// for (auto x : s1) hash[x - 'a']++;
// // 再扫描第二个字符串，看看是否能重排
// for (auto x : s2)
// {
// hash[x - 'a']--;
// if (hash[x - 'a'] < 0) return false;
// }
// return true;
// }
//};
#include<unordered_set>
//class Solution {
//public:
// bool containsDuplicate(vector<int>& nums)
// {
// unordered_set<int> hash;
// for (auto x : nums)
// {
// if (hash.count(x)) return true;
// else hash.insert(x);
// }
// return false;
// }
//};z
//class Solution
//{
//public:
// bool containsNearbyDuplicate(vector<int>& nums, int k)
// {
// unordered_map<int, int> hash;
// for (int i = 0; i < nums.size(); i++)
// {
// if (hash.count(nums[i]))
// {
// if (i - hash[nums[i]] <= k) return true;
// }
// hash[nums[i]] = i;
// }
// return false;
// }
//};
#include<vector>
//int x, y;
//class Solution {
//public:
// vector<vector<string>> groupAnagrams(vector<string>& strs)
// {
// unordered_map<string, vector<string>> hash;
// // 1.把所有的字母异位词分组
// for (auto& s : strs)
// {
// string tmp = s;
// sort(tmp.begin(), tmp.end());
// hash[tmp].push_back(s);
// }
// // 2.结果提取出来
// vector<vector<string>> ret;
// for (auto& [x, y] : hash)
// {
// ret.push_back(y);
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// string longestCommonPrefix(vector<string>& strs)
// {
// // 解法⼀：两两⽐较
// string ret = strs[0];
// for (int i = 1; i < strs.size(); i++)
// ret = findCommon(ret, strs[i]);
// return ret;
// }
// string findCommon(string& s1, string& s2)
// {
// int i = 0;
// while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
// return s1.substr(0, i);
// }
//};
//
//
//class Solution
//{
//public:
// string longestCommonPrefix(vector<string>& strs)
// {
// // 解法⼆：统⼀⽐较
// for (int i = 0; i < strs[0].size(); i++)
// {
// char tmp = strs[0][i];
// for (int j = 1; j < strs.size(); j++)
// if (i == strs[j].size() || tmp != strs[j][i])
// return strs[0].substr(0, i);
// }
// return strs[0];
// }
//};
//class Solution
//{
//public:
// string longestPalindrome(string s)
// {
// // 中⼼扩展算法
// int begin = 0, len = 0, n = s.size();
// for (int i = 0; i < n; i++) // 依次枚举所有的中点
// {
// // 先做⼀次奇数⻓度的扩展
// int left = i, right = i;
// while (left >= 0 && right < n && s[left] == s[right])
// {
// left--;
// right++;
// }
// if (right - left - 1 > len)
// {
// begin = left + 1;
// len = right - left - 1;
// }
// // 偶数⻓度的扩展
// left = i, right = i + 1;
// while (left >= 0 && right < n && s[left] == s[right])
// {
// left--;
// right++;
// }
// if (right - left - 1 > len)
// {
// begin = left + 1;
// len = right - left - 1;
// }
// }
// return s.substr(begin, len);
// }
//};
//class Solution {
//public:
// string addBinary(string a, string b)
// {
// string str;
// int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
// while (cur1 >= 0 || cur2 >= 0 || t)
// {
// if (cur1 >= 0) t += a[cur1--] - '0';
// if (cur2 >= 0) t += b[cur2--] - '0';
// str += t % 2 + '0';
// t /= 2;
// }
// reverse(str.begin(), str.end());
// return str;
// }
//};
//class Solution {
//public:
// string multiply(string num1, string num2)
// {
// // 无进位相乘后相加，然后处理进位
// int m = n1.size(), n = n2.size();
// reverse(n1.begin(), n1.begin());
// reverse(n2.begin(), n2.begin());
// vector<int> tmp(m + n - 1);
// // 1.无进位相乘后相加
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
// // 2. 处理进位
// int cur = 0, t = 0;
// string ret;
// while (cur < m + n - 1 || t)
// {
// if (cur < m + n - 1) t += tmp[cur++];
// ret += t % 10 + '0';
// t /= 10;
// }
// // 3. 处理前导零
// while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
// reverse(ret.begin(), ret.end());
// return ret;
// }
//};
//
//
//class Solution
//{
//public:
// string multiply(string n1, string n2)
// {
// // 解法：⽆进位相乘后相加，然后处理进位
// int m = n1.size(), n = n2.size();
// reverse(n1.begin(), n1.end());
// reverse(n2.begin(), n2.end());
// vector<int> tmp(m + n - 1);
// // 1. ⽆进位相乘后相加
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
//
// // 2. 处理进位
// int cur = 0, t = 0;
// string ret;
// while (cur < m + n - 1 || t)
// {
// if (cur < m + n - 1) t += tmp[cur++];
// ret += t % 10 + '0';
// t /= 10;
// }
// // 3. 处理前导零
// while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
// reverse(ret.begin(), ret.end());
// return ret;
// }
//};
#include<string>
//class Solution
//{
//public:
// string removeDuplicates(string s)
// {
// string ret; // 搞⼀个数组，模拟栈结构即可
// for (auto ch : s)
// {
// if (ret.size() && ch == ret.back()) ret.pop_back(); // 出栈
// else ret += ch; // ⼊栈
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// bool backspaceCompare(string s, string t)
// {
// return changeStr(s) == changeStr(t);
// }
// string changeStr(string& s)
// {
// string ret; // ⽤数组模拟栈结构
// for (char ch : s)
// {
// if (ch != '#') ret += ch;
// else
// {
// if (ret.size()) ret.pop_back();
// }
// }
// return ret;
// }
//};
//class Solution {
//public:
// bool backspaceCompare(string s, string t)
// {
// string str1, str2;
// for (auto x : s)
// {
// if (str1.size() && x == '#') str1.pop_back();
// else {
// if (x != '#') str1 += x;
// }
// }
// for (auto x : t)
// {
// if (str2.size() && x == '#') str2.pop_back();
// else {
// if (x != '#') str2 += x;
// }
// }
// return strcmp(str1.c_str(), str2.c_str()) == 0;
// }
//};
//class Solution
//{
//public:
// int calculate(string s)
// {
// vector<int> st; // ⽤数组来模拟栈结构
// int i = 0, n = s.size();
// char op = '+';
// while (i < n)
// {
// if (s[i] == ' ') i++;
// else if (s[i] >= '0' && s[i] <= '9')
// {
// // 先把这个数字给提取出来
// int tmp = 0;
// while (i < n && s[i] >= '0' && s[i] <= '9')
// tmp = tmp * 10 + (s[i++] - '0');
// if (op == '+') st.push_back(tmp);
// else if (op == '-') st.push_back(-tmp);
// else if (op == '*') st.back() *= tmp;
// else st.back() /= tmp;
// }
// else
// {
// op = s[i];
// i++;
// }
// }
// int ret = 0;
// for (auto x : st) ret += x;
// return ret;
// }
//};
#include<stack>
#include<string>
//class Solution
//{
//public:
// string decodeString(string s)
// {
// stack<int> nums;
// stack<string> st;
// st.push("");
// int i = 0, n = s.size();
// while (i < n)
// {
// if (s[i] >= '0' && s[i] <= '9')
// {
// int tmp = 0;
// while (s[i] >= '0' && s[i] <= '9')
// {
// tmp = tmp * 10 + (s[i] - '0');
// i++;
// }
// nums.push(tmp);
// }
// else if (s[i] == '[')
// {
// i++; // 把括号后⾯的字符串提取出来
// string tmp = "";
// while (s[i] >= 'a' && s[i] <= 'z')
// {
// tmp += s[i];
// i++;
// }
// st.push(tmp);
// }
// else if (s[i] == ']')
// {
// string tmp = st.top();
// st.pop();
// int k = nums.top();
// nums.pop();
// while (k--)
// {
// st.top() += tmp;
// }
// i++; // 跳过这个右括号
// }
// else
// {
// string tmp;
// while (i < n && s[i] >= 'a' && s[i] <= 'z')
// {
// tmp += s[i];
// i++;
// }
// st.top() += tmp;
// }
// }
// return st.top();
// }
//};
//
//
//class Solution {
//public:
// bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
// {
// stack<int> st;
// int i = 0, n = pushed.size();
// for (auto x : pushed)
// {
// st.push(x);
// while (st.size() && st.top() == popped[i])
// {
// st.pop();
// i++;
// }
// }
// return i == n;
// }
//};
// Definition for a Node.
//class TreeNode {
//public:
// int val;
// vector<TreeNode*> children;
// int left;
// int right;
//
// TreeNode() {}
//
// TreeNode(int _val) {
// val = _val;
// }
//
// TreeNode(int _val, vector<TreeNode*> _children) {
// val = _val;
// children = _children;
// }
//};
//
//
//class Solution {
//public:
// vector<vector<int>> levelOrder(Node* root)
// {
// vector<vector<int>> ret;// 记录最终结果
// queue<Node*> q; // 层序遍历需要的队列
// if (root == nullptr) return ret;
// q.push(root);
// while (q.size())
// {
// int sz = q.size(); // 求出本层元素的个数
// vector<int> tmp; //统计本层的节点
// for (int i = 0; i < sz; i++)
// {
// Node* t = q.front(); // 取出对头
// q.pop();
// tmp.push_back(t->val);
// for (Node* child : t->children) //让下一层节点入队列
// {
// if (child != nullptr) q.push(child);
// }
// }
// ret.push_back(tmp);
// }
// return ret;
// }
//};
/**
* 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>> zigzagLevelOrder(TreeNode* root)
// {
// vector<vector<int>> ret;
// if (root == nullptr) return ret;
// queue<TreeNode*> q;
// q.push(root);
// int level = 1;
// while (q.size())
// {
// int sz = q.size();
// vector<int> tmp;
// for (int i = 0; i < sz; i++)
// {
// auto t = q.front();
// q.pop();
// tmp.push_back(t->val);
// if (t->left) q.push(t->left);
// if (t->right) q.push(t->right);
// }
// // 判断是否逆序
// if (level % 2 == 0) reverse(tmp.begin(), tmp.end());
// ret.push_back(tmp);
// level++;
// }
// return ret;
// }
//};
///**
// * 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 widthOfBinaryTree(TreeNode* root)
// {
// vector<pair<TreeNode*, unsigned int>> q;//用数组模拟队列
// q.push_back({ root , 1 });
// unsigned int ret = 0;
// while (q.size())
// {
// // 先更新这一层的宽度
// auto& [x1, y1] = q[0];
// auto& [x2, y2] = q.back();
// ret = max(ret, y2 - y1 + 1);
// // 让下一层进队列
// vector<pair<TreeNode*, unsigned int>> tmp;//让下一层进入这个队列
// for (auto& [x, y] : q)
// {
// if (x->left) tmp.push_back({ x->left, y * 2 });
// if (x->right) tmp.push_back({ x->right, y * 2 + 1 });
// }
// q = tmp;
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// vector<int> largestValues(TreeNode* root)
// {
// vector<int> ret;
// if (root == nullptr) return ret;
// queue<TreeNode*> q;
// q.push(root);
// while (q.size())
// {
// int sz = q.size();
// int tmp = INT_MIN;
// for (int i = 0; i < sz; i++)
// {
// auto t = q.front();
// q.pop();
// tmp = max(tmp, t->val);
// if (t->left) q.push(t->left);
// if (t->right) q.push(t->right);
// }
// ret.push_back(tmp);
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// int lastStoneWeight(vector<int>& stones)
// {
// // 1. 创建⼀个⼤根堆
// priority_queue<int> heap;
// // 2. 将所有元素丢进这个堆⾥⾯
// for (auto x : stones) heap.push(x);
// // 3. 模拟这个过程
// while (heap.size() > 1)
// {
// int a = heap.top(); heap.pop();
// int b = heap.top(); heap.pop();
// if (a > b) heap.push(a - b);
// }
// return heap.size() ? heap.top() : 0;
// }
//};
//class KthLargest
//{
// // 创建⼀个⼤⼩为 k 的⼩跟堆
// priority_queue<int, vector<int>, greater<int>> heap;
// int _k;
//public:
// KthLargest(int k, vector<int>& nums)
// {
// _k = k;
// for (auto x : nums)
// {
// heap.push(x);
// if (heap.size() > _k) heap.pop();
// }
// }
//
// int add(int val)
// {
// heap.push(val);
// if (heap.size() > _k) heap.pop();
// return heap.top();
// }
//};
///**
// * Your KthLargest object will be instantiated and called as such:
// * KthLargest* obj = new KthLargest(k, nums);
// * int param_1 = obj->add(val);
// */
//class Solution
//{
// typedef pair<string, int> PSI;
// struct cmp
// {
// bool operator()(const PSI& a, const PSI& b)
// {
// if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列
// {
// return a.first < b.first;
// }
// return a.second > b.second;
// }
// };
//public:
// vector<string> topKFrequent(vector<string>& words, int k)
// {
// // 1. 统计⼀下每⼀个单词的频次
// unordered_map<string, int> hash;
// for (auto& s : words) hash[s]++;
// // 2. 创建⼀个⼤⼩为 k 的堆
// priority_queue<PSI, vector<PSI>, cmp> heap;
// // 3. TopK 的主逻辑
// for (auto& psi : hash)
// {
// heap.push(psi);
// if (heap.size() > k) heap.pop();
// }
// // 4. 提取结果
// vector<string> ret(k);
// for (int i = k - 1; i >= 0; i--)
// {
// ret[i] = heap.top().first;
// heap.pop();
// }
// return ret;
// }
//};
//class MedianFinder
//{
// priority_queue<int> left; // ⼤根堆
// priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
//public:
// MedianFinder()
// {}
//
// void addNum(int num)
// {
// // 分类讨论即可
// if (left.size() == right.size()) // 左右两个堆的元素个数相同
// {
// if (left.empty() || num <= left.top()) // 放 left ⾥⾯
// {
// left.push(num);
// }
// else
// {
// right.push(num);
// left.push(right.top());
// right.pop();
// }
// }
// else
// {
// if (num <= left.top())
// {
// left.push(num);
// right.push(left.top());
// left.pop();
// }
// else
// {
// right.push(num);
// }
// }
// }
//
// double findMedian()
// {
// if (left.size() == right.size()) return (left.top() + right.top()) /
// 2.0;
// else return left.top();
// }
//};
///**
// * Your MedianFinder object will be instantiated and called as such:
// * MedianFinder* obj = new MedianFinder();
// * obj->addNum(num);
// * double param_2 = obj->findMedian();
// */
/*
*The task state array is a strange "bitmap" of
*reasons to sleep. Thus "running" is zero, and
*you can test for combinations of others with
*simple bit tests.
*/
//static const char* const task_state_array[] =
//{
// "R (running)", /*0 */
// "S (sleeping)", /*1 */
// "D (disk sleep)", /*2 */
// "T (stopped)", /*4 */
// "t (tracing stop)", /*8 */
// "X (dead)", /*16 */
// "Z (zombie)", /*32 */
//};
//
//
//#include <sys/time.h>
//#include <sys/resource.h>
//int getpriority(int which, int who);
//int setpriority(int which, int who, int prio);
// 第一种方法：命令行第三个参数
//#include <stdio.h>
//int main(int argc, char* argv[], char* env[])
//{
// int i = 0;
// for (; env[i]; i++) {
// printf("%s\n", env[i]);
// }
// return 0;
//}
//// 第二种方法：通过第三方变量environ获取
//int main(int argc, char* argv[])
//{
// extern char** environ;
// int i = 0;
// for (; environ[i]; i++) {
// printf("%s\n", environ[i]);
// }
// return 0;
//}
//
//#include <stdio.h>
//#include <stdlib.h>
//int main()
//{
// printf("%s\n", getenv("PATH"));
// return 0;
//}
//#include <stdio.h>
//#include <unistd.h>
//#include <stdlib.h>
//int g_val = 0;
//int main()
//{
// pid_t id = fork();
// if (id < 0) {
// perror("fork");
// return 0;
// }
// else if (id == 0) { //child
// printf("child[%d]: %d : %p\n", getpid(), g_val, &g_val);
// }
// else { //parent
// printf("parent[%d]: %d : %p\n", getpid(), g_val, &g_val);
// }
// sleep(1);
// return 0;
//}
//#include <stdio.h>
//#include <unistd.h>
//#include <stdlib.h>
//int g_val = 0;
//int main()
//{
// pid_t id = fork();
// if (id < 0) {
// perror("fork");
// return 0;
// }
// else if (id == 0) { //child,⼦进程肯定先跑完，也就是⼦进程先修改，完成之后，⽗进程
// 再读取
// g_val = 100;
// printf("child[%d]: %d : %p\n", getpid(), g_val, &g_val);
// }
// else { //parent
// sleep(3);
// printf("parent[%d]: %d : %p\n", getpid(), g_val, &g_val);
// }
// sleep(1);
// return 0;
//}
//struct task_struct
//{
// /*...*/
// struct mm_struct* mm; //对于普通的⽤⼾进程来说该字段指向他
// //的虚拟地址空间的⽤⼾空间部分，对于内核线程来说这部分为NULL。
// struct mm_struct* active_mm;
// // 该字段是内核线程使⽤的。当
// //该进程是内核线程时，它的mm字段为NULL，表⽰没有内存地址空间，可也并不是真正的没有，这是因
// //为所有进程关于内核的映射都是⼀样的，内核线程可以使⽤任意进程的地址空间。
// /*...*/
//}
//struct mm_struct
//{
// /*...*/
// struct vm_area_struct* mmap; /* 指向虚拟区间(VMA)链表 */
// struct rb_root mm_rb; /* red_black树 */
// unsigned long task_size; /*具有该结构体的进程的虚拟地址空间的⼤⼩*/
// /*...*/
// // 代码段、数据段、堆栈段、参数段及环境段的起始和结束地址。
// unsigned long start_code, end_code, start_data, end_data;
// unsigned long start_brk, brk, start_stack;
// unsigned long arg_start, arg_end, env_start, env_end;
//}
//struct device
//{
// int id;
// int vender;
// int status;
// void* data;
// struct device* next;
// int type;
// struct task_struct* wait_queue;
//};
//struct list_head
//{
// tast_struct都是用双向链表链接起来
// struct list_head* next, * prev;
//};
//
//
// 方法 nice renice命令
//#include<sys/time.h>
//int getpriority(int which, int who);
//#include<sys/resource.h>
//int setpriority(int which, int who, int prio);
//int a = 0;
//int b = 0;
//
//
//class Solution {
//public:
// typedef pair<int, int> PII;
// int dx[4] = { 0,0,1,-1 };
// int dy[4] = { 1,-1,0,0 };
// vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
// {
// int prev = image[sr][sc];
// if (prev == color) return image;
// int m = image.size(), n = image[0].size();
// queue<PII> q;
// q.push({ sr,sc });
// while (!q.empty())
// {
// auto [a, b] = q.front();
// image[a][b] = color;
// q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
// {
// q.push({ x,y });
// }
// }
// }
// return image;
// }
//};
//class Solution
//{
// int dx[4] = { 1, -1, 0, 0 };
// int dy[4] = { 0, 0, 1, -1 };
// bool vis[301][301];
// int m, n;
//public:
// int numIslands(vector<vector<char>>& grid)
// {
// m = grid.size(), n = grid[0].size();
// int ret = 0;
// for (int i = 0; i < m; i++)
// {
// for (int j = 0; j < n; j++)
// {
// if (grid[i][j] == '1' && !vis[i][j])
// {
// ret++;
// bfs(grid, i, j); // 把这块陆地全部标记⼀下
// }
// }
// }
// return ret;
// }
// void bfs(vector<vector<char>>& grid, int i, int j)
// {
// queue<pair<int, int>> q;
// q.push({ i, j });
// vis[i][j] = true;
// while (q.size())
// {
// auto [a, b] = q.front();
// q.pop();
// for (int k = 0; k < 4; k++)
// {
// int x = a + dx[k], y = b + dy[k];
// if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' &&
// !vis[x][y])
// {
// q.push({ x, y });
// vis[x][y] = true;
// }
// }
// }
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
// bool vis[51][51];
// int m, n;
//public:
// int maxAreaOfIsland(vector<vector<int>>& grid)
// {
// m = grid.size(), n = grid[0].size();
// int ret = 0;
// for (int i = 0; i < m; i++)
// {
// for (int j = 0; j < n; j++)
// {
// if (grid[i][j] == 1 && !vis[i][j])
// {
// ret = max(ret, bfs(grid, i, j));
// }
// }
// }
// return ret;
// }
// int bfs(vector<vector<int>>& grid, int i, int j)
// {
// int count = 0;
// queue<pair<int, int>> q;
// q.push({ i, j });
// vis[i][j] = true;
// count++;
// while (q.size())
// {
// auto [a, b] = q.front();
// q.pop();
// for (int k = 0; k < 4; k++)
// {
// int x = a + dx[k], y = b + dy[k];
// if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
// !vis[x][y])
// {
// q.push({ x, y });
// vis[x][y] = true;
// count++;
// }
// }
// }
// return count;
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
// int m, n;
//public:
// void solve(vector<vector<char>>& board)
// {
// m = board.size(), n = board[0].size();
// // 1. 先处理边界上的 'O' 联通块，全部修改成 '.'
// for (int j = 0; j < n; j++)
// {
// if (board[0][j] == 'O') bfs(board, 0, j);
// if (board[m - 1][j] == 'O') bfs(board, m - 1, j);
// }
// for (int i = 0; i < m; i++)
// {
// if (board[i][0] == 'O') bfs(board, i, 0);
// if (board[i][n - 1] == 'O') bfs(board, i, n - 1);
// }
// // 2. 还原
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (board[i][j] == 'O') board[i][j] = 'X';
// else if (board[i][j] == '.') board[i][j] = 'O';
// }
// void bfs(vector<vector<char>>& board, int i, int j)
// {
// queue<pair<int, int>> q;
// q.push({ i, j });
// board[i][j] = '.';
// while (q.size())
// {
// auto [a, b] = q.front();
// q.pop();
// for (int k = 0; k < 4; k++)
// {
// int x = a + dx[k], y = b + dy[k];
// if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
// {
// q.push({ x, y });
// board[x][y] = '.';
// }
// }
// }
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
//public:
// int nearestExit(vector<vector<char>>& maze, vector<int>& e)
// {
// int m = maze.size(), n = maze[0].size();
// bool vis[m][n];
// memset(vis, 0, sizeof vis);
// queue<pair<int, int>> q;
// q.push({ e[0], e[1] });
// vis[e[0]][e[1]] = true;
// int step = 0;
// while (q.size())
// {
// step++;
// int sz = q.size();
// for (int i = 0; i < sz; i++)
// {
// auto [a, b] = q.front();
// q.pop();
// for (int j = 0; j < 4; j++)
// {
// int x = a + dx[j], y = b + dy[j];
// if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.'
// && !vis[x][y])
// {
// // 判断是否已经到达出⼝
// if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return
// step;
// q.push({ x, y });
// vis[x][y] = true;
// }
// }
// }
// }
// return -1;
// }
//};
//class Solution
//{
//public:
// int minMutation(string startGene, string endGene, vector<string>& bank)
// {
// unordered_set<string> vis; // ⽤来标记已经搜索过的状态
// unordered_set<string> hash(bank.begin(), bank.end()); // 存储基因库⾥⾯的字符串
// string change = "ACGT";
// if (startGene == endGene) return 0;
// if (!hash.count(endGene)) return -1;
// queue<string> q;
// q.push(startGene);
// vis.insert(startGene);
// int ret = 0;
// while (q.size())
// {
// ret++;
// int sz = q.size();
// while (sz--)
// {
// string t = q.front();
// q.pop();
// for (int i = 0; i < 8; i++)
// {
// string tmp = t; // 细节问题
// for (int j = 0; j < 4; j++)
// {
// tmp[i] = change[j];
// if (hash.count(tmp) && !vis.count(tmp))
// {
// if (tmp == endGene) return ret;
// q.push(tmp);
// vis.insert(tmp);
// }
// }
// }
// }
// }
// return -1;
// }
//};
//class Solution
//{
//public:
// int ladderLength(string beginWord, string endWord, vector<string>&
// wordList)
// {
// unordered_set<string> hash(wordList.begin(), wordList.end());
// unordered_set<string> vis; // 标记已经搜索过的单词
// if (!hash.count(endWord)) return 0;
// queue<string> q;
// q.push(beginWord);
// vis.insert(beginWord);
// int ret = 1;
// while (q.size())
// {
// ret++;
// int sz = q.size();
// while (sz--)
// {
// string t = q.front();
// q.pop();
// for (int i = 0; i < t.size(); i++)
// {
// string tmp = t;
// for (char ch = 'a'; ch <= 'z'; ch++)
// {
// tmp[i] = ch;
// if (hash.count(tmp) && !vis.count(tmp))
// {
// if (tmp == endWord) return ret;
// q.push(tmp);
// vis.insert(tmp);
// }
// }
// }
// }
// }
// return 0;
// }
//};
//class Solution
//{
// int m, n;
//public:
// int cutOffTree(vector<vector<int>>& f)
// {
// m = f.size(), n = f[0].size();
// // 1. 准备⼯作：找出砍树的顺序
// vector<pair<int, int>> trees;
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (f[i][j] > 1) trees.push_back({ i, j });
//
// sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const
// pair<int, int>& p2)
// {
// return f[p1.first][p1.second] < f[p2.first][p2.second];
// });
// // 2. 按照顺序砍树
// int bx = 0, by = 0;
// int ret = 0;
// for (auto& [a, b] : trees)
// {
// int step = bfs(f, bx, by, a, b);
// if (step == -1) return -1;
// ret += step;
// bx = a, by = b;
// }
// return ret;
// }
// bool vis[51][51];
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
// int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
// {
// if (bx == ex && by == ey) return 0;
// queue<pair<int, int>> q;
// memset(vis, 0, sizeof vis); // 清空之前的数据
// q.push({ bx, by });
// vis[bx][by] = true;
// int step = 0;
// while (q.size())
// {
// step++;
// int sz = q.size();
// while (sz--)
// {
// auto [a, b] = q.front();
// q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] && !vis[x]
// [y])
// {
// if (x == ex && y == ey) return step;
// q.push({ x, y });
// vis[x][y] = true;
// }
// }
// }
// }
// return -1;
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
//public:
// vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
// {
// int m = mat.size(), n = mat[0].size();
//
// // dist[i][j] == -1 表⽰：没有搜索过
// // dist[i][j] != -1 表⽰：最短距离
// vector<vector<int>> dist(m, vector<int>(n, -1));
// queue<pair<int, int>> q;
// // 1. 把所有的源点加⼊到队列中
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (mat[i][j] == 0)
// {
// q.push({ i, j });
// dist[i][j] = 0;
// }
//
// // 2. ⼀层⼀层的往外扩
// while (q.size())
// {
// auto [a, b] = q.front(); q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
// {
// dist[x][y] = dist[a][b] + 1;
// q.push({ x, y });
// }
// }
// }
// return dist;
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
//public:
// int numEnclaves(vector<vector<int>>& grid)
// {
// int m = grid.size(), n = grid[0].size();
// vector<vector<bool>> vis(m, vector<bool>(n));
// queue<pair<int, int>> q;
// // 1. 把边上的 1 加⼊到队列中
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
// {
// if (grid[i][j] == 1)
// {
// q.push({ i, j });
// vis[i][j] = true;
// }
// }
// // 2. 多源 bfs
// while (q.size())
// {
// auto [a, b] = q.front();
// q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
// !vis[x][y])
// {
// vis[x][y] = true;
// q.push({ x, y });
// }
// }
// }
// // 3. 统计结果
// int ret = 0;
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (grid[i][j] == 1 && !vis[i][j])
// ret++;
// return ret;
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
//public:
// vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
// {
// int m = isWater.size(), n = isWater[0].size();
// vector<vector<int>> dist(m, vector<int>(n, -1));
// queue<pair<int, int>> q;
// // 1. 把所有的源点加⼊到队列⾥⾯
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (isWater[i][j])
// {
// dist[i][j] = 0;
// q.push({ i, j });
// }
// // 2. 多源 bfs
// while (q.size())
// {
// auto [a, b] = q.front(); q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
// {
// dist[x][y] = dist[a][b] + 1;
// q.push({ x, y });
// }
// }
// }
// return dist;
// }
//};
//class Solution
//{
// int dx[4] = { 0, 0, 1, -1 };
// int dy[4] = { 1, -1, 0, 0 };
//public:
// int maxDistance(vector<vector<int>>& grid)
// {
// int m = grid.size(), n = grid[0].size();
// vector<vector<int>> dist(m, vector<int>(n, -1));
// queue<pair<int, int>> q;
// for (int i = 0; i < m; i++)
// for (int j = 0; j < n; j++)
// if (grid[i][j])
// {
// dist[i][j] = 0;
// q.push({ i, j });
// }
//
// int ret = -1;
// while (q.size())
// {
// auto [a, b] = q.front(); q.pop();
// for (int i = 0; i < 4; i++)
// {
// int x = a + dx[i], y = b + dy[i];
// if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
// {
// dist[x][y] = dist[a][b] + 1;
// q.push({ x, y });
// ret = max(ret, dist[x][y]);
// }
// }
// }
// return ret;
// }
//};
//class Solution
//{
//public:
// bool canFinish(int n, vector<vector<int>>& p)
// {
// unordered_map<int, vector<int>> edges; // 邻接表
// vector<int> in(n); // 存储每⼀个结点的⼊度
//
// // 1. 建图
// for (auto& e : p)
// {
// int a = e[0], b = e[1];
// edges[b].push_back(a);
// in[a]++;
// }
// // 2. 拓扑排序 - bfs
// queue<int> q;
// // 把所有⼊度为 0 的点加⼊到队列中
// for (int i = 0; i < n; i++)
// {
// if (in[i] == 0) q.push(i);
// }
// // 层序遍历
// while (!q.empty())
// {
// int t = q.front();
// q.pop();
// // 修改相连的边
// for (int e : edges[t])
// {
// in[e]--;
// if (in[e] == 0) q.push(e);
// }
// }
// // 3. 判断是否有环
// for (int i : in)
// if (i)
// return false;
//
// return true;
// }
//};
//class Solution
//{
//public:
// vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
// {
// // 1. 准备⼯作
// vector<vector<int>> edges(numCourses); // 邻接表存储图
// vector<int> in(numCourses); // 存储每⼀个点的⼊度
// // 2. 建图
// for (auto& p : prerequisites)
// {
// int a = p[0], b = p[1]; // b -> a
// edges[b].push_back(a);
// in[a]++;
// }
// // 3. 拓扑排序
// vector<int> ret; // 统计排序后的结果
// queue<int> q;
// for (int i = 0; i < numCourses; i++)
// {
// if (in[i] == 0) q.push(i);
// }
// while (q.size())
// {
// int t = q.front(); q.pop();
// ret.push_back(t);
// for (int a : edges[t])
// {
// in[a]--;
// if (in[a] == 0) q.push(a);
// }
// }
// if (ret.size() == numCourses) return ret;
// else return {};
// }
//};
//class Solution
//{
// unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
// unordered_map<char, int> in; // 统计⼊度
// bool cheak; // 处理边界情况
//public:
// string alienOrder(vector<string>& words)
// {
// // 1. 建图 + 初始化⼊度哈希表
// for (auto& s : words)
// {
// for (auto ch : s)
// {
// in[ch] = 0;
// }
// }
// int n = words.size();
// for (int i = 0; i < n; i++)
// {
// for (int j = i + 1; j < n; j++)
// {
// add(words[i], words[j]);
// if (cheak) return "";
// }
// }
//
// // 2. 拓扑排序
// queue<char> q;
// for (auto& [a, b] : in)
// {
// if (b == 0) q.push(a);
// }
// string ret;
// while (q.size())
// {
// char t = q.front(); q.pop();
// ret += t;
// for (char ch : edges[t])
// {
// if (--in[ch] == 0) q.push(ch);
// }
// }
// // 3. 判断
// for (auto& [a, b] : in)
// if (b != 0) return "";
//
// return ret;
// }
// void add(string& s1, string& s2)
// {
// int n = min(s1.size(), s2.size());
// int i = 0;
// for (; i < n; i++)
// {
// if (s1[i] != s2[i])
// {
// char a = s1[i], b = s2[i]; // a -> b
// if (!edges.count(a) || !edges[a].count(b))
// {
// edges[a].insert(b);
// in[b]++;
// }
// break;
// }
// }
// if (i == s2.size() && i < s1.size()) cheak = true;
// }
//};
// 补充内容，其实是差了几道题
//class Solution {
//public:
// int hammingWeight(int n)
// {
// int sum = 0;
// int i = 0;
// for (int i = 0; i < 32; i++)
// {
// if ((n >> i) & 1 == 1)
// {
// sum++;
// }
// }
// return sum;
// }
//};
//class Solution {
//public:
// vector<int> countBits(int n)
// {
// vector<int> nums(n + 1);
// for (int i = 0; i <= n; i++)
// {
// int sum = 0;
// for (int j = 0; j < 32; j++)
// {
// if ((i >> j) & 1 == 1)
// sum++;
// }
// nums[i] = sum;
// }
// return nums;
// }
//};
//class Solution {
//public:
// int hammingDistance(int x, int y)
// {
// int sum = 0;
// for (int i = 0; i < 32; i++)
// {
// if (((x >> i) & 1) ^ ((y >> i) & 1) == 1)
// sum++;
// }
// return sum;
// }
//};
//class Solution {
//public:
// int singleNumber(vector<int>& nums)
// {
// int ret = 0;
// for (int i = 0; i < nums.size(); i++)
// {
// ret ^= nums[i];
// }
// return ret;
// }
//};
#include<stdlib.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* singleNumber(int* nums, int numsSize, int* returnSize)
//{
// int* ans = (int*)calloc(2, sizeof(int));
// int ret = 0;
// int i = 0;
// //计算数组中所有数异或起来的结果ret
// for (i = 0; i < numsSize; i++) {
// ret ^= nums[i];
// }
//
// //从低位往⾼位遍历计算ret的⼆进制中哪⼀位是1
// int pos = 0;
// for (i = 0; i < 32; i++) {
// if (((ret >> i) & 1) == 1) {
// pos = i;
// break;
// }
// }
// //3. 分组异或
// for (i = 0; i < numsSize; i++) {
// //若当前数pos位为1，作为其中⼀组对ans[0]进⾏异或操作
// if (((nums[i] >> pos) & 1) == 1) {
// ans[0] ^= nums[i];
// }
// //否则，作为另⼀组对ans[1]进⾏异或操作。
// else {
// ans[1] ^= nums[i];
// }
// }
// //ans[1]另⼀种计算⽅法
// //ans[1]=ret^ans[0];
// //更新数组⻓度
// *returnSize = 2;
// //返回答案数组
// return ans;
//}