前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode周赛276场,Amazon赞助,你能做出几题?

LeetCode周赛276场,Amazon赞助,你能做出几题?

作者头像
TechFlow-承志
发布2022-09-22 14:40:57
3010
发布2022-09-22 14:40:57
举报
文章被收录于专栏:TechFlow

作者 | 梁唐

出品 | 公众号:Coder梁(ID:Coder_LT)

大家好,我是梁唐。

昨天参加了LeetCode第276场周赛,这场周赛的美国区是Amazon赞助的。

不知道是不是给钱比较多的缘故,这次的题目质量很高,非常值得一做,我们一道一道来看题解吧。

字符串拆分

字符串 s 可以按下述步骤划分为若干长度为 k 的组:

  • 第一组由字符串中的前 k 个字符组成,第二组由接下来的 k 个字符串组成,依此类推。每个字符都能够成为 某一个 组的一部分。
  • 对于最后一组,如果字符串剩下的字符 不足 k 个,需使用字符 fill 来补全这一组字符。

注意,在去除最后一个组的填充字符 fill(如果存在的话)并按顺序连接所有的组后,所得到的字符串应该是 s 。

给你一个字符串 s ,以及每组的长度 k 和一个用于填充的字符 fill ,按上述步骤处理之后,返回一个字符串数组,该数组表示 s 分组后 每个组的组成情况 。

解法

模拟题,按照题目要求分别取出s串中长度为k的子串。

最后不够拆分的部分需要特殊处理,通过下标是否超过s范围来判断即可。

代码语言:javascript
复制
class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string> ret;
        int n = s.length();
        for (int i = 0; i < n; i += k) {
            if (i+k < n) 
                // 如果还能拆分,则取出s[i, i+k]子串
                ret.push_back(s.substr(i, k));
            else {
                // 不能拆分
                string cur = "";
                // 下标超过范围则选fill,否则选s[j]
                for (int j = i; j < i+k; j++) {
                    if (j < n) cur.push_back(s[j]);
                    else cur.push_back(fill);
                }
                ret.push_back(cur);
            }
        }
        
        return ret;
    }
};

得到目标值的最小行动步数

你正在玩一个整数游戏。从整数 1 开始,期望得到整数 target 。

在一次行动中,你可以做下述两种操作之一:

  • 递增,将当前整数的值加 1(即, x = x + 1)。
  • 加倍,使当前整数的值翻倍(即,x = 2 * x)。

在整个游戏过程中,你可以使用 递增 操作 任意 次数。但是只能使用 加倍 操作 至多 maxDoubles 次。

给你两个整数 target 和 maxDoubles ,返回从 1 开始得到 target 需要的最少行动次数。

解法

这里要注意一下target的范围是1e9,显然,当target很大,而maxDoubles很小时,我们需要采取的步骤数很大。比如记得情况当maxDoubles为0时,答案的大小同样是1e9。

因此选择搜索的方式是不行的,一定会超时。

深入思考可以想到,可以采取的决策只有两种,加一或者是翻倍。游戏中我们当前的数永远大于等于1,显然翻倍带来的提升一定是大于加一的。而翻倍之前的值越大翻倍带来的收益越大,所以越晚翻倍越划算,需要的步骤越少。可以考虑贪心,从target往1进行倒推。

当target为奇数时,肯定不能通过翻倍得到,只能通过加一得到,所以之前一位操作一定是加一。如果为偶数,当翻倍次数没有超过maxDoubles时,一定是使用翻倍得到最优,否则只能使用加一。

代码语言:javascript
复制
class Solution {
public:
    int minMoves(int target, int maxDoubles) {
        int ret = 0;
        while (target > 1) {
            // 如果为奇数,之前一位操作一定是+1
            if (target % 2) {
                ret++;
                target--;
                continue;
            }
            // 如果为偶数,且翻倍操作还没用完,则之前一位操作为翻倍
            if (maxDoubles > 0) {
                maxDoubles--;
                target /= 2;
                ret++;
            // 如果用完了所有翻倍次数,只能通过+1得到
            }else {
                ret += (target-1);
                break;
            }
        }
        return ret;
    }
};

解决智力问题

给你一个下标从 0 开始的二维整数数组 questions ,其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目,你需要 按顺序 (也就是从问题 0 开始依次解决),针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数,但是你将 无法 解决接下来的 brainpoweri 个问题(即只能跳过接下来的 brainpoweri 个问题)。如果你跳过问题 i ,你可以对下一个问题决定使用哪种操作。

  • 比方说,给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] :
    • 如果问题 0 被解决了, 那么你可以获得 3 分,但你不能解决问题 1 和 2 。
    • 如果你跳过问题 0 ,且解决问题 1 ,你将获得 4 分但是不能解决问题 2 和 3 。请你返回这场考试里你能获得的 最高 分数。

