On the shoulders of giants.

weekly-contest-183

非递增顺序的最小子序列

给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和最大 的子序列。

与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些(也可能不分离)元素得到。

注意,题目数据保证满足所有约束条件的解决方案是 唯一 的。同时,返回的答案应当按 非递增顺序 排列。

示例 1:

输入:nums = [4,3,10,9,8]
输出:[10,9] 
解释:子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。 

示例 2:

输入:nums = [4,4,7,6,7]
输出:[7,7,6] 
解释:子序列 [7,7] 的和为 14 ,不严格大于剩下的其他元素之和(14 = 4 + 4 + 6)。因此,[7,6,7] 是满足题意的最小子序列。注意,元素按非递增顺序返回。  

示例 3:

输入:nums = [6]
输出:[6]

提示:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100
题解

从大到小排序后,从左到右连续选择满足题意的数。

时间复杂度:\(O(n\log n + n)\)

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int sum = 0, ans = 0, k, result = 0;
        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());
        for(auto x : nums) sum += x;
        for(int i = 0; i < nums.size(); i++) {
            ans += nums[i];
            if(sum - ans < ans) {
                k = i + 1;
                break;
            }
        }
        return vector<int> (nums.begin(), nums.begin() + k);
    }
};

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

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数:

  • 如果当前数字为偶数,则将其除以 2 。
  • 如果当前数字为奇数,则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例 1:

输入:s = "1101"
输出:6
解释:"1101" 表示十进制数 13 。
Step 1) 13 是奇数,加 1 得到 14 
Step 2) 14 是偶数,除 2 得到 7
Step 3) 7  是奇数,加 1 得到 8
Step 4) 8  是偶数,除 2 得到 4  
Step 5) 4  是偶数,除 2 得到 2 
Step 6) 2  是偶数,除 2 得到 1  

示例 2:

输入:s = "10"
输出:1
解释:"10" 表示十进制数 2 。
Step 1) 2 是偶数,除 2 得到 1 

示例 3:

输入:s = "1"
输出:0

提示:

  • 1 <= s.length <= 500
  • s 由字符 '0''1' 组成。
  • s[0] == '1'
题解

二进制中最低位为 1 时,是奇数;最低位为 0 时,是偶数。

从最低为开始模拟。最低位为 1 时,加 1;最低位为 0 时,右移。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int numSteps(string s) {
        reverse(s.begin(), s.end());
        int p = s.length() - 1, k = 0, count = 0;
        while(k != p) {
            if(s[k] == '1') {
                s[k] = '0', s[k + 1]++;
                int j = k + 1;
                while(s[j] == '2') {
                    if(j == p) s += '0', p++;
                    s[j] = '0', s[++j]++;
                }
            } else k++;
            count++;
        }
        return count;
    }
};

最长快乐字符串

如果字符串中不含有任何 'aaa''bbb''ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。

给你三个整数 abc,请你返回 任意一个 满足下列全部条件的字符串 s

  • s 是一个尽可能长的快乐字符串。
  • s最多a 个字母 'a'b 个字母 'b'c 个字母 'c'
  • s 中只含有 'a''b''c' 三种字母。

如果不存在这样的字符串 s ,请返回一个空字符串 ""

示例 1:

输入:a = 1, b = 1, c = 7
输出:"ccaccbcc"
解释:"ccbccacc" 也是一种正确答案。

示例 2:

输入:a = 2, b = 2, c = 1
输出:"aabbc"

示例 3:

输入:a = 7, b = 1, c = 0
输出:"aabaa"
解释:这是该测试用例的唯一正确答案。

提示:

  • 0 <= a, b, c <= 100
  • a + b + c > 0
题解

每次选择最多字符的加入串中,如果当前要加入的字符与串中最后两个字符相同,则选择次大的字符,以此类推。

时间复杂度:\(O(kn)\)

typedef pair<int, char> PIC;
class Solution {
public:
    static bool Cmp(PIC& tmp1, PIC& tmp2) {
        return tmp1.first > tmp2.first;
    }
    bool isInsert(string& ret, PIC& tmp) {
        if(tmp.first == 0) return false;
        int n = ret.length();
        if(2 <= n && ret[n - 1] == ret[n - 2] && ret[n - 1] == tmp.second) 
            return false;
        ret += tmp.second, tmp.first--;
        return true;
    }
    string longestDiverseString(int a, int b, int c) {
        vector<PIC> H{{a, 'a'}, {b, 'b'}, {c, 'c'}};
        string ret = "";
        int flag = 1;
        while(flag) {
            sort(H.begin(), H.end(), Cmp);
            flag = 0;
            for(int i = 0; i < 3 && !flag; i++) {
                if(isInsert(ret, H[i])) flag = 1;
            }
        }
        return ret;
    }
};

石子游戏 III

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie”

示例 1:

输入:values = [1,2,3,7]
输出:"Bob"
解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。

示例 2:

输入:values = [1,2,3,-9]
输出:"Alice"
解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。
如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。
如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。
注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。

示例 3:

输入:values = [1,2,3,6]
输出:"Tie"
解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。

示例 4:

输入:values = [1,2,3,-1,-2,-3,7]
输出:"Alice"

示例 5:

输入:values = [-1,-2,-3]
输出:"Tie"

提示:

  • 1 <= values.length <= 50000
  • -1000 <= values[i] <= 1000
题解

动态规划,设 \(dp_{k,x}\) 为 k 号人当前局面是 \([x,n)\) 时的 Alice 得分减去 Bob 得分。

如果 Alice 要赢,那么他要最大化这个得分;如果 Bob 要赢,那么他要最小化这个得分。

我们通过记忆化搜索转移:

Alice 表示 0 号,\(dp_{0,x}=\max (\sum_{i=x}^{x+k}score_i+dp_{1,x+k+1}),k\in [0,3)\)

Bob 表示 1 号,\(dp_{1,x}=\max (dp_{0,x+k+1})-\sum_{i=x}^{x+k}score_i,k\in [0,3)\)

时间复杂度:\(O(n)\)

const int N = 5E4 + 10, INF = 1E9;
int dp[2][N], vis[2][N], n;
class Solution {
public:
    vector<int> nums;
    int dfs(int who, int x) {
        if(n <= x) return 0;
        if(vis[who][x]) return dp[who][x];
        if(who == 0) {
            int sum = 0;
            dp[who][x] = -INF;
            for(int i = 0; i < min(3, n - x); i++) {
                sum += nums[x + i];
                dp[who][x] = max(dp[who][x], sum + dfs(who ^ 1, x + i + 1));
            }
        } else {
            int sum = 0;
            dp[who][x] = INF;
            for(int i = 0; i < min(3, n - x); i++) {
                sum += nums[x + i];
                dp[who][x] = min(dp[who][x], dfs(who ^ 1, x + i + 1) - sum);
            }
        }
        vis[who][x] = 1;
        return dp[who][x];
    }
    string stoneGameIII(vector<int>& stoneValue) {
        nums = stoneValue;
        n = stoneValue.size();
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        dp[0][0] = dfs(0, 0);
        if(dp[0][0] == 0) return "Tie";
        return dp[0][0] < 0 ? "Bob" : "Alice";
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注