代码随想录
参考资料
- 代码随想录 - 系统刷题, 总结的很棒 - 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) {
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用 vector 定义一个二维数组
int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
int loop = n / 2; // 每个圈循环几次, 例如 n 为奇数 3, 那么 loop = 1 只是循环一圈, 矩阵中间的值需要单独处理
int mid = n / 2; // 矩阵中间的位置, 例如 :n 为 3, 中间的位置就是(1, 1), n 为 5, 中间位置为(2, 2)
int count = 1; // 用来给矩阵中每一个空格赋值
int offset = 1; // 需要控制每一条边遍历的长度, 每次循环右边界收缩一位
int i, j;
while (loop --) {
i = startx;
j = starty;
// 下面开始的四个 for 就是模拟转了一圈
// 模拟填充上行从左到右(左闭右开)
for (j; j < n - offset; j++) {
res[i][j] = count++;
}
// 模拟填充右列从上到下(左闭右开)
for (i; i < n - offset; i++) {
res[i][j] = count++;
}
// 模拟填充下行从右到左(左闭右开)
for (; j > starty; j--) {
res[i][j] = count++;
}
// 模拟填充左列从下到上(左闭右开)
for (; i > startx; i--) {
res[i][j] = count++;
}
// 第二圈开始的时候, 起始位置要各自加 1, 例如 :第一圈起始位置是(0, 0), 第二圈起始位置是(1, 1)
startx++;
starty++;
// offset 控制每一圈里每一条边遍历的长度
offset += 1;
}
// 如果 n 为奇数的话, 需要单独给矩阵最中间的位置赋值
if (n % 2) {
res[mid][mid] = count;
}
return res;
}
};
- 模拟, 坚持循环不变量原则, 左闭右开
卡码网 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;
}
};
- 堆板子
二叉树
二叉树遍历
- 前序遍历, 中序遍历, 后序遍历, 层序遍历
- 递归遍历, 迭代遍历
- 略
力扣 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