解法

这是一道典型的动态规划问题,我们使用数组arr存储中间状态的最优解。arr[i]表示对于在回答第i题之前,能够获得的最大分数。

那么在第i题回答之后,所能得到的分数为arr[i] + questions[i][0],我们把它记录为变量c。由于第i题如果回答,会需要连续跳过questions[i][1]题。我们可以把连续跳过若干题看成是一种状态转移,可以从状态i转移到所有大于i+questions[i][1]的状态中。

由于这样的转移数很多,如果我们一一穷举会超时,我们可以采用滚动维护的方法,只更新i+questions[i][1]+1的状态,在每个状态开始执行之前,传递一下arr[i],即执行arr[i] = max(arr[i-1], arr[i])

代码语言:javascript
复制
class Solution {
public:
    long long arr[2000050];
    
    long long mostPoints(vector<vector<int>>& questions) {
        long long ret = 0;
        int n = questions.size();
        
        for (int i = 0; i < n; i++) {
            // 滚动维护状态i的最大值
            if (i > 0) arr[i] = max(arr[i], arr[i-1]);
            // 当前问题回答之后能够达到的收益
            long long c = arr[i] + questions[i][0];
            ret = max(ret, c);
            int next = i + questions[i][1] + 1;
            // 更新状态next,对于next之后的位置可以通过arr[i] = max(arr[i], arr[i-1]);维护
            if (next < n) arr[next] = max(arr[next], c);
        }
        
        return ret;
    }
};

同时运行N台电脑的时间

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ,其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟。你想使用这些电池让 全部 n 台电脑 同时 运行。

一开始,你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻,你都可以将一台电脑与它的电池断开连接,并连接另一个电池,你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池,也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意,你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的 最长 分钟数。

解法

同样通过数据范围, 我们可以判断出一定不能使用搜索或其他复杂度更高的解法。

首先,通过仔细分析题意,我们可以得到几个性质,我们可以把电池更换的操作看成是充电。比如A电池运行1分钟之后,换上B电池,可以等价看成是A电池给B电池充上了一分钟电。其次对于每个电池来说,最多只能同时在一个位置使用,要么给某台电脑供电,要么给其他某节电池充电,不能同时使用在两个地方。

我们不难可以想到,可以将电池按照电量倒排之后分成两组。电量最大的N个电池用来给电脑供电,剩余的M(M=batteries.size()-N)个电池用来给这N个电池充电。我们可以把充电看成是电量累加,要求的就是在累加之后,N当中的最小值的最大取值。

经过这么一番转换之后,很容易想到,我们要做的就是用M个电池给N个电池充电,尽量让N个电池的电量平均。由于每个电池的电量都是可以拆分的,比如可以先给A充一分钟,再给B充一分钟。所以我们可以将它们的电量合并统筹分配。

我们先从电量最少的电池开始充电,将它充到和倒数第二的电池一样,再同时给这两个电池充电,充到和倒数第三的电池一样。依次循环往复,直到所有电池电量均等,或者能充的电量用完为止。最后如果还有剩余,再分配到所有电池上。

代码语言:javascript
复制
class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        int k = batteries.size();
        if (k < n) return 0;
        // 按电池电量倒叙排列
        sort(batteries.begin(), batteries.end(), greater<int>());
        
        long long ret = batteries[n-1];
        long long left = 0;
        // 求出充电组的电量总和
        for (int i = n; i < k; i++) left += batteries[i];
        
        int s = n-1;
        // 从电量最低的电池开始充电
        while (left > 0 && s > 0) {
            // 充电的量为要充电的电池数*和前一位的电量差距
            long long req = (n-s) * (batteries[s-1] - batteries[s]);
            if (left >= req) {
                left -= req;
                ret += batteries[s-1] - batteries[s];
            }else {
                ret += left / (n-s);
                left = 0;
                break;
            }
            s--;
        }
        // 如果所有电池电量相等之后还有剩余,就平均分配
        if (left > 0) ret += left / n;
        return ret;
    }
};

到这里,关于这一场的四道题就算是讲完了。

这一场的题目不算很难,也没用到什么高深的算法,主要考察的还是思维的活跃以及对问题的分析。我个人还是很喜欢这套题的,强力推荐给大家,如果有空的话,不妨都做一做。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-01-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 字符串拆分
    • 解法
    • 得到目标值的最小行动步数
      • 解法
      • 解决智力问题
        • 解法
        • 同时运行N台电脑的时间
          • 解法
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档