前言

一共四题，AC三题，第四题线段树不搞acm了根本写不出来- -，懒得复习一遍了，就写三题的题解吧

第一题

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.统计道路上的碰撞次数

题解

两个方向相反的车相撞加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.射箭比赛中的最大得分

题解

两种思路

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
}