代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

简介: 代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

1. LeetCode 1005. K 次取反后最大化的数组和

1.1 思路

  1. 本题有两次贪心的选择,第一次贪心在优先对负数取反,再优先对绝对值大的负数取反。第二次贪心是此时若数组里都是非负数时就对最小的非负数进行取反
  2. 全局最优:得到数组的最大数组和。找不出明显反例反驳
  3. 首先对数组排序,我们要自己实现按照绝对值从大到小排序。然后遍历数组,for(int i=0; i<nums.length; i++)if(nums[i]<0&&k>0)优先对绝对值大的负数取反,nums[i]=-nums[i],k--。这里就是完成了第一次贪心的策略
  4. 此时数组都是非负数了,可能 k 还没用完,接下来就优先对最小的非负数取反。if(k%2==1)nums[nums.length-1]=-nums[nums.length-1]。注意这里数组还是按照绝对值从大到小排序的。这里 k 是奇数就取反,如果是偶数无所谓,因为偶数次取反,非负数还是非负数
  5. 以上这么写性能很好

1.2 代码

//
class Solution {
    public int largestSumAfterKNegations(int[] nums, int K) {
      // 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
  nums = IntStream.of(nums)
         .boxed()
         .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
         .mapToInt(Integer::intValue).toArray();
  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();
    }
}

2. LeetCode 134. 加油站

2.1 思路


  1. 本题虽然是一维数组但是是首尾相连的
  2. 这题有补充有消耗,应该关注的是有补充有消耗之后油箱还剩多少油,最终对油箱的油量是增加还是消耗的作用。通过 gas[i]-cost[i] 得到净剩油的数组,这里定义个 curSum 统计我们每一个站点剩余的油量,一旦为负数了就选择下一个站点(i+1)开始。贪心思路:不断累加剩余的油量,一旦在某个站点 curSum 为负数了,说明这个站点(i)之前每个站点作为其实位置都是不行的,因此选择下一个站点(i+1)为起始位置,继续向后遍历。这里有疑问,为什么这个 i 之前的所有位置作为起始位置都是不行的。假设区间 2 的和 curSum>0,从这里开始,区间 1 的和加上区间 2 的和就是 curSum 此时<0,如果区间 2 的和>0,那么区间 1 的和就是<0,那么按照上面的规则就应该是从区间 2 作为起点往后继续累加了

  3. 局部最优:当前累加剩余数组 rest[i] 的和 curSum 一旦小于 0,起始位置至少要是 i+1,因为从 i 之前开始一定不行。
  4. 全局最优:找到可以跑一圈的起始位置。
  5. 定义个 curSum 统计从头开始每一站的剩余油量,totalSum 把所有剩余油量加起来如果<0,说明从任何一个位置跑的话都不可能跑完一圈,定义个 start,如果 curSum<0 就从 i+1 开始
  6. for(int i=0; i<gas.length; i++)curSum+=(gas[i]-cost[i]),totalSum+=(gas[i]-cost[i]),if(curSum<0)start=i+1,并且 curSum=0 重新开始统计。
  7. 退出循环后 if(totalSum<0)return -1;最后 return start 即可
  8. 按照这个思路到最后一个位置的时候已经可以确定没有结果了

2.2 代码

//
// 解法2
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;
    }
}

3. LeetCode 135. 分发糖果

3.1 思路

  1. 每个小孩至少 1 个糖果,得分高的小孩比旁边低分的糖果要多糖果,但最终是求最少的给糖果数量
  2. 我们的难题是要和两边的小孩一起进行比较。不少题都有这种情况,两边一起比较就很容易乱,这种题解题思路一定是先确定一边再确定另一边。
  3. 首先先看情况 1:右边比左边得分高,if(rating[i-1]<rating[i]) 这个 candy[i]=candy[i-1]+1。这就是右边比左边得分高的处理方式。注意这里是从左向右遍历
  4. 情况 2:左边比右边高,注意这里是从右向左遍历,为什么?因为这种情况如果从左向右遍历是无法使用到情况 1 处理的结果的,因为比较依赖第 i+1 个元素。 if(rating[i]>rating[i+1]) 这个 candy[i]=canddy[i+1]+1,由于情况 1 也算了个 candy[i] 我们要在两者间取个值,我们此时如果这个孩子得分比较高是要既比左边大又要比右边大的,因此要比较求最大值,所以实际上 candy[i]=Math.max(candy[i+1]+1,candy[i]),算完以后 candy[i] 就是每个小孩子应得的糖果数,最后累加就是我们要求的结果
  5. 定义数组 candy,candy[0]=1;情况 1 for(int i=1;i<rating.length; i++) 从 1 开始是因为最开始是从 i 和 i-1 比较,if(rating[i-1]<rating[i-1])candy[i]=candy[i-1]+1,否则就是 candy[i]=1;
  6. 情况 2 for(int i=rating.length-2; i>=0; i--),从这个位置开始是因为 rating.length-1 是最后一个位置,而最开始是最后一个位置和倒数第二个位置比较,即 i(倒数第二) 和 i+1(最后一个),if(rating[i]>rating[i+1]) candy[i]=Math.max(candy[i+1]+1,candy[i])
  7. 最后定义个 result 累加 candy 数组,然后返回 result 即可

3.2 代码

//
class Solution {
    /**
         分两个阶段
         1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
         2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
    */
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candyVec = new int[len];
        candyVec[0] = 1;
        for (int i = 1; i < len; i++) {
            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]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        int ans = 0;
        for (int num : candyVec) {
            ans += num;
        }
        return ans;
    }
}
相关文章
|
25天前
|
机器学习/深度学习 算法 PyTorch
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
180 1
|
1月前
|
算法 安全 C语言
使用C语言实现DES算法代码
使用C语言实现DES算法代码
|
1月前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
16天前
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
4天前
|
C++
【力扣】2562. 找出数组的串联值
【力扣】2562. 找出数组的串联值
|
26天前
|
存储 机器学习/深度学习 算法
C语言代码实现数据结构与算法
以上代码中,哈希表使用链表解决哈希冲突,每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值,insert函数用于向哈希表中插入一个键值对,若当前位置为空,则直接插入;否则,将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值,若存在则返回其值,否则返回-1。
32 1
|
1月前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
|
1月前
|
机器学习/深度学习 算法 生物认证
基于深度学习的人员指纹身份识别算法matlab仿真
基于深度学习的人员指纹身份识别算法matlab仿真
|
26天前
|
传感器 算法 计算机视觉
基于肤色模型和中值滤波的手部检测算法FPGA实现,包括tb测试文件和MATLAB辅助验证
该内容是关于一个基于肤色模型和中值滤波的手部检测算法的描述,包括算法的运行效果图和所使用的软件版本(matlab2022a, vivado2019.2)。算法分为肤色分割和中值滤波两步,其中肤色模型在YCbCr色彩空间定义,中值滤波用于去除噪声。提供了一段核心程序代码,用于处理图像数据并在FPGA上实现。最终,检测结果输出到&quot;hand.txt&quot;文件。
|
1月前
|
机器学习/深度学习 算法 计算机视觉
基于yolov2深度学习网络的视频手部检测算法matlab仿真
基于yolov2深度学习网络的视频手部检测算法matlab仿真