简单题目
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
index := 0
for 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 := 0
for i := 0; i < len(nums); i++ {
result += nums[i]
}
return result
}感悟：首先按照绝对值从大到小的方式排序，然后从大到小依次翻转，如果反转之后还需要翻转，那么就选择最小的翻转（k的次数如果是奇数）
func lemonadeChange(bills []int) bool {
five,ten := 0,0
if 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
}感悟：极其基础，适当练练手
中等题目
序列问题
func wiggleMaxLength(nums []int) int {
if len(nums) == 0 || len(nums) == 1{
return len(nums)
}
cnt := 0
prediff := 0
curdiff := 0
for 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 = curdiff
cnt++
}
}
return cnt+1
}感悟：忘记处理pre初始的时候是0了。。。
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 := 0
for 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] = 0
dp[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
}感悟：局部最优去找全局最优，在本题体现的淋漓尽致！！！也就是说只要挣钱就买入再卖出
两个维度权衡问题
func candy(ratings []int) int {
need := make([]int,len(ratings))
sum := 0
for 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]去插入。
有点难度
区间问题
func canJump(nums []int) bool {
if len(nums) == 0{
return true
}
cover := 0
for 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
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 = nextcover
if 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 := 1
curcover := 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 := 1
curcover := 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的位置。
//终止点排序
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 := 1
cur := 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 := 0
cur := 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。或者索性用终点排序，这样直接头对尾
func partitionLabels(s string) []int {
res := []int{}
var marks [26]int
left,right := 0,0
for 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+1
right = 0
}
}
return res
}
func max(a, b int) int {
if a < b {
a = b;
}
return a;
}感悟：一刷的时候当时太忙了，思路有点忘了，但是看一眼之后就能自然的写出来了。先预处理每个字符的最后出现位置，然后使用贪心策略：遍历时维护当前区间能达到的最远边界，当当前位置等于最远边界时，就找到了一个合理的划分段。"
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
}
感悟：本题感觉写的很随意，感觉就是那么回事儿，一遍过了～
其余
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]，他只会一直更新到最后，不会记录局部最大值
func canCompleteCircuit(gas []int, cost []int) int {
totalGass, totalCost := 0 ,0
currentGas := 0
start := 0
for i := 0;i<len(gas);i++{
totalGass += gas[i]
totalCost += cost[i]
currentGas += gas[i] - cost[i]
if currentGas < 0{
start = i + 1
currentGas = 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开始的起点
func minCameraCover(root *TreeNode) int {
// 定义状态：
// 0: 该节点未被监控
// 1: 该节点被监控但没有摄像头
// 2: 该节点有摄像头
result := 0
var dfs func(node *TreeNode) int
dfs = 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.如果找到最后遍历完之后，根节点还是空节点，那么加一
