134.加油站
在一条环路上有
n
个加油站,其中第i
个加油站有汽油gas[i]
升。你有一辆油箱容量无限的的汽车,从第
i
个加油站开往第i+1
个加油站需要消耗汽油cost[i]
升。你从其中的一个加油站出发,开始时油箱为空。给定两个整数数组
gas
和cost
,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回-1
。如果存在解,则 保证 它是 唯一 的。示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。 因此,3 可为起始索引。示例 2:
输入: gas = [2,3,4], cost = [3,4,3] 输出: -1 解释: 你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油 开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油 开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油 你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。 因此,无论怎样,你都不可能绕环路行驶一周。提示:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
- 输入保证答案唯一。
解题思路
问题核心:
- 有 n 个加油站,gas[i] 表示第 i 个加油站可加的油量,cost[i] 表示从第 i 到第 i+1 个加油站的耗油量。
- 油箱容量无限,初始为空,需找到一个起始站,使得汽车能绕环路一周(回到起点,油量非负)。
- 如果存在解,答案唯一;否则返回 -1。
贪心策略:
- 净油量计算:
- 对于每个加油站,计算净油量 res[i] = gas[i] - cost[i],表示在站 i 加完油并开往下一站后的油量变化。
- 如果总净油量 sum(res[i]) < 0,无法绕一周,返回 -1(因为总油量不足以覆盖总消耗)。
- 起始点选择:
- 使用 currSum 跟踪从某个起始点开始的累计净油量。
- 如果在某个点 i,currSum < 0,说明从当前起始点 start 到 i 的路径不可行,重置 start = i + 1,并清零 currSum。
- 继续遍历,直到检查所有站。
- 为什么贪心有效:
- 总油量检查:如果 sum(res[i]) >= 0,存在至少一个解(题目保证唯一)。
- 局部失败处理:如果从某个起点 start 到 i 的 currSum < 0,则 start 到 i 之间的任何点都不能作为起点(因为油量会更早变负)。
- 唯一解:题目保证如果解存在,则唯一。贪心算法通过排除不可行起点,找到唯一可行起点。
- 环形处理:
- 环形路径通过数组循环模拟(i+1 模 n),但你的代码通过单次遍历和总和检查隐式处理环形约束。
时间复杂度:
- 单遍遍历数组:O(n),其中 n 是 gas.length。
- 空间复杂度:O(n)(用于 res 数组),可优化为 O(1)(直接用 gas[i] - cost[i])。
代码
import java.util.*;class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 创建净油量数组,res[i] = gas[i] - cost[i]int[] res = new int[gas.length];// sum 记录总净油量,currSum 记录当前路径的净油量int sum = 0, currSum = 0;// start 记录潜在的起始加油站索引int start = 0;// 遍历所有加油站for (int i = 0; i < res.length; i++) {// 计算第 i 个加油站的净油量res[i] = gas[i] - cost[i];// 更新总净油量sum += res[i];// 更新当前路径净油量currSum += res[i];// 如果当前路径油量为负,当前起点不可行if (currSum < 0) {currSum = 0; // 重置当前路径油量start = i + 1; // 将起点移到下一个加油站}}// 如果总净油量 < 0,无法绕一周if (sum < 0) {return -1;}// 返回唯一可行起点(或 -1 如果 start 越界)return start;}
}
135.分发糖果
n
个孩子站成一排。给你一个整数数组ratings
表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
示例 1:
输入:ratings = [1,0,2] 输出:5 解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2:
输入:ratings = [1,2,2] 输出:4 解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。提示:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
解题思路
问题核心:
- 给定数组 ratings,ratings[i] 表示第 i 个孩子的评分。
- 分配规则:
- 每个孩子至少 1 颗糖果。
- 如果 ratings[i] > ratings[i-1],第 i 个孩子比第 i-1 个孩子多拿糖果。
- 如果 ratings[i] > ratings[i+1],第 i 个孩子比第 i+1 个孩子多拿糖果。
- 目标:最小化总糖果数。
贪心策略:
- 初始化:
- 为每个孩子分配 1 颗糖果(满足“至少 1 颗”)。
- 两次遍历:
- 从左到右:处理评分递增的情况。如果 ratings[i] > ratings[i-1],则 candies[i] = candies[i-1] + 1,确保左边邻居规则。
- 从右到左:处理评分递减的情况。如果 ratings[i] > ratings[i+1],则 candies[i] = max(candies[i], candies[i+1] + 1),确保右边邻居规则,并保留左遍历结果的最大值。
- 求和:累加 candies 数组,得到最小糖果数。
- 为什么贪心有效:
- 左遍历确保评分递增时糖果数递增,满足左侧约束。
- 右遍历修正评分递减的情况,确保右侧约束,同时取最大值避免破坏左遍历结果。
- 两次遍历综合考虑所有相邻关系,保证满足所有条件且糖果数最小。
时间复杂度:
- 初始化和两次遍历:O(n)。
- 求和:O(n)。
- 总计:O(n)。
空间复杂度:
- O(n)(candies 数组)。
代码
import java.util.*;class Solution {public int candy(int[] ratings) {// 获取数组长度int n = ratings.length;// 初始化糖果数组,每个孩子至少 1 颗糖果int[] candies = new int[n];Arrays.fill(candies, 1);// 从左到右遍历:处理评分递增情况for (int i = 1; i < n; i++) {// 如果当前孩子评分高于前一个,分配更多糖果if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历:处理评分递减情况for (int i = n - 2; i >= 0; i--) {// 如果当前孩子评分高于后一个,确保糖果数大于后一个if (ratings[i] > ratings[i + 1]) {// 取当前糖果数和后一个糖果数+1的最大值,保留左遍历结果candies[i] = Math.max(candies[i], candies[i + 1] + 1);}}// 计算总糖果数int sum = 0;for (int candy : candies) {sum += candy;}return sum;}
}
860.柠檬水找零
在柠檬水摊上,每一杯柠檬水的售价为
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。提示:
1 <= bills.length <= 105
bills[i]
不是5
就是10
或是20
解题思路
问题核心:
- 每位顾客支付 5、10 或 20 美元,购买一杯 5 美元的柠檬水,需找回 bill - 5 美元。
- 初始没有零钱,只能用收到的钞票找零。
- 目标:判断是否能为所有顾客正确找零,返回 true 或 false。
贪心策略:
- 跟踪零钱:
- 只需跟踪 5 美元和 10 美元钞票的数量(five 和 ten),因为 20 美元钞票无法用于找零(题目中找零只涉及 5 美元和 10 美元)。
- 处理每种账单:
- 5 美元:直接收下,增加 five++,无需找零。
- 10 美元:需找回 5 美元(10 - 5),消耗 1 张 5 美元钞票(five--),增加 1 张 10 美元钞票(ten++)。如果 five == 0,无法找零,返回 false。
- 20 美元:需找回 15 美元(20 - 5),有两种找零方式:
- 优先用 1 张 10 美元 + 1 张 5 美元(ten--, five--),以保留更多 5 美元钞票(因为 5 美元更灵活)。
- 如果没有 10 美元钞票,尝试用 3 张 5 美元(five -= 3)。
- 如果两者都不可行,返回 false。
- 为什么贪心有效:
- 优先使用 10 美元 + 5 美元找零 20 美元,减少对 5 美元钞票的消耗,因为 5 美元钞票对后续找零(10 美元或 20 美元)更关键。
- 每次决策局部最优(保留最多 5 美元钞票),确保全局可行性。
- 如果某次无法找零,说明零钱不足,返回 false;否则,遍历完成返回 true。
时间复杂度:
- 单遍遍历 bills 数组:O(n),其中 n 是 bills.length。
- 总计:O(n)。
空间复杂度:
- O(1),仅使用两个变量(five 和 ten)。
代码
class Solution {public boolean lemonadeChange(int[] bills) {// 初始化 5 美元和 10 美元钞票数量int five = 0, ten = 0;// 遍历每位顾客支付的账单for (int bill : bills) {if (bill == 5) {// 收到 5 美元,无需找零,增加 5 美元钞票数量five++;} else if (bill == 10) {// 收到 10 美元,需找回 5 美元if (five == 0) {// 没有 5 美元钞票,无法找零return false;}five--; // 消耗 1 张 5 美元钞票ten++; // 增加 1 张 10 美元钞票} else { // bill == 20// 收到 20 美元,需找回 15 美元if (ten > 0 && five > 0) {// 优先用 1 张 10 美元 + 1 张 5 美元找零ten--;five--;} else if (five >= 3) {// 否则用 3 张 5 美元找零five -= 3;} else {// 无法找零return false;}}}// 所有顾客都成功找零return true;}
}
406.根据身高重建队列
假设有打乱顺序的一群人站成一个队列,数组
people
表示队列中一些人的属性(不一定按顺序)。每个people[i] = [hi, ki]
表示第i
个人的身高为hi
,前面 正好 有ki
个身高大于或等于hi
的人。请你重新构造并返回输入数组
people
所表示的队列。返回的队列应该格式化为数组queue
,其中queue[j] = [hj, kj]
是队列中第j
个人的属性(queue[0]
是排在队列前面的人)。示例 1:
输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释: 编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。示例 2:
输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]提示:
1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
- 题目数据确保队列可以被重建
解题思路
问题核心:
- 给定数组 people,people[i] = [hi, ki] 表示第 i 个人身高为 hi,前面有 ki 个身高大于或等于 hi 的人。
- 目标是构造队列 queue,使得 queue[j] = [hj, kj] 表示队列第 j 位的属性,且满足 ki 条件。
- 题目保证队列可被重建,解唯一。
贪心策略:
- 排序:
- 按身高 hi 降序排序,若身高相同,则按 ki 升序排序。
- 理由:身高高的人应先安排,因为他们的 ki 表示前面高或等高的人数,优先处理高个子可以简化后续插入(矮个子的 ki 不会受高个子影响)。
- 身高相同按 ki 升序,确保 ki 较小的人先插入(因为他们需要更靠前的位置)。
- 插入:
- 遍历排序后的 people,将每个 person = [hi, ki] 插入到结果队列的索引 ki 处。
- 插入时,ki 表示前面应有 ki 个高或等高的人。由于已按身高降序排序,之前插入的人身高大于或等于当前 hi,插入到 ki 位置正好满足条件。
- 使用动态列表(ArrayList)支持按索引插入,插入后队列自动调整。
- 转换为数组:
- 将动态列表转换为 int[][] 数组返回。
- 为什么贪心有效:
- 按身高降序排序确保高个子优先安排,矮个子插入时不会影响高个子的 ki(因为矮个子身高小于之前的人)。
- 按 ki 插入保证每个人的 ki 约束(前面正好有 ki 个高或等高的人)。
- 题目保证解存在,排序和插入策略确保唯一正确队列。
时间复杂度:
- 排序:O(n log n),其中 n 是 people.length。
- 插入:ArrayList 的插入操作为 O(n),总共 n 次插入,O(n²)。
- 总计:O(n²)(插入操作主导)。
空间复杂度:
- O(n)(queue 列表,不计输出数组)。
代码
import java.util.*;class Solution {public int[][] reconstructQueue(int[][] people) {// 按身高降序排序,若身高相同则按 ki 升序排序Arrays.sort(people, (a, b) -> {if (a[0] != b[0]) return b[0] - a[0]; // 身高降序(高的先处理)return a[1] - b[1]; // 身高相同,ki 升序(小的 ki 先插入)});// 使用动态列表存储重建的队列List<int[]> queue = new ArrayList<>();// 遍历排序后的数组,按 ki 插入到正确位置for (int[] person : people) {queue.add(person[1], person); // 在索引 person[1](ki)处插入 person}// 将列表转换为 int[][] 数组return queue.toArray(new int[people.length][]);}
}