算法闭关修炼百题计划（一）

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> heap;for(int i = 0; i < nums.size(); i ++){if(heap.find(target - nums[i]) != heap.end()) return {heap[target - nums[i]], i};heap[nums[i]] = i;}return {};}
};

2.前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> valToFreq;vector<int> result;for(auto num : nums){valToFreq[num] ++;}vector<pair<int,int>> vec(valToFreq.begin(), valToFreq.end());sort(vec.begin(),vec.end(),[](pair<int,int>& a, pair<int,int>& b){return a.second > b.second;});for(auto pair:vec){if(k > 0){result.push_back(pair.first);   }k--;}return result;}
};

3.只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

不能用sort也不能新开空间！
小tips：

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；
一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。
对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素。

class Solution {
public:int singleNumber(std::vector<int>& nums) {int res = 0;for (int n : nums) {res ^= n;}return res;}
};

4.数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

class Solution {
public:const int N = 50010;int findShortestSubArray(vector<int>& nums) {int n = nums.size(), maxP = 0, ans = 0x3f3f3f3f;//统计频率unordered_map<int, int> umap;//统计每个元素出现的最早和最晚位置vector<int> first(N, -1), last(N, -1);for(int i = 0; i < nums.size(); i ++){umap[nums[i]]++;maxP = max(maxP, umap[nums[i]]);if(first[nums[i]] == -1) first[nums[i]] = i;last[nums[i]] = i;}for(auto t : nums){if(umap[t] == maxP) ans = min(ans, last[t] - first[t] + 1);}return ans;}
};

5.最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。

class Solution {
public:int maxScoreSightseeingPair(vector<int>& values) {//求value[i] + value[j] + i - j的max//相当于求value[i] + i, 和value[j] - j的最大值, i < j//所以只需要遍历一次int maxScore = INT_MIN, left = values[0];for(int i = 1; i < values.size(); i ++){maxScore = max(maxScore, values[i] - i + left);left = max(left, values[i] + i);}return maxScore;}
};

6.整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹ − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
public:int reverse(int x) {long long res = 0;  // 使用 long long 避免溢出int sign = (x < 0) ? -1 : 1;  // 根据 x 的符号确定结果的符号x = abs(x);  // 只处理正数，避免负号干扰while (x != 0) {res = res * 10 + x % 10;  // 反转数字x /= 10;  // 去除最低位if (res > INT_MAX) return 0;  // 检查溢出}return sign * res;  // 应用符号并返回结果}
};

7.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

这个最小的正整数一定在[1，nums.size() + 1]之间，为什么。想一想

class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_map<int, int> umap;for(int i = 0; i < nums.size(); i++){umap[nums[i]]++;}for(int i = 1; i <= nums.size(); i ++){if(umap[i] == 0) return i;}return nums.size()+1;}
};

8.字符串中最多数目的子序列

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

比如：
输入：text = “abdcdbc”, pattern = “ac”
输出：4

思路：
首先考虑不加的情况，怎么计算子序列？
使用两个变量 cnt0 和 cnt1 分别记录 pattern[0] 和 pattern[1] 出现了多少次，使用 ans 记录答案数量。

遍历字符串，如果当前字符和 pattern[1] 相同，那么ans += cnt0（这是因为之前的每个pattern[0]都可以和当前字符组成pattern，并且cnt1 += 1；

如果当前字符和pattern[0]相同，那么cnt0 += 1。

现在再考虑加上字符，会有什么变化？
如果要添加pattern[0]到字符串中，那么肯定要将pattern[0]添加到字符串开头，这样后面每个pattern[1]都可以和开头新增的这个pattern[0]组成pattern，答案数量增加cnt1（有多少个pattern[1]就能多组成多少个pattern）；

如果要添加pattern[1]到字符串中，那么肯定要添加到字符串尾，这样答案数量就会增加cnt0。

也就是说，往字符串中添加字符，最多可以令答案增加max(cnt0，cnt1)

typedef long long ll;
class Solution{
public:ll maximumSubsequenceCount(string text, string pattern) {ll ans = 0;ll cnt0 = 0, cnt1 = 0;//for计算不加的情况,顺便记录cnt01值for(char c : text){if(c == pattern[1]){cnt1++;ans += cnt0;}if(c == pattern[0]){cnt0++;}}return ans + max(cnt0, cnt1);}
};

9.k个一组翻转链表

题目要求输入 head，reverseKGroup 函数能够把以 head 为头的这条链表进行翻转。

我们要充分利用这个递归函数的定义，把原问题分解成规模更小的子问题进行求解。
先翻转以head开头的k个元素，将第k+1个元素作为head递归调用 reverseKGroup 函数。

然后还需要将两个过程的结果连起来

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {if(head == nullptr) return nullptr;//区间[a,b)包含k个待翻转的元素ListNode* a = head;ListNode* b = head;for(int i = 0; i < k; i ++){if(b ==  nullptr) return head;b = b->next;}//翻转前k个ListNode* newHead = reverse(a, b);//翻转前后连起来a->next = reverseKGroup(b, k);return newHead;}//[a,b)ListNode* reverse(ListNode* a, ListNode* b){ListNode* pre, *cur, *tmp;pre = nullptr;cur = a;tmp = a;while(cur != b){tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}
};

10.反转链表II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

假如left == 1，需要反转的部分从链表的第一个节点就开始，那么翻转后链表的头结点将发生变化，使用dummy可以特殊处理这种情况。

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* p0 = dummy;for(int i = 1; i < left; i ++) p0 = p0->next;ListNode* pre = nullptr;ListNode* cur = p0->next;for(int i = 0; i < right - left + 1; i ++){ListNode* tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}p0->next->next = cur;p0->next = pre;return dummy->next;}
};

