讨论/技术交流/🏆 第 183 场力扣周赛/
🏆 第 183 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 非递增顺序的最小子序列
4 分 - 将二进制表示减到 1 的步骤数
6 分 - 最长快乐字符串
7 分 - 石子游戏 III

共 22 个回复

难的我又说不会,简单的我又说水,我真挑剔。

39
T1. Array + Sort
    返回子序列而不是子串(子数组), 因此对nums递减排序, 然后自左向右累加nums[i]并存nums[i]至结果数组, 直到累加元素和 > 未累加元素和时, 跳出循环直接返回结果数组. 此时结果数组必然是最短且元素和最大的子序列。
    时间复杂度O(nlogn), 空间复杂度O(n)。
class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        curSum, total = 0, sum(nums)
        res = []
        nums = sorted(nums, reverse=True)
        for i in range(len(nums)):
            curSum += nums[i]
            res.append(nums[i])
            if curSum > total - curSum:
                break
        return res
T2. String + Math
更正题解:
法一 - 字符串转10进制数, 然后模拟即可。时间复杂度O(n), 空间复杂度O(1)。
不过需要注意给定串s最大长度可达500, 直接操作并不可取, 语言不通用!
class Solution:
    def numSteps(self, s: str) -> int:
        num, val, res = 0, 1, 0
        for i in range(len(s) - 1, -1, -1):
            num += (ord(s[i]) - 48) * val
            val *= 2
        while num != 1:
            if num % 2 == 0:
                num //= 2
            else:
                num += 1
            res += 1
        return res

法二: 模拟
字符串->字符数组, 然后自右向左遍历, 若当前位为0则继续考察前一位, 当前位为1则模拟从低位向高位的进位, 直到发现某个数位为'0', 将其进1置'1'.
时间复杂度O(n), 空间复杂度O(n).
class Solution:
    def numSteps(self, s: str) -> int:
        s = list(s)
        curIdx, res = len(s) - 1, 0
        while curIdx > 0:
            if s[curIdx] == '0':
                curIdx -= 1; res += 1
            else:
                res += 1
                while curIdx >= 0 and s[curIdx] == '1':
                    curIdx -= 1; res += 1
                if curIdx > 0:
                    s[curIdx] = '1'
        return res
T3. Greedy
    贪心策略: 每次追加'a', 'b', 'c'中剩余数量最多的字符, 并记录上次添加的字符是哪种, 从而使得不会有连续的3'a', 'b''c'出现, 同时保证串最长.
    时间复杂度O(n), 空间复杂度O(1)。
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        lastCh, isAdd = "x", 1
        res = ""
        while isAdd:
            isAdd = 0
            if a >= b >= c or a >= c >= b:
                if lastCh != "a":
                    if a >= 2:
                        res += "aa"; a -= 2
                    elif a == 1:
                        res += "a"; a -= 1
                    lastCh = "a"; isAdd = 1
                else:
                    if b >= c and b >= 1:
                        res += "b"; lastCh = "b"; b -= 1; isAdd = 1
                    elif c >= b and c >= 1:
                        res += "c"; lastCh = "c"; c -= 1; isAdd = 1
            elif b >= a >= c or b >= c >= a:
                if lastCh != "b":
                    if b >= 2:
                        res += "bb"; b -= 2
                    elif b == 1:
                        res += "b"; b -= 1
                    lastCh = "b"; isAdd = 1
                else:
                    if a >= c and a >= 1:
                        res += "a"; lastCh = "a"; a -= 1; isAdd = 1
                    elif c >= a and c >= 1:
                        res += "c"; lastCh = "c"; c -= 1; isAdd = 1
            elif c >= a >= b or c >= b >= a:
                if lastCh != "c":
                    if c >= 2:
                        res += "cc"; c -= 2
                    elif c == 1:
                        res += "c"; c -= 1
                    lastCh = "c"; isAdd = 1
                else:
                    if a >= b and a >= 1:
                        res += "a"; lastCh = "a"; a -= 1; isAdd = 1
                    elif b >= a and b >= 1:
                        res += "b"; lastCh = "b"; b -= 1; isAdd = 1
        return res
