当前位置: 首页 > news >正文

算法训练营day29, 贪心算法3

import (

  "sort"

)

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

func largestSumAfterKNegations(nums []int, k int) int {

  //先从小到大排序

  sort.Ints(nums)

  sum := 0

  //将数组中负数转为正数

  for i := 0; i < len(nums); i++ {

    if nums[i] < 0 && k > 0 {

      nums[i] = -nums[i]

      k--

    }

  }

  //二次排序

  sort.Ints(nums)

  //如果k还没用完且为奇数,把最小值转为负数,影响最小

  if k > 0 && k%2 == 1 {

    nums[0] = -nums[0]

  }

  for i := 0; i < len(nums); i++ {

    sum += nums[i]

  }

  return sum

}

//134. 加油站

func canCompleteCircuit(gas []int, cost []int) int {

  curSum := 0 //统计油箱剩余量

  sum := 0   //统计所有加油站油耗剩余

  index := 0 //出发时加油站的编号

  for i := 0; i < len(gas); i++ {

    curSum += (gas[i] - cost[i])

    sum += (gas[i] - cost[i])

    //如油箱剩余量小于零则把下标移动到下一个,同时油箱归零

    if curSum < 0 {

      index = i + 1

      curSum = 0

    }

  }

  //如果所有加油站油耗剩余小于零则说明无法跑完一圈返回-1

  if sum < 0 {

    return -1

  }

  return index

}

//135. 分发糖果

func candy(ratings []int) int {

  n := len(ratings)

  candys := make([]int, n)

  candySum := 0

  //先想左统计一圈

  candys[0] = 1

  for i := 0; i < n-1; i++ {

    if ratings[i+1] > ratings[i] {

      candys[i+1] = candys[i] + 1

    } else {

      candys[i+1] = 1

    }

  }

  //在向右统计一圈

  for i := n - 1; i > 0; i-- {

    if ratings[i-1] > ratings[i] {

      //比较当前值和前一个值+1中取二者最大值

      if candys[i-1] < candys[i]+1 {

        candys[i-1] = candys[i] + 1

      }

    }

  }

  for i := 0; i < n; i++ {

    candySum += candys[i]

  }

  return candySum

}

http://www.lryc.cn/news/300804.html

相关文章:

  • 164基于matlab的奇异值分解、小波降噪、zoom细化
  • 每日OJ题_算法_递归③力扣206. 反转链表
  • 【Linux】指令 【whereis】
  • 牛客网SQL进阶128:未完成试卷数大于1的有效用户
  • GitHub的使用操作
  • 智慧公厕管理软件
  • 【30秒看懂大数据】数据中台
  • 【UI自动化测试技术】自动化测试研究:Python+Selenium+Pytest+Allure,详解UI自动化测试,了解元素交互的常用方法(精)(三)
  • GPT-4带来的思想火花
  • 使用倒模耳机壳UV村脂胶液制作舞台监听耳返入耳式耳机壳有哪些优点?
  • html从零开始8:css3新特性、动画、媒体查询、雪碧图、字体图标【搬代码】
  • HAL库 STM32驱动W25QXX驱动例程
  • C#入门及进阶|数组和集合(九):Stack类
  • 算法训练day31贪心算法理论基础Leetcode455分发饼干376摆动序列53最大子序和
  • Java与JavaScript同源不同性
  • 【JavaEE】spring boot快速上手
  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)
  • GPT SOVITS项目 一分钟克隆 (文字输出)
  • python34-Python列表和元组之加法
  • 不做程序员了(转岗半年后对程序员岗位的思考)
  • DS:八大排序之直接插入排序、希尔排序和选择排序
  • 【MySQL】-21 MySQL综合-8(MySQL默认值+MySQL非空约束+MySQL查看表中的约束)
  • 力扣hot3--并查集+哈希
  • 微信网页版能够使用(会顶掉微信app的登陆)
  • word软件中硬件图像加速有什么用处?禁用硬件图形加速(G)会影响word文档中插入图片的分辨率吗?
  • .NET Core MongoDB数据仓储和工作单元模式封装
  • lua:有关表访问的metamethod
  • 【MySQL】索引事务
  • ChatGPT重大升级:能自动记住用户的习惯和喜好,用户有权决定是否共享数据给OpenAI
  • CSS设置盒子阴影