贪心算法
贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,从而 使得结果也是最优解,适合去解决具有最优子结构的问题。
最优子结构的特征:
- 每一次操作对结果直接产生影响
- 不依赖于之前的操作
- 子问题的最优解是全局最优解的一部分
思路:每个格子
i
作为起跳点最远能跳到nums[i]
处,所以遍历数组得到最远距离并与数组长度进行比较即可。这题只需要判断能否到达终点而无需给出具体路径,所以不需要用回溯的方法。
public boolean canJump(int[] nums) {
int maxLen = 0;
for (int i = 0; i < nums.length; i++) {
// 当前格子已经无法跳到
if (i > maxLen) return false;
// 更新能跳到的最远距离
maxLen = Math.max(maxLen, i + nums[i]);
}
return true;
}
思路:确保每次跳跃选择的格子都有最远的跳跃范围。
public int jump(int[] nums) {
int steps = 0;
int start = 0;
int end = 1;
while (end < nums.length) {
// 确定最远的跳跃范围
int maxPosition = 0;
for (int i = start; i < end; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
}
start = end;
end = maxPosition + 1;
// 步数增加
steps++;
}
return steps;
}
对每个孩子i
,都有一个胃口值g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j
,都有一个尺寸s[j]
。如果s[j] >= g[i]
,我们可以将这个饼干j
分配给孩 子i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
思路:先排序,再贪心,让饼干优先满足胃口更多的孩子
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int p = 0;
int q = 0;
while (p < g.length && q < s.length) {
if (g[p] <= s[q]) {
p++;
}
q++;
}
return p;
}
最近更新 2yr ago