这是 labuladong 的算法小抄 的刷题记录。每一节选一道代表题目,方便快速复习。
补充一个在LeetCode网页上刷题的时候的 Debug 技巧。因为非会员在 LeetCode 上没有调试功能,所以我们只能 print
打印一些关键变量的值。
但是如果遇到递归算法的时候,直接打印变量会十分混乱。 这里提供一个十分好用的方法。
首先我们需要定义一个函数 debug
和一个全局变量 _count
,然后在递归函数开始时执行debug(_count++)
在递归函数结束前执行debug(--_count)
。然后在中间我们就可以正常打印我们需要的关键变量。debug
函数如下:
// 调试
int _count = 0;
void debug(int count){
// 打印 count 个缩进
for(int i = 0; i < count; i++){
printf(" ");
}
// 这句可以不写
printf("[%d] ", count);
}
我们以一个较为复杂的题目 236. 二叉树的最近公共祖先 为例,递归版本的算法如下:
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return dfs(root, p, q);
}
private:
TreeNode* dfs(TreeNode *root, TreeNode *p, TreeNode *q){
if(root == nullptr){
return nullptr;
}
if(root == p || root == q){
return root;
}
TreeNode *left = dfs(root->left, p, q);
TreeNode *right = dfs(root->right, p, q);
if(left != nullptr && right != nullptr){
return root;
}
return left == nullptr ? right : left;
}
};
我们进行 debug 打印关键变量的信息:
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return dfs(root, p, q);
}
private:
// 调试
int _count = 0;
void debug(int count){
// 打印 count 个缩进
for(int i = 0; i < count; i++){
printf(" ");
}
// 这句可以不写
printf("[%d] ", count);
}
TreeNode* dfs(TreeNode *root, TreeNode *p, TreeNode *q){
// 函数开始时调用debug,并打印当前节点的信息
debug(_count++);
cout<<"node: ";
root == nullptr ? cout<<"nullptr"<<endl : cout<<root->val<<endl;
if(root == nullptr){
// 函数结束时调用debug,并打印返回值的信息
debug(--_count);
cout<<"retrun nullptr"<<endl;
return nullptr;
}
if(root == p || root == q){
// 函数结束时调用debug,并打印返回值的信息
debug(--_count);
cout<<"return "<<root->val<<endl;
return root;
}
TreeNode *left = dfs(root->left, p, q);
TreeNode *right = dfs(root->right, p, q);
if(left != nullptr && right != nullptr){
// 函数结束时调用debug,并打印返回值的信息
debug(--_count);
cout<<"return ";
root == nullptr ? cout<<"nullptr"<<endl : cout<<root->val<<endl;
return root;
}
// 函数结束时调用debug,并打印返回值的信息
debug(--_count);
cout<<"return ";
TreeNode *node = left == nullptr ? right : left;
node == nullptr ? cout<<"nullptr"<<endl : cout<<node->val<<endl;
return left == nullptr ? right : left;
}
};
打印结果如下:
/**
* 输入:
* [3,5,1,6,2,0,8,null,null,7,4]
* 5
* 8
*/
[0] node: 3
[1] node: 5
[1] return 5
[1] node: 1
[2] node: 0
[3] node: nullptr
[3] retrun nullptr
[3] node: nullptr
[3] retrun nullptr
[2] return nullptr
[2] node: 8
[2] return 8
[1] return 8
[0] return 3
可以看到这种方法可以很直观地看出递归的过程,我们很容易就能分析出这个算法的执行流程。
自己写的题解:合并K个升序链表:优先队列
自己写的题解:环形链表:双指针
自己写的题解:相交链表:双指针
自己写的题解:反转链表:递归 - 反转链表 II
自己写的题解:K个一组反转链表
自己写的题解:回文链表:反转链表 + 链表中间结点
难度简单
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
arr.resize(matrix.size() + 1, vector<int>(matrix[0].size()+1, 0));
for(int i = 1; i < arr.size(); i++){
for(int j = 1; j < arr[0].size(); j++){
arr[i][j] = matrix[i-1][j-1] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return arr[row2+1][col2+1] - arr[row2+1][col1] - arr[row1][col2+1] + arr[row1][col1];
}
private:
vector<vector<int>> arr;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
难度==中等==
class Difference{
private:
vector<int> diff;
public:
Difference(int n){
diff.resize(n, 0);
}
void increment(int i, int j, int val){
diff[i] += val;
if(j + 1 < diff.size()){
diff[j + 1] -= val;
}
}
vector<int> result(){
vector<int> res(diff.size(), 0);
res[0] = diff[0];
for(int i = 1; i < res.size(); i++){
res[i] = res[i-1] + diff[i];
}
return res;
}
};
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
Difference diff(1001);
for(int i = 0; i < trips.size(); i++){
int val = trips[i][0];
int start = trips[i][1];
int end = trips[i][2]-1;
diff.increment(start, end, val);
}
vector<int> res = diff.result();
for(int i = 0; i < res.size(); i++){
if(res[i] > capacity){
return false;
}
}
return true;
}
};
难度简单
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0, fast = 0;
while(fast < nums.size()){
if(/* fast指针找到满足条件的元素 */){
// 将元素放在slow指针处
slow++;
}
fast++;
}
return slow+1;
}
}
难度==中等==
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int upper = 0, lower = m - 1, left = 0, right = n - 1;
vector<int> res;
while(res.size() < m*n){
if(upper <= lower){
for(int j = left; j <= right; j++){
res.push_back(matrix[upper][j]);
}
upper++;
}
if(left <= right){
for(int i = upper; i <= lower ; i++){
res.push_back(matrix[i][right]);
}
right--;
}
if(upper <= lower){
for(int j = right; j >= left; j--){
res.push_back(matrix[lower][j]);
}
lower--;
}
if(left <= right){
for(int i = lower; i >= upper; i--){
res.push_back(matrix[i][left]);
}
left++;
}
}
return res;
}
};
难度==困难==
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for(char c : t){
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
int start = 0, len = INT_MAX;
while(right < s.size()){
char c = s[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
char d = s[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
自己写的题解:二分查找模版总结
难度==中等==
class Solution {
public:
Solution(vector<int>& w) {
presum.resize(w.size() + 1, 0);
for(int i = 1; i < presum.size(); i++){
presum[i] = presum[i - 1] + w[i - 1];
}
}
int pickIndex() {
int n = presum.size();
int target = rand() % presum[n - 1] + 1;
return left_bound(presum, target) - 1;
}
private:
vector<int> presum;
int left_bound(vector<int> &presum, int target){
int left = 0, right = presum.size() - 1;
while(left <= right){
int mid = (right - left)/2 + left;
if(presum[mid] < target){
left = mid + 1;
} else if(presum[mid] > target){
right = mid - 1;
} else {
right = mid - 1;
}
}
return left;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(w);
* int param_1 = obj->pickIndex();
*/
难度==中等==
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1, right = *max_element(piles.begin(), piles.end());
while(left <= right){
int mid = (right - left)/2 + left;
if(finishtime(piles, mid) > h){
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
private:
int finishtime(vector<int> &piles, int speed){
int sum = 0;
for(int i = 0; i < piles.size(); i++){
sum += (piles[i] + speed - 1) / speed;
}
return sum;
}
};
难度==中等==
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
for(int i = 0; i < nums2.size(); i++){
q.push(make_pair(nums2[i], i));
}
int n = nums1.size();
int left = 0, right = n - 1;
vector<int> res(n, 0);
while(!q.empty()){
int maxval = q.top().first;
int index = q.top().second;
q.pop();
if(maxval < nums1[right]){
res[index] = nums1[right];
right--;
} else {
res[index] = nums1[left];
left++;
}
}
return res;
}
private:
struct cmp{
bool operator()(pair<int, int> p1, pair<int, int> p2){
return p1.first < p2.first;
}
};
};
自己写的题解:O(1) 时间插入、删除和获取随机元素:变长数组+哈希表 + 黑名单中的随机数:哈希表 - 黑名单中的随机数 - 力扣(LeetCode)
由浅入深,单调栈思路去除重复字符 - 去除重复字母 - 力扣(LeetCode)
改进:可以直接将 res 做为单调栈,不用另开辟空间
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<bool> inStack(256, false);
vector<int> count(256, 0);
string res;
for(char c : s){
count[c]++;
}
for(char c : s){
count[c]--;
if(inStack[c]){
continue;
}
while(!res.empty() && res[res.size() - 1] > c){
if(count[res[res.size() - 1]] == 0){
break;
}
inStack[res[res.size() - 1]] = false;
res.pop_back();
}
res += c;
inStack[c] = true;
}
return res;
}
};
自己写的题解:二叉树的直径:后序遍历解决二叉树深度问题
自己写的题解:二叉树展开为链表:后序遍历
自己写的题解:填充每个节点的下一个右侧节点指针:DFS
自己写的题解:二叉树的构造问题解题方法
自己写的题解:二叉树的序列化与反序列化:DFS+BFS - 二叉树的序列化与反序列化 - 力扣(LeetCode)
自己写的题解:寻找重复的子树:后序遍历+序列化二叉树 - 寻找重复的子树 - 力扣(LeetCode)
自己写的题解:排序算法
自己写的题解:数组中的逆序对:归并排序
自己写的题解:把二叉搜索树转换为累加树:中序遍历
自己写的题解:二叉搜索树的增删改查操作
自己写的题解:不同的二叉搜索树:暴力搜索 + 优化 = 动态规划
自己写的题解:数组中的第k个最大元素:优先队列 + 快速选择算法
自己写的题解:二叉树的最近公共祖先大集合:后序遍历
自己写的题解:完全二叉树的节点个数:普通二叉树 + 满二叉树
自己写的题解:797. 所有可能的路径:图的回溯
自己写的题解:判断二分图:DFS
自己写的题解:判断图是否有环:图的回溯
自己写的题解:图的拓扑排序:判断图是否有环+图的后序遍历
自己写的题解:被围绕的区域:DFS + 并查集
自己写的题解:被围绕的区域:DFS + 并查集
自己写的题解:最小生成树:Kruskal + Prim - 连接所有点的最小费用 - 力扣(LeetCode)
自己写的题解:496. 下一个更大元素 I:单调栈
自己写的题解:LRU缓存:哈希表+双向链表
自己写的题解:滑动窗口最大值:堆(优先队列)、单调队列 - 滑动窗口最大值
自己写的题解:设计推特:哈希表+链表+优先队列
自己写的题解:零钱兑换:动态规划
自己写的题解:最长递增子序列:动态规划+二分查找
自己写的题解:下降路径最小和:动态规划 - 下降路径最小和 - 力扣(LeetCode)
自己写的题解:编辑距离:动态规划
问题描述: 给你一个可装载重量为 W
的背包和 N
个物品,每个物品有重量和价值两个属性。其中第 i
个物品的重量为 wt[i]
,价值为 val[i]
,现在让你用这个背包装物品,最多能装的价值是多少?
int knapsack(int w, int n, vector<int> &wt, vector<int> &val) {
vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
// for(int i = 0; i < dp.size(); i++){
// dp[i][0] = 0;
// }
for(int i = 1; i < dp.size(); i++){
for(int j = 1; j < dp[0].size(); j++){
if(j - wt[i-1][0] < 0){
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i-1][0]] + val[i-1][1]);
}
}
}
return dp[n][w];
}
自己写的题解:分割等和的子集:0-1 背包问题
自己写的题解:最小路径和:从记忆化递归到动态规划
自己写的题解:地下城游戏:DFS+后序遍历+动态规划思想
自己写的题解:正则表达式匹配:递归 + 记忆化 = 动态规划
自己写的题解:打家劫舍:经典动态规划问题
自己写的题解:状态机解决所有股票问题!!! - 买卖股票的最佳时机 - 力扣(LeetCode)
自己写的题解:实现 strStr():KMP 算法
自己写的题解:无重叠区间:贪心算法
自己写的题解:N皇后:回溯
自己写的题解:回溯问题大合集:子集、组合、排列
自己写的题解:集合划分问题:回溯 - 划分为k个相等的子集
自己写的题解:最短路径:广度优先搜索 - 打开转盘锁
自己写的题解:为运算符表达式设计优先级:分治算法 - 为运算表达式设计优先级
自己写的题解:接雨水:动态规划+双指针+单调栈
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。