第 285 场周赛

• 6027. 统计数组中峰和谷的数量
• 6028. 统计道路上的碰撞次数
• 6029. 射箭比赛中的最大得分
• 6030. 由单个字符重复的最长子字符串

6027. 统计数组中峰和谷的数量

题目
给你一个下标从 0 开始的整数数组 nums 。如果两侧距 i 最近的不相等邻居的值均小于 nums[i] ，则下标 i 是 nums 中，某个峰的一部分。类似地，如果两侧距 i 最近的不相等邻居的值均大于 nums[i] ，则下标 i 是 nums 中某个谷的一部分。对于相邻下标 i 和 j ，如果 nums[i] == nums[j] ， 则认为这两下标属于 同一个 峰或谷。

注意，要使某个下标所做峰或谷的一部分，那么它左右两侧必须 都 存在不相等邻居。

返回 nums 中峰和谷的数量。

示例 1：

输入：nums = [2,4,1,1,6,5]
输出：3
解释：
在下标 0 ：由于 2 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：4 的最近不相等邻居是 2 和 1 。由于 4 > 2 且 4 > 1 ，下标 1 是一个峰。
在下标 2 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 2 是一个谷。
在下标 3 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 3 符合谷的定义，但需要注意它和下标 2 是同一个谷的一部分。
在下标 4 ：6 的最近不相等邻居是 1 和 5 。由于 6 > 1 且 6 > 5 ，下标 4 是一个峰。
在下标 5 ：由于 5 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 3 个峰和谷，所以返回 3 。

示例 2：

输入：nums = [6,6,5,5,4,1]
输出：0
解释：
在下标 0 ：由于 6 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：由于 6 的左侧不存在不相等邻居，所以下标 1 既不是峰也不是谷。
在下标 2 ：5 的最近不相等邻居是 6 和 4 。由于 5 4 ，下标 2 既不是峰也不是谷。
在下标 3 ：5 的最近不相等邻居是 6 和 4 。由于 5 4 ，下标 3 既不是峰也不是谷。
在下标 4 ：4 的最近不相等邻居是 5 和 1 。由于 4 1 ，下标 4 既不是峰也不是谷。
在下标 5 ：由于 1 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 0 个峰和谷，所以返回 0 。

提示：

3 <= nums.length <= 100
1 <= nums[i] <= 100

分析
本题其实是一个查找极小值和极大值的题目，以第一个示例为例，我们做出图像

由于连续相同的数只计算一次，所以我们的问题可以变为

化成这种形式之后我们只需比较一个点与其前后的点的大小即可
代码

class Solution {public:    int countHillValley(vector<int>& nums) { if(nums.size()==0){     return 0; } int cnt=0; vector<int> tmp; tmp.push_back(nums[0]); for(int i=1; i < nums.size(); i++){     if(tmp.back() != nums[i]){  tmp.push_back(nums[i]);     } } for(int i=1; i < tmp.size()-1; i++){     if((tmp[i-1] < tmp[i] && tmp[i+1] < tmp[i])||(tmp[i-1] > tmp[i] && tmp[i+1] > tmp[i])){  cnt++;     } } return cnt;    }};

6028. 统计道路上的碰撞次数

题目
在一条无限长的公路上有 n 辆汽车正在行驶。汽车按从左到右的顺序按从 0 到 n - 1 编号，每辆车都在一个 独特的 位置。

给你一个下标从 0 开始的字符串 directions ，长度为 n 。directions[i] 可以是 ‘L’、‘R’ 或 ‘S’ 分别表示第 i 辆车是向 左 、向 右 或者 停留 在当前位置。每辆车移动时 速度相同 。

碰撞次数可以按下述方式计算：

当两辆移动方向 相反 的车相撞时，碰撞次数加 2 。
当一辆移动的车和一辆静止的车相撞时，碰撞次数加 1 。
碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。

