代码随想录
参考资料
- 代码随想录 - 系统刷题, 总结的很棒 - 5
数组
力扣 no.704
二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right){
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
};
- 前提为有序无重复
- 区间的定义 (循环不变量) 为两种, 左闭右闭或左闭右开
- 左闭右闭, while 使用 <=, if (nums [middle]>target) right 赋值为 middle-1
- 左闭右开, while 使用 <, if (nums [middle]>target) right 赋值为 middle
力扣 no.27
移除元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
- 双指针法
- 快指针寻找新数组的元素, 慢指针指向更新新数组下标的位置
- 首尾指针, 从数组两端向中间移动可以将 \(n+k\) 优化到 \(n\)
力扣 no.977
有序数组的平方
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要 i <= j, 因为最后要处理两个元素
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
};
- 双指针法, 一开始我以为要合并相等项呢 (其实也差不多)
力扣 no.209
长度最小的子数组
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用 while, 每次更新 i(起始位置), 并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处, 不断变更 i(子序列的起始位置)
}
}
// 如果 result 没有被赋值的话, 就返回 0, 说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
- 滑动窗口法
力扣 no.59
螺旋矩阵 II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int t = 0; // top
int b = n-1; // bottom
int l = 0; // left
int r = n-1; // right
vector<vector<int>> ans(n,vector<int>(n));
int k=1;
while(k<=n*n){
for(int i=l;i<=r;++i,++k) ans[t][i] = k;
++t;
for(int i=t;i<=b;++i,++k) ans[i][r] = k;
--r;
for(int i=r;i>=l;--i,++k) ans[b][i] = k;
--b;
for(int i=b;i>=t;--i,++k) ans[i][l] = k;
++l;
}
return ans;
}
};
- 模拟, 坚持循环不变量原则, 左闭右开
卡码网 no.58
区间和
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, a, b;
cin >> n;
vector<int> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i];
while (cin >> a >> b) {
int sum = 0;
// 累加区间 a 到 b 的和
for (int i = a; i <= b; i++) sum += vec[i];
cout << sum << endl;
}
}
- 前缀和
卡码网 no.44
开发商购买土地\ n*m 个区块拥有权值, 所有区块分配给 A 和 B\ 只允许将区域按横向或纵向划分成两个子区域, 求 A 和 B 的最小权值之差\
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main () {
int n, m;
cin >> n >> m;
int sum = 0;
vector<vector<int>> vec(n, vector<int>(m, 0)) ;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> vec[i][j];
sum += vec[i][j];
}
}
int result = INT_MAX;
int count = 0; // 统计遍历过的行
for (int i = 0; i < n; i++) {
for (int j = 0 ; j < m; j++) {
count += vec[i][j];
// 遍历到行末尾时候开始统计
if (j == m - 1) result = min (result, abs(sum - count - count));
}
}
count = 0; // 统计遍历过的列
for (int j = 0; j < m; j++) {
for (int i = 0 ; i < n; i++) {
count += vec[i][j];
// 遍历到列末尾的时候开始统计
if (i == n - 1) result = min (result, abs(sum - count - count));
}
}
cout << result << endl;
}
- 求前缀和的过程中可解
链表
力扣 no.203
移除链表元素
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是 if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next!= NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
- 虚拟头节点/递归/朴素, 解法很多
力扣 no.707
设计链表
//get(index)：获取链表中第 index 个节点的值 如果索引无效, 则返回-1
//addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点 插入后, 新节点将成为链表的第一个节点
//addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素
//addAtIndex(index, val)：在链表中的第 index 个节点之前添加值为 val 的节点 如果 index 等于链表的长度, 则该节点将附加到链表的末尾 如果 index 大于链表长度, 则不会插入节点 如果 index 小于 0, 则在头部插入节点
//deleteAtIndex(index)：如果索引 index 有效, 则删除链表中的第 index 个节点
- 略
力扣 no.206
翻转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
- 迭代/递归
力扣 no.24
两两交换链表中的节点
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* temp = dummyHead;
while (temp->next != nullptr && temp->next->next != nullptr) {
ListNode* node1 = temp->next;
ListNode* node2 = temp->next->next;
temp->next = node2;
node1->next = node2->next;
node2->next = node1;
temp = node1;
}
ListNode* ans = dummyHead->next;
delete dummyHead;
return ans;
}
};
- easy
力扣 no.19
删除链表的倒数第 N 个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
head=new ListNode(0, head);
ListNode *s(head), *q(head);
for(;n>-1;n--) q=q->next;
while(q){
q=q->next;
s=s->next;
}
s->next=s->next->next;
return head->next;
}
};
- 双指针加哑节点
力扣 no.160
判断两个链表相交点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
// 双指针正解真的巧妙, 指针走完后交换到另一个链表的头节点
// 把三段距离设为 abc, 一个走完是 a+c, 另一个 b+c, 交换链表, 走同样距离刚好是 a+b+c, 刚好在交点处
- 用哈希 / 对齐太简单, 不说了
力扣 no.142
环形链表 II
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
- 快慢指针
- s 到达环入口时 (f - 环入口) 一定等于 s 与 f 相遇时 (环入口 - s) 设为距离 c
- 链表头到环入口距离一定为整数倍的环长 + c
哈希表
力扣 no.242
给定两个字符串 s 和 t, 编写一个函数来判断 t 是否是 s 的字母异位词
class Solution {
public:
bool isAnagram(string s, string t) {
int m[26]={0}, l(0);
if(s.size()==t.size()) l=s.size();
else return 0;
for(int i(0);i<l;i++){
m[s[i]-'a']++;m[t[i]-'a']--;
}
for(int i(0);i<26;i++){
if(m[i]) return 0;
}
return 1;
}
};
- easy
力扣 no.349
给定两个数组 nums1 和 nums2, 返回它们的交集
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s(nums1.begin(), nums1.end());
unordered_set<int> res;
for(int i(0);i<nums2.size();i++){
if(s.find(nums2[i])!=s.end()) res.insert(nums2[i]);
}
return vector<int>(res.begin(), res.end());
}
};
- unordered_set 秒杀
力扣 no.202
快乐数
class Solution {
int happy(int n){
int sum;
for(sum=0;n>0;n/=10) sum+=(n%10)*(n%10);
return sum;
}
public:
bool isHappy(int n) {
map<int, bool> m;
while(n!=1){
n=happy(n);
if(m[n]) return 0;
m[n]=1;
}
return 1;
}
};
- 直接哈希非常简单
- 快慢指针判断环更好!!!
- 正解: 数学角度, 这道题其实只能存在一个环, 硬编码那个环, 然后只要到达环中某一个数字就返回 0
力扣 no.1
两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int, int> map;
for(int i = 0; i < nums.size(); i++) {
// 遍历当前元素，并在 map 中寻找是否有匹配的 key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到 map 中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
- 无需多言
力扣 no.454
四数相加 II
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:a+b 的数值，value:a+b 数值出现的次数
// 遍历大 A 和大 B 数组，统计两个数组元素之和，和出现的次数，放到 map 中
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 统计 a+b+c+d = 0 出现的次数
// 再遍历大 C 和大 D 数组，找到如果 0-(c+d) 在 map 中出现过的话，就把 map 中 key 对应的 value 也就是出现次数统计出来。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
- \(O(n^2)\) 记录 \(a+b\) 的和, 然后 \(O(n^2)\) 遍历 \(c+d\) 看是否有相反数
力扣 no.383
赎金信
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
int[] cnt = new int[26];
for (char c : magazine.toCharArray()) {
cnt[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a']--;
if(cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
}
- 简单
力扣 no.15
三数之和
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出 a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 错误去重 a 方法，将会漏掉-1, -1, 2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
*/
// 正确去重 a 方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0, 0, 0 这种三元组
/*
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
*/
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后，对 b 和 c 去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
- 排序加双指针
- 这题的去重比较复杂, 要注意
力扣 no.18
四数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 0) {
// 一级剪枝
break;
}
// 对 nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 2 级剪枝处理
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对 nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对 nums[left]和 nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
- 类似三数之和, 只是多了一层循环, 注意复杂的去重
字符串
力扣 no.344
反转字符串
class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
for (int left = 0, right = n - 1; left < right; ++left, --right) {
swap(s[left], s[right]);
}
}
};
- easy
力扣 no.541
反转字符串 II
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.length();
for (int i = 0; i < n; i += 2 * k) {
reverse(s.begin() + i, s.begin() + min(i + k, n));
}
return s;
}
};
- easy
卡码网 no.54
替换数字
#include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
int sOldIndex = s.size() - 1;
int count = 0; // 统计数字的个数
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
count++;
}
}
// 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
s.resize(s.size() + count * 5);
int sNewIndex = s.size() - 1;
// 从后往前将数字替换为"number"
while (sOldIndex >= 0) {
if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
s[sNewIndex--] = 'r';
s[sNewIndex--] = 'e';
s[sNewIndex--] = 'b';
s[sNewIndex--] = 'm';
s[sNewIndex--] = 'u';
s[sNewIndex--] = 'n';
} else {
s[sNewIndex--] = s[sOldIndex];
}
sOldIndex--;
}
cout << s << endl;
}
}
- easy
力扣 no.151
反转字符串中的单词
class Solution {
public:
string reverseWords(string s) {
string ans;
int i(s.size()-1);
for(;i>=0;i--) if(s[i]!=' ') break; // 找到第一个非空格字符
for(;i>=0;i--){
if(s[i]==' '&&s[i+1]!=' '){ // 找到一个单词的结束位置
for(int k=i+1;k<s.size()&&s[k]!=' ';k++) ans+=s[k]; // 反转单词
ans+=' '; // 单词之间添加空格
}
}
if(s[0]!=' ') // 处理第一个单词
for(int k=0;k<s.size()&&s[k]!=' ';k++) ans+=s[k];
else ans.erase(ans.size()-1); // 第一个单词后面没有空格, 所以需要删除最后一个空格
return ans;
}
};
- 这是刚学的时候写的代码, 实际上有\(O(1)\)空间的解法
class Solution {
public:
void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
for (int i = start, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
int slow = 0; //整体思想参考https://programmercarl.com/0027.移除元素.html
for (int i = 0; i < s.size(); ++i) { //
if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0 说明不是第一个单词，需要在单词前添加空格。
while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
s[slow++] = s[i++];
}
}
}
s.resize(slow); //slow的大小即为去除多余空格后的大小。
}
string reverseWords(string s) {
removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
reverse(s, 0, s.size() - 1);
int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是 0。
for (int i = 0; i <= s.size(); ++i) {
if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
start = i + 1; //更新下一个单词的开始下标start
}
}
return s;
}
};
- 先反转整个字符串, 然后再反转每个单词
卡码网 no.55
右旋字符串
#include <iostream>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
reverse(s.begin(), s.begin() + s.size() - n);
reverse(s.begin() + s.size() - n, s.end());
reverse(s.begin(), s.end());
cout << s << endl;
}
- 显然跟右旋数组一样
力扣 no.28
实现 strStr()
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
vector<int> pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
};
- KMP 板子
### 力扣 no.459
重复的子字符串
```C++
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};
- 想法易于理解, 证明困难
- 使用语言的子串查找函数 (部分是 BM 算法)
// 模式串自前向后匹配, 匹配时自后向前, 因此匹配失败时, 会同时出现坏字符和好后缀
// 坏字符规则的实现
// 维护字符到模式串中最后一次出现的位置的映射
int BadChar(int j, char temp, string str) {
int index = -1;
for (int i = j - 1; i >= 0; --i) {
if (str[i] == temp) {
index = i;
break;
}
}
return j - index;
}
// 好后缀规则的实现
// 维护好后缀到模式串中最后一次出现的位置的映射, 有点像 KMP 算法的 next 数组
int GoodSuffix(int j, string& pat) {
int terminal = pat.length() - 1;
int index = -1;
j--;
while (j >= 0) {
if (pat[j] == pat[terminal]) {
index = j;
break;
} else j--;
}
return terminal - index;
}
// Boyer-Moore搜索算法的主体
// 每次匹配失败时, 坏字符和好后缀的移动距离取较大的那个
int BM(string source, string target) {
int i = 0, j = 0, soulen = source.length(), tarlen = target.length();
int badvalue = 0, distance = 0;
if (soulen < tarlen) {
printf("字符串的长度小于搜索词的长度\n");
return -1;
}
i = tarlen - 1; j = tarlen - 1;
while (i < soulen) {
if (source[i] == target[j]) {
if (j == 0) {
printf("匹配成功\n");
return i;
}
i--; j--;
} else {
if (j == tarlen - 1) {
badvalue = BadChar(j, source[i], target);
cout << "坏字符移动：" << badvalue << endl;
i = i + tarlen - 1 - j + badvalue;
j = tarlen - 1;
} else {
badvalue = BadChar(j, source[i], target);
if (badvalue == -1) badvalue = target.length();
distance = badvalue > GoodSuffix(j, target) ? badvalue : GoodSuffix(j, target);
cout << "好后缀为：" << GoodSuffix(j, target) << " 坏字符为：" << badvalue << " 比较之后移动" << distance << endl;
i = i + tarlen - 1 - j + distance;
j = tarlen - 1;
}
}
}
return -1;
}
- 优化的 BM 算法的平均时间复杂度普遍优于 KMP 算法
- 这题可以使用 KMP 算法, 原因是
next[n-1] == n-1-i与题目等效, 即 next 指示的最后一个字符的回退长度为 i
栈与队列
力扣 no.232
用栈实现队列
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
/** Get the front element. */
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stIn.empty() && stOut.empty();
}
};
- 两个栈来回倒数据
力扣no.225
用队列实现栈
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
int top(){
int size = que.size();
size--;
while (size--){
// 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时获得的元素就是栈顶的元素了
que.push(que.front()); // 将获取完的元素也重新添加到队列尾部，保证数据结构没有变化
que.pop();
return result;
}
bool empty() {
return que.empty();
}
};
- 每次 pop 操作都需要将队列头部的元素 (除了最后一个元素外) 重新添加到队列尾部
力扣 no.20
有效的括号
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};
- easy
力扣 no.1047
删除字符串中的所有相邻重复项
class Solution {
public:
string removeDuplicates(string S) {
string result;
for(char s : S) {
if(result.empty() || result.back() != s) {
result.push_back(s);
}
else {
result.pop_back();
}
}
return result;
}
};
- easy
力扣 no.150
逆波兰表达式求值
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
if (tokens[i] == "-") st.push(num2 - num1);
if (tokens[i] == "*") st.push(num2 * num1);
if (tokens[i] == "/") st.push(num2 / num1);
} else {
st.push(stoll(tokens[i]));
}
}
long long result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
};
- easy
力扣 no.239
滑动窗口最大值
class Solution {
private:
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};
- 单调队列板子
- 很容易想到新值进入的逻辑, 对于当前最大值出队列只需要知道队列此时接下来的最大值, 因此只保留单调递减的元素即可
- 不需要考虑元素的位次只需要维护队列的最大大小即可
力扣 no.347
前 K 个高频元素
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 要统计元素出现频率
unordered_map<int, int> map; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
// 桶排序
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
int max_count = 0;
for (const int & num : nums) {
max_count = max(max_count, ++counts[num]);
}
vector<vector<int>> buckets(max_count + 1);
for (const auto & p : counts) {
buckets[p.second].push_back(p.first);
}
vector<int> ans;
for (int i = max_count; i >= 0 && ans.size() < k; --i) {
for (const int & num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k) {
break;
}
}
}
return ans;
}
};
- 堆板子
- 桶排序!!!
二叉树
二叉树遍历
- 前序遍历, 中序遍历, 后序遍历, 层序遍历
- 递归遍历, 迭代遍历
- 略
力扣 no.654
最大二叉树
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
int n = nums.size();
vector<int> stk;
vector<TreeNode*> tree(n);
for (int i = 0; i < n; ++i) {
tree[i] = new TreeNode(nums[i]);
while (!stk.empty() && nums[i] > nums[stk.back()]) {
tree[i]->left = tree[stk.back()];
stk.pop_back();
}
if (!stk.empty()) {
tree[stk.back()]->right = tree[i];
}
stk.push_back(i);
}
return tree[stk[0]];
}
};
- 在构建单调栈时, 如果不单调往外出顺手挂上左, 依然单调就挂右
力扣 no.226
翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right); // 右
if(node->left) st.push(node->left); // 左
}
return root;
}
};
- 遍历时交换左右子树即可
力扣 no.101
对称二叉树
class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
else return compare(left->left, right->right) && compare(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
- 可以迭代
- 本质就是通过相反的遍历顺序, 来 "翻转" 左子树与右子树, 然后比较是否相等
力扣 no.104
二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return 1 + max(leftDepth, rightDepth);
}
};
- 递归遍历, 取左右子树的最大深度 + 1 即可
力扣 no.111
二叉树的最小深度
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
if (root->left == NULL && root->right != NULL) return 1 + rightDepth;
else if (root->left != NULL && root->right == NULL) return 1 + leftDepth;
else return 1 + min(leftDepth, rightDepth);
}
};
- 递归遍历, 取左右子树的最小深度 + 1 即可
- 注意, 当左子树或右子树为空时, 最小深度为右子树或左子树的深度 + 1
力扣 no.222
完全二叉树的节点个数
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftDepth++;
}
while (right) { // 求右子树深度
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
- 利用完全二叉树特性, 将树分为若干满二叉树与其他节点
- 力扣官方题解为二分
力扣 no.110
平衡二叉树
class Solution {
public:
// 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
int getHeight(TreeNode* node) {
if (node == NULL) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) return -1;
int rightHeight = getHeight(node->right);
if (rightHeight == -1) return -1;
return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
- 用
-1表示已经不是平衡二叉树
力扣 no.257
二叉树的所有路径
class Solution {
private:
void traversal(TreeNode* cur, string path, vector<string>& result) {
path += to_string(cur->val); // 中
if (cur->left == NULL && cur->right == NULL) {
result.push_back(path);
return;
}
if (cur->left) traversal(cur->left, path + "->", result); // 左
if (cur->right) traversal(cur->right, path + "->", result); // 右
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
string path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}
};
- easy
力扣 no.404
左叶子之和
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
int leftValue = sumOfLeftLeaves(root->left); // 左
int rightValue = sumOfLeftLeaves(root->right); // 右
int midValue = 0;
if (root->left && !root->left->left && !root->left->right) {
midValue = root->left->val;
}
int sum = midValue + leftValue + rightValue;
return sum;
}
};
- easy
力扣 no.513
找树左下角的值
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int result = 0;
if (root == NULL) return result;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (i == 0) result = node->val; // 记录最后一行第一个元素
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
- 层序遍历秒杀
力扣 no.112
路径总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == NULL) return false;
if (root->left == NULL && root->right == NULL) return targetSum == root->val;
return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}
};
- easy
力扣 no.113
路径总和 II
class solution {
private:
vector<vector<int>> result;
vector<int> path;
// 递归函数不需要返回值，因为我们要遍历整个树
void traversal(TreeNode* cur, int count) {
if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点且找到了和为sum的路径
result.push_back(path);
return;
}
if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边，直接返回
if (cur->left) { // 左 （空节点不遍历）
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
return ;
}
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
result.clear();
path.clear();
if (root == NULL) return result;
path.push_back(root->val); // 把根节点放进路径
traversal(root, sum - root->val);
return result;
}
};
力扣 no.106
从中序与后序遍历序列构造二叉树
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return NULL;
// 后序遍历数组最后一个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (postorder.size() == 1) return root;
// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};
- 以后序数组的最后一个元素为切割点, 先切中序数组, 根据中序数组, 反过来再切后序数组
力扣 no.105
从前序与中序遍历序列构造二叉树
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
if (preorderBegin == preorderEnd) return NULL;
int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
TreeNode* root = new TreeNode(rootValue);
if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割前序数组
// 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
int leftPreorderBegin = preorderBegin + 1;
int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
// 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
int rightPreorderEnd = preorderEnd;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (inorder.size() == 0 || preorder.size() == 0) return NULL;
// 参数坚持左闭右开的原则
return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
}
};
- 以前序数组的第一个元素为切割点, 先切中序数组, 根据中序数组, 反过来再切前序数组
力扣 no.654
最大二叉树
class Solution {
private:
// 在左闭右开区间[left, right)，构造二叉树
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left >= right) return nullptr;
// 分割点下标：maxValueIndex
int maxValueIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
}
TreeNode* root = new TreeNode(nums[maxValueIndex]);
// 左闭右开：[left, maxValueIndex)
root->left = traversal(nums, left, maxValueIndex);
// 左闭右开：[maxValueIndex + 1, right)
root->right = traversal(nums, maxValueIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
- easy
力扣 no.617
合并二叉树
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2;
if (t2 == NULL) return t1;
queue<TreeNode*> que;
que.push(t1);
que.push(t2);
while(!que.empty()) {
TreeNode* node1 = que.front(); que.pop();
TreeNode* node2 = que.front(); que.pop();
// 此时两个节点一定不为空，val相加
node1->val += node2->val;
// 如果两棵树左节点都不为空，加入队列
if (node1->left != NULL && node2->left != NULL) {
que.push(node1->left);
que.push(node2->left);
}
// 如果两棵树右节点都不为空，加入队列
if (node1->right != NULL && node2->right != NULL) {
que.push(node1->right);
que.push(node2->right);
}
// 当t1的左节点 为空 t2左节点不为空，就赋值过去
if (node1->left == NULL && node2->left != NULL) {
node1->left = node2->left;
}
// 当t1的右节点 为空 t2右节点不为空，就赋值过去
if (node1->right == NULL && node2->right != NULL) {
node1->right = node2->right;
}
}
return t1;
}
};
- 其实用指针迭代遍历就行
力扣 no.700
二叉搜索树中的搜索
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
}
};
- easy
力扣 no.98
验证二叉搜索树
class Solution {
public:
TreeNode* pre = NULL; // 用来记录前一个节点
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
bool left = isValidBST(root->left);
if (pre != NULL && pre->val >= root->val) return false;
pre = root; // 记录前一个节点
bool right = isValidBST(root->right);
return left && right;
}
};
- 就是中序遍历有序性
力扣 no.530
二叉搜索树的最小绝对差
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = NULL;
int result = INT_MAX;
while (cur != NULL || !st.empty()) {
if (cur != NULL) { // 指针来访问节点，访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top();
st.pop();
if (pre != NULL) { // 中
result = min(result, cur->val - pre->val);
}
pre = cur;
cur = cur->right; // 右
}
}
return result;
}
};
- 同上
力扣 no.501
二叉搜索树中的众数
- 同上
力扣 no.236
二叉树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == q || root == p || root == NULL) return root; // 遇到空返回
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != NULL && right != NULL) return root; // 左右都不为空，说明根节点就是最近公共祖先
else if (left == NULL && right != NULL) return right; // 左空右有，返回右
else if (left != NULL && right == NULL) return left; // 左有右空，返回左
else { // (left == NULL && right == NULL)
return NULL;
}
}
};
- 后序遍历
- 左右各有一个节点，说明根节点就是最近公共祖先
力扣 no.235
二叉搜索树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
int l = min(p->val, q->val),r = max(p->val, q->val);
while(root){
if (root->val > r) root = root -> left;
else if (root->val < l) root = root -> right;
else return root;
}
return root;
}
};
- easy
力扣 no.701
二叉搜索树中的插入操作
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
TreeNode* pos = root;
while (pos != nullptr) {
if (val < pos->val) {
if (pos->left == nullptr) {
pos->left = new TreeNode(val);
break;
} else {
pos = pos->left;
}
} else {
if (pos->right == nullptr) {
pos->right = new TreeNode(val);
break;
} else {
pos = pos->right;
}
}
}
return root;
}
};
- 找不到就插
力扣 no.450
删除二叉搜索树中的节点
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val > key) {
root->left = deleteNode(root->left, key);
return root;
}
if (root->val < key) {
root->right = deleteNode(root->right, key);
return root;
}
if (root->val == key) {
if (!root->left && !root->right) {
return nullptr;
}
if (!root->right) {
return root->left;
}
if (!root->left) {
return root->right;
}
TreeNode *successor = root->right;
while (successor->left) {
successor = successor->left;
}
root->right = deleteNode(root->right, successor->val);
successor->right = root->right;
successor->left = root->left;
return successor;
}
return root;
}
};
- 先找到目标节点, 然后看左右子树, 如果都有, 把后继给填上就可以
力扣 no.669
修剪二叉搜索树
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
return nullptr;
}
if (root->val < low) {
return trimBST(root->right, low, high);
} else if (root->val > high) {
return trimBST(root->left, low, high);
} else {
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
}
};
- 对于每个节点只需要管自己在不在就行
力扣 no.108
将有序数组转换为二叉搜索树
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
// 选择任意一个中间位置数字作为根节点
int mid = (left + right + rand() % 2) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, left, mid - 1);
root->right = helper(nums, mid + 1, right);
return root;
}
};
- 每次取中间点, 递归构建左右子树
力扣 no.538
把二叉搜索树转换为累加树
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (!root) return 0;
convertBST(root->right);
sum+=root ->val;
root ->val =sum;
convertBST(root->left);
return root;
}
};
- 从右到左中序遍历, 累加即可
单调栈
力扣 no.739
每日温度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
- 单调栈板子
力扣 no.496
下一个更大元素 I
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> hashmap;
stack<int> st;
for (int i = nums2.size() - 1; i >= 0; --i) {
int num = nums2[i];
while (!st.empty() && num >= st.top()) {
st.pop();
}
hashmap[num] = st.empty() ? -1 : st.top();
st.push(num);
}
vector<int> res(nums1.size());
for (int i = 0; i < nums1.size(); ++i) {
res[i] = hashmap[nums1[i]];
}
return res;
}
};
- 单调栈 + 哈希表
力扣 no.503
下一个更大元素 II
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ret(n, -1);
stack<int> stk;
for (int i = 0; i < n * 2 - 1; i++) {
while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
ret[stk.top()] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ret;
}
};
- 单调栈 + 循环数组
力扣 no.42
接雨水
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
};
- 求两侧最高 -> DP
- 单调栈出栈时, 计算面积
- 双指针, 能升高时尽量高, 降低时, 计算面积
力扣 no.84
柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n, n);
stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
right[mono_stack.top()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
- 通过单调栈, 求每个柱子的左侧和右侧第一个比它低的柱子的下标
- 计算面积
贪心
力扣 no.455
分发饼干
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int m = g.size(), n = s.size();
int count = 0;
for (int i = 0, j = 0; i < m && j < n; i++, j++) {
while (j < n && g[i] > s[j]) {
j++;
}
if (j < n) {
count++;
}
}
return count;
}
};
- easy
力扣 no.376
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int prevdiff = nums[1] - nums[0];
int ret = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
}
};
- 贪心
### 力扣 no.53
最大子数组和
```C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
- 贪心 + DP
力扣 no.122
买卖股票的最佳时机 II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int n = prices.size();
for (int i = 1; i < n; ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};
- easy
力扣 no.55
跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
};
- 贪心
力扣 no.45
跳跃游戏 II
class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0, n = nums.size(), end = 0, step = 0;
for (int i = 0; i < n - 1; ++i) {
if (maxPos >= i) {
maxPos = max(maxPos, i + nums[i]);
if (i == end) {
end = maxPos;
++step;
}
}
}
return step;
}
};
- 贪心
力扣 no.1005
K 次取反后最大化的数组和
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int i = 0;
while (i < n && k > 0) {
if (nums[i] < 0) {
nums[i] = -nums[i];
k--;
i++;
} else {
break;
}
}
if (k > 0 && k % 2 == 1) {
sort(nums.begin(), nums.end());
nums[0] = -nums[0];
}
int ans = 0;
for (int num : nums) {
ans += num;
}
return ans;
}
};
- 排序 + 贪心
力扣 no.134
加油站
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int i = 0;
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if (sumOfCost > sumOfGas) {
break;
}
cnt++;
}
if (cnt == n) {
return i;
} else {
i = i + cnt + 1;
}
}
return -1;
}
};
- 贪心
力扣 no.135
分发糖果
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int ret = 1; //用于记录答案
//pre用于记录前一个同学分得的糖果数量
int inc = 1, dec = 0, pre = 1;
for (int i = 1; i < n; i++) {
if(ratings[i] >= ratings[i-1]){
//处于递增序列中
dec = 0; //递减序列长度在递增序列中始终为0
pre = ratings[i] == ratings[i- 1] ? 1 : pre+1; //当前同学和上一个同学分数相等时，直接分配1个就行，这样满足最小
ret += pre;
inc = pre; //inc用于记录上一个递增序列的长度
}else {
//处于递减序列中
dec++;
if(dec == inc){
//当递减序列长度和递增序列长度相等时，把递增序列的最后一个同学分配到递减序列中
dec++;
}
ret += dec; //这里加的dec相当于把递减序列翻转后加的每个同学的糖果数量
pre = 1; //pre在递减序列中没有意义，因为我肯定比前一个同学少；
}
}
return ret;
}
}
- 贪心
力扣 no.860
柠檬水找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) {
five++;
} else if (bill == 10) {
if (five == 0) {
return false;
}
five--;
ten++;
} else {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};
- 贪心
力扣 no.406
根据身高重建队列
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
});
int n = people.size();
vector<vector<int>> ans(n);
for (const vector<int>& person: people) {
int spaces = person[1] + 1;
for (int i = 0; i < n; ++i) {
if (ans[i].empty()) {
--spaces;
if (!spaces) {
ans[i] = person;
break;
}
}
}
}
return ans;
}
};
- 一眼正解, 在想数据结构快速确定前空位数量
- 结果答案 \(O(n^2)\)
力扣 no.452
用最少数量的箭引爆气球
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
return u[1] < v[1];
});
int pos = points[0][1];
int ans = 1;
for (const vector<int>& balloon: points) {
if (balloon[0] > pos) {
pos = balloon[1];
++ans;
}
}
return ans;
}
};
- 排序 + 贪心