学习总结

一、时间安排

阿里云天池leetcode训练营（二月）。

task01 数组

2月14日-2月15日

leetcode题号	题目	题解链接	注意事项
16	最接近的三数之和	C++题解	双指针

task02 链表

2月16日-2月17日

leetcode题号	题目	题解链接	注意事项
61	旋转链表	已完成	第n-k-1为新头节点
剑指 Offer 25.	合并两个排序的链表	已完成	常规题，哨兵节点
160	相交链表	C++题解	简单数学
82	删除排序链表中的重复元素 II	C++题解	每段可以循环删除

task03 栈

2月18日-2月19日

leetcode题号	题目	题解链接	注意事项
20	有效的括号	C++题解	栈
150	逆波兰表达式求值	C++题解	栈
155	最小栈	C++题解	借助辅助栈
844	比较含退格的字符串	C++题解	双栈或者双指针，后者方法才能$O(1)$空间复杂度
227	基本计算器 II	C++题解	这几题中最综合的一题，值得二刷，从加减法、乘除法、加入括号（递归）逐层思考。

task04 字符串

2月20日-2月21日
可以熟悉C++和字符串相关的api，如isalnum判断是否为字母或者数字，如果不知道api就写判断条件；tolower是将char字符转为小写字母。

leetcode题号	题目	题解链接	注意事项
125	验证回文串	C++题解	isalnum和tolower
151	翻转字符串里的单词	C++题解	和剑指offer58 I.翻转单词顺序相同（istringstream）
680	验证回文字符串 II	C++题解	s.substr(a, b)表示从s字符串的a下标开始算，连续b个字符
168	Excel表列名称	C++题解	从1开始的进制转换
394	字符串解码	Python题解	栈

task05 树

2月22日-2月23日
常用递归，方法和思路可以参考宏观角度看递归。

leetcode题号	题目	题解链接	注意事项
104	二叉树的最大深度	C++题解	递归or迭代
108	将有序数组转换为二叉搜索树	C++题解	中序遍历，为了严格平衡BST，可以选中间节点为根结点
111	二叉树的最小深度	C++题解	递归or层次遍历的迭代
112	路径总和	C++题解	边界条件： root为NULL要return，root左右子树为NULL时要判断是否为sum
173	二叉搜索树迭代器	C++题解	中序遍历，注意引用的用法

task06 位运算

2月24日-2月25日

（1）n&(n-1)可以将n的二进制位的最低位1移除；
（2）n&(-n)==n则说明n是2的幂，负数在计算机中是按补码存储的，-n是n的每位取反再加1。

leetcode题号	题目	题解链接	注意事项
136	只出现一次的数字	C++题解	异或的位运算
260	只出现一次的数字III	C++题解	分组是关键，异或，与操作
231	2的幂	C++题解	（n & (n - 1) == 0或n & (-n) == n）
137	只出现一次的数字II	C++题解	每个数的第j列元素相加余3
78	子集	C++题解	2种回溯方法

task07 双指针

2月26日-2月27日

leetcode题号	题目	题解链接	注意事项
206	反转链表	C++题解	递归or迭代法
19	删除链表的倒数第N个结点	C++题解	有哨兵节点
704	二分查找	已完成	常规题
33	搜索旋转排序数组	C++题解	二分查找的变种

task08 搜索

2月28日-3月1日

leetcode题号	题目	题解链接	注意事项
704	二分查找	已完成	常规题
33	搜索旋转排序数组	C++题解	二分查找的变种
101	对称二叉树	C++题解	递归or迭代
94	二叉树的中序遍历	已完成	模板题，inorder单独写出来
230	二叉搜索树中第K小的元素	已完成	就中序遍历数组，取第k-1个

task09 排序

3月2日-3月3日

快速排序的模板：

class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();quick_sort(nums,0,n-1);return nums;}void quick_sort(vector<int> &q ,int l,int r){//递归边界if(l>=r) return;//这里初值设置为l-1,r+1是因为while中是do,while结构//先使i+1,j-1指向数组的第一和最后一个位置，再开始判断int x = q[(l+r) >> 1],i  = l-1, j=r+1;while(i<j){//将比枢轴小的元素do{i++;} while(q[i] < x);do{j--;} while(q[j] > x);if(i < j) swap(q[i], q[j]);}//递归左右子序列quick_sort(q,l,j);quick_sort(q,j+1,r);}
};

leetcode题号	题目	题解链接	注意事项
88	合并两个有序数组	已完成	直接把nums2补在nums1尾巴后sort
912	排序数组	C++题解	如果用快速排序，选枢轴需要随机or取中间的！！不然会超时
977	有序数组的平方	已完成	直接平方后排序了（偷懒）
1122	数组的相对排序	C++题解	哈希表 or 自定义排序sort函数
147	对链表进行插入排序	C++题解	可以先对节点进行sort排序后再将节点连接起来，排序函数如下

sort(vec.begin(), vec.end(), [&](ListNode* n1, ListNode* n2){return n1->val < n2->val;
});

task10 动态规划

3月4日-3月5日
四部曲：确定状态；状态转移方程（描述子问题之间的联系）；边界+初始条件；遍历顺序。

leetcode题号	题目	题解链接	注意事项
53	最大子数组和	C++题解	注意是连续，用dp后，还可以使用分治法
1143	最长公共子序列	C++题解	这里的子序列可以不连续
121	买卖股票的最佳时机	C++题解	二维数组
122	买卖股票的最佳时机 II	C++题解	比I多了个多次买卖
516	最长回文子序列	C++题解	使用中心扩散法（更好想），有奇数和偶数两种情况，palindrome单独写

task11 分治

3月6日-3月7日

分治思想：将原问题划分为n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后合并结果，得到原问题的解。

每一次递归都会设计3个操作：

• 分解：将原问题分解成一系列子问题；
• 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
• 合并：将子问题的结果合并成原问题；

leetcode题号	题目	题解链接	注意事项
108	将有序数组转换为二叉搜索树	C++题解	中序遍历构建BST，每次取中间节点作为当前根结点即可保证高度平衡
106	从中序与后序遍历序列构造二叉树	C++题解	边界小心
168	多数元素	C++题解	摩尔投票法
53	最大子数组和	C++题解	动态规划，要补分治法
105	从前序与中序遍历序列构造二叉树	C++题解	和106类似

task12 哈希表

3月8日-3月9日

leetcode题号	题目	题解链接	注意事项
217	存在重复元素	已完成	—
36	有效的数独	C++题解	三个哈希表
219	存在重复元素 II	C++题解	哈希，mp[i]=j表示数字i在原数组的下标为j
771	宝石与石头	已完成	基础题，哈希
811	子域名访问计数	待完成	涉及很多字符串处理（如分割和拼接）