返回在这条道路上发生的 碰撞总次数 。

示例 1：

输入：directions = “RLRSLL”
输出：5
解释：
将会在道路上发生的碰撞列出如下：

• 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。
• 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。
• 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。
• 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。
  因此，将会在道路上发生的碰撞总次数是 5 。

示例 2：

输入：directions = “LLRR”
输出：0
解释：
不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。

提示：

1 <= directions.length <= 105
directions[i] 的值为 ‘L’、‘R’ 或 ‘S’

分析
模拟题，按照题目要求模拟即可。在这里我们采用先从左向右观察是否会相撞并统计，然后将相撞的车标记为静止，在从右向左观察是否会相撞。在代码中我们用ocur变量来表示前一个位置的状态，从左向右时第一个位置默认为L因为无论是向哪里走都不会撞，从右想左同理设为R
代码

class Solution {public:    int countCollisions(string directions) { int cnt=0; char ocur='L'; for(int i=0; i < directions.size(); i++){     if(ocur=='R' && directions[i]=='L'){  cnt+=2;  ocur='S';  directions[i]= directions[i-1]='S';     }else if(ocur=='R' && directions[i]=='S'){  cnt++;  ocur='S';  directions[i]= directions[i-1]='S';     }else if(ocur=='S' && directions[i]=='L'){  cnt++;  ocur='S';  directions[i]= directions[i-1]='S';     }else{  ocur=directions[i];     } } ocur='R'; for(int i=directions.size()-1; i >= 0; i--){     if(ocur=='L' && directions[i]=='R'){  cnt+=2;  ocur='S';  directions[i]='S';     }else if(ocur=='S' && directions[i]=='R'){  cnt++;  ocur='S';  directions[i]='S';     }else if(ocur=='L' && directions[i]=='S'){  cnt++;  ocur='S';  directions[i]='S';     }else{  ocur=directions[i];     } } return cnt;    }};

6029. 射箭比赛中的最大得分

题目
Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
如果 ak == bk == 0 ，那么无人得到 k 分。
例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个 计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

提示：

1 <= numArrows <= 10^5
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows

贪心+二进制做法分析
贪心+二进制遍历，由于这道题的范围较小，所以我们可以使用二进制遍历根据贪心的思路我们应该优先从最高分值的时候开始射箭，同时要比Alice射出的箭多1才能保证得分。对于最后有多余的箭的情况我们直接将箭射到分数为0的情况即可
贪心+二进制做法代码

class Solution {public:    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) { int maxScore=0; vector<int> ans; for(int i=1;i<(1<<12);i++){     int cur = 0;     vector<int> tmp(12);     int arrows = numArrows;     for(int j=11;j>=0;j--){  if(i&(1<<j)){      if(arrows>aliceArrows[j]){   tmp[j]=aliceArrows[j]+1;   arrows-=tmp[j];   cur+=j;      }      else break;  }     }     if(arrows)tmp[0]+=arrows;     if(cur>maxScore){  maxScore=cur;  ans=tmp;     } } return ans;    }};

动态规划还原做法分析
dp数组为dp[12][numArrows+1]表示的是前i个位置和前j个箭数最大的得分， 初始值为0。
当前i个位置和前j个箭数时，如果j<i位置alice的箭说明这时就算是把所有的箭都射完也不能得分，所以这时能达到的最高分为前i-1个位置和前j个箭数时的最高分数；如果j>=i位置alice的箭，说明此时可以得到第i个位置的分数，这是就面临两个选择——射出大于alice的箭得到当前的分数或者保留当前的箭数。那么在前i个位置和前j个箭数时的最高分数为前i-1个位置和前j个箭数时的最高分数（i位置不射箭的分数）和前i-1个位置和前j-alice箭数-1个箭数时的最高分数（i位置射箭）。这里为什么是j-alice箭数-1呢，我们要保证前面的分数最高，就要保证除了现在我们i位置需要射出的箭之外，在i之前的箭已经射完。到这里我们只是完成了一半，我们还需要对射箭过程进行还原

