[数据结构与算法]代码随想录：贪心/动态规划 刷题笔记（六月记录）

2022六月算法学习日志

6.5

贪心：用常识，想清楚局部最优，想清楚全局最优，想不出反例

分发饼干

遍历不一定用循环，自减/自增也可

6.7

最大子序列的和

C中常量INT_MAX和INT_MIN分别表示最大、最小整数，定义在头文件limits.h中。

C/C++整型上下限INT_MAX INT_MIN及其运算

买卖股票最佳时机

区分最优解（买卖区间）和最优解的值（最佳利润）

6.8

跳跃问题

不用管是不是刚好，超过范围肯定能达到

先处理特殊情况（只有一步的时候）

for循环边界可以实时变更

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FS6TI0Z6-1656656996469)(C:\Users\hj\AppData\Roaming\Typora\typora-user-images\image-20220608094027944.png)]

跳跃问题2

i的移动和当前&下一步最大范围的交替隔离看待

6.9

k次取反后最大化数组的和

取相反数：a=-a || a*=-1

cmp可自定义排序规则（比如按绝对值排序）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0VbtDID9-1656656996471)(C:\Users\hj\AppData\Roaming\Typora\typora-user-images\image-20220609095011076.png)]

加油站

如果收入>支出，则一定成立，这种情况下只管找成立的解，而不用再怀疑其成立性

6.15

分发糖果

如果在考虑局部的时候想两边兼顾，就会顾此失彼。

由后往前考虑的时候，会使用到由前往后考虑到的结果

柠檬水找零

一种c++遍历方式

for(int bill:bills)

根据身高重建队列

同上，两个维度前后考虑

6.16

无重叠区间&引爆气球

逆向思维：移除区间总数=总区间数-无交叉区间个数

6.17

划分字母区间

因为统计的是字母，26个，用hash就还好

// 统计每一个字符最后出现的位置
for(){
hash[S[i]-'a'] = i;
}
// 找到字符出现的最远边界
right = max(right, hash[S[i] - 'a']);

合并区间

注意开始排除空数组的特殊情况

虽然用了for循环，i步长为1，但循环体内i还是可以加速的

一种为二维数组添加元素的方法

result.push_back({left,right});

区分当前和上一个 与 当前与历史极值

6.18

单调递增的数字

把n位数字拆解为2位子问题（局部最优）——再考虑合并的规则

//int转为string
string s = to_string(n);
//string转为int
stoi(strNum);

注意从后往前的边界控制：从 s.size()-1 开始

买卖股票最佳时机（含手续费）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uJKMm1jv-1656656996473)(C:\Users\hj\AppData\Roaming\Typora\typora-user-images\image-20220618104138561.png)]

标红：

若prices[i]-fee<prices[i+1]，说明i位置符合卖出要求，但仍处地位，非最佳卖出时机；

若prices[i]-fee>prices[i+1]，说明后有低位，可以出手，进行新一轮买进卖出；

监控二叉树

递归拆分子问题（双层二叉树三个节点），罗列出可能出现的所有情况及返回值

6.19

动态规划：解决具有很多重叠子问题的问题，每一个状态都从上一个状态推导过来

6.25

最小代价爬楼梯

1.明确dp[i]含义；

2.递推公式；

3.初始化；

4.遍历顺序；

5.手工推dp数组检查

不同路径

初始化数值是1好伐

//初始化m*n二维数组
vector<vector<int>> dp(m,vector<int>(n,0));

//获取二维数组大小
int m = array.size();
int n = array[0].size();

注意先判断终点有障碍物的特殊情况

6.28

不同路径2