1. 回顾数据结构&算法
让我们重新回顾一下数据结构的整体分类和算法,并自己内心说明各个数据结构的特性,回忆算法的思想和代码模板。
1.1 一维数据结构
基础的有:数组(查询快,插入操作较慢,需要重新分配空间)、链表(查询慢,插入比数组快)
高级的有:栈stack(先进后出)、队列queue(先进先出)、双端队列deque(适用于FIFO和LIFO两个场景)、集合Set(无重复元素集合)、映射map(hash 或者 map)、etc
1.2 二维数据结构
基础的有:树tree、图Graph(链表是特殊化的树,树是特殊化的图)
高级的有:二叉搜索树binary search tree (red-black tree,AVL)、堆heap、并查集disjoint Set、字典树 Trie、etc
1.3 特殊
位运算 bitwise、布隆过滤器 BloomFilter
LRU Cache
注意:在脑海中回忆数据结构的特点
1.4 算法
- if-else,switch ——> branch
- for,while loop ——> Iteration
- 递归 Recursion(Divide & Conquer,backtrace)
- 搜索Search:深度优先搜索 Depth first Search, 广度优先搜索Breadth first search , A*,etc
- 动态规划 Dynamic Programming
- 二分查找 binary Search
- 贪心算法 Greedy
- 数学 Math,几何 Geometry
注意:在脑海中回忆上面的各种算法思想和代码模板
默写上一章节中:深度优先搜索和广度优先搜索的代码模板,递归和非递归版本都要默写
注意:树的定义和树的遍历,dfs和bfs的特点和遍历代码模板。
回顾完成后我们开始学习贪心算法
**
2. 贪心算法 Greedy
贪心算法概念:贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。
贪心算法和动态规划的比较:贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
贪心算法的作用:贪心法可以解决一些最优化问题,如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题,贪心法一般不能得到我们所要求的答案。
贪心法应用特点:一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
学习理解案例:
https://leetcode-cn.com/problems/coin-change/
2.1 适合贪心算法的场景
简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
3. 练习
- https://leetcode-cn.com/problems/lemonade-change/description/
2. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
3. https://leetcode-cn.com/problems/assign-cookies/description/
4. https://leetcode-cn.com/problems/walking-robot-simulation/description/
5. https://leetcode-cn.com/problems/jump-game/
https://leetcode-cn.com/problems/jump-game-ii/