T4. DFS + Memo
    dfs(i, M) - 从第i堆石子开始取, 最多能取M(M = 3)堆时可取到的最大石子数, 然后记忆化搜索Alice取得的最大石子数之和, 石子数总和-Alice取得的最大石子数之和即为Bob取得的石子数, 取得更多石子数量的即为胜者。
    时间复杂度O(n), 空间复杂度O(n).
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n, total = len(stoneValue), sum(stoneValue)
        
        sufSum = [0] * (n + 1)
        memo = {}
        
        for i in range(n - 1, -1, -1):
            sufSum[i] = sufSum[i + 1] + stoneValue[i]
        
        # dfs(i, M) - 从第i堆石子开始取, 最多能取M(M = 3)堆时可取到的最大石子数
        def dfs(i, M):
            # 记忆化: 若组合(i, M)已经搜索过, 则直接返回
            if (i, M) in memo:
                return memo[(i, M)]
            # 边界: 石子已全部取完
            if i >= n:
                return 0
            # 搜索过程: 枚举拿x∈[1, 3]堆时的最优解(注意values[i]可能为负数, 故应初始化为一个"无穷小"的负数)
            best = float("-inf")
            for x in range(1, M + 1):
                # 剩余石子减去对方最优策略
                best = max(best, sufSum[i] - dfs(i + x, M))
            # 记忆化最优解, 并返回之
            memo[(i, M)] = best
            return best
        
        Alice = dfs(0, 3)
        Bob = total - Alice
        if Alice > Bob: return "Alice"
        elif Bob > Alice: return "Bob"
        else: return "Tie"
14

284名,算是有进步了。
做出了前三题,第四题dp还是不太会。
但是比一开始打周赛的时候好太多了。
刷题还是有一定效果的,冲压!

6

使用力扣一个月,从简单题都磕磕碰碰、见到普通题就蒙圈到现在基本能做出普通题,还算是有进步。这是第一次加周赛,做出前三题,第四题没什么思路,460/3753,还算满意吧,继续加油。

5

第一次全部完成 73/3735

5

为啥最后2题都没啥思路啊..

3

非递增顺序的最小子序列

思路

  1. 逆序
  2. 求和
  3. 当前缀和 * 2 大于总和,其元素是最小子序列

答题

    vector<int> minSubsequence(vector<int>& nums) 
    {
        sort(nums.rbegin(), nums.rend());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        vector<int> ans;
        int cur = 0;
        for (auto n : nums)
        {
            ans.push_back(n);
            cur += n;
            if (cur * 2 > sum) break;
        }
        return ans;
    }

将二进制表示减到 1 的步骤数

思路

  1. 去掉前面的 0
  2. 去掉后面的 0 ,记录操作数
  3. 如果此时长度只有 1 ,那么就返回操作数
  4. 现在得到一个结尾是 1 的长度大于 1 的字符串,例:1101
    41. 因为结尾是 1 要进行 +1 操作,如: 01 -> 1001111 -> 10000
    42. 把连续的 1 ,一口气全部变成 0 ,操作数等于变成 0 的个数加上最前面一个变成 1 的操作
    43. 需要在字符串头部插入一个 0 ,因为原头部的 1 肯定会被后面 +1
    44. 这一系列操作就可以放入一个循环处理

答题

    int numSteps(string s) 
    {
        int ans = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '0') continue;
            s = s.substr(i, s.size() - i);
            break;
        }
        while (s.back() == '0')
        {
            ans++;
            s.pop_back();
        }
        if (s.size() == 1) return ans;

        s.insert(s.begin(), '0');
        for (int i = s.size() - 1; i > 0;)
        {
            int cnt = 1;
            while (i - cnt >= 0 && s[i - cnt] == '1')
            {
                cnt++;
            }
            ans += cnt + 1;
            i -= cnt;
        }
        return ans;
    }

最长快乐字符串

思路

  1. 需要对字母和其个数连带排序
    11. 我使用 vector<vector<int>> ,将字母 a 转化为 int ,放在第 2 维
    12. 这样对其排序,会优先根据第 1 维的数量来排序
  2. 制作规则
    21. 当数量最多的字母,比其他两个字母的数量之和还多,每次填充 2 个最多字母,配 1 个第二多字母
    22. 否则,就尽量 2 个最多字母配 2 个第二多字母
    23. 当最多字母不足 2 个(无需搭配),或者第二多字母不足 1 个(无法搭配),跳出循环进行最后一次填充
    24. 最后一次填充按照顺序每个字母最多填 2 个

