我要评论这次有点水 最后题vector申请空间莫名其妙超时 用int[]才过了
文章目录
圆形赛道上经过次数最多的扇区
a.题目
给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。
请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。
注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。
示例 1
输入：n = 4, rounds = [1,3,1,2]
输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）–> 4 --> 1（阶段 2 结束）–> 2（阶段 3 结束，即本场马拉松结束）
其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。扇区 3 和 4 都只经过了一次。
示例 2
输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
输出：[2]
示例 3
输入：n = 7, rounds = [1,3,5,7]
输出：[1,2,3,4,5,6,7]
提示
- 2 <= n <= 100
- 1 <= m <= 100
- rounds.length == m + 1
- 1 <= rounds[i] <= n
- rounds[i] != rounds[i + 1] ，其中 0 <= i < m
a.分析
100的复杂度 抛开脑子直接模拟 第一题还是要快
直接按题目说的做 选阶段的起点和终点 然后一步一步跑过去
每跑过一个扇区就记录那个扇区经历+1
最后把最大记录的扇区的索引输出到答案中即可
总的时间复杂度为O（n^2) 即遍历阶段的n乘上模拟跑圈的n
也许有更快的 但是第一题 不花时间想了
模拟要注意下 每次选取的是起点和终点 终点会在下个起点计数
所以最后一个终点需要额外记录一下
a.参考代码
class Solution {
public:
vector<int> mostVisited(int n, vector<int>& rounds) {
vector<int> cnt(n,0); //计数 cnt[i]表示第i个扇区经历的次数
for(int i=1;i<rounds.size();i++){
int a=rounds[i-1]-1,b=rounds[i]-1; //起点和终点
for(int j=a;j!=b;j=(j+1)%n){ //绕圈圈跑 终点不计数
cnt[j]++;
}
}
cnt[rounds.back()-1]++; //最后终点加个计数
int Max=0; //以下是不用脑子的挑选最大的索引
for(int i=0;i<cnt.size();i++)Max=max(Max,cnt[i]);
vector<int> ans;
for(int i=0;i<cnt.size();i++)if(cnt[i]==Max)ans.push_back(i+1);
return ans;
}
};
你可以获得的最大硬币数目
b.题目
有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
- Alice 将会取走硬币数量最多的那一堆。
- 你将会取走硬币数量第二多的那一堆。
- Bob 将会取走最后一堆。
重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
示例 1
输入：piles = [2,4,1,2,7,8]
输出：9
解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
你可以获得的最大硬币数目：7 + 2 = 9.
考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
示例 2
输入：piles = [2,4,5]
输出：4
示例 3
输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18
提示
- 3 <= piles.length <= 10^5
- piles.length % 3 == 0
- 1 <= piles[i] <= 10^4
b.分析
这题看了一下之后有个贪心猜想：
每次总是选择剩下的 {最小，次大，最大}
而得分总是选择次大的
那么这个贪心对不对呢 比赛时简单证明下：
反证法 假如不选择次大的 那么就只能选择更小的 那么选择更小的之后
显然就更没办法选择这个次大的(因为会被下轮当最大的取走)
如果每次都不选次大 显然最后大的都被Alice拿走
总的时间复杂度为O（n）
b.参考代码
class Solution {
public:
int maxCoins(vector<int>& piles) {
int n=piles.size()/3;
sort(piles.begin(),piles.end());
int ans=0;
for(int i=piles.size()-2;n;n--,i-=2)ans+=piles[i]; //每次都拿次小的
return ans;
}
};
查找大小为 M 的最新分组
c.题目
给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。
示例 1
输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1：“00100”，由 1 构成的组：[“1”]
步骤 2：“00101”，由 1 构成的组：[“1”, “1”]
步骤 3：“10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：“11101”，由 1 构成的组：[“111”, “1”]
步骤 5：“11111”，由 1 构成的组：[“11111”]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。
示例 2
输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1：“00100”，由 1 构成的组：[“1”]
步骤 2：“10100”，由 1 构成的组：[“1”, “1”]
步骤 3：“10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：“10111”，由 1 构成的组：[“1”, “111”]
步骤 5：“11111”，由 1 构成的组：[“11111”]
不管是哪一步骤都无法形成长度为 2 的一组 1 。
示例 3
输入：arr = [1], m = 1
输出：1
示例 4
输入：arr = [2,1], m = 2
输出：2
提示
- n == arr.length
- 1 <= n <= 10^5
- 1 <= arr[i] <= n
- arr 中的所有整数 互不相同
- 1 <= m <= arr.length
c.分析
怎么说呢 我看到它的那个样例 就觉得它这样子每步都统计出有多少个连续个1就已经能做了 那么我们就根据这个模拟每步的步骤来实现
我们需要有一个记录每个位置1的个数的东西 比如说011101101
我就想v[1]=v[2]=v[3]=3 v[5]=v[6]=2 v[8]=1 类似这样的
那么我们在处理相邻的时候就可以直接通过v数组来获取到长度
我们也需要一个cnt数组 例如cnt[2]=4 表示连续的1长度为2有4段
首先 每步都只能把一个位置x的0变成1 那么变完之后 就只会影响到它隔壁的两个1的计数
也就是说 把隔壁两个1给延展了
延展之后会出现以下变化：
- 前后的连续的1的cnt计数会变少（因为和当前的1合并了）
- 合并之后要更新一个左右区间的v计数 （如何更新是重点）
前后连续1计数变少这个容易搞定 只需要cnt[v[x]]-=1即可
那么更新左右区间的话 如果把v全部都更新的话 那么这个复杂度会炸
思考一下发现 由于是连续的 所以下次肯定只会碰到左右端点的1 （不可能在中间 因为是连续的）
所以连续1的中间的v就没有意义了 就不用更新了 因此每个步骤只需要更新两个v即可 复杂度可以接受
显然 左端点为x-v[x-1] 右端点为x+v[x+1] 假如隔壁两个都有1的话 如果没有 则左端点和右端点初始值为x
那么一顿操作之后 每次步骤看一下cnt[m]是否>0即可 更新一下最后步骤的索引i
总的时间复杂度为遍历步骤的O（n） 每次更新左右端点计数以及cnt计数为O（1）
详细看代码注释理解
c.参考代码
class Solution {
public:
int findLatestStep(vector<int>& arr, int m) {
int n=arr.size();
vector<int> v(n+1,0); //v[i]表示第i个位置的连续1长度
vector<int> cnt(n+1,0); //cnt[i]表示长度i的连续1有多少段
int ans=-1; //没有答案
for(int i=0;i<arr.size();i++){
int x=arr[i]; //当前位置
int l=x,r=x; //初始化左右端点
if(x-1>0&&v[x-1]){ //左边有1 合并
cnt[v[x-1]]--;
l=x-v[x-1];
}
if(x+1<=n&&v[x+1]){ //右边有1 合并
cnt[v[x+1]]--;
r=x+v[x+1];
}
v[l]=1+v[l]+v[r]; //更新下左右端点的v
v[r]=v[l];
cnt[v[l]]++;
if(cnt[m])ans=i+1; //更新答案
}
return ans;
}
};
石子游戏 V
d.题目
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1
输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
示例 2
输入：stoneValue = [7,7,7,7,7,7,7]
输出：28
示例 3
输入：stoneValue = [4]
输出：0
提示
- 1 <= stoneValue.length <= 500
- 1 <= stoneValue[i] <= 10^6
d.分析
直觉 你需要遍历全部分割情况 不存在贪心的做法
那么首先就要想到就是遍历分割点 不同分割点后再在剩余的再进行遍历分割点
很显然 分割点后{i,j}区间 是可以复用的 立刻想到dp
于是 定义dp[i][j]为{i,j}区间的答案 也就是假如只有{i,j}区间的子问题
边界为dp[i][i]=0 因为一个石头不可分
状态转移方程 很轻松就能根据题目得出来
对于{i,j}区间 假设我们定的分割点为k 把其分成{i,k-1}和{k,j}后
sum{i,k-1}>sum{k,j}左大右小 因此我们只能拿小的 拿完小的之后再分割的问题就是已知的dp状态dp[i][j]=max(dp[i][j],dp[k][j]+sum{k,j}sum{i,k-1}<sum{k,j}左小右大 因此我们只能拿小的 拿完小的之后再分割的问题就是已知的dp状态dp[i][j]=max(dp[i][j],dp[i][k-1]+sum{i,k-1}- 相等的情况 那么此时的sum都是一样的 那么就比较下
dp[i][k-1] dp[k][j]哪个大即可
由于转移方程的dp[i][k-1]和dp[k][j]需要已知 那么我们需要根据长度去迭代更新子问题的答案dp值 最小是len=2开始更新到最终问题的len=n
至于sum 做到第四题的同学都知道可以用前缀和来获取
总的时间复杂度为O（n^3) 是可以过的 貌似还能优化成平方 比赛肯定不去想 500可以过
d.参考代码
int dp[505][505];
int sum[505];
class Solution {
public:
int n;
int stoneGameV(vector<int>& sv) {
n=sv.size();
if(n==1)return 0;
memset(dp,0,sizeof(dp));
sum[0]=sv[0];
for(int i=1;i<n;i++)sum[i]=sv[i]+sum[i-1]; //前缀和预处理
for(int len=1;len<=n;len++) //枚举长度
for(int l=0;l<n-len;l++){ //枚举左区间起点
int r=l+len; //终点
for(int k=l+1;k<=r;k++){ //枚举分割点
int suml=sum[k-1]-(l-1>=0?sum[l-1]:0),sumr=sum[r]-sum[k-1];
if(suml>sumr)dp[l][r]=max(dp[l][r],dp[k][r]+sumr);
else if(suml<sumr)dp[l][r]=max(dp[l][r],dp[l][k-1]+suml);
else dp[l][r]=max(dp[l][r],suml+max(dp[l][k-1],dp[k][r]));
}
}
return dp[0][n-1]; //最终的最大子问题
}
};
本文地址：https://blog.csdn.net/weixin_43596429/article/details/108181963
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论