簡單題目
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的累計和第一次出現負數，那么：
-
從0到i之間的任何點作為起點都無法完成全程
-
但是可能存在從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.如果找到最后遍歷完之后，根節點還是空節點，那么加一
