目标:一天一道,同时用go和c++实现
- go题解:halfrost/LeetCode-Go: ✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解 (github.com)
- youngyangyang04/leetcode-master: 《代码随想录》LeetCode 刷题攻略:200道经典题目刷题顺序,共60w字的详细图解,视频难点剖析,50余张思维导图,支持C++,Java,Python,Go,JavaScript等多语言版本,从此算法学习不再迷茫!🔥🔥 来看看,你会发现相见恨晚!🚀 (github.com)
- 此外学习 ACwing的内容,参考ACwing,同时用 go 和 c++完成,并且兼顾库中的内容。
- Notes中主要记录的内容是在刷题过程中可能经常会遇到的 go 和 c++的库相关的内容,这部分内容可能已经在相关的笔记里面记过了,但是这里也单独拿出来再记一遍。
-
数组过于简单,但你该了解这些! (2022年10月30日)
-
数组:二分查找(2022年10月30日)
二分查找最重要的就是思考清楚是“左闭右开还是左闭右闭,这取决于有变量是否有意义,有意义这应该是左闭右闭,此时r应该始终有意义,且改变r时不能再+1二分查找全部统一到 acwing 的模版上来!。
-
704 二分查找(2022年10月30日,2023年07月06日)
-
35.搜索插入位置(2022年10月31日,2023年07月08日)
要搞清楚到底i是取上还是取下,比如左闭右闭,就要取上,左闭右开,就要取下
-
34.在排序数组中查找元素的第一个和最后一个位置(2022年11月01日,2023年07月06日)
-
69.x 的平方根(2022年11月02日)
-
367.有效的完全平方数(2022年11月03日)使用c++时注意防止溢出
-
-
-
27. 移除元素【快慢指针】(2022年11月04日)
-
26.删除排序数组中的重复项(2022年11月05日)
c++的stl unique就是干这个的
class Solution { public: int removeDuplicates(vector<int>& nums) { auto iter = unique(nums.begin(), nums.end()); return iter - nums.begin(); } };
非常的快,但是还是双指针更通用。
-
283.移动零(2022年11月06日)
-
844.比较含退格的字符串(2022年11月07日,2023年04月22日)📌
用栈非常简单,但是考虑下不用栈原地的方法
正着走感觉比较困难,因为你很难判断要走多少才能确保没有#,如果找到头那时间复杂度就成了$O(n^2)$,比较极端的情况例如前半段都是字符,后半段全是#就很惨。所以从后往前会好一些,因为这样是先看到删除再看到字符。这个用双指针比较困难,考虑的细节很多,需要再巩固。
这个简单题并不简单,需要谨慎的去思考退格的情况,特别要注意,退格是不能删除退格的。
"bxj##tw" "bxo#j##tw" "bbbextm" "bbb#extm" "bxj##tw" "bxj###tw"
-
977.有序数组的平方(2022年11月08日)
-
-
数组:序数组的平方 (2022年11月08日)
-
数组:长度最小的子数组滑动窗口问题(2022年11月9日)
-
数组:螺旋矩阵II(2022年11月14日,:pushpin:)
-
54.螺旋矩阵(2022年11月15日,:pushpin:)
-
剑指Offer 29.顺时针打印矩阵(2022年11月16日)
-
- 关于链表,你该了解这些!
- 链表:移除链表元素(2022年11月17日)
- 链表:设计链表(2022年11月18日)
双指针法:
-
链表:翻转链表 (2022年11月19日)
-
链表:两两交换链表中的节点(2022年11月20日)
-
链表:删除链表的倒数第 N 个结点(2022年11月21日)
-
链表:链表相交(2022年11月22日)
-
141. 环形链表(2022年11月23日,:pushpin:,2023年07月11日)
-
链表:环形链表(2022年11月24日,:pushpin:)
从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。这个代码不难,但是**很有意思,应该要记住。
- 关于哈希表,你该了解这些!
- 哈希表:有效的字母异位词(2022年11月25日)
- 哈希表:查找常用字符(2022年11月26日)
- 哈希表:两个数组的交集(2022年11月28日)
- 哈希表:快乐数(2022年11月29日)
- 哈希表:两数之和(2022年12月05日)
- 哈希表:四数相加II(2022年12月06日,:pushpin:,2023年07月13日)
- 哈希表:赎金信(2022年12月07日)
- 哈希表:三数之和(2022年12月16日,:pushpin:,2023年07月09日)
- 双指针法:四数之和
- 哈希表:总结篇!
- 字符串:反转字符串(2022年12月27日)
- 字符串:反转字符串II(2023年02月15日)
- 字符串:替换空格(2023年02月16日)
- 字符串:翻转字符串里的单词(2023年02月17日)
- 字符串:左旋转字符串(2023年02月18日)
- 帮你把KMP算法学个通透
- 字符串:重复的子字符串
- 字符串:总结篇!
双指针法基本都是应用在数组,字符串与链表的题目上
- 数组:移除元素(2023年02月20日,2023年07月16日)
- 字符串:反转字符串(2022年12月27日)
- 字符串:替换空格(2023年02月21日)
- 字符串:翻转字符串里的单词(2023年02月17日)
- 链表:翻转链表(2023年02月22日)
- 链表:删除链表的倒数第 N 个结点(2023年02月22日)
- 链表:链表相交
- 链表:环形链表
- 双指针:三数之和
- 双指针:四数之和
- 双指针:总结篇!
- 栈与队列:来看看栈和队列不为人知的一面(2023年02月23日)
- 栈与队列:用栈实现队列(2023年02月23日)
- 栈与队列:用队列实现栈(2023年02月24日)
- 栈与队列:有效的括号(2023年02月27日)
- 栈与队列:删除字符串中的所有相邻重复项(2023年02月28日)
- 栈与队列:逆波兰表达式求值(2023年03月01日)
- 栈与队列:滑动窗口最大值(2023年03月06日,:pushpin:)
- 栈与队列:前K个高频元素(2023年03月07日,:pushpin:,主要是优先队列的写法)
- 栈与队列:总结篇!
- 关于二叉树,你该了解这些!
- 二叉树:二叉树的递归遍历(2023年03月12日)
- 二叉树:二叉树的迭代遍历(2023年03月13日)
- 二叉树:二叉树的统一迭代法
- 二叉树:二叉树的层序遍历 (3.15-3.18)
- 二叉树:翻转二叉树 (2023年03月20日)
- 本周小结!(二叉树)
- 二叉树:对称二叉树(2023年03月21日-2023年03月22日)
- 二叉树:二叉树的最大深度(2023年03月23日)
- 二叉树:二叉树的最小深度(2023年03月23日)
- 二叉树:完全二叉树的节点个数(2023年03月24日)
- 二叉树:平衡二叉树(2023年03月24日)
- 二叉树:二叉树的所有路径(2023年03月27日)
- 本周总结!二叉树系列二
- 二叉树:二叉树中递归带着回溯
- 二叉树:左叶子之和(2023年03月28日)
- 二叉树:找树左下角的值(2023年03月29日)
- 二叉树:路径总和(2023年03月29日)(2023年04月20日)(2023年04月21日)
- 二叉树:构造二叉树(2023年03月30日)
- 二叉树:最大二叉树(2023年03月31日)
- 本周小结!(二叉树系列三)
- 二叉树:合并两个二叉树(2023年04月01日) 二叉搜索树的中序遍历就是一个升序的数组。
- 二叉树:二叉搜索树登场!(2023年04月01日)
- 二叉树:验证二叉搜索树(2023年04月02日)
- 二叉树:搜索树的最小绝对差(2023年04月02日)
- 二叉树:二叉搜索树中的众数(2023年04月03日, 📌)
- 二叉树:公共祖先问题(2023年04月04日)
- 本周小结!(二叉树系列四)
- 二叉树:搜索树的最近公共祖先(2023年04月04日)
- 二叉树:搜索树中的插入操作(2023年04月05日)
- 二叉树:搜索树中的删除操作(2023年04月06日)
- 二叉树:修剪一棵搜索树(2023年04月06日)
- 二叉树:构造一棵搜索树(2023年04月07日) 附加. 二叉树:二叉树的序列化与反序列化(2023年04月10日)
- 二叉树:搜索树转成累加树(2023年04月11日)
- 二叉树:总结篇!(需要掌握的二叉树技能都在这里了)
csview 补充题目
- 二叉树的完全性检验(2023年04月13日)
- 662. 二叉树最大宽度(2023年04月14日)
- 226. 翻转二叉树(2023年04月15日)
- 572. 另一棵树的子树(2023年04月15日)
- 230. 二叉搜索树中第K小的元素(2023年04月15日,,2023年04月24日)
- 103. 二叉树的锯齿形层序遍历(2023年04月16日)
- 199. 二叉树的右视图(2023年04月17日)
- 124. 二叉树中的最大路径和(2023年04月18日)
- 543. 二叉树的直径(2023年04月19日)
- 129. 求根节点到叶节点数字之和(2023年04月20日)
- 剑指 Offer 54. 二叉搜索树的第k大节点(2023年04月22日)
题目分类大纲如下:
-
回溯算法:组合问题(2023年04月12日)
-
回溯算法:组合问题再剪剪枝(2023年04月12日)
-
回溯算法:求组合总和!(2023年05月02日)
-
回溯算法:电话号码的字母组合(2023年05月03日)
-
回溯算法:求组合总和(二)(2023年05月04日)
-
回溯算法:求组合总和(三)(2023年05月05日,:pushpin:,2023年05月15日)
-
回溯算法:分割回文串(2023年05月06日,简单方法,:pushpin:)
-
回溯算法:复原IP地址(2023年05月08日,:pushpin:,2023年06月06日,:pushpin:,2023年06月07日)
-
回溯算法:求子集问题!(2023年05月09日)
-
回溯算法:求子集问题(二)(2023年05月10日)
-
回溯算法:递增子序列(2023年05月12日)
回溯算法的去重问题的总结:去重主要是同层去重,即广度去重,深度不用去重。
大体上分为可排序问题和不可排序问题。
对于可排序问题的去重,需要先对输入进行排序,然后在 for 循环处,判断该元素与上个元素是否相等。
for (auto it = beg; it < end; it++) { if (it != beg && *(it - 1) == *it) { continue; } // ... } sort(nums.begin(),nums.end());
对于不可排序的,如该题,如果范围给出了,那么可以用数组,效率会高。注意是同层去重,因此不需要 pop 啥的。
array<bool, 201> used{}; for (auto it = beg; it < end; it++) { if (used[*it+100] || (!path.empty() && *it < path.back())) { continue; } path.push_back(*it); used[*it + 100] = true; if (path.size() > 1) { result.push_back(path); } backtracing(it + 1, end); path.pop_back(); } }
而如果范围也没有给出,就只能用unordered_set了。
unordered_set<int> used; for (auto it = beg; it < end; it++) { if (used.find(*it)!=used.end() || (!path.empty()&&*it < path.back())) { continue; } path.push_back(*it); used.insert(*it); if (path.size() > 1) { result.push_back(path); } backtracing(it + 1, end); path.pop_back(); } }
-
回溯算法:排列问题!(2023年05月13日)
-
回溯算法:排列问题(二)(2023年05月14日,:pushpin:,2023-06-05)
可以想象填格子的过程,横向是决定这个空填多少,填过了的肯定不能再填。
纵向是决定是填第几个空。
-
回溯算法:重新安排行程(2023年05月31日,:pushpin:,2023年06月01日)
-
回溯算法:N皇后问题(2023年06月02日)
-
回溯算法:解数独(2023年06月03日,:pushpin:,2023年06月04日)
题目分类大纲如下:
- 关于贪心算法,你该了解这些!
- 贪心算法:分发饼干(2023年06月08日)
- 贪心算法:摆动序列(2023年06月09日,:pushpin:,2023年06月26日)
- 贪心算法:最大子序和(2023年06月10日)
- 本周小结!(贪心算法系列一)
- 贪心算法:买卖股票的最佳时机II(2023年06月11日)
- 贪心算法:跳跃游戏(2023年06月11日)
- 贪心算法:跳跃游戏II(2023年06月12日,:pushpin:,2023年06月26日,:pushpin:)
- 贪心算法:K次取反后最大化的数组和(2023年06月13日)
- 本周小结!(贪心算法系列二)
- 贪心算法:加油站(2023年06月14日,:pushpin:)
- 贪心算法:分发糖果(2023年06月15日,multimap没有贪心)
- 贪心算法:柠檬水找零(2023年06月16日)
- 贪心算法:根据身高重建队列(2023年06月19日)
- 本周小结!(贪心算法系列三)
- 贪心算法:根据身高重建队列(续集)
- 贪心算法:用最少数量的箭引爆气球(2023年06月20日)
- 贪心算法:无重叠区间(2023年06月21日)
- 贪心算法:划分字母区间(2023年06月22日,:pushpin:)
- 贪心算法:合并区间(2023年06月23日)
- 本周小结!(贪心算法系列四)
- 贪心算法:单调递增的数字(2023年06月24日,:pushpin:)
- 贪心算法:买卖股票的最佳时机含手续费(2023年06月25日,:pushpin:)
- 贪心算法:我要监控二叉树!
- 贪心算法:总结篇!(每逢总结必经典)
动态规划专题已经开始啦,来不及解释了,小伙伴们上车别掉队!
- 关于动态规划,你该了解这些!
- 动态规划:斐波那契数
- 动态规划:爬楼梯
- 动态规划:使用最小花费爬楼梯
- 本周小结!(动态规划系列一)
- 动态规划:不同路径
- 动态规划:不同路径还不够,要有障碍!
- 动态规划:整数拆分,你要怎么拆?
- 动态规划:不同的二叉搜索树
- 本周小结!(动态规划系列二)
背包问题系列:
- 动态规划:关于01背包问题,你该了解这些!
- 动态规划:关于01背包问题,你该了解这些!(滚动数组)
- 动态规划:分割等和子集可以用01背包!
- 动态规划:最后一块石头的重量 II
- 本周小结!(动态规划系列三)
- 动态规划:目标和!
- 动态规划:一和零!
- 动态规划:关于完全背包,你该了解这些!
- 动态规划:给你一些零钱,你要怎么凑?
- 本周小结!(动态规划系列四)
- 动态规划:Carl称它为排列总和!
- 动态规划:以前我没得选,现在我选择再爬一次!
- 动态规划: 给我个机会,我再兑换一次零钱
- 动态规划:一样的套路,再求一次完全平方数
- 本周小结!(动态规划系列五)
- 动态规划:单词拆分
- 动态规划:关于多重背包,你该了解这些!
- 听说背包问题很难? 这篇总结篇来拯救你了
打家劫舍系列:
股票系列:
- 动态规划:买卖股票的最佳时机
- 动态规划:本周我们都讲了这些(系列六)
- 动态规划:买卖股票的最佳时机II
- 动态规划:买卖股票的最佳时机III
- 动态规划:买卖股票的最佳时机IV
- 动态规划:最佳买卖股票时机含冷冻期
- 动态规划:本周我们都讲了这些(系列七)
- 动态规划:买卖股票的最佳时机含手续费
- 动态规划:股票系列总结篇
子序列系列:
- 动态规划:最长递增子序列
- 动态规划:最长连续递增序列
- 动态规划:最长重复子数组
- 动态规划:最长公共子序列
- 动态规划:不相交的线
- 动态规划:最大子序和
- 动态规划:判断子序列
- 动态规划:不同的子序列
- 动态规划:两个字符串的删除操作
- 动态规划:编辑距离
- 为了绝杀编辑距离,Carl做了三步铺垫,你都知道么?
- 动态规划:回文子串
- 动态规划:最长回文子序列
- 动态规划总结篇
(持续更新中....)
- 并查集
- 最小生成树
- 线段树
- 树状数组
- 字典树
以上题目是重中之重,大家至少要刷两遍以上才能彻底理解,如果熟练以上题目之后还在找其他题目练手,可以再刷以下题目:
这些题目很不错,但有的题目是和刷题攻略类似的,有的题解后面还会适当补充,所以我还没有将其纳入到刷题攻略。一些题解等日后我完善一下,再纳入到刷题攻略。
- 1365.有多少小于当前数字的数字
- 941.有效的山脉数组 (双指针)
- 1207.独一无二的出现次数 数组在哈希法中的经典应用
- 283.移动零 【数组】【双指针】
- 189.旋转数组
- 724.寻找数组的中心索引
- 34.在排序数组中查找元素的第一个和最后一个位置 (二分法)
- 922.按奇偶排序数组II
- 35.搜索插入位置
- 24.两两交换链表中的节点
- 234.回文链表
- 143.重排链表【数组】【双向队列】【直接操作链表】
- 141.环形链表
- 160.相交链表
- 205.同构字符串:【哈希表的应用】
- 925.长按键入 模拟匹配
- 0844.比较含退格的字符串【栈模拟】【空间更优的双指针】
- 129.求根到叶子节点数字之和
- 1382.将二叉搜索树变平衡 构造平衡二叉搜索树
- 100.相同的树 同101.对称二叉树 一个思路
- 116.填充每个节点的下一个右侧节点指针
- 649.Dota2参议院 有难度
- 1221.分割平衡字符 简单贪心
- 5.最长回文子串 和647.回文子串 差不多是一样的
- 132.分割回文串II 与647.回文子串和 5.最长回文子串 很像
- 673.最长递增子序列的个数
- 684.冗余连接 【并查集基础题目】
- 685.冗余连接II【并查集的应用】
-
两数之和 II - 输入有序数组,双指针,2023年07月08日
-
15. 三数之和,双指针,2023年07月09日
-
16. 最接近的三数之和,双指针,2023年07月10日
-
2544. 交替数字和,2023年07月12日
-
979. 在二叉树中分配硬币,2023年07月14日
-
18. 四数之和双指针,2023年07月15日
一定要注意,这种后面会不会超过数据范围。
-
307 区域和检索 - 数组可修改,2023年11月13日
树状数组,所有的同时要求了更新某个数和求区间和的题目都可以用这个方法。
add函数和prefixSum函数时间复杂度均为O(logn)
-
4.寻找两个正序数组的中位数,二分查找进阶,2023年11月14日
-
11. 盛最多水的容器,双指针,2023年11月14日