# leetcode_hot_100

**Repository Path**: velon/leetcode_hot_100

## Basic Information

- **Project Name**: leetcode_hot_100
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-07-18
- **Last Updated**: 2024-10-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 数据结构与算法

## README

# 1007
52. 完全平方数
完全背包问题，正序遍历即可
dp[i] = min(dp[i - j * j] + 1,dp[i]);
53. 零钱兑换
完全背包问题
if(i - coins[j] >= 0 && dp[i - coins[j]] != INT32_MAX)
    dp[i] = min(dp[i],dp[i - coins[j]] + 1);
54. 单词拆分
完全背包问题
if(dp[j] && hashSet.find(s.substr(j,i - j )) != hashSet.end()){
                    dp[i] = true;
                    break;
}
55. 最长递增子序列
子序列问题（不连续）
if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j] + 1);
56. 最长连续递增子序列
if(nums[i] > nums[i - 1]) dp[i] =dp[i - 1] + 1;

# 1006
47. 01背包
dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
倒序遍历dp数组，防止重复添加物品
48. 完全背包
正序遍历dp数组，重复添加物品
49. 爬楼梯
普通
50. 杨辉三角
普通
51. 打家劫舍
dp[i] = max(dp[i - 1],dp[i - 2] + num[i - 1]);
注意此处的nums[i - 1]指的是第i户人家

# 0908
41. 144二叉树前序遍历
递归注意先后顺序，迭代法用栈来实现
42. 94二叉树中序遍历
递归法与前序遍历基本一致，迭代法注意先把当前节点移到最左边的节点
43. 145二叉树后序遍历
递归法就是标准模板，迭代法注意是“前序遍历”反过来（reverse一下） 
44. 70爬楼梯
dp[i] = dp[i - 1] + dp[i - 2];
45. 1出现的次数
把int类型的数转成字符串类型即可
46. 快速排序
采用分治的思想来递归的划分数组

# 0905
39. 42接雨水
- 用双指针来实现非常的优雅（左指针从最左边开始，右指针从最右边开始）
双指针的思路本身就有一点像动态规划
- 动态规划思路（计算left_max与right_max，然后统计重叠面积）
- 单调栈
40. 704二分查找
注意保证能出循环，具体做法是每次更新mid时，让right - 1,left + 1

# 0904
38. 206反转链表
注意用双指针法来实现

# 0903 
35. 94二叉树的中序遍历
用栈迭代实现（可以思考一下怎么递归实现）
36. 104二叉树的最大深度
层序遍历即可解决
37. 226翻转二叉树
- 可以考虑使用层序遍历来交换每一层的节点
- 使用递归的逻辑来实现（需要明天进一步弄清楚递归本身）


# 0902
31. 300最长递增子序列
dp[i] = max(dp[i],dp[j] + 1);注意初值和返回值
其中初值代表的含义是子序列至少是1，返回值是所有的子序列中最长的那个
32. 152乘积最大子数组
dp_max[i] = max(dp_max[i - 1] * nums[i],max(dp_min[i - 1] * nums[i],nums[i]));
dp_min[i] = min(dp_min[i - 1] * nums[i],min(dp_max[i - 1] * nums[i],nums[i]));
注意连续的条件和对初值的处理
33. 416分割等和子集
dp[i] = dp[i] || dp[i - num];
注意初值的情况以及要把问题进行分解，即找sum_half的过程
34. 32最长有效括号（动态规划hard）
(可以参考一下leetcode官方题解)
- 当遇到 ')' 时，可能形成有效括号子串，因此需要进行以下判断：
- 如果前一个字符是 '('，即 s[i-1] == '('，那么我们可以直接更新 dp[i] = dp[i-2] + 2（如果 i >= 2）。
- 如果前一个字符是 ')'，且 s[i-1] == ')'，则检查 i-dp[i-1]-1 位置的字符是否为 '('。如果是，则有 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2（其中 dp[i-dp[i-1]-2] 是补上前面的有效长度，若 i-dp[i-1] >= 2）。

# 0901
28. 249完全平方数
dp[i] = min(dp[i - j * j] + 1,dp[i]);
类似于背包问题
29. 322零钱兑换
dp[i] = min(dp[i],dp[i - coins[j]] + 1);
与上一道题类似，注意要判断一下dp[i - coins[j]]不能是无穷大，因为这样会超出整型表示的最大范围
30. 139单词拆分
dp[j] && hash_dic.find(s.substr(j,i - j)) != hash_dic.end()
其中dp[j]为真就已经说明前面的j个字符串已经在字典中可以找到，这是解题的关键

# 0831
25. 70爬楼梯
dp[i] = dp[i - 1] + dp[i - 2];
26. 118杨辉三角
temp[j] = res[i - 2][j - 1] + res[i - 2][j];
这块逻辑处理的不太好，主要是编程中有下标0
27. 198打家劫舍
dp[i] = max(dp[i - 1],dp[i - 2] + nums[i - 1]);
跟爬楼梯的逻辑有点像，主要是考虑第i - 1户人家偷还是不偷


# 0804
19. 144二叉树前序遍历
递归法实现,三段式：注意递归函数的参数和返回值；设置终止条件；递归单层逻辑
20. 94二叉树中序遍历(**二刷迭代法**)
同19，在用迭代实现（即用栈来模拟递归的过程）中，中序遍历较难实现
21. 145二叉树后序遍历
同20,迭代法在前序遍历的基础之上只需要改变一下入栈顺序然后再reverse一下就行
22. 102二叉树层序遍历
定义好size逐层搜索即可
23. 107二叉树的层序遍历II
在102的基础上把结果反转一下即可
24. 104二叉树最大深度
层序遍历秒了（可能最小深度难一点，不过也只是多了一个判断）

# 0731
17. 541反转字符串II
单独写一个字符串反转的函数
18. 151反转字符串里面的单词(**难**)
注意把任务进行分解。任务 = 反转字符串 + 去除多余的空格 + 反转句子

# 0730
12. 454四数相加
统计count的时候应该是统计那一个key上的值，而不是直接+1
13. 383赎金信
跟字母异位词一个套路，声明一个26大小的数组即可：vector<int> arrary(26,0)
14. 15三数之和(**难**)
本题还是颇有难度的需要找时间重新再写一遍；尤其是要注意当固定第一个数之后搜索的过程中有去重的步骤（两次去重复）
15. 18四数之和(**需单步调试看值**)
注意二次剪裁以及去重操作
16. 344反转字符串
（原地修改数组）
注意给i加限制之和就不需要给j加限制了，本质上就是双指针法，跟反转链表那道题类似


# 0729
10. 202快乐数
注意快乐数的构成：创建一个unordered_set，存储一个num进入set之中假如下一个和在
set里面已经存在的话，则证明已经构成死循环不可能是快乐数，另外注意一下取模运算用于提取一个数中的各个位
11. 1两数之和
主要是学习map的语法（迭代器和second以及pair对的使用）

1. 203移除链表元素
2. 707设计链表(细节问题很多，需要及时review)(需近期二刷)
3. 206反转链表
4. 24两两交换链表中的节点
# 0727

5. 19删除链表的倒数第N个节点
快指针前进N步慢指针紧跟
6. 面试题02.07.链表相交
7. 142环形链表
x = (n - 1)(y + z) + z
是一个数学问题，x是起点到环的距离，y是慢指针在环中走过的距离，z是慢指针所在终点到环入口的距离
8. 242有效的字母异位词
C++数组最好使用vector
9. 349两个数组的交集
熟悉stl库中vector和unordered_set的互相转化以及迭代器