节能网站源码,创欧科技 网站建设,昆明php网站建设,中山做外贸网站建设1.贪心算法
贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。
如何能看出局部最优是否能推出整体最优
靠自己手动模拟#xff0c;如果模拟可行#xff0c;就可以试一试贪心策略#xff0c;如果不可行#xff0c;可能需要动态规划。
如何验证可不可以…1.贪心算法
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
如何能看出局部最优是否能推出整体最优
靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。
如何验证可不可以用贪心算法
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
可有有同学认为手动模拟举例子得出的结论不靠谱想要严格的数学证明。
一般数学证明有如下两种方法
数学归纳法反证法
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
2.分发饼干
力扣题目链接(opens new window)
假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 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.
提示
1 g.length 3 * 10^40 s.length 3 * 10^41 g[i], s[j] 2^31 - 1
public class Distribute_Cookies {public int findContentChildren1(int[] g, int[] s) {//接受两个整数数组 g 和 s 作为参数分别表示孩子们的满足度和饼干的大小返回能满足的孩子的最大数量。Arrays.sort(g);//对孩子们的满足度数组 g 进行升序排序。排序后满足度低的孩子会排在前面方便后续依次尝试为他们分配饼干。Arrays.sort(s);//对饼干的大小数组 s 进行升序排序。排序后小的饼干会排在前面优先满足满足度低的孩子。int start 0;//用于跟踪 g 数组中当前考虑的孩子的索引初始值为 0表示从满足度最低的孩子开始考虑。int count 0;//用于计数成功满足的孩子的数量初始值为 0。for (int i 0; i s.length start g.length; i) {//遍历饼干数组s同时确保不超过g数组的长度。这个循环确保我们考虑每个饼干并尝试找到一个满足度匹配或更高的孩子。if (s[i] g[start]) {//如果当前饼干的大小s[i]大于或等于当前孩子的满足度g[start]则表示这个孩子可以被这个饼干满足。start;//将 start 加 1指向下一个孩子准备为下一个孩子寻找合适的饼干。count;//将满足的孩子数量加 1。}}return count;//循环结束后count 中存储的就是能满足的孩子的最大数量将其返回。}
}
假设 g [1, 2, 3]s [1, 1]
排序后g [1, 2, 3]s [1, 1]。初始化 start 0count 0。进入 for 循环 当 i 0 时s[0] 1g[0] 1s[0] g[0] 成立start 变为 1count 变为 1。当 i 1 时s[1] 1g[1] 2s[1] g[1] 不成立不执行 start 和 count。循环结束返回 count即 1表示最多能满足 1 个孩子。
再假设 g [1, 2]s [1, 2, 3]
排序后g [1, 2]s [1, 2, 3]。初始化 start 0count 0。进入 for 循环 当 i 0 时s[0] 1g[0] 1s[0] g[0] 成立start 变为 1count 变为 1。当 i 1 时s[1] 2g[1] 2s[1] g[1] 成立start 变为 2count 变为 2。循环结束返回 count即 2表示最多能满足 2 个孩子。
通过这种方式代码通过排序和遍历有效地找出了最多能满足的孩子数量。
3.摆动序列
力扣题目链接(opens new window)
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。
例如 [1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
给定一个整数序列返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]输出: 6解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]输出: 7解释: 这个序列包含几个长度为 7 摆动序列其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]输出: 2
public class Oscillating_Sequence {public int wiggleMaxLength1(int[] nums) {//接受一个整数数组 nums 作为参数返回该数组中摆动序列的最大长度。if (nums.length 1) {//单个元素或空数组本身就是摆动序列。return nums.length;//如果数组 nums 的长度小于等于 1那么这个数组本身就是一个摆动序列直接返回数组的长度。}int curDiff 0; //表示当前元素与前一个元素的差值初始值为 0。int preDiff 0;//表示前一个元素与前前一个元素的差值初始值为 0。int count 1;//表示摆动序列的长度由于至少包含第一个元素所以初始值为 1。for (int i 1; i nums.length; i) {//从第二个元素开始遍历数组。curDiff nums[i] - nums[i - 1];//计算当前元素与前一个元素的差值。if ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) {//检查当前差值和上一个差值的符号是否相反一正一负或者当前差值不为0而上一个差值为0初始情况。count;//如果满足条件将摆动序列的长度 count 加 1。preDiff curDiff;//将当前差值赋值给上一个差值为下一次迭代做准备。}}return count;//循环结束后count 中存储的就是数组 nums 中摆动序列的最大长度将其返回。}
}
假设输入数组 nums [1, 7, 4, 9, 2, 5]
初始化curDiff 0preDiff 0count 1。第一次循环i 1curDiff 7 - 1 6preDiff 0满足 curDiff 0 preDiff 0count 变为 2preDiff 变为 6。第二次循环i 2curDiff 4 - 7 -3preDiff 6满足 curDiff 0 preDiff 0count 变为 3preDiff 变为 -3。第三次循环i 3curDiff 9 - 4 5preDiff -3满足 curDiff 0 preDiff 0count 变为 4preDiff 变为 5。第四次循环i 4curDiff 2 - 9 -7preDiff 5满足 curDiff 0 preDiff 0count 变为 5preDiff 变为 -7。第五次循环i 5curDiff 5 - 2 3preDiff -7满足 curDiff 0 preDiff 0count 变为 6preDiff 变为 3。
最终返回 count即 6表示数组 [1, 7, 4, 9, 2, 5] 中摆动序列的最大长度是 6。
4.最大子序和
力扣题目链接(opens new window)
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
public class Maximum_Subarray_Sum {public int maxSubArray1(int[] nums) {//接受一个整数数组nums作为参数返回该数组中的最大子序和。if (nums.length 1){//只有一个元素那么最大子序和就是该元素本身直接返回。return nums[0];}int sum Integer.MIN_VALUE;//用于存储最大子序和初始值设为Integer.MIN_VALUE这样可以确保任何数组元素都比它大方便后续更新最大子序和。int count 0;//用于存储当前子序的和初始值为0。for (int i 0; i nums.length; i){//从数组的第一个元素索引为 0开始遍历到最后一个元素。count nums[i];//将当前元素加到当前子序和中不断累加以计算包含当前元素的子序和。sum Math.max(sum, count);//如果当前子序和大于已知的最大子序和则更新最大子序和。if (count 0){//如果当前子序和小于等于0说明继续累加只会使和更小因此重置当前子序和为0从下一个元素开始新的子序。count 0;}}return sum;//循环结束后sum中存储的就是数组nums中的最大子序和将其返回。}
}
假设输入数组nums [-2, 1, -3, 4, -1, 2, 5, -3]
初始化sum Integer.MIN_VALUEcount 0。第一次循环i 0count count (-2) -2sum Math.max(Integer.MIN_VALUE, -2) -2因为count -2 0所以count 0。第二次循环i 1count count 1 1sum Math.max(-2, 1) 1count 1 0count保持为 1。第三次循环i 2count 1 (-3) -2sum Math.max(1, -2) 1因为count -2 0所以count 0。第四次循环i 3count 0 4 4sum Math.max(1, 4) 4count 4 0count保持为 4。第五次循环i 4count 4 (-1) 3sum Math.max(4, 3) 4count 3 0count保持为 3。第六次循环i 5count 3 2 5sum Math.max(4, 5) 5count 5 0count保持为 5。第七次循环i 6count 5 5 10sum Math.max(5, 10) 10count 10 0count保持为 10。第八次循环i 7count 10 (-3) 7sum Math.max(10, 7) 10count由于大于 0 保持不变。
最终返回sum即 10这就是数组[-2, 1, -3, 4, -1, 2, 5, -3]中的最大子序和。
5.买卖股票的最佳时机 II
力扣题目链接(opens new window)
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1:
输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。
示例 2:
输入: [1,2,3,4,5]输出: 4解释: 在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4 。注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示
1 prices.length 3 * 10 ^ 40 prices[i] 10 ^ 4
public class The_Best_Time_to_Buy_and_Sell_StocksII {public int maxProfit1(int[] prices) {//接受一个整数数组prices作为参数该数组表示每天的股票价格返回在这些价格序列下进行多次买卖所能获得的最大利润。int result 0;//用于累积所有交易的总利润初始值为 0。for (int i 1; i prices.length; i) {//从数组的第二个元素索引为 1开始遍历到最后一个元素。这是因为我们需要比较当前天的价格prices[i]和前一天的价格prices[i - 1]所以i从 1 开始。result Math.max(prices[i] - prices[i - 1], 0);//计算当前天的股票价格与前一天的股票价格之差这个差值表示如果在第i - 1天买入在第i天卖出所能获得的利润。并使用Math.max函数来确保这个差值不会是负数。如果差值是正数表示卖出价格高于买入价格说明第i天的价格高于第i - 1天的价格在这种情况下进行一次买卖可以获得利润就将这个利润值累加到result中如果差值是负数表示卖出价格低于买入价格进行这次买卖会亏损为了保证总利润不减少这里取 0即不进行这次买卖。每次循环都会将这个计算得到的利润或者 0加到result变量上从而不断累积总利润。}return result;//循环结束后result中存储的就是在给定的股票价格序列下进行多次买卖所能获得的最大利润将其返回。}
}
假设输入数组prices [7, 1, 5, 3, 6, 4]
第一次循环i 1prices[1] - prices[0] 1 - 7 -6Math.max(-6, 0) 0result 0 0 0。第二次循环i 2prices[2] - prices[1] 5 - 1 4Math.max(4, 0) 4result 0 4 4。第三次循环i 3prices[3] - prices[2] 3 - 5 -2Math.max(-2, 0) 0result 4 0 4。第四次循环i 4prices[4] - prices[3] 6 - 3 3Math.max(3, 0) 3result 4 3 7。第五次循环i 5prices[5] - prices[4] 4 - 6 -2Math.max(-2, 0) 0result 7 0 7。
最终返回result即 7这就是在股票价格序列[7, 1, 5, 3, 6, 4]下进行多次买卖所能获得的最大利润。这种方法的核心思想是只要当天价格比前一天高就进行一次买卖通过不断累加这些小的利润来获得最大总利润。
6.跳跃游戏
力扣题目链接(opens new window)
给定一个非负整数数组你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]输出: true解释: 我们可以先跳 1 步从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]输出: false解释: 无论怎样你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 所以你永远不可能到达最后一个位置。
public class Jump_Game {public boolean canJump(int[] nums) {//接受一个整数数组 nums 作为参数返回一个布尔值表示是否能够通过跳跃到达数组的末尾。if (nums.length 1) {//数组只有一个元素那么不需要跳跃直接返回true。return true;}int coverRange 0;//存储当前能够到达的最远位置。初始值为 0表示从数组的第一个位置开始。for (int i 0; i coverRange; i) {//从数组的第一个元素开始遍历只要当前索引 i 不超过当前能够到达的最远位置 coverRange就继续循环。coverRange Math.max(coverRange, i nums[i]);//对于每个索引 ii nums[i] 表示从当前位置 i 出发最多能够跳跃到的位置。通过 Math.max 函数取 coverRange 和 i nums[i] 中的较大值更新 coverRange即当前能够到达的最远位置。if (coverRange nums.length - 1) {//每次更新 coverRange 后检查 coverRange 是否大于或等于数组的最后一个元素的索引nums.length - 1。如果是说明可以通过跳跃到达数组的末尾直接返回 true。return true;}}return false;//如果 for 循环结束后仍然没有满足 coverRange nums.length - 1 的条件说明无法通过跳跃到达数组的末尾返回 false。}}
假设输入数组 nums [2, 3, 1, 1, 4]
初始化coverRange 0。第一次循环i 0i nums[i] 0 2 2coverRange Math.max(0, 2) 2。此时 coverRange nums.length - 1继续循环。第二次循环i 1i nums[i] 1 3 4coverRange Math.max(2, 4) 4。此时 coverRange nums.length - 1因为 nums.length - 1 4返回 true。
再假设输入数组 nums [3, 2, 1, 0, 4]
初始化coverRange 0。第一次循环i 0i nums[i] 0 3 3coverRange Math.max(0, 3) 3。此时 coverRange nums.length - 1继续循环。第二次循环i 1i nums[i] 1 2 3coverRange Math.max(3, 3) 3。第三次循环i 2i nums[i] 2 1 3coverRange Math.max(3, 3) 3。第四次循环i 3i nums[i] 3 0 3coverRange Math.max(3, 3) 3。此时 coverRange nums.length - 1循环结束。最终返回 false因为无法到达数组末尾。
通过这种方式代码能够有效地判断在给定的跳跃规则下是否能够到达数组的末尾。
7.跳跃游戏 II
力扣题目链接(opens new window)
给定一个非负整数数组你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
public class Jump_GameII {public int jump2(int[] nums) {//接受一个整数数组 nums 作为参数返回从数组第一个元素跳到最后一个元素所需的最少跳跃次数。int result 0;//用来记录跳跃的次数。int end 0; // 当前覆盖的最远距离下标int temp 0; // 下一步覆盖的最远距离下标for (int i 0; i end end nums.length - 1; i) {//循环会在到达最远位置或者到达数组末尾时停止。for 循环的条件是 i end end nums.length - 1。i end 确保当前遍历的位置 i 在当前能够覆盖的范围内end nums.length - 1 表示当前覆盖的最远距离还没有到达数组的末尾。只要这两个条件都满足循环就会继续执行。temp Math.max(temp, i nums[i]);//对于每个索引 ii nums[i] 表示从当前位置 i 出发最多能够跳跃到的位置。通过 Math.max 函数取 temp 和 i nums[i] 中的较大值更新 temp即记录下一步可能覆盖的最远距离下标。if (i end) {//当 i 等于 end 时说明已经走到了当前步骤能够到达的最远位置。此时将 end 更新为 temp即更新当前覆盖的最远距离下标。同时将跳跃次数 result 加 1表示进行了一次新的跳跃。end temp;result;}}return result;//循环结束后result 中存储的就是从数组第一个元素跳到最后一个元素所需的最少跳跃次数将其返回。}
}
假设输入数组 nums [2, 3, 1, 1, 4]
初始化result 0end 0temp 0。第一次循环i 0i nums[i] 0 2 2temp Math.max(0, 2) 2。此时 i end 成立end temp 2result 1。第二次循环i 1i nums[i] 1 3 4temp Math.max(2, 4) 4。此时 i! end不执行更新 end 和 result 的操作。第三次循环i 2i nums[i] 2 1 3temp Math.max(4, 3) 4。此时 i end 成立end temp 4result 2。循环结束因为 end nums.length - 1返回 result即 2。这表示从数组第一个元素跳到最后一个元素最少需要跳跃 2 次。
8.K次取反后最大化的数组和
给定一个整数数组 A我们只能用以下方法修改该数组我们选择某个索引 i 并将 A[i] 替换为 -A[i]然后总共重复这个过程 K 次。我们可以多次选择同一个索引 i。
以这种方式修改数组后返回数组可能的最大和。
示例 1
输入A [4,2,3], K 1输出5解释选择索引 (1) 然后 A 变为 [4,-2,3]。
示例 2
输入A [3,-1,0,2], K 3输出6解释选择索引 (1, 2, 2) 然后 A 变为 [3,1,0,2]。
示例 3
输入A [2,-3,-1,5,-4], K 2输出13解释选择索引 (1, 4) 然后 A 变为 [2,3,-1,5,4]。
提示
1 A.length 100001 K 10000-100 A[i] 100
public class Maximum_Sum_of_Array_After_K_Negations {public int largestSumAfterKNegations2(int[] nums, int k) {//接受一个整数数组 nums 和一个整数 k 作为参数k 表示可以对数组元素进行取反操作的次数。方法返回经过 k 次取反操作后数组的最大和。if (nums.length 1) return nums[0];//如果数组只有一个元素那么不需要进行任何取反操作直接返回该元素作为最大和。Arrays.sort(nums);//对数组 nums 进行升序排序。这样做的目的是将数组中的负数排在前面因为对负数进行取反操作可以使数组的和增大。for (int i 0; i nums.length k 0; i) {//检查k是否大于0即是否还有取反操作的机会。for 循环用于遍历数组 nums同时检查是否还有剩余的取反操作次数k 0。if (nums[i] 0) {//检查当前元素是否为负数。如果是那么将当前元素取反负数变正数并将k减1。nums[i] -nums[i];k--;}}if (k % 2 1) {//循环结束后如果k是奇数这意味着我们还需要进行一次取反操作。这行代码再次对数组进行排序以便找到最小的元素可能是负数或正数然后将其取反以最大化数组的和。这是因为对最小的元素取反无论它是正数还是负数对总和的影响最小从而可以保证最终的和是最大的。Arrays.sort(nums);nums[0] -nums[0];}int sum 0;//初始化一个变量 sum 为 0用于存储数组的和。for (int num : nums) {//使用增强型 for 循环遍历数组 nums将每个元素累加到 sum 中。sum num;}return sum;//最后返回 sum即经过 k 次取反操作后数组的最大和。}
}
假设输入数组 nums [-4, -2, -3]k 4
首先数组只有一个元素的情况不满足继续执行。对数组进行排序nums 变为 [-4, -3, -2]。进入 for 循环 当 i 0 时nums[0] -4 0nums[0] -(-4) 4k 4 - 1 3。当 i 1 时nums[1] -3 0nums[1] -(-3) 3k 3 - 1 2。当 i 2 时nums[2] -2 0nums[2] -(-2) 2k 2 - 1 1。for 循环结束后k 1k % 2 1 成立。再次对数组进行排序nums 变为 [2, 3, 4]。将 nums[0] 取反nums[0] -2此时 nums 变为 [-2, 3, 4]。计算数组的和sum -2 3 4 5返回 5。
通过以上步骤代码能够有效地计算出经过 k 次取反操作后数组的最大和。
9. 加油站
力扣题目链接(opens new window)
在一条环路上有 N 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -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 的环形数组当访问索引 n 时实际上会回到索引 0 的位置访问索引 n 1 时会对应到索引 1 的位置。
(i 1) % gas.length 这一操作就是用于实现环形数组索引的关键。 当 i 1 未超过数组长度时 假设 gas.length 为 5当 i 2 时i 1 3此时 (i 1) % gas.length 3 % 5 3这个结果就是正常的下一个索引位置符合我们在普通数组中访问下一个元素的逻辑。 当 i 1 超过数组长度时 对于一个长度为 5 的数组有效的索引是 0、1、2、3、4。 当 i 4 时i 1 5这个 5 在常规数组索引的语境下是超过了有效范围的。 同样假设 gas.length 为 5当 i 4 时i 1 5而 (i 1) % gas.length 5 % 5 0。这里通过取模运算使得索引回到了数组的开头实现了环形数组的特性。
当 curSum 0 时需要将起点索引 index 更新为下一个加油站的索引。由于是环形路线当 i 已经是数组的最后一个元素即 i gas.length - 1时下一个加油站的索引应该是 0。通过 (i 1) % gas.length 这种取模运算无论 i 处于什么位置都能正确地计算出下一个加油站在环形数组中的索引确保程序能够正确地遍历整个环形路线来寻找合适的起点。
public class gas_station {public int canCompleteCircuit2(int[] gas, int[] cost) {//接受两个整数数组gas和cost作为参数分别表示每个加油站的汽油量和从该加油站到下一个加油站的消耗量。方法返回能够完成环形路线的起点索引如果不存在则返回 - 1。int curSum 0;//用于记录当前起点开始的累计油量差油量减去消耗量。int totalSum 0;//用于记录整个环形路线上的总油量差。int index 0;//用于记录当前的起点索引。for (int i 0; i gas.length; i) {//在for循环中对于每个加油站i计算从该加油站获得的汽油量gas[i]减去行驶到下一个加油站的消耗量cost[i]并将结果累加到curSum和totalSum中。curSum表示从当前假设的起点开始到当前加油站的累计油量差totalSum表示整个环形路线的总油量差。curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if (curSum 0) {//如果 curSum 小于0说明从当前起点开始的油量不足以到达下一个加油站此时需要更换起点。index (i 1) % gas.length ;//更新起点索引 index 为下一个加油站使用取模运算(i 1) % gas.length是为了确保索引在环形数组的范围内即如果i 1超过了数组的长度会回到数组的开头。。curSum 0;//将curSum重置为 0因为从新的起点开始重新计算累计油量差。}}if (totalSum 0) return -1;//如果totalSum小于 0说明整个环形路线上的总汽油量小于总消耗量无论从哪个起点出发汽车都无法完成一圈的行驶因此返回 - 1。return index;//如果totalSum大于或等于 0说明至少存在一个起点可以让汽车完成整个环形路线。此时index记录的就是这样一个起点的索引将其返回。}
}
假设gas [1, 2, 3, 4, 5]cost [3, 4, 5, 1, 2]
初始化curSum 0totalSum 0index 0。第一次循环i 0curSum 1 - 3 -2totalSum -2。因为curSum 0index (0 1) % 5 1curSum 0。第二次循环i 1curSum 2 - 4 -2totalSum -2 (-2) -4。因为curSum 0index (1 1) % 5 2curSum 0。第三次循环i 2curSum 3 - 5 -2totalSum -4 (-2) -6。因为curSum 0index (2 1) % 5 3curSum 0。第四次循环i 3curSum 4 - 1 3totalSum -6 3 -3。curSum 0继续循环。第五次循环i 4curSum 5 - 2 3totalSum -3 3 0。循环结束totalSum 0不小于 0返回index即3。这表示从索引为 3 的加油站出发可以完成环形路线。
通过这种方式代码有效地判断了是否存在能够完成环形路线的起点并找到了这个起点的索引。 10.分发糖果
力扣题目链接(opens new window)
老师想给孩子们分发糖果有 N 个孩子站成了一条直线老师会根据每个孩子的表现预先给他们评分。
你需要按照以下要求帮助老师给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻的孩子中评分高的孩子必须获得更多的糖果。
那么这样下来老师至少需要准备多少颗糖果呢
示例 1:
输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]输出: 4解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这已满足上述两个条件。
public class distribute_candies {public int candy(int[] ratings) {//接受一个整数数组 ratings 作为参数该数组表示每个孩子的评分。方法返回分配给所有孩子的糖果总数。int len ratings.length;//len 变量存储数组 ratings 的长度。int[] candyVec new int[len];//整数数组用于存储每个孩子应该获得的糖果数量初始长度与 ratings 相同。candyVec[0] 1;//第一个孩子至少获得 1 个糖果。for (int i 1; i len; i) {//从第二个孩子开始遍历到数组的末尾。对于每个孩子 i如果他们的评分 ratings[i] 高于前一个孩子 ratings[i - 1]那么这个孩子将获得比前一个孩子多 1 个糖果即 candyVec[i - 1] 1否则这个孩子至少获得 1 个糖果。candyVec[i] (ratings[i] ratings[i - 1]) ? candyVec[i - 1] 1 : 1;}for (int i len - 2; i 0; i--) {//从倒数第二个孩子开始遍历到第一个孩子。对于每个孩子如果他们的评分高于后一个孩子他们将获得至少比后一个孩子多一个糖果以确保后一个孩子不能偷走超过一半的糖果。if (ratings[i] ratings[i 1]) {//Math.max 函数是为了确保在更新 candyVec[i] 时不会破坏之前从左到右遍历所确定的糖果数量关系。例如如果之前从左到右遍历确定 candyVec[i] 已经比较大了而从右到左遍历时需要根据当前条件调整 candyVec[i]那么取两者中的较大值以满足所有的条件。candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}int ans 0;//将每个孩子获得的糖果数量累加到 ans 变量中。for (int num : candyVec) {//使用增强型 for 循环遍历 candyVec 数组将每个孩子获得的糖果数量累加到 ans 中。ans num;}return ans;//最后返回 ans即分配给所有孩子的糖果总数。}
}
假设输入数组 ratings [1, 2, 2]
初始化len 3candyVec [1,?,?]。第一次遍历从左到右 当 i 1 时ratings[1] 2 ratings[0] 1所以 candyVec[1] candyVec[0] 1 2。当 i 2 时ratings[2] 2 ratings[1] 2所以 candyVec[2] 1。此时 candyVec [1, 2, 1]。第二次遍历从右到左 当 i 1 时ratings[1] 2 ratings[2] 2 不成立不更新 candyVec[1]。当 i 0 时ratings[0] 1 ratings[1] 2 不成立不更新 candyVec[0]。此时 candyVec 仍然是 [1, 2, 1]。计算总糖果数ans 1 2 1 4返回 4。
再假设输入数组 ratings [1, 3, 2, 2, 1]
初始化len 5candyVec [1,?,?]。第一次遍历从左到右 当 i 1 时ratings[1] 3 ratings[0] 1所以 candyVec[1] candyVec[0] 1 2。当 i 2 时ratings[2] 2 ratings[1] 3所以 candyVec[2] 1。当 i 3 时ratings[3] 2 ratings[2] 2所以 candyVec[3] 1。当 i 4 时ratings[4] 1 ratings[3] 2所以 candyVec[4] 1。此时 candyVec [1, 2, 1, 1, 1]。第二次遍历从右到左 当 i 3 时ratings[3] 2 ratings[4] 1所以 candyVec[3] Math.max(candyVec[3], candyVec[4] 1) 2。当 i 2 时ratings[2] 2 ratings[3] 2 不更新 candyVec[2]。当 i 1 时ratings[1] 3 ratings[2] 2所以 candyVec[1] Math.max(candyVec[1], candyVec[2] 1) 3。当 i 0 时ratings[0] 1 ratings[1] 3 不更新 candyVec[0]。此时 candyVec [1, 3, 1, 2, 1]。计算总糖果数ans 1 3 1 2 1 8返回 8。 11.柠檬水找零
力扣题目链接(opens new window)
在柠檬水摊上每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。
每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。
注意一开始你手头没有任何零钱。
如果你能给每位顾客正确找零返回 true 否则返回 false 。
示例 1
输入[5,5,5,10,20]输出true解释 前 3 位顾客那里我们按顺序收取 3 张 5 美元的钞票。第 4 位顾客那里我们收取一张 10 美元的钞票并返还 5 美元。第 5 位顾客那里我们找还一张 10 美元的钞票和一张 5 美元的钞票。由于所有客户都得到了正确的找零所以我们输出 true。
示例 2
输入[5,5,10]输出true
示例 3
输入[10,10]输出false
示例 4
输入[5,5,10,10,20]输出false解释 前 2 位顾客那里我们按顺序收取 2 张 5 美元的钞票。对于接下来的 2 位顾客我们收取一张 10 美元的钞票然后返还 5 美元。对于最后一位顾客我们无法退回 15 美元因为我们现在只有两张 10 美元的钞票。由于不是每位顾客都得到了正确的找零所以答案是 false。
提示
0 bills.length 10000bills[i] 不是 5 就是 10 或是 20
public class Lemonade_Change {public boolean lemonadeChange(int[] bills) {//接受一个整数数组 bills 作为参数该数组表示顾客支付的一系列钞票面额。方法返回一个布尔值true 表示可以给所有顾客正确找零false 表示无法完成所有顾客的找零。int five 0, ten 0;//用于记录5元钞票的数量,用于记录10元钞票的数量。for (int bill : bills) {//循环会遍历每一个顾客支付的钞票对每张钞票进行相应的找零处理。if (bill 5) {//如果 bill 的值为 5说明顾客支付了一张 5 元钞票。此时将 five 变量的值加 1表示我们现在拥有的 5 元钞票数量增加了一张。因为收到 5 元钞票不需要找零直接增加 5 元钞票的储备。five;} else if (bill 10) {//当 bill 的值为 10 时说明顾客支付了一张 10 元钞票。由于柠檬水售价假设为 5 元需要找零 5 元。if (five 0) {//首先检查 five 是否为 0如果 five 为 0即没有 5 元钞票用于找零那么无法完成这次找零直接返回 false。return false;}//如果有 5 元钞票five 0则将 five 的值减 1表示用掉了一张 5 元钞票用于找零同时将 ten 的值加 1表示收到了一张 10 元钞票。five--;ten;} else {//如果顾客支付的是20元钞票有两种情况可以找零如果有一张10元钞票和至少一张5元钞票减少一张10元钞票和一张5元钞票。如果没有10元钞票但至少有三张5元钞票减少三张5元钞票。如果以上两种情况都不满足返回 false 表示无法完成找零。if (five 0 ten 0) {five--;ten--;} else if (five 3) {five - 3;} else {return false;}}}return true;//如果整个 for 循环顺利结束没有因为无法找零而返回 false说明可以给所有顾客正确找零此时返回 true。}
}
假设输入 bills [5, 5, 10, 20]
当 bill 5 时five 变为 1ten 为 0。当 bill 5 时five 变为 2ten 为 0。当 bill 10 时five 变为 1ten 变为 1。当 bill 20 时因为有一张 10 元钞票和一张 5 元钞票five 变为 0ten 变为 0。循环结束返回 true。
假设输入 bills [5, 5, 10, 10, 20]
当 bill 5 时five 变为 1ten 为 0。当 bill 5 时five 变为 2ten 为 0。当 bill 10 时five 变为 1ten 变为 1。当 bill 10 时five 变为 0ten 变为 2。当 bill 20 时既没有一张 10 元钞票和一张 5 元钞票的组合也没有三张 5 元钞票返回 false。
12.根据身高重建队列
力扣题目链接(opens new window)
假设有打乱顺序的一群人站成一个队列数组 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 20000 hi 10^60 ki people.length
题目数据确保队列可以被重建
public class Reconstruct_Queue_by_Height {//接受一个二维整数数组 people 作为参数其中每个元素 people[i] 是一个包含两个整数的数组people[i][0] 表示第 i 个人的身高people[i][1] 表示第 i 个人在队列中的相对位置即前面有多少个身高大于或等于他的人。方法返回一个重建后的二维数组表示正确的队列顺序。public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) - {//Arrays.sort方法对people数组进行排序。这里使用了lambda表达式来定义比较器。在比较器中如果两个人的身高相同a[0] b[0]则根据他们的相对位置a[1]和b[1]进行升序排序。这是因为身高相同的人相对位置小的应该排在前面。如果两个人的身高不同则根据身高进行降序排序。这是因为身高较高的人会影响到身高较低的人的相对位置先排身高高的人可以方便后续按照相对位置进行插入操作。if (a[0] b[0]) return a[1] - b[1];return b[0] - a[0];});LinkedListint[] que new LinkedList();//用于存储重建后的队列。for (int[] p : people) {//循环遍历排序后的 people 数组。对于数组中的每一个人 p使用 que.add(p[1], p) 将其插入到 LinkedList 的指定位置 p[1]。这里的 p[1] 就是该人在队列中的相对位置通过这种方式能够保证每个人都被正确地插入到队列中使得前面有 p[1] 个身高大于或等于他的人。que.add(p[1],p);}return que.toArray(new int[people.length][]);//将链表转换回二维数组并返回。}
}
假设输入的 people 数组为 [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
排序后 根据排序规则数组会被排序为 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]。重建队列过程 对于 [7,0]插入到位置 0此时队列为 [[7,0]]。对于 [7,1]插入到位置 1此时队列为 [[7,0], [7,1]]。对于 [6,1]插入到位置 1此时队列为 [[7,0], [6,1], [7,1]]。对于 [5,0]插入到位置 0此时队列为 [[5,0], [7,0], [6,1], [7,1]]。对于 [5,2]插入到位置 2此时队列为 [[5,0], [7,0], [5,2], [6,1], [7,1]]。对于 [4,4]插入到位置 4此时队列为 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。
最终返回的重建后的队列就是 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。通过这种排序和插入的方式成功地重建了符合要求的队列。
13.用最少数量的箭引爆气球
力扣题目链接(opens new window)
在二维空间中有许多球形的气球。对于每个气球提供的输入是水平方向上气球直径的开始和结束坐标。由于它是水平的所以纵坐标并不重要因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后可以无限地前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量。
给你一个数组 points 其中 points [i] [xstart,xend] 返回引爆所有气球所必须射出的最小弓箭数。
示例 1
输入points [[10,16],[2,8],[1,6],[7,12]]输出2解释对于该样例x 6 可以射爆 [2,8],[1,6] 两个气球以及 x 11 射爆另外两个气球
示例 2
输入points [[1,2],[3,4],[5,6],[7,8]]输出4
示例 3
输入points [[1,2],[2,3],[3,4],[4,5]]输出2
示例 4
输入points [[1,2]]输出1
示例 5
输入points [[2,3],[2,3]]输出1
提示
0 points.length 10^4points[i].length 2-2^31 xstart xend 2^31 - 1
public class Use_the_minimum_number_of_arrows_to_pop_balloons {public int findMinArrowShots(int[][] points) {//接受一个二维整数数组 points 作为参数points 中的每个元素是一个包含两个整数的数组分别表示一个气球的开始坐标和结束坐标。方法返回引爆所有气球所需的最少箭数。Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));//对输入的points数组进行排序。points是一个二维整数数组其中每个元素是一个包含两个整数的数组分别代表气球的开始坐标和结束坐标。这里使用Integer.compare方法根据气球的开始坐标进行升序排序。表示按照气球的开始坐标 a[0] 和 b[0] 进行升序排序。这样排序后数组中前面的气球开始坐标总是小于或等于后面气球的开始坐标方便后续处理重叠的气球。int count 1;//初始化一个计数器count用于记录需要的最少箭数。因为至少需要一支箭来引爆至少一个气球所以初始值为1。for (int i 1; i points.length; i) {//从第二个气球开始遍历排序后的points数组。第一个气球已经默认用了一支箭所以从第二个气球开始检查与前一个气球的关系。if (points[i][0] points[i - 1][1]) {//检查当前气球points[i]是否与前一个气球points[i - 1]相邻。如果不相邻即当前气球的开始坐标大于前一个气球的结束坐标则需要额外的一支箭来引爆当前气球因此count加1。count;} else {points[i][1] Math.min(points[i][1], points[i - 1][1]); // 如果当前气球与前一个气球相邻即有重叠部分则更新当前气球的结束坐标为两者结束坐标的较小值。这是因为一支箭可以同时引爆这两个气球所以需要更新结束坐标以反映合并后的气球的结束位置以便后续继续检查与其他气球的重叠情况。}}return count;//遍历完所有气球后count 中存储的就是引爆所有气球所需的最少箭数将其返回。}
}
假设输入的 points 数组为 [[10,16], [2,8], [1,6], [7,12]] 排序后 数组排序后变为 [[1,6], [2,8], [7,12], [10,16]]。 遍历过程 当 i 1 时points[1][0] 2points[0][1] 6因为 2 6说明这两个气球有重叠部分。更新 points[1][1] Math.min(8, 6) 6。此时 count 1。当 i 2 时points[2][0] 7points[1][1] 6因为 7 6这两个气球不相邻需要额外一支箭countcount 变为 2。当 i 3 时points[3][0] 10points[2][1] 12因为 10 12这两个气球有重叠部分。更新 points[3][1] Math.min(16, 12) 12。此时 count 2。 最终结果 遍历结束后返回 count即 2表示引爆所有气球最少需要 2 支箭。
通过这种排序和遍历的方式代码能够有效地计算出引爆所有气球所需的最少箭数。
14.无重叠区间
力扣题目链接(opens new window)
给定一个区间的集合找到需要移除区间的最小数量使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间因为它们已经是无重叠的了。
public class Non_overlapping_Intervals {public int eraseOverlapIntervals1(int[][] intervals) {//接受一个二维整数数组 intervals 作为参数intervals 中的每个元素是一个包含两个整数的数组分别表示区间的开始和结束坐标。方法返回需要移除的区间数量以使剩下的区间互不重叠。Arrays.sort(intervals, (a, b)- {return Integer.compare(a[0],b[0]);});//使用 Arrays.sort 方法对 intervals 数组进行排序。这里通过 lambda 表达式定义了比较器Integer.compare(a[0], b[0]) 按照区间的开始坐标 a[0] 和 b[0] 进行升序排序。这样排序后数组中前面的区间开始坐标总是小于或等于后面区间的开始坐标方便后续处理重叠区间。int count 1;//记录可以选择的不重叠区间的数量。初始值为1因为至少可以选择第一个区间。for(int i 1;i intervals.length;i){//从第二个区间索引为 1开始遍历排序后的 intervals 数组。因为第一个区间已经默认被选择所以从第二个区间开始检查与前一个区间的重叠情况。if(intervals[i][0] intervals[i-1][1]){//检查当前区间 intervals[i] 的开始坐标是否小于前一个区间 intervals[i - 1] 的结束坐标。如果是说明这两个区间重叠。intervals[i][1] Math.min(intervals[i - 1][1], intervals[i][1]);//在重叠的情况下更新当前区间的结束坐标为当前区间和前一个区间结束坐标中的较小值。这是因为我们希望保留一个较短的区间以减少后续区间重叠的可能性。然后使用 continue 跳过当前循环继续检查下一个区间因为当前区间与前一个区间重叠不能同时被选择。continue;}else{//如果当前区间的开始坐标大于或等于前一个区间的结束坐标说明这两个区间不重叠。此时将 count 加 1表示又找到了一个可以选择的不重叠区间。count;}}return intervals.length - count;//遍历完所有区间后count 中存储的是可以选择的不重叠区间的数量。用总区间数 intervals.length 减去 count就得到了需要移除的区间数量以保证剩下的区间互不重叠。}
}
假设输入的 intervals 数组为 [[1,2], [2,3], [3,4], [1,3]]
排序后 数组排序后变为 [[1,2], [1,3], [2,3], [3,4]]。遍历过程 当 i 1 时intervals[1][0] 1intervals[0][1] 2因为 1 2这两个区间重叠。更新 intervals[1][1] Math.min(2, 3) 2然后 continue继续下一次循环。此时 count 1。当 i 2 时intervals[2][0] 2intervals[1][1] 2因为 2 2这两个区间不重叠countcount 变为 2。当 i 3 时intervals[3][0] 3intervals[2][1] 3因为 3 3这两个区间不重叠countcount 变为 3。最终结果 总区间数为 4可以选择的不重叠区间数量为 3所以返回 4 - 3 1即需要移除 1 个区间才能使剩下的区间互不重叠。
通过这种排序和遍历的方式代码能够有效地计算出需要移除的区间数量以实现区间的不重叠。
15.划分字母区间
力扣题目链接(opens new window)
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例
输入S ababcbacadefegdehijhklij输出[9,7,8] 解释 划分结果为 ababcbaca, defegde, hijhklij。 每个字母最多出现在一个片段中。 像 ababcbacadefegde, hijhklij 的划分是错误的因为划分的片段数较少。
提示
S的长度在[1, 500]之间。S只包含小写字母 a 到 z 。
public class Divide_the_Letter_Ranges {public ListInteger partitionLabels1(String S) {//接受一个字符串 S 作为参数返回一个包含每个划分区间长度的列表。ListInteger list new LinkedList();//存储最终的划分区间的长度。int[] edge new int[26];//存储每个字母最后一次出现的位置。因为英文字母表有26个字母所以数组大小为26。char[] chars S.toCharArray();//将输入的字符串S转换为字符数组。for (int i 0; i chars.length; i) {//遍历字符数组使用字符的ASCII码减去a的ASCII码来作为索引记录每个字母最后一次出现的索引位置。遍历字符数组 chars对于每个字符 chars[i]计算其对应的数组索引 chars[i] - a并将该字符最后一次出现的位置 i 记录在 edge 数组中。例如如果字符是 a则 a - a 0edge[0] 将记录 a 在字符串中最后一次出现的位置。edge[chars[i] - a] i;}int idx 0;//记录当前考察的区间的最右端边界。int last -1;//记录当前划分区间的开始位置。for (int i 0; i chars.length; i) {//for 循环中对于每个字符 chars[i]idx Math.max(idx,edge[chars[i] - a]);//对于当前遍历到的字符更新idx为当前字符最后一次出现的位置和当前idx的最大值。这一步确保 idx 始终是当前考察区间内所有字符中最晚出现的位置。if (i idx) {//如果当前索引i等于idx则表示当前字符是构成区间的最后一个字符因为它是当前考察区间内所有字符中最晚出现的。list.add(i - last);//将当前区间的长度结束位置i减去开始位置last添加到结果列表中。last i;//更新last为当前索引i为下一个区间做准备。}}return list;//返回包含每个划分区间长度的列表。}
}
假设输入字符串 S ababcbacadefegdehijhklij
计算每个字母最后一次出现的位置 遍历字符串后edge 数组记录了每个字母最后一次出现的位置。例如a 最后一次出现在位置 8b 最后一次出现在位置 5等等。划分区间过程 初始化 idx 0last -1。当 i 0chars[0] aidx Math.max(0, edge[a - a]) 8。当 i 1chars[1] bidx Math.max(8, edge[b - a]) 8。当 i 2chars[2] aidx Math.max(8, edge[a - a]) 8。当 i 3chars[3] bidx Math.max(8, edge[b - a]) 8。当 i 4chars[4] cidx Math.max(8, edge[c - a]) 8。当 i 5chars[5] bidx Math.max(8, edge[b - a]) 8。当 i 6chars[6] aidx Math.max(8, edge[a - a]) 8。当 i 7chars[7] cidx Math.max(8, edge[c - a]) 8。当 i 8chars[8] ai idx此时将 8 - (-1) 9 添加到 list 中last 8。后续继续遍历依次计算其他区间长度并添加到 list 中。
最终list 中存储了每个划分区间的长度返回该列表。
16.合并区间
力扣题目链接(opens new window)
给出一个区间的集合请合并所有重叠的区间。
示例 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] 可被视为重叠区间。注意输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
public class Merge_Intervals {public int[][] merge2(int[][] intervals) {//接受一个二维整数数组 intervals 作为参数返回合并后的区间数组。LinkedListint[] res new LinkedList();//存储合并后的区间。使用 LinkedList 是因为在遍历过程中可能需要频繁地添加和删除元素LinkedList 在这种情况下具有较好的性能。Arrays.sort(intervals, (o1, o2) - Integer.compare(o1[0], o2[0]));//使用 Arrays.sort 方法对 intervals 数组进行排序。这里通过 lambda 表达式定义了比较器Integer.compare(o1[0], o2[0]) 表示按照区间的左边界 o1[0] 和 o2[0] 进行升序排序。排序后数组中前面的区间左边界总是小于或等于后面区间的左边界方便后续合并重叠区间。res.add(intervals[0]);//将排序后的第一个区间 intervals[0] 添加到结果列表 res 中。这是因为第一个区间是合并过程的起始区间。for (int i 1; i intervals.length; i) {//从第二个区间索引为 1开始遍历排序后的 intervals 数组。if (intervals[i][0] res.getLast()[1]) {//检查当前区间 intervals[i] 的左边界是否小于或等于结果列表 res 中最后一个区间的右边界。如果是则说明这两个区间重叠。int start res.getLast()[0];//如果区间重叠获取结果列表中最后一个区间的左边界因为合并后的区间左边界不变。int end Math.max(intervals[i][1], res.getLast()[1]);//算合并后的区间右边界取当前区间 intervals[i] 的右边界和结果列表中最后一个区间的右边界的较大值。res.removeLast();//从结果列表中移除最后一个区间因为要将其与当前区间合并。res.add(new int[]{start, end});//将合并后的区间添加到结果列表中。}else {res.add(intervals[i]);//当区间不重叠直接将当前区间 intervals[i] 添加到结果列表 res 中因为它与结果列表中的最后一个区间不重叠不需要合并。}}return res.toArray(new int[res.size()][]);//将结果列表转换为二维数组并返回。}}
假设输入的 intervals 数组为 [[1,3], [2,6], [8,10], [15,18]]
排序后 数组排序后仍为 [[1,3], [2,6], [8,10], [15,18]]因为原数组已经按左边界有序。遍历和合并过程 初始化 res [[1,3]]。当 i 1 时intervals[1][0] 2res.getLast()[1] 3因为 2 3区间重叠。合并后的区间为 [1, 6]此时 res [[1,6]]。当 i 2 时intervals[2][0] 8res.getLast()[1] 6因为 8 6区间不重叠将 [8,10] 添加到 res 中此时 res [[1,6], [8,10]]。当 i 3 时intervals[3][0] 15res.getLast()[1] 10因为 15 10区间不重叠将 [15,18] 添加到 res 中此时 res [[1,6], [8,10], [15,18]]。最终结果 将 res 转换为二维数组并返回结果为 [[1,6], [8,10], [15,18]]。
通过这种排序和遍历的方式代码有效地实现了区间的合并功能。
17.单调递增的数字
力扣题目链接(opens new window)
给定一个非负整数 N找出小于或等于 N 的最大的整数同时这个整数需要满足其各个位数上的数字是单调递增。
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
示例 1:
输入: N 10输出: 9
示例 2:
输入: N 1234输出: 1234
示例 3:
输入: N 332输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
public class monotonically_increasing_numbers {public int monotoneIncreasingDigits2(int n) {//接受一个整数n作为参数并返回一个整数该整数是小于或等于n的最大单调递增数字。String s String.valueOf(n);//将整数n转换为字符串s以便逐位处理。char[] chars s.toCharArray();//将字符串s转换为字符数组chars这样可以通过索引访问和修改每一位数字。int start s.length();//初始化start变量为字符串的长度这个变量将用于标记需要被修改的数字位的起始位置。for (int i s.length() - 2; i 0; i--) {//从数组的倒数第二个元素开始向前遍历检查每一位数字是否大于其后一位数字。if (chars[i] chars[i 1]) {//如果当前位数字大于其后一位数字说明我们需要调整当前位数字以保持单调递增。我们将当前位数字减1并更新start为当前位的索引。chars[i]--;start i1;//将 start 更新为 i 1这是因为从 i 1 位置开始往后的所有数字都需要被设置为 9以确保得到的数字是小于或等于原始数字 n 的最大单调递增数字。}}for (int i start; i s.length(); i) {//从start位置开始将所有后续的数字位设置为9这是因为在调整了前面的数字后为了保证得到的数字是最大的单调递增数字后面的数字都应该取最大值 9。chars[i] 9;}return Integer.parseInt(String.valueOf(chars));//使用String.valueOf方法将字符数组重新组合成一个字符串然后使用Integer.parseInt将其转换回整数。}
}
假设输入 n 332
将 n 转换为字符串 s 332再转换为字符数组 chars {3, 3, 2}。初始化 start 3。进入第一个 for 循环 当 i 1 时chars[1] 3chars[2] 2因为 3 2所以 chars[1]--chars[1] 变为 2start 2。进入第二个 for 循环 当 i 2 时chars[2] 9。字符数组变为 {3, 2, 9}转换为字符串 329再转换为整数 329 并返回。
通过以上步骤代码能够正确地找到小于或等于给定整数的最大单调递增数字。
18.监控二叉树
力扣题目链接(opens new window)
给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1 输入[0,0,null,0,0]输出1解释如图所示一台摄像头足以监控所有节点。
示例 2 输入[0,0,null,0,null,0,null,null,0]输出2解释需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示
给定树的节点数的范围是 [1, 1000]。每个节点的值都是 0。
public class Binary_Tree_Monitoring {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}static int ans;//定义了一个静态变量 ans用于记录覆盖整个二叉树所需的最小摄像头数量。静态变量的作用是在整个类的范围内共享这个数据确保在不同方法调用之间能够正确地累加摄像头数量。public int minCameraCover2(TreeNode root) {//接受一个二叉树的根节点root作为参数并返回覆盖整个二叉树所需的最小摄像头数量。ans 0;//用于记录总共需要的摄像头数量。if(f(root) 0) ans ;//返回0表示根节点需要一个摄像头因为它的子节点和子树已经覆盖了它则ans增加1。return ans;//最后返回 ans即覆盖整个二叉树所需的最小摄像头数量。}public static int f(TreeNode x) {//用于遍历二叉树并确定在每个节点上放置摄像头的最佳方式。if(x null) return 1;//如果当前节点x为空返回1。这里的1表示空节点不需要摄像头也不被任何摄像头覆盖但是它的存在对于其父节点来说相当于一个“覆盖”状态。例如一个节点的左子树为空对于该节点来说左子树方向相当于已经被 “覆盖” 了。int l f(x.left);//对于非空节点递归调用f方法处理左子树和右子树分别获取左右子节点的返回值l和r。int r f(x.right);//通过递归从叶子节点开始向上处理每个节点。if(l 0 || r 0) {//如果l或r返回0表示当前节点的一个子节点需要一个摄像头来覆盖因此当前节点也需要一个摄像头这是因为要覆盖子节点必须在当前节点放置摄像头。ans增加1返回2。这里的 2 表示当前节点放置了摄像头并且该摄像头可以覆盖当前节点及其子节点。ans ;return 2;}if(l 1 r 1) return 0;//如果l和r都返回1表示当前节点的两个子节点都不需要摄像头当前节点也不需要因为它已经被子节点的“覆盖”状态覆盖返回0。这里的 0 表示当前节点不需要摄像头但它没有被任何摄像头覆盖需要其父节点来覆盖它。return 1;//如果其他情况返回1表示当前节点不需要摄像头但是它的存在对于其父节点来说相当于一个“覆盖”状态。例如一个子节点放置了摄像头那么它的父节点就处于被覆盖的状态虽然父节点本身不需要摄像头但它对更上层的节点有 “覆盖” 的影响。}
}
假设我们有一个简单的二叉树 1/ \2 3首先调用 minCameraCover2(root)ans 初始化为 0。调用 f(root) 对于节点 1先递归调用 f(2) 和 f(3)。对于节点 2它没有子节点f(2.left) 和 f(2.right) 都返回 1因为子节点为空。由于左右子节点都返回 1f(2) 返回 0表示节点 2 需要被父节点覆盖。对于节点 3同理f(3) 返回 0。回到节点 1因为 f(2) 和 f(3) 都返回 0所以节点 1 需要一个摄像头ans 增加 1f(1) 返回 2。由于 f(root) 返回 2minCameraCover2 方法中不需要额外增加 ans最后返回 ans即 1表示覆盖这个二叉树需要 1 个摄像头。
通过这种递归的方式代码能够有效地确定覆盖整个二叉树所需的最少摄像头数量。
