豪圣建设项目管理网站,做兼职的网站,建筑网官网下载,分销系统多少钱一套由于这周来不及了#xff0c;先过一遍后面的思路#xff0c;具体实现等下周再开始详细写。
贪心算法
这个图非常好 122.买卖股票的最佳时机 II(妙#xff0c;拆分利润)
把利润分解为每天为单位的维度#xff0c;需要收集每天的正利润就可以#xff0c;收集正利润的区间…
由于这周来不及了先过一遍后面的思路具体实现等下周再开始详细写。
贪心算法
这个图非常好 122.买卖股票的最佳时机 II(妙拆分利润)
把利润分解为每天为单位的维度需要收集每天的正利润就可以收集正利润的区间就是股票买卖的区间而我们只需要关注最终利润不需要记录区间。 55. 跳跃游戏(妙覆盖范围)
不用拘泥于每次究竟跳几步而是看覆盖范围覆盖范围内一定是可以跳过来的不用管是怎么跳的。 45.跳跃游戏 II(难)
还是要看最大覆盖范围。
以最小的步数增加最大的覆盖范围覆盖范围一旦覆盖了终点得到的就是最少步数不用管具体是怎么跳的不纠结于一步究竟跳一个单位还是两个单位。
这里需要统计两个覆盖范围当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了还没有到终点的话那么就必须再走一步来增加覆盖范围直到覆盖范围覆盖了终点。 1005.K次取反后最大化的数组和(简单)
先让绝对值大的负数变为正数当前数值达到最大然后如果K依然大于0只找数值最小的正整数进行反转。
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小第二步从前向后遍历遇到负数将其变为正数同时K--第三步如果K还大于0那么反复转变数值最小的元素将K用完第四步求和 将数组按照绝对值大小从大到小排序
nums IntStream.of(nums).boxed().sorted((o1, o2) - Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();
对int[]数组元素求和
Arrays.stream(nums).sum() int ans 0;for (int num : nums) {ans num;}
134. 加油站(妙)
补充for循环适合模拟从头到尾的遍历而while循环适合模拟环形遍历要善于使用while
当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置。 135. 分发糖果(妙2次贪心)
先确定一边之后再确定另一边例如比较每一个孩子的左边然后再比较右边如果两边一起考虑一定会顾此失彼。
两次贪心的策略
一次是从左到右遍历只比较右边孩子评分比左边大的情况。一次是从右到左遍历只比较左边孩子评分比右边大的情况。
分两个阶段
1、起点下标1 从左往右只要 右边 比 左边 大右边的糖果左边 1
2、起点下标 ratings.length - 2 从右往左 只要左边 比 右边 大
此时 左边的糖果应该 取本身的糖果数符合比它左边大
和 右边糖果数 1 二者的最大值这样才符合
它比它左边的大也比它右边大 860.柠檬水找零(简单) 直接统计five,ten的count就好了 情况一账单是5直接收下。情况二账单是10消耗一个5增加一个10情况三账单是20优先消耗一个10和一个5如果不够再消耗三个5 406.根据身高重建队列(难妙2次贪心) 本题有两个维度h和k看到这种题目一定要想如何确定一个维度然后再按照另一个维度重新排列。
如果按照k来从小到大排序排完之后会发现k的排列并不符合条件身高也不符合条件两个维度哪一个都没确定下来。
那么按照身高h来排序呢身高一定是从大到小排身高相同的话则k小的站前面让高个子在前面。
此时我们可以确定一个维度了就是身高前面的节点一定都比本节点高
那么只需要按照k为下标重新插入队列就可以了 二维数据排序
// 身高从大到小排身高相同k小的站前面Arrays.sort(people, (a, b) - {if (a[0] b[0]) return a[1] - b[1]; // a - b 是升序排列故在a[0] b[0]的狀況下會根據k值升序排列return b[0] - a[0]; //b - a 是降序排列在a[0] ! b[0]的狀況會根據h值降序排列});
Linkedlist.add()
Linkedlist.add(index, value)会将value插入到指定index里
452. 用最少数量的箭引爆气球(重叠区间)
重叠区间问题本质就是更新区间的边界
按照气球的起始位置排序
// int[][] points
Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));
如果气球重叠了重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭
不需要移走气球直接记录res即可。
技巧寻找重复的气球寻找重叠气球最小右边界
points[i][1] Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界 435. 无重叠区间(重叠区间)
本质还是排序更新边界
有452本题很好理解 763.划分字母区间(妙重叠区间)
用最远出现距离模拟了圈字符的行为。思路很巧妙
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点 统计字符串S中每个字母char出现的最远位置
int[] edge new int[26];char[] chars S.toCharArray();for (int i 0; i chars.length; i) {edge[chars[i] - a] i;}
idx Math.max(idx,edge[chars[i] - a]); // 更新right下标
56. 合并区间(简单重叠区间)
没什么好说的简单 //按照左边界排序
Arrays.sort(intervals, (x, y) - Integer.compare(x[0], y[0])); 738.单调递增的数字(妙flag的运用) 例如N98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]--然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。从后向前遍历 举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。 那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299 用一个flag(start)来标记从哪里开始赋值9。 // flag用来标记赋值9从哪里开始
// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行
将一个 int 类型的整数 N 转换为字符串然后将这个字符串按字符拆分为一个字符数组。 String[] strings (N ).split(); String, char 与 int 的转换使用
class Solution {public int monotoneIncreasingDigits(int n) {String s String.valueOf(n);char[] chars s.toCharArray();int start s.length();for (int i s.length() - 2; i 0; i--) {if (chars[i] chars[i 1]) {chars[i]--;start i1;}}for (int i start; i s.length(); i) {chars[i] 9;}return Integer.parseInt(String.valueOf(chars));}
} 968.监控二叉树(难) 贪心二叉树
麻烦的是判断出每个节点的状态与各种转移情况。考虑的细节比较繁多。
思路从低到上遍历先给叶子节点父节点放个摄像头然后隔两个节点放一个摄像头直至到二叉树头结点。
后序遍历左右中 隔两个节点放一个摄像头状态转移
每个节点可能的三种状态
0该节点无覆盖1本节点有摄像头2本节点有覆盖
空节点的状态只能是有覆盖这样就可以在叶子节点的父节点放摄像头了
单层逻辑处理主要有如下四类情况
情况1左右节点都有覆盖中间节点应该就是无覆盖 return 0情况2左右节点至少有一个无覆盖的情况中间节点放摄像头 result且return 1情况3左右节点至少有一个有摄像头父节点就是覆盖 return 2情况4头结点没有覆盖 result以上都处理完了递归结束之后可能头结点 还有一个无覆盖的情况 动态规划 耶耶耶贪心终于结束开始动态规划