答题

    string longestDiverseString(int a, int b, int c)
    {
        string ans;
        vector<vector<int>> cnt = { {a, 0}, {b, 1}, {c, 2} };

        while (true)
        {
            sort(cnt.rbegin(), cnt.rend());
            if (cnt[0][0] < 2) break;
            if (cnt[1][0] < 1) break;
            if (cnt[0][0] > cnt[1][0] + cnt[2][0])
            {
                ans += ('a' + cnt[0][1]);
                ans += ('a' + cnt[0][1]);
                cnt[0][0] -= 2;
                ans += ('a' + cnt[1][1]);
                cnt[1][0] -= 1;
            }
            else
            {
                ans += ('a' + cnt[0][1]);
                ans += ('a' + cnt[0][1]);
                cnt[0][0] -= 2;
                if (cnt[1][0] > 1)
                {
                    ans += ('a' + cnt[1][1]);
                    cnt[1][0] -= 1;
                }
                ans += ('a' + cnt[1][1]);
                cnt[1][0] -= 1;
            }
        }

        sort(cnt.rbegin(), cnt.rend());
        for (int i = 0; i < cnt.size(); i++)
        {
            if (cnt[i][0] == 0) return ans;
            ans += ('a' + cnt[i][1]);
            if (cnt[i][0] != 1)
            {
                ans += ('a' + cnt[i][1]);
            }
        }
        return ans;
    }

石子游戏 III

思路

  1. 两个人的分数最终只比较大小,可以通过加减来区分存成一份
  2. 从后往前

答题

    string stoneGameIII(vector<int>& stoneValue)
    {
        vector<int> dp(stoneValue.size(), INT_MIN);
        for (int i = stoneValue.size() - 1; i >= 0; i--)
        {
            int s = 0;
            for (int j = 0; j < 3 && i + j + 1 <= stoneValue.size(); j++)
            {
                s += stoneValue[i + j];
                dp[i] = (i + j + 1 == stoneValue.size()) ? max(dp[i], s) : dp[i] = max(dp[i], s - dp[i + j + 1]);
            }
        }

        if (dp[0] == 0) return "Tie";
        return (dp[0] > 0) ? "Alice" : "Bob";
    }

致谢

做的太慢啦,T4 还没做完,太菜了,中午吃饭贡献一个菜

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

2

这次好不容易会做第四题了,但是第三题搞不出来了,dfs会TLE,贪心又WA……

3

醉了,Python3简直有毒,同一样的代码放到Python里就过了,Python3竟然算错了??????????

1
T3.贪心策略,每次选取剩余数量最多的同时保证连续三个字符不会相同的字符加入道字符串的末尾即可。
class Solution {
public:
    static char biggest(map<char,int>num,char x){
        char maxx;
        if(x =='o'){
            //找三者的最大值
            if(num['a']>num['b']){
                maxx='a';
            }else maxx='b';
            if(num['c']>num[maxx])maxx='c';
        }else if(x=='a'){
            maxx=num['b']>num['c']?'b':'c';
        }else if(x=='b'){
            maxx=num['a']>num['c']?'a':'c';
        }else if(x=='c'){
            maxx=num['a']>num['b']?'a':'b';
        }
        return maxx;
    }
    string longestDiverseString(int a, int b, int c) {
        map<char,int>num;
        num['a']=a;
        num['b']=b;
        num['c']=c;
        string s;
        char big;
            big=biggest(num,'o');
        num[big]=num[big]-1;
        s+=big;
        if(a+b+c==1)return s;
        else{
        big=biggest(num,'o');
        num[big]=num[big]-1;
        s+=big;
            while(num['a']!=0||num['b']!=0||num['c']!=0){
                if(s[s.length()-1]==s[s.length()-2]){
                    big = biggest(num,s[s.length()-1]);
                    if(num[big]<=0)break;
                    s+=big;
                    num[big]=num[big]-1;
                }else{
                    big = biggest(num,'o');
                    s+=big;
                    num[big]=num[big]-1;
                }
            }
            return s;
        }

    }
};
1