代码随想录二刷之“贪心算法”～GO

简单题目

1.455. 分发饼干 - 力扣（LeetCode）

func findContentChildren(g []int, s []int) int {sort.Ints(g)sort.Ints(s)index := 0for i := 0;i<len(s);i++{if index < len(g) && g[index] <= s[i]{index++}}return index
}

感悟：本题一点都不难，就是做的时候天气太燥热，然后index和i还有大于小于号搞混了

2.1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

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;i<len(nums);i++{if k > 0 && nums[i] < 0{nums[i] = -nums[i]k--}//负数翻转}if k > 0 && k % 2 == 1{nums[len(nums) - 1] = - nums[len(nums) -1]}result := 0for i := 0; i < len(nums); i++ {result += nums[i]}return result
}

感悟：首先按照绝对值从大到小的方式排序，然后从大到小依次翻转，如果反转之后还需要翻转，那么就选择最小的翻转（k的次数如果是奇数）

3.860. 柠檬水找零 - 力扣（LeetCode）

func lemonadeChange(bills []int) bool {five,ten := 0,0if bills[0] != 5{return false} for i := 0;i<len(bills);i++{if bills[i] == 5{five++}if bills[i] == 10{if five == 0{return false}ten++five--}if bills[i] == 20{if five < 3 && ten == 0 || five ==0 && ten >=1{return false}if ten == 0{five -= 3}else{ten--five -= 1}}}return true
}

感悟：极其基础，适当练练手

中等题目

序列问题

4.376. 摆动序列 - 力扣（LeetCode）

func wiggleMaxLength(nums []int) int {if len(nums) == 0 || len(nums) == 1{return len(nums)}cnt := 0prediff := 0curdiff := 0for i := 0;i < len(nums)-1;i++{curdiff = nums[i] - nums[i+1]if curdiff == 0{continue}if curdiff > 0 && prediff <= 0 || curdiff < 0 && prediff >= 0{prediff = curdiffcnt++}}return cnt+1
}

感悟：忘记处理pre初始的时候是0了。。。

 5.738. 单调递增的数字 - 力扣（LeetCode）

func monotoneIncreasingDigits(n int) int {s := []byte(strconv.Itoa(n))//数字->字符串->字节切片for i := len(s) - 2;i >= 0;i--{if s[i] > s[i+1]{s[i]--//当前位减一for j := i + 1;j<len(s);j++{s[j] = '9'}}}result,_ := strconv.Atoi(string(s))return result
}

感悟：本题没做出来。主体思路就是从后往前遍历，比如332.首先遍历到32，发现不是单调递增到，那么当前位置减1，然后他的下一位一直到最后都置9（因为贪心）。

关于转换问题，strconv(数字与字符串间的转化)

// int() 转换
var b byte = '9'
n := int(b)        // 57 (ASCII码值)
n := int(b - '0')  // 9 (数字值)// string() 转换  
num := 65
s := string(num)   // "A" (Unicode字符)
c := byte('0' + n) // '65' (字符'65')

// 数字 → 字符串
n := 123
s1 := strconv.Itoa(n)       // "123" (推荐)// 字符串 → 数字  
s := "456"
num, err := strconv.Atoi(s) // 456 (推荐)// 字符串 → 字节切片（用于修改字符）
str := "789"
bytes := []byte(str)        // ['7','8','9']// 字节切片 → 字符串
newStr := string(bytes)     // "789"// 字符 → 数字
c := '9'
num := int(c - '0')         // 9 (推荐)
num2 := int(c)              // 57 (错误！得到的是ASCII码)// 数字 → 字符
n := 5
char := byte('0' + n)       // '5' (推荐)
char2 := string(n)          // "\x05" (错误！)

贪心解决股票问题

6.122. 买卖股票的最佳时机 II - 力扣（LeetCode）