11. 公司命名

难得一批，但是看懂了

思路：
按照首字母来统计后半部分字符串的集合，如果2个集合之间的元素可以互换首字母，那么只要满足A集合中的没有在B集合出现过即可。

class Solution {
public:long long distinctNames(vector<string>& ideas) {// 使用数组存储每个首字母对应的尾部部分集合vector<unordered_set<string>> sets(26);// 将 ideas 按首字母分类存入对应的集合for (const string& idea : ideas) {sets[idea[0] - 'a'].insert(idea.substr(1));}long long ans = 0;// 双重循环比较不同首字母的集合for (int i = 0; i < 26; i++) {for (int j = 0; j < i; j++) {int m = 0;// m 统计两个集合中相同尾部部分的个数for (const string& s : sets[i]) {if (sets[j].count(s)) {m++;}}// 计算有效组合ans += (long long)(sets[i].size() - m) * (sets[j].size() - m);}}return ans * 2;}
};

12.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

注意他的for是怎么遍历的

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//按照start排序sort(intervals.begin(), intervals.end(),[](vector<int> a, vector<int> b){return a[0] < b[0];});vector<vector<int>> res;//把第一个元素push进去res.push_back(intervals[0]);for(int i = 1; i < intervals.size(); i ++){//区间重叠if(res.back()[1] >= intervals[i][0]){res.back()[1] = max(res.back()[1], intervals[i][1]);}//区间不重叠else{res.push_back(intervals[i]);}}return res;}
};

13.快速排序

快排就是分治，给一个基准值，左边都小于这个基准值，右边都大于这个基准值
分别排序左右，合并就是有序数组了
注意mid = nums[(l + r) / 2]，而不是mid = (l + r) / 2，不要用索引直接用值

class Solution {
public:void quick_sort(vector<int>& nums, int l, int r){if(l >= r) return;int left = l - 1, right = r + 1, mid = nums[(l + r) / 2];while(left < right){do left ++; while(nums[left] < mid);do right--;while(nums[right] > mid);if(left < right) swap(nums[left], nums[right]);}quick_sort(nums, l, right);quick_sort(nums, right + 1, r);}vector<int> sortArray(vector<int>& nums) {quick_sort(nums, 0, nums.size() - 1);return nums;}
};

14.数字中的第k个最大元素

真的很想sort，但是这道题考频这么高，不可能让你调用库函数…

如果对原数组排序，再返回倒数第k个位置，这样复杂度是O(nlogn)
其实可以更快
在快排中，每次经过划分后，一定可以确定一个元素的最终位置，即x的最终位置是q，并且a[l…q - 1]中的每个元素小于等于a[q]，且a[q]小于等于a[q + 1…r]中的每个元素，所以只要某次划分的q为倒数第k个下标的时候，我们就找到了答案，只需关注这点。

class Solution {
public:int quickselect(vector<int> &nums, int l, int r, int k) {if (l == r)return nums[k];int mid = nums[(l + r)/2], i = l - 1, j = r + 1;while (i < j) {do i++; while (nums[i] < mid);do j--; while (nums[j] > mid);if (i < j)swap(nums[i], nums[j]);}if (k <= j) return quickselect(nums, l, j, k);else return quickselect(nums, j + 1, r, k);}int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, n - k);}
};

15.归并排序

如果说快排是前序，那么归并就是后序，一个是先计算再递归，一个是先递归再计算
两个都属于分治算法

void merge_sort(vector<int>& nums, int lo, int hi){if(lo >= hi) return;int mid = (lo + hi) >> 1;merge_sort(nums, lo, mid);merge_sort(nums, mid + 1, hi);vector<int> tmp(hi - lo + 1); // 创建一个新的 tmp 数组int k = 0;int i = lo, j = mid + 1;while(i <= mid && j <= hi){if(nums[i] > nums[j]){tmp[k++] = nums[j++];}else{tmp[k++] = nums[i++];}}while(i <= mid) tmp[k++] = nums[i++];while(j <= hi) tmp[k++] = nums[j++];for(int i = lo, j = 0; i <= hi && j < k; i ++, j ++){nums[i] = tmp[j];}
}

