讨论/题目交流/🏆 第 183 场力扣周赛/
🏆 第 183 场力扣周赛

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

image.png

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

展开讨论

非递增顺序的最小子序列

思路

  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
展开全部 22 讨论