func maxProfit(prices []int) int {sum := 0for i := 0;i < len(prices)-1;i++{if prices[i+1] - prices[i] > 0{sum += prices[i+1] - prices[i]}}return sum
}//动态规划
func maxProfit(prices []int) int {dp := make([][]int, len(prices))for i := 0; i < len(dp); i++ {dp[i] = make([]int, 2)}dp[0][0] = 0dp[0][1] = -prices[0]for i := 1;i<len(prices);i++{dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1] = max(dp[i-1][0] - prices[i],dp[i-1][1])}return dp[len(prices)-1][0]
}
func max(a, b int) int {if a > b {return a}return b
}

感悟：局部最优去找全局最优，在本题体现的淋漓尽致！！！也就是说只要挣钱就买入再卖出

两个维度权衡问题

7.135. 分发糖果 - 力扣（LeetCode）

func candy(ratings []int) int {need  := make([]int,len(ratings))sum := 0for i := 0;i<len(ratings);i++{need[i] = 1//初始化}for i:=0;i<len(ratings)-1;i++{//右边大的加一if ratings[i] < ratings [i+1]{need[i+1] = need[i] + 1}}for i := len(ratings)-1;i>0;i--{//左边大  if ratings[i] < ratings[i-1]{need[i-1] = max(need[i-1],need[i]+1)}}for i := 0;i<len(ratings);i++{sum += need[i]}return sum
}
func max(i,j int)int{if i > j{return i}else{return j}
}

感悟：本题需要三刷，半年没刷确实是忘了。核心思路：两次贪心的策略：

• 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
• 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。

这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。

8.406. 根据身高重建队列 - 力扣（LeetCode）

func reconstructQueue(people [][]int) [][]int {sort.Slice(people,func(i,j int)bool{if people[i][0] == people[j][0]{return people[i][1] < people[j][1]}else{return people[i][0] > people[j][0]}})//排序，两个维度先确定身高res := [][]int{}for i := 0;i<len(people);i++{k := people[i][1]res = append(res[:k],append([][]int{people[i]},res[k:]...)...)}return res
}

感悟：这道题要三刷，一点也不会。主体思想：比如你在排队，先让个子高的去排，然后等矮个子排的时候，高个子已经有序了。所以按照people[i][1]去插入。

有点难度

区间问题

9.55. 跳跃游戏 - 力扣（LeetCode）

func canJump(nums []int) bool {if len(nums) == 0{return true}cover := 0for i := 0;i<=cover;i++{cover = max(nums[i]+i,cover)if cover >= len(nums)-1{return true}}return false
}
func max(i,j int)int{if i > j{return i}else{return j}
}

感悟：瞅了眼一刷的记录，才想起了cover

10.45. 跳跃游戏 II - 力扣（LeetCode）

func jump(nums []int) int {if len(nums) <= 1{return 0}curcover := 0 //当前覆盖最远距离step := 0 //最大步数nextcover := 0 //下一步覆盖最远距离for i:= 0;i<len(nums);i++{nextcover = max(nums[i]+i,nextcover)if i == curcover{step++curcover = nextcoverif nextcover >= len(nums)-1{break}}}return step
}func max(i,j int)int{if i > j{return i}else{return j}
}//优化后
func jump(nums []int) int {curcover := 0 //当前覆盖最远距离step := 0 //最大步数nextcover := 0 //下一步覆盖最远距离for i:= 0;i<len(nums)-1;i++{nextcover = max(nums[i]+i,nextcover)if i == curcover{step++curcover = nextcover        }}return step
}

感悟：本题需要三刷，核心思路就是，如果当前遍历到比如从第一个开始能跳到的最远距离的话（且下一步还没有跳到最后一个格子里），那就再加一步。然后nextcover赋值给curcover，然后接着计算nextcover，知道跳出去，否则如果i又等于curcover，那么接着跳一步，知道nextcover可以覆盖到。

对于优化后的版本：精髓在下标i只移动到倒数第二个位置，如果i==当前覆盖到的最大下标，证明到倒数第二步，还需要一步才能跳出去（题干规定）。如果不等于当前覆盖到最大下标，说明最大下标已经出去了，所以自然不用step++

11.452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

//思路1
func findMinArrowShots(points [][]int) int {sort.Slice(points,func(a,b int)bool{return points[a][0] < points[b][0]})cnt := 1curcover := points[0][1]for i := 1;i<len(points);i++{if points[i][0] <= curcover {if points[i][1] < curcover{curcover = points[i][1]}}else{curcover = points[i][1]cnt++}}return cnt
}//思路2
func findMinArrowShots(points [][]int) int {sort.Slice(points,func(a,b int)bool{return points[a][1] < points[b][1]})cnt := 1curcover := points[0][1]for i := 1;i<len(points);i++{if points[i][0] > curcover{cnt++curcover = points[i][1]}}return cnt
}

感悟：对于思路一，刚才忘考虑这种情况：[2,5][2,3][4,6]。索引curcover忘记更新了,导致缺少情况。所以要这种情况就要找相对小的cover。（按照起始地从小到大排序）。对于思路二，如果按照目的地（从小到大排序），就不需要上述操作了。因为如果下一个的起始点小于cover（暗含着该点的目的地大于cover了），continue。直到遇到下一个起始点大于cover的位置。

12.435. 无重叠区间 - 力扣（LeetCode）

//终止点排序
func eraseOverlapIntervals(intervals [][]int) int {if len(intervals) == 0{return 0}sort.Slice(intervals,func(i,j int)bool{return intervals[i][1] < intervals[j][1]})count := 1cur := intervals[0][1]for i := 1;i<len(intervals);i++{if intervals[i][0] >= cur{//可以保留count++cur = intervals[i][1]}}return len(intervals) - count
}//起始点排序
func eraseOverlapIntervals(intervals [][]int) int {if len(intervals) == 0 {return 0}// 按起始点升序排序，起始点相同时按结束点升序排序sort.Slice(intervals, func(i, j int) bool {if intervals[i][0] == intervals[j][0] {return intervals[i][1] < intervals[j][1]}return intervals[i][0] < intervals[j][0]})res := 0cur := intervals[0][1]for i := 1;i<len(intervals);i++{if intervals[i][0] < cur{//重叠区间处理res++if intervals[i][1] < cur{cur = intervals[i][1]}}else{cur = intervals[i][1]}}return res
}

感悟：我发现我经常性的使用起始点排序，然后导致逻辑混乱。脑袋里要时刻想着：[2，7][3，6],这种情况删掉[2,7]，之后用6作为cur。或者索性用终点排序，这样直接头对尾

13.763. 划分字母区间 - 力扣（LeetCode）

func partitionLabels(s string) []int {res := []int{}var marks [26]intleft,right := 0,0for i:=0;i<len(s);i++{marks[s[i] - 'a'] = i}//最远到达for i:=0;i<len(s);i++{right = max(right,marks[s[i]-'a'])if i == right{res = append(res,right - left + 1)left = i+1right = 0}}return res
}func max(a, b int) int {if a < b {a = b;}return a;
}

感悟：一刷的时候当时太忙了，思路有点忘了，但是看一眼之后就能自然的写出来了。先预处理每个字符的最后出现位置，然后使用贪心策略：遍历时维护当前区间能达到的最远边界，当当前位置等于最远边界时，就找到了一个合理的划分段。"

14.56. 合并区间 - 力扣（LeetCode）

func merge(intervals [][]int) [][]int {if len(intervals) == 1{return intervals}sort.Slice(intervals,func(i,j int)bool{return intervals[i][0] < intervals[j][0]})res := [][]int{}cur := intervals[0][1]pre := intervals[0][0]for i := 1;i<len(intervals);i++{if intervals[i][0] <= cur{if intervals[i][1] <= cur{continue}else{cur = intervals[i][1]}}else{res = append(res,[]int{pre,cur})pre = intervals[i][0]cur = intervals[i][1]}}res = append(res,[]int{pre,cur})return res
}

感悟：本题感觉写的很随意，感觉就是那么回事儿，一遍过了～

其余

15.53. 最大子数组和 - 力扣（LeetCode）

func maxSubArray(nums []int) int {if len(nums) == 0 {return 0}currentSum := nums[0]  // 当前子数组的和globalMax := nums[0]   // 全局最大值for i := 1; i < len(nums); i++ {// 决定是开始新的子数组，还是加入当前子数组if nums[i] > currentSum + nums[i] {currentSum = nums[i]} else {currentSum += nums[i]}// 更新全局最大值if currentSum > globalMax {globalMax = currentSum}}return globalMax
}//动态规划
func maxSubArray(nums []int) int {max := nums[0]//nums[i]表示到i的最大子序和for i := 1;i<len(nums);i++{if nums[i] + nums[i-1] > nums[i]{nums[i] += nums[i-1]}if nums[i] > max{max = nums[i]}}return max
}

感悟：我发现今天做题都是细节方面的错误，这个题没有记录全局最大值。比如对于[-2,1,-3,4,-1,2,1,-5,4]，他只会一直更新到最后，不会记录局部最大值

16.134. 加油站 - 力扣（LeetCode）

func canCompleteCircuit(gas []int, cost []int) int {totalGass, totalCost := 0 ,0currentGas := 0start := 0for i := 0;i<len(gas);i++{totalGass += gas[i]totalCost += cost[i]currentGas += gas[i] - cost[i]if currentGas < 0{start = i + 1currentGas = 0}}if totalCost > totalGass{return -1}return start
}

感悟：本题需要三刷，刚才刷的时候直接暴力了。。。然后刚才贪心还没理解明白，要理解的是：

ABC（这里代表区间和）。如果A+B是第一次出现负数的话，说明一定要在i+1重新寻找。那么为什么不会再AB之间重新找呢。因为A+B>0,如果在AB的话，那么B>0,但既然是第一次出现负数，所以A>0，矛盾。同时如果i+1到最后都大于零的话，再结合前面整体的负收益，如果total大于0，那么就可以抵消掉，否则返回-1.

如果从起点s到i的累计和第一次出现负数，那么：

1. 从0到i之间的任何点作为起点都无法完成全程

2. 但是可能存在从i+1开始的起点

17.968. 监控二叉树 - 力扣（LeetCode）

func minCameraCover(root *TreeNode) int {// 定义状态：// 0: 该节点未被监控// 1: 该节点被监控但没有摄像头// 2: 该节点有摄像头result := 0var dfs func(node *TreeNode) intdfs = func(node *TreeNode) int {if node == nil {return 1 // 空节点默认被监控（虚拟监控）}left := dfs(node.Left)right := dfs(node.Right)// 如果左右子节点有任何一个未被监控if left == 0 || right == 0 {result++ // 需要在此节点放置摄像头return 2 // 返回有摄像头的状态}// 如果左右子节点有任何一个有摄像头if left == 2 || right == 2 {return 1 // 此节点被监控但无摄像头}// 左右子节点都被监控但都没有摄像头return 0 // 此节点未被监控}// 检查根节点是否被监控if dfs(root) == 0 {result++}return result
}

四种情况：

• 0: 该节点未被监控
• 1: 该节点被监控但没有摄像头
• 2: 该节点有摄像头

1.左右孩子至少一个没有被监控：父节点要摄像头；​​​​​​​

// 情况1// left == 0 && right == 0 左右节点无覆盖// left == 2 && right == 0 左节点有摄像头，右节点无覆盖// left == 0 && right == 2 左节点有无覆盖，右节点摄像头// left == 0 && right == 1 左节点无覆盖，右节点覆盖// left == 1 && right == 0 左节点覆盖，右节点无覆盖

2.左右孩子都被监控：父节点不被监控0（因为他的父节点要添加摄像头）；

// 情况2// left == 1 && right == 1 左右节点都被监控

3.左右孩子至少一个摄像头：父节点被监控；

// 情况3// left == 1 && right == 2 右节点有摄像头，左节点有覆盖// left == 2 && right == 1 右节点有覆盖，左节点有摄像头// left == 2 && right == 2 左右节点都有摄像头

4.如果找到最后遍历完之后，根节点还是空节点，那么加一