还原过程相较前一个过程比较简单，我们只需从后先前遍历：如果i位置的最大分数比i-1位置高，说明在i位置一定有箭射入，我们按照规则射入即可。但是我们有可能遇到箭用不完的情况，由于只用返回一种情况并且我们已经取得了最大值，所以我们默认多出来的箭射到得分为0的位置即可。
动态规划还原做法代码

class Solution {public:    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {  int dp[12][numArrows+1]; memset(dp,0,sizeof(dp)); vector<int>ans(12,0);     for(int i=1;i<12;i++){     int aa = aliceArrows[i];     for(int j=1;j<=numArrows;j++){  if(j<aa+1)dp[i][j] = dp[i-1][j];  else dp[i][j] = max(dp[i-1][j-aa-1]+i,dp[i-1][j]);     } }  for(int i=11;i>0;i--){     if(dp[i][numArrows]>dp[i-1][numArrows]){  int aa = aliceArrows[i];  ans[i]=aa+1;  numArrows-=(aa+1);     } }  ans[0] = numArrows; return ans;    }};

6030. 由单个字符重复的最长子字符串

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。

示例 1：

输入：s = “babacc”, queryCharacters = “bcb”, queryIndices = [1,3,3]
输出：[3,3,4]
解释：

• 第 1 次查询更新后 s = “bbbacc” 。由单个字符重复组成的最长子字符串是 “bbb” ，长度为 3 。
• 第 2 次查询更新后 s = “bbbccc” 。由单个字符重复组成的最长子字符串是 “bbb” 或 “ccc”，长度为 3 。
• 第 3 次查询更新后 s = “bbbbcc” 。由单个字符重复组成的最长子字符串是 “bbbb” ，长度为 4 。
  因此，返回 [3,3,4] 。

示例 2：

输入：s = “abyzz”, queryCharacters = “aa”, queryIndices = [2,1]
输出：[2,3]
解释：

• 第 1 次查询更新后 s = “abazz” 。由单个字符重复组成的最长子字符串是 “zz” ，长度为 2 。
• 第 2 次查询更新后 s = “aaazz” 。由单个字符重复组成的最长子字符串是 “aaa” ，长度为 3 。
  因此，返回 [2,3] 。

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 105
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length

分析
线段树染色
代码

const int maxn = 1e5+5;int stll[maxn*4], strr[maxn*4], stmm[maxn*4];const char *ss;inline void push_up(int x, int m, int l, int r){    stll[x] = stll[x<<1];    strr[x] = strr[x<<1|1];    stmm[x] = max(stmm[x<<1], stmm[x<<1|1]);    if(ss[m] == ss[m+1]){ if(stll[x<<1] >= m-l+1)     stll[x] += stll[x<<1|1]; if(strr[x<<1|1] >= r-m)     strr[x] += strr[x<<1]; stmm[x] = max(stmm[x], strr[x<<1]+stll[x<<1|1]);    }}void build(int x, int l, int r){    if(l == r){ stll[x] = strr[x] = stmm[x] = 1; return;    }    int m = (l+r)>>1;    build(x<<1, l, m);    build(x<<1|1, m+1, r);    push_up(x, m, l, r);}void update(int x, int l, int r, int id){    if(l == r) return;    int m = (l+r)>>1;    if(id <= m) update(x<<1, l, m, id);    else update(x<<1|1, m+1, r, id);    push_up(x, m, l, r);}class Solution {public:    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) { int n = s.length(), k = queryIndices.size(); ss = s.c_str(); build(1, 0, n-1); vector<int> ret; for(int i = 0; i < k; i++){     int cid = queryIndices[i];     s[cid] = queryCharacters[i];     update(1, 0, n-1, cid);     ret.push_back(stmm[1]); } return ret;    }};