欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 第203场周赛 题解

程序员文章站 2022-06-22 23:50:22
这次有点水 最后题vector申请空间莫名其妙超时 用int[]才过了文章目录圆形赛道上经过次数最多的扇区a.题目a.分析a.参考代码你可以获得的最大硬币数目b.题目b.分析b.参考代码查找大小为 M 的最新分组c.题目c.分析c.参考代码石子游戏 Vd.题目d.分析d.参考代码圆形赛道上经过次数最多的扇区a.题目给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成,扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛,该马拉松全程由 m 个阶段组成。其中,第...

这次有点水 最后题vector申请空间莫名其妙超时 用int[]才过了

圆形赛道上经过次数最多的扇区

a.题目

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成,扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛,该马拉松全程由 m 个阶段组成。其中,第 i 个阶段将会从扇区 rounds[i - 1] 开始,到扇区 rounds[i] 结束。举例来说,第 1 阶段从 rounds[0] 开始,到 rounds[1] 结束。
请你以数组形式返回经过次数最多的那几个扇区,按扇区编号 升序 排列。
注意,赛道按扇区编号升序逆时针形成一个圆(请参见第一个示例)。

示例 1
LeetCode 第203场周赛 题解

输入: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