前言
一共四题，AC三题，第四题线段树不搞acm了根本写不出来- -，懒得复习一遍了，就写三题的题解吧
第一题
2210.统计数组中峰和谷的数量
2210.统计数组中峰和谷的数量
题解
简单题，直接模拟就行了，不过题目中说的是左边第一个不相等和右边第一个不相等，相等的要跳过再去找，所有这里用两个for找出l和r
代码
func countHillValley(nums []int) int { mp := make(map[int]int) ans := 0 for i := 1; i <= len(nums)-1-1; i++ { l, r := i-1, i+1 for l >= 0 && nums[l] == nums[i] { l-- } for r <= len(nums)-1 && nums[r] == nums[i] { r++ } if l >= 0 && r <= len(nums)-1 { if nums[i] > nums[l] && nums[i] > nums[r] { mp[i] = 1 if mp[i-1] == 1 { continue } ans++ } else if nums[i] < nums[l] && nums[i] < nums[r] { mp[i] = -1 if mp[i-1] == -1 { continue } ans++ } } } return ans }
第二题
2211.统计道路上的碰撞次数
2211.统计道路上的碰撞次数
题解
两个方向相反的车相撞加2分，s车被撞加1分，其实就是每个撞车都会贡献1分，不分左右，因为RL=2，R=1，L=1，所以除了开头的LLL和结尾的RRR会跑出去，中间的都会撞，那么就统计L和R有多少个就行了
代码
func countCollisions(directions string) int { l, r := 0, len(directions)-1 ans := 0 for l <= len(directions)-1 && directions[l] == 'L' { l++ } for r >= 0 && directions[r] == 'R' { r-- } for i := l; i <= r; i++ { if directions[i] == 'L' || directions[i] == 'R' { ans++ } } return ans }
第三题
2212.射箭比赛中的最大得分
2212.射箭比赛中的最大得分
题解
两种思路
- dfs+回溯，贪心，想要得分高，就从分高的区域开始计算，对于每个区域，有不射和比A多射一支的选择，那么就dfs即可，注意如果到了0区域，还有多的剑，就都给0就好了
- 二进制枚举，一共12个区域，2^12次，全部枚举一遍即可
代码
- dfs+回溯
func maximumBobPoints(numArrows int, aliceArrows []int) (ans []int) { score, cnt := 0, 0 ans, cntSlice := make([]int, len(aliceArrows)), make([]int, len(aliceArrows)) var dfs func(numArrows int, idx int) dfs = func(numArrows int, idx int) { if numArrows == 0 && idx == -1 { if score < cnt { score = cnt copy(ans, cntSlice) } } if idx <= -1 || numArrows < 0 { return } //不选idx cntSlice[idx] = 0 dfs(numArrows, idx-1) //选idx cnt += idx if idx == 0 { cntSlice[idx] = numArrows dfs(0, idx-1) } else { cntSlice[idx] = aliceArrows[idx] + 1 dfs(numArrows-aliceArrows[idx]-1, idx-1) } cnt -= idx //回溯 cntSlice[idx] = 0 //回溯 } dfs(numArrows, 11) return }
- 二进制枚举
func maximumBobPoints(numArrows int, aliceArrows []int) (ans []int) { n := 1<<len(aliceArrows) - 1 score := 0 for i := 0; i <= n; i++ { cnt := 0 out := 0 cntSlice := make([]int, len(aliceArrows)) for j, v := range aliceArrows { if i>>j&1 == 1 { //其中一个区域如果选中了 cnt += j //统计分数 out += v + 1 //统计射出去的剑 cntSlice[j] = v + 1 //比A多射一个剑 } } if out > numArrows { continue } cntSlice[0] += numArrows - out //把剩下的减都给0区域 if score < cnt { score = cnt ans = cntSlice } } return }