16.岛屿数量

class Solution {
private:int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){for(int i = 0; i < 4; i ++){//4个方向的1全标记trueint nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == '1'){visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited(n, vector<bool>(m, false));int res = 0;for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++){if(!visited[i][j] && grid[i][j] == '1'){res++;dfs(grid, visited, i, j);}}}return res;}
};

17.每种字符至少取k个

给你一个由字符 ‘a’、‘b’、‘c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

两边不好想，用滑动窗口想中间
怎么看外面字符呢，用一个tar数组，初始化为-k，for遍历++，tar中存的就是比k多的数量
滑动窗口内的数字，和tar里面留的数字比较，滑动窗口的数字小于tar中的，说明两侧这个字母的数量>k，滑动窗口的数字大于tar中的，说明两侧这个字母小于k

什么时候缩小窗口：因为当窗口中某个字符的数量 超过 tar 时，就意味着在剩余的字符串中，该字符的数量将 少于 k，这不符合题目要求。tar[i] 表示的是在可以移除的字符中，每种字符最多能移除的数量（即总数量减去 k）。因此，在滑动窗口中，我们需要确保窗口中每种字符的数量 不超过 tar[i]。

class Solution {
public:int takeCharacters(string s, int k) {vector<int> tar(3, -k);  // 初始化目标数组为-kfor (char c : s) tar[c - 'a']++;  // 计数数组// 如果任意字符计数小于0，则无法形成有效子串if (tar[0] < 0 || tar[1] < 0 || tar[2] < 0) return -1;// 如果所有字符恰好达到k次，返回整个字符串长度if (tar[0] == 0 && tar[1] == 0 && tar[2] == 0) return s.length();int l = 0, r = 0, res = 0;vector<int> cnt(3, 0);  // 计数当前窗口中各字符的数量while (r < s.length()) {cnt[s[r++] - 'a']++;  // 扩展窗口右边界// 当窗口中任一字符数量超过tar时，收缩窗口左边界while (cnt[0] > tar[0] || cnt[1] > tar[1] || cnt[2] > tar[2]) {cnt[s[l++] - 'a']--;}// 更新最大子串长度res = max(res, r - l);}// 返回除去最短有效子串后的剩余长度return s.length() - res;}
};

18.螺旋矩阵II

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

四个方向循环的表达式 dirIdx = (dirIdx + 1) % 4; 是一种非常高效且常用的方式来实现这种循环控制：

• dirIdx + 1：这部分是将当前的方向索引增加1，以便移动到下一个方向。
• 取模运算符 % 用来实现循环效果。因为有四个方向，所以取模4。这意味着当 dirIdx 从3增加1变为4时，4 % 4 的结果是0，从而将方向索引重置为0（即向右方向），形成一个循环。

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.empty()) return {}; // 处理空矩阵的情况int n = matrix.size();int m = matrix[0].size();vector<int> res;vector<vector<int>> direction = {{0, 1},  // 向右移动{1, 0},  // 向下移动{0, -1}, // 向左移动{-1, 0}  // 向上移动};vector<vector<bool>> seen(n, vector<bool>(m, false));int i = 0, j = 0, dirIdx = 0; // dirIdx 用来控制方向for (int k = 0; k < m * n; k++) {res.push_back(matrix[i][j]);seen[i][j] = true;int nexti = i + direction[dirIdx][0];int nextj = j + direction[dirIdx][1];// 检查是否需要转向：下一步是否出界或已访问if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && !seen[nexti][nextj]) {i = nexti;j = nextj;} else {// 调整方向dirIdx = (dirIdx + 1) % 4; // 四个方向循环i += direction[dirIdx][0];j += direction[dirIdx][1];}}return res;}
};

19.旋转图像

90度旋转

要求原地旋转，不另开数组

其实是个数学问题
先上下对称翻转，再主对角线翻转

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size() ;//首先进行上下翻转for( int i = 0 ; i < n/2 ; i ++ ){swap(matrix[ i ], matrix[ n - i - 1]) ; }//然后进行对角线翻转for( int i = 0 ; i < n ; i ++ ){for( int j = i ; j < n ;j ++ ){swap(matrix[i][j],matrix[j][i]) ;}}}
};

20.删除数组中重复的元素II

有重复的全删掉，一个也不留

需要dummy node
初始化cur指向dummy node
每次循环看下一个节点和下下节点的值是不是一样的，如果是一样的，就嵌套一个while，不一样，cur就移动

这里嵌套while的方法无敌，仔细学

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* cur = dummy;while(cur && cur->next && cur->next->next){//先把这个值存下来int num = cur->next->val;if(cur->next->next->val == num){//可能不止2个while(cur->next && cur->next->val == num){cur->next = cur->next->next;}}else cur = cur->next;}return dummy->next;}
};