赞
踩
贪心算法是一种在算法设计中常用的方法,它在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。
贪心算法与枚举法的不同之处在于每个子问题都选择最优的情况,然后向下继续进行,且不能回溯。枚举法是将所有情况都考虑然后选出最优的情况。贪心算法在解决问题时,不从整体考虑,而是采用一种一眼看到局部最优解的选择方式。并且,贪心算法没有固定的模板可以遵循,每个题目都有不同的贪心策略,所以算法设计的关键在于贪心策略的选择。
贪心算法有一个必须注意的事情。贪心算法对于问题的要求是,所有的选择必须是无后效性的,即当前的选择不能影响后续选择对于结果的影响。
贪心算法主要适用于最优化问题,例如:最小生成树问题。有时候贪心算法并不能得到最优答案,但是能得到精确答案的近似结果。有时可以辅助其他算法得到不那么精确的结果。
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i
,都有一个胃口值 g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j
,都有一个尺寸 s[j]
。如果 s[j] >= g[i]
,我们可以将这个饼干 j
分配给孩子 i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
这个问题可以用贪心算法来解决。我们的目标是尽可能满足更多的孩子,所以我们应该优先满足胃口小的孩子,因为他们更容易被满足。同时,我们应该使用尽可能小的饼干来满足孩子,这样才能保留较大的饼干满足胃口更大的孩子。
g
和饼干尺寸数组 s
进行排序。class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); // 对孩子的胃口值进行排序 Arrays.sort(s); // 对饼干尺寸进行排序 int childIndex = 0, cookieIndex = 0; int count = 0; while (childIndex < g.length && cookieIndex < s.length) { if (g[childIndex] <= s[cookieIndex]) { // 如果当前饼干可以满足当前孩子的胃口,计数加一 count++; childIndex++; // 考虑下一个孩子 } cookieIndex++; // 取下一块饼干 } return count; } }
在柠檬水摊上,每一杯柠檬水的售价为 5
美元。顾客排队购买你的产品,(按账单 bills
支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5
美元、10
美元或 20
美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5
美元。注意,一开始你手头没有任何零钱。
给你一个整数数组 bills
,其中 bills[i]
是第 i
位顾客付的账。如果你能给每位顾客正确找零,返回 true
,否则返回 false
。
示例 1:
输入:bills = [5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。
示例 2:
输入:bills = [5,5,10,10,20]
输出:false
解释:
前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零,所以答案是 false。
问题关键在于如何有效管理手头的零钱,以确保能够为每位顾客正确找零。算法的基本思路是:尽量保留更多的 5
美元纸币,因为它们对找零来说更灵活。当顾客使用 20
美元时,优先使用 10
美元来找零(如果有的话),这样可以留下更多的 5
美元来应对未来的交易。
5
美元和 10
美元纸币数量。bills
数组。
5
美元,增加 5
美元纸币的数量。10
美元,检查是否有 5
美元纸币用于找零。如果有,则减少 5
美元的数量并增加 10
美元的数量;如果没有,则无法找零,返回 false
。20
美元,优先使用 10
美元和 5
美元的组合来找零(如果可能)。如果不可能,则尝试使用三张 5
美元纸币。如果两种方式都不可行,则返回 false
。true
。class Solution { public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; // 初始没有任何零钱 for (int bill : bills) { if (bill == 5) { five++; // 收到5美元,five增加 } else if (bill == 10) { if (five == 0) return false; // 没有5美元找零 five--; ten++; } else { // 优先使用10美元和5美元组合找零 if (five > 0 && ten > 0) { five--; ten--; } else if (five >= 3) { five -= 3; // 只能用三张5美元找零 } else { return false; // 无法找零 } } } return true; } }
给定一个区间的集合 intervals
,其中 intervals[i] = [starti, endi]
。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
基本思路是优先保留结束时间早的区间,因为这样留给其他区间的空间更多,从而减少重叠的可能性。按照区间的结束时间对所有区间进行排序,然后遍历区间集合,每次选择结束时间最早且与前一个选择的区间不重叠的区间。
class Solution { public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length == 0) return 0; // 按照区间的结束时间进行排序 Arrays.sort(intervals, (a, b) -> a[1] - b[1]); int end = intervals[0][1]; int count = 1; // 计数器,记录非重叠区间的数量 for (int[] interval : intervals) { if (interval[0] >= end) { // 如果当前区间的开始时间大于等于上一个区间的结束时间,更新end并计数 end = interval[1]; count++; } } return intervals.length - count; // 返回需要移除的区间数量 } }
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points
,其中points[i] = [xstart, xend]
表示水平直径在 xstart
和 xend
之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x
处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart
,xend
, 且满足 xstart ≤ x ≤ xend
,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。
给你一个数组 points
,返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1:
输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 6处射出箭,击破气球[2,8]和[1,6]。
- 在x = 11处发射箭,击破气球[10,16]和[7,12]。
示例 2:
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
示例 3:
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2]和[2,3]。
- 在x = 4处射出箭,击破气球[3,4]和[4,5]。
关键在于找出一种方式,使得每一支射出的弓箭能引爆尽可能多的气球。为此,我们可以将问题视为一个区间重叠的问题,其中每个气球代表一个区间。如果两个气球(区间)至少有一个共同点,那么一支弓箭就能引爆它们。
class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) return 0; // 根据每个气球的结束坐标进行排序 Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); int arrowPos = points[0][1]; // 第一支箭射在第一个气球的结束位置 int arrowCount = 1; for (int[] balloon : points) { // 如果当前气球的开始位置在上一支箭的射击位置之后,需要再射一支箭 if (balloon[0] > arrowPos) { arrowPos = balloon[1]; // 更新箭的位置到当前气球的结束位置 arrowCount++; } } return arrowCount; } }
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) return intervals; // 按照起始位置排序 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); LinkedList<int[]> merged = new LinkedList<>(); for (int[] interval : intervals) { // 如果列表为空,或者当前区间不与前一个区间重叠,直接添加 if (merged.isEmpty() || merged.getLast()[1] < interval[0]) { merged.add(interval); } else { // 否则,我们合并当前和前一个区间 merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); } }
在这个解法中,我们首先对区间进行排序,然后创建一个 LinkedList
来存储合并后的区间。通过遍历排序后的区间,我们逐一确定是否需要合并区间,或者将当前区间添加到结果列表中。最后,将 LinkedList
转换为二维数组并返回。
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
基本思路是在每一步中更新你所能到达的最远位置。遍历数组中的每个元素,如果当前位置可以达到,并且从这个位置可以跳到更远的地方,则更新最远可达位置。如果在某个时刻,这个最远位置超过或等于数组的最后一个下标,就意味着可以到达数组的末尾。
maxReach
,表示从当前位置或之前的任意位置可以达到的最远位置。maxReach
),则更新 maxReach
为当前位置加上该位置可跳跃的最大长度和 maxReach
本身中的较大者。maxReach
超过或等于数组的最后一个下标,则返回 true
。如果遍历结束 maxReach
未能达到或超过最后一个下标,则返回 false
。class Solution { public boolean canJump(int[] nums) { int maxReach = 0; // 最远可达位置初始化为0 for (int i = 0; i < nums.length; i++) { if (i > maxReach) { return false; // 当前位置不可达 } maxReach = Math.max(maxReach, i + nums[i]); // 更新最远可达位置 if (maxReach >= nums.length - 1) { return true; // 可以到达数组末尾 } } return false; } }
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
与判断是否能到达数组末尾的问题类似,这里的目标是计算到达数组末尾的最小跳跃次数。我们可以在每一步中贪心地选择能跳得最远的那个位置,同时计算跳跃次数。
初始化变量:
jumps
:跳跃次数,初始化为 0。maxReach
:当前跳跃可以达到的最远位置,初始化为 nums[0]
。end
:当前跳跃的结束位置,初始化为 nums[0]
。遍历数组:从第一个元素开始,遍历到倒数第二个元素(因为起始位置已经是 nums[0]
,且最后一个位置是我们的目标)。
更新最远可达位置:更新 maxReach
为当前位置加上该位置可跳跃的最大长度和 maxReach
本身中的较大者。
跳跃:如果到达了当前跳跃的结束位置,则增加跳跃次数,并将当前跳跃的结束位置更新为当前可以达到的最远位置。
返回结果:最后返回跳跃次数。
class Solution { public int jump(int[] nums) { if (nums.length <= 1) { return 0; } int jumps = 0, maxReach = nums[0], end = nums[0]; for (int i = 1; i < nums.length - 1; i++) { maxReach = Math.max(maxReach, i + nums[i]); if (i == end) { jumps++; end = maxReach; } } return jumps + 1; // 加上最初的一跳 } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。