免费网站开发框架,电子商务网站建设与维护pdf,腾讯邮箱企业邮箱登录,文山做网站的地方算法题
Leetcode 1005.K次取反后最大化的数组和
题目链接:1005.K次取反后最大化的数组和 大佬视频讲解#xff1a;K次取反后最大化的数组和视频讲解 个人思路 思路清晰#xff0c;因为是取反当然是取越小的负数越好#xff0c;那么先按绝对值排序。如果是负数就取反#… 算法题
Leetcode 1005.K次取反后最大化的数组和
题目链接:1005.K次取反后最大化的数组和 大佬视频讲解K次取反后最大化的数组和视频讲解 个人思路 思路清晰因为是取反当然是取越小的负数越好那么先按绝对值排序。如果是负数就取反相应取反次数减一遍历到没有负数后还有取反次数就选绝对值最小的值取反剩下的次数最后数组和就是最大的也是局部最优求全局最优的结果可以用贪心 解法
贪心法
按照贪心法的步骤来解题步骤为
第一步将数组按照绝对值大小从大到小排序第二步从前向后遍历遇到负数将其变为正数同时K--第三步如果K还大于0那么反复转变数值最小的元素将K用完第四步求和 class Solution {public int largestSumAfterKNegations(int[] nums, int K) {nums IntStream.of(nums) //创建了一个原始类型 int 的流.boxed()//将流中的int值装箱成Integer对象.sorted((o1, o2) - Math.abs(o2) - Math.abs(o1))//按绝对值大小排序.mapToInt(Integer::intValue).toArray();//转回int[] 类型的数组int len nums.length; for (int i 0; i len; i) {//从前向后遍历遇到负数将其变为正数同时K--if (nums[i] 0 K 0) {nums[i] -nums[i];K--;}}// 如果K还大于0那么反复转变数值最小的元素将K用完if (K % 2 1) nums[len - 1] -nums[len - 1];return Arrays.stream(nums).sum();}
}时间复杂度:O(n log n)排序操作的时间复杂度是 n log n 空间复杂度:O(n);代码使用了额外的数组来存储排序后的结果 Leetcode 134. 加油站
题目链接:134. 加油站
大佬视频讲解加油站视频讲解 个人思路 首先总油量减去总消耗大于等于零那么一定可以跑完一圈找起点就从头遍历油减油耗如果有负数就当前遍历点加1重新计算直到遍历完总油耗还是大于0 解法
贪心法 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈也就是各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。 每个加油站的剩余量rest[i]为gas[i] - cost[i]。 i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSumi1后面如果出现更大的负数就是更新i那么起始位置又变成新的i1了 局部最优当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置。局部推全部贪心
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum 0;//当前油耗int totalSum 0;//全部油耗int index 0;//起点for (int i 0; i gas.length; i) {curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if (curSum 0) {index (i 1) % gas.length ; //更换新起点curSum 0;}}if (totalSum 0) return -1;return index;}
} 时间复杂度:O(n)遍历整个数组 空间复杂度:O(1);常量级的变量 Leetcode 135. 分发糖果
题目链接:135. 分发糖果
大佬视频讲解分发糖果视频讲解 个人思路
到底是一起算还是分开计算呢思路不清晰... 解法
贪心法
这道题目一定是要确定一边之后再确定另一边先比较每一个孩子的左边然后再比较右边如果两边一起考虑一定会顾此失彼。 先确定右边评分大于左边的情况比较左孩子从前向后遍历确定分发糖果的第一个数组
再确定左孩子大于右孩子的情况比较右孩子从后向前遍历对前一个数组优化比较右孩子增加糖果的同时也要比交上一个数组的糖果值二者取最大的. 具象化代码步骤就是分两个阶段 1、起点下标1 从左往右只要 右边 比 左边 大右边的糖果左边 1 2、起点下标 ratings.length - 2 从右往左 只要左边 比 右边 大此时 左边的糖果应该 取本身的糖果数符合比它左边大 和 右边糖果数 1 二者的最大值这样才符合 它比它左边的大也比它右边大 class Solution {public int candy(int[] ratings) {int len ratings.length;int[] candyNums new int[len];candyNums[0] 1;//初始化第一个孩子糖果数for (int i 1; i len; i) {//从左往右比左孩子candyNums[i] (ratings[i] ratings[i - 1]) ? candyNums[i - 1] 1 : 1;}for (int i len - 2; i 0; i--) {//从右往左比右孩子if (ratings[i] ratings[i 1]) {candyNums[i] Math.max(candyNums[i], candyNums[i 1] 1);//取最大糖果数}}int ans 0;for (int num : candyNums) {//累加和ans num;}return ans;}
} 时间复杂度:O(n)遍历两遍整个数组 空间复杂度:O(n);暂存数组大小 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
