贪心算法学习三

例题一

解法(贪⼼):
贪⼼策略:
⽤尽可能多的字符去构造回⽂串:
a. 如果字符出现偶数个,那么全部都可以⽤来构造回⽂串;
b. 如果字符出现奇数个,减去⼀个之后,剩下的字符能够全部⽤来构造回⽂串;
c. 最后再判断⼀下,如果有字符出现奇数个,就把它单独拿出来放在中间。

例题二

解法(贪⼼):
贪⼼策略:
a. 当遇到 'I' 的时候,为了让下⼀个上升的数可选择的「范围更多」,当前选择「最⼩」的那个数;
b. 当遇到 'D' 的时候,为了让下⼀个下降的数可选择的「范围更多」,选择当前「最⼤」的那个数。

例题三

贪⼼策略:
先将两个数组排序。
针对胃⼝较⼩的孩⼦,从⼩到⼤挑选饼⼲:
i. 如果当前饼⼲能满⾜,直接喂(最⼩的饼⼲都能满⾜,不要浪费⼤饼⼲);
ii. 如果当前饼⼲不能满⾜,放弃这个饼⼲,去检测下⼀个饼⼲(这个饼⼲连最⼩胃⼝的孩⼦都⽆法满⾜,更别提那些胃⼝⼤的孩⼦了)。

例题四

解法(贪⼼):
贪⼼策略:
在最终的结果中,前两个数的位置是⽆法改变的。因为每⼀个数的都是⼤于等于 2 的,为了让结果更⼤,我们应该尽可能的把剩下的数全都放在「分⼦」上.

例题五

解法(动态规划 + 类似层序遍历):
动态规划:
a. 状态表⽰:
dp[i] 表⽰从 0 位置开始,到达 i 位置时候的最⼩跳跃次数。
b. 状态转移⽅程:
对于 dp[i] ,我们遍历 0 ~ i - 1 区间(⽤指针 j 表⽰),只要能够从 j 位置跳到 i 位置( nums[j] + j >= i ),我们就⽤ dp[j] + 1 更新 dp[i] ⾥⾯的值,找到所有情况下的最⼩值即可。
类似层序遍历的过程:
⽤类似层序遍历的过程,将第 i 次跳跃的「起始位置」和「结束位置」找出来,⽤这次跳跃的情
况,更新出下⼀次跳跃的「起始位置」和「终⽌位置」。这样「循环往复」,就能更新出到达 n - 1 位置的最⼩跳跃步数。

例题六

解法:
和 跳跃游戏II ⼀样,仅需修改⼀下返回值即可。

相关推荐

  1. 贪心算法

    2024-06-13 19:30:01       24 阅读
  2. 力扣贪心算法--第

    2024-06-13 19:30:01       15 阅读
  3. 贪心算法基础题(第天)

    2024-06-13 19:30:01       11 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-13 19:30:01       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-06-13 19:30:01       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-06-13 19:30:01       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-06-13 19:30:01       18 阅读

热门阅读

  1. MySQL bin-log日志恢复数据

    2024-06-13 19:30:01       9 阅读
  2. LVS ipvsadm命令的使用(二)

    2024-06-13 19:30:01       8 阅读
  3. CVE-2020-1472域渗透 NetLogon 权限提升漏洞

    2024-06-13 19:30:01       9 阅读
  4. 在 Visual Studio 调试器中指定符号 (.pdb) 和源文件

    2024-06-13 19:30:01       7 阅读
  5. Android 调用系统相册、系统相机拍照

    2024-06-13 19:30:01       8 阅读
  6. 新视野大学英语2 词组 6.13

    2024-06-13 19:30:01       7 阅读
  7. Hutool有哪些常用方法

    2024-06-13 19:30:01       9 阅读
  8. SQL Server几种琐

    2024-06-13 19:30:01       5 阅读