File tree Expand file tree Collapse file tree 4 files changed +27
-19
lines changed Expand file tree Collapse file tree 4 files changed +27
-19
lines changed Original file line number Diff line number Diff line change 19
19
[ 1,4] ,
20
20
]
21
21
22
+ 也可以直接看我的B站视频:[ 带你学透回溯算法-组合问题(对应力扣题目:77.组合)] ( https://www.bilibili.com/video/BV1ti4y1L7cv#reply3733925949 )
23
+
22
24
# 思路
23
25
24
26
本题这是回溯法的经典题目。
Original file line number Diff line number Diff line change @@ -21,6 +21,8 @@ https://leetcode-cn.com/problems/valid-anagram/
21
21
22
22
** 数组其实就是一个简单哈希表** ,而且这道题目中字符串只有小写字符,那么就可以定义一个数组,来记录字符串s里字符出现的次数。
23
23
24
+ 如果对哈希表的理论基础关于数组,set,map不了解的话可以看这篇:[ 关于哈希表,你该了解这些!] ( https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA )
25
+
24
26
需要定义一个多大的数组呢,定一个数组叫做record,大小为26 就可以了,初始化为0,因为字符a到字符z的ASCII也是26个连续的数值。
25
27
26
28
为了方便举例,判断一下字符串s= "aee", t = "eae"。
@@ -43,6 +45,8 @@ https://leetcode-cn.com/problems/valid-anagram/
43
45
44
46
时间复杂度为O(n),空间上因为定义是的一个常量大小的辅助数组,所以空间复杂度为O(1)。
45
47
48
+ 看完这篇哈希表总结:[ 哈希表:总结篇!(每逢总结必经典)] ( https://mp.weixin.qq.com/s/1s91yXtarL-PkX07BfnwLg ) ,详细就可以哈希表的各种用法非常清晰了。
49
+
46
50
# C++ 代码
47
51
```
48
52
class Solution {
@@ -67,5 +71,8 @@ public:
67
71
}
68
72
};
69
73
```
70
- > 更过算法干货文章持续更新,可以微信搜索「代码随想录」第一时间围观,关注后,回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等,就可以获得我多年整理的学习资料。
74
+ > ** 我是[ 程序员Carl] ( https://github.com/youngyangyang04 ) ,[ 组队刷题] ( https://img-blog.csdnimg.cn/20201115103410182.png ) 可以找我,本文[ leetcode刷题攻略] ( https://github.com/youngyangyang04/leetcode-master ) 已收录,更多[ 精彩算法文章] ( https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect ) 尽在:[ 代码随想录] ( https://img-blog.csdnimg.cn/20200815195519696.png ) ,关注后就会发现和「代码随想录」相见恨晚!**
75
+
76
+ ** 如果感觉题解对你有帮助,不要吝啬给一个👍吧!**
77
+
71
78
Original file line number Diff line number Diff line change
1
+ > leetcode上版本
1
2
2
3
本题是KMP 经典题目。
3
4
Original file line number Diff line number Diff line change
1
+ # 关于贪心算法,你该了解这些!
1
2
2
- ## 什么是贪心
3
+ > 正式开始新的系列了,贪心算法!
4
+ 通知:一些录友表示经常看不到每天的文章,现在公众号已经不按照发送时间推荐了,而是根据一些规则乱序推送,所以可能关注了「代码随想录」也一直看不到文章,建议把「代码随想录」设置星标哈,设置星标之后,每天就按发文时间推送了,我每天都是定时8:35发送的,嗷嗷准时,哈哈。
5
+
6
+ # 什么是贪心
3
7
4
8
** 贪心的本质是选择每一阶段的局部最优,从而达到全局最优** 。
5
9
11
15
12
16
每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
13
17
14
- 再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,一定不行 。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
18
+ 再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了 。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
15
19
16
- ## 贪心的套路(什么时候用贪心)
20
+ # 贪心的套路(什么时候用贪心)
17
21
18
22
很多同学做贪心的题目的时候,想不出来是贪心,想知道有没有什么套路可以一看就看出来是贪心。
19
23
46
50
47
51
** 例如刚刚举的拿钞票的例子,就是模拟一下每次拿做大的,最后就能拿到最多的钱,这还要数学证明的话,其实就不在算法面试的范围内了,可以看看专业的数学书籍!**
48
52
49
- 所以这也是为什么很多同学通过(accept)了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!
53
+ 所以这也是为什么很多同学通过(accept)了贪心的题目,但都不知道自己用了贪心算法,** 因为贪心有时候就是常识性的推导,所以会认为本应该就这么做!**
50
54
51
55
** 那么刷题的时候什么时候真的需要数学推导呢?**
52
56
53
- 例如环形链表2,这道题目不用数学推导一下 ,就找不出环的起始位置,想试一下就不知道怎么试,这种题目确实需要数学简单推导一下。
57
+ 例如这道题目: [ 链表:环找到了,那入口呢? ] ( https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA ) ,这道题不用数学推导一下 ,就找不出环的起始位置,想试一下就不知道怎么试,这种题目确实需要数学简单推导一下。
54
58
55
- ## 贪心一般解题步骤
59
+ # 贪心一般解题步骤
56
60
57
61
贪心算法一般分为如下四步:
58
62
61
65
* 求解每一个子问题的最优解
62
66
* 将局部最优解堆叠成全局最优解
63
67
64
- 一个子问题的最优解会是下一个子问题最优解的一部分,重复这个操作直到推出整个问题的最优解!
68
+ 其实这个分的有点细了,真正做题的时候很难分出这么详细的解题步骤,可能就是因为贪心的题目往往还和其他方面的知识混在一起。
65
69
66
70
# 总结
67
71
68
- 理论篇给出了什么是贪心以及大家关心的贪心算法固定套路。
69
-
70
- 不好意思了,贪心没有套路,平时刷题或者面试的时候就是常识性推导加上举反例。
71
-
72
- 最后给出一个贪心的一般解题步骤,大家可以发现这个解题步骤也是毕竟抽象的,不像是 二叉树,回溯算法,给出了那么具体的解题套路和模板。
73
-
74
-
72
+ 本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
75
73
74
+ ** 不好意思了,贪心没有套路,说白了就是常识性推导加上举反例** 。
76
75
76
+ 最后给出贪心的一般解题步骤,大家可以发现这个解题步骤也是比较抽象的,不像是二叉树,回溯算法,给出了那么具体的解题套路和模板。
77
77
78
- 贪心算法的应用
79
- 对数据压缩编码的霍夫曼编码(Huffman Coding)
80
- 求最小生成树的 Prim 算法
81
- 求单源最短路径的Dijkstra算法
78
+ 本篇没有配图,其实可以找一些动漫周边或者搞笑的图配一配(符合大多数公众号文章的作风),但这不是我的风格,所以本篇文字描述足以!
82
79
80
+ 就酱,「代码随想录」值得你的关注!
You can’t perform that action at this time.
0 commit comments