平湖市网站建设,浙江网商银行股份有限公司,实体店怎么在网上推广,东莞响应式网站制作贪心
1、1005. K 次取反后最大化的数组和
题目#xff1a; 给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后…贪心
1、1005. K 次取反后最大化的数组和
题目 给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后返回数组 可能的最大和 。 输入nums [4,2,3], k 1 输出5 解释选择下标 1 nums 变为 [4,-2,3] 。
思路
负数变成正数很有意思哈学一下go的sort.Slice
func largestSumAfterKNegations(nums []int, k int) int {// 代码一刷sort.Slice(nums, func(i,j int) bool {return math.Abs(float64(nums[i])) math.Abs(float64(nums[j]))})for i:0; ilen(nums); i {if k 0 nums[i] 0 {k--nums[i] -nums[i]}}if k%2 1 {nums[len(nums)-1] -nums[len(nums)-1]}res : 0for i:0; ilen(nums); i {res nums[i]}return res
}2、134. 加油站
题目 在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。 给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 输入: gas [1,2,3,4,5], cost [3,4,5,1,2] 输出: 3
思路
很巧妙的一个total使得看起来像循环一圈能完成了
func canCompleteCircuit(gas []int, cost []int) int {// 代码一刷贪心curSum : 0totalSum : 0start : 0for i: 0; ilen(gas); i {curSum gas[i]-cost[i]totalSum gas[i]-cost[i]if curSum 0 {start i1curSum 0}}if totalSum 0 {return -1}return start
}3、135. 分发糖果
题目 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
思路
至少为每个人一个糖果两边分别算取最大值
func candy(ratings []int) int {// 贪心res1 : make([]int, len(ratings))for i:0; ilen(ratings);i {res1[i] 1}for i: 1; ilen(ratings); i {// 右边比左边大的情况从左开始if ratings[i] ratings[i-1] {res1[i] res1[i-1]1}// else { 不需要减一别变成了0// res1[i] res1[i]-1// }}for i:len(res1)-1; i0; i-- {// 左边比右边大 从右开始if ratings[i-1] ratings[i] {res1[i-1] max(res1[i-1], res1[i]1)}}ans : 0for i:0; ilen(res1); i {ans res1[i]}return ans
}
func max(a,b int) int {if ab {return a}; return b}
