找工程项目信息网站,食品网站开发的背景,成都广告公司有哪些,做百度推广的公司电话号码随想录日记part26【把这两天没写的补回来】 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.22-24 主要内容#xff1a;今天开始学习贪心算法#xff0c;基础知识可以看链接#xff0c;#xff1a;接下来是针对题目的讲解#xff1a;1.分配饼干 #x…随想录日记part26【把这两天没写的补回来】 t i m e time time 2024.03.22-24 主要内容今天开始学习贪心算法基础知识可以看链接接下来是针对题目的讲解1.分配饼干 2.摆动序列 3.最大子序列和4.买卖股票的最佳时机II5.跳跃游戏6.跳跃游戏II
455.分发饼干376. 摆动序列53. 最大子序和122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏 II Topic1分发饼干
题目 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i i i都有一个胃口值 g [ i ] g[i] g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j j j都有一个尺寸 s [ j ] s[j] s[j] 。如果 s [ j ] g [ i ] s[j] g[i] s[j]g[i]我们可以将这个饼干 j j j 分配给孩子 i i i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 输入 g [ 1 , 2 , 3 ] , s [ 1 , 1 ] g [1,2,3], s [1,1] g[1,2,3],s[1,1] 输出 1 1 1
思路 可以尝试使用贪心策略先将饼干数组和小孩数组排序。 然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。 代码如下 class Solution {
//优先考虑胃口先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int index s.length - 1;int result 0;for (int i g.length - 1; i 0; i--) {if (index 0 s[index] g[i]) {index--;result;}}return result;}
}时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 空间复杂度 O ( 1 ) O(1) O(1) Topic2摆动序列
题目 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如 [ 1 , 7 , 4 , 9 , 2 , 5 ] [1, 7, 4, 9, 2, 5] [1,7,4,9,2,5] 是一个 摆动序列 因为差值 ( 6 , − 3 , 5 , − 7 , 3 ) (6, -3, 5, -7, 3) (6,−3,5,−7,3) 是正负交替出现的。相反 [ 1 , 4 , 7 , 2 , 5 ] [1, 4, 7, 2, 5] [1,4,7,2,5] 和 [ 1 , 7 , 4 , 5 , 5 ] [1, 7, 4, 5, 5] [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。子序列可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。给你一个整数数组 n u m s nums nums 返回 n u m s nums nums 中作为摆动序列的最长子序列的长度 。 输入 n u m s [ 1 , 7 , 4 , 9 , 2 , 5 ] nums [1,7,4,9,2,5] nums[1,7,4,9,2,5] 输出 6 6 6
思路 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。 整体最优整个序列有最多的局部峰值从而达到最长摆动序列 所以整体代码如下 class Solution {public int wiggleMaxLength(int[] nums) {int count 1;// 记录摆动个数int pre 0;int aft 0;if (nums.length 1)return 1;for (int i 0; i nums.length - 1; i) {aft nums[i 1] - nums[i];if ((pre 0 aft 0) || (pre 0 aft 0)) {count;}pre aft;}return count;}
}Topic3最大子序和
题目 给你一个整数数组 n u m s nums nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。
输入 n u m s [ − 2 , 1 , − 3 , 4 , − 1 , 2 , 1 , − 5 , 4 ] nums [-2,1,-3,4,-1,2,1,-5,4] nums[−2,1,−3,4,−1,2,1,−5,4] 输出 6 6 6 解释 连续子数组 [ 4 , − 1 , 2 , 1 ] [4,-1,2,1] [4,−1,2,1] 的和最大为 6 6 6 。 思路 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。 全局最优选取最大“连续和” 代码实现如下 class Solution {public int maxSubArray(int[] nums) {int resultInteger.MIN_VALUE;int count0;for(int i0;inums.length;i){countnums[i];if(resultcount)resultcount;if(count0)count0;}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1) Topic4买卖股票的最佳时机 II
题目 给你一个整数数组 p r i c e s prices prices 其中 p r i c e s [ i ] prices[i] prices[i] 表示某支股票第 i i i 天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买然后在同一天出售。返回你能获得的最大利润
输入 p r i c e s [ 7 , 1 , 5 , 3 , 6 , 4 ] prices [7,1,5,3,6,4] prices[7,1,5,3,6,4] 输出 7 7 7 解释 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 思路 这道题目可能我们只会想选一个低的买入再选个高的卖再选一个低的买入…循环反复 代码实现如下 class Solution {public int maxProfit(int[] prices) {int result0;for(int i1;iprices.length;i){resultInteger.max(0,prices[i]-prices[i-1]);}return result;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1) Topic5跳跃游戏
题目 给你一个非负整数数组 n u m s nums nums 你最初位于数组的第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回 t r u e true true 否则返回 f a l s e false false 。
输入 n u m s [ 2 , 3 , 1 , 1 , 4 ] nums [2,3,1,1,4] nums[2,3,1,1,4] 输出 t r u e true true 解释 可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标 思路 贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。 代码实现如下 class Solution {public boolean canJump(int[] nums) {int result 0;if (nums.length 1)return true;for (int i 0; i result; i) {result Integer.max(result, i nums[i]);if (result nums.length - 1)return true;}if (result nums.length - 1)return true;elsereturn false;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1) Topic6跳跃游戏||
题目 给定一个长度为 n n n 的 0 索引整数数组 n u m s nums nums。初始位置为 n u m s [ 0 ] nums[0] nums[0]。每个元素 n u m s [ i ] nums[i] nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 n u m s [ i ] nums[i] nums[i] 处你可以跳转到任意 n u m s [ i j ] nums[i j] nums[ij] 处: 0 j n u m s [ i ] 0 j nums[i] 0jnums[i] i j n i j n ijn 返回到达 n u m s [ n − 1 ] nums[n - 1] nums[n−1] 的最小跳跃次数。生成的测试用例可以到达 n u m s [ n − 1 ] nums[n - 1] nums[n−1]。
输入 n u m s [ 2 , 3 , 1 , 1 , 4 ] nums [2,3,1,1,4] nums[2,3,1,1,4] 输出 2 2 2 解释 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。 思路 要从覆盖范围出发不管怎么跳覆盖范围内一定是可以跳到的以最小的步数增加覆盖范围覆盖范围一旦覆盖了终点得到的就是最少步数这里需要统计两个覆盖范围当前这一步的最大覆盖和下一步最大覆盖。 代码实现如下 class Solution {public int jump(int[] nums) {if (nums.length 1)return 0;int now 0;int next 0;int step 0;for (int i 0; i nums.length; i) {next Integer.max(next, nums[i] i);if (now i) {step;now next;if (next nums.length - 1)break;}}return step;}
}时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
