On the shoulders of giants.

biweekly-contest-25

拥有最多糖果的孩子

给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子,检查是否存在一种方案,将额外的 extraCandies 个糖果分配给孩子们之后,此孩子有 最多 的糖果。注意,允许有多个孩子同时拥有 最多 的糖果数目。

示例 1:

输入:candies = [2,3,5,1,3], extraCandies = 3
输出:[true,true,true,false,true] 
解释:
孩子 1 有 2 个糖果,如果他得到所有额外的糖果(3个),那么他总共有 5 个糖果,他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果,他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果,即使他得到所有额外的糖果,他也只有 4 个糖果,无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果,如果他得到至少 2 个额外糖果,那么他将成为拥有最多糖果的孩子。

示例 2:

输入:candies = [4,2,1,1,2], extraCandies = 1
输出:[true,false,false,false,false] 
解释:只有 1 个额外糖果,所以不管额外糖果给谁,只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3:

输入:candies = [12,1,12], extraCandies = 10
输出:[true,false,true]

提示:

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50
题解

求出最大值后,直接遍历判断即可。

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

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int n = candies.size(), Max = candies[0];
        for(int i = 1; i < n; i++) {
            Max = max(Max, candies[i]);
        }
        vector<bool> result;
        for(int i = 0; i < n; i++) {
            result.push_back(Max <= candies[i] + extraCandies);
        }
        return result;
    }
};

改变一个整数能得到的最大差值

给你一个整数 num 。你可以对它进行如下步骤恰好 两次 :

  • 选择一个数字 x (0 <= x <= 9).
  • 选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
  • num 中所有出现 x 的数位都用 y 替换。
  • 得到的新的整数 不能 有前导 0 ,得到的新整数也 不能 是 0 。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值

示例 1:

输入:num = 555
输出:888
解释:第一次选择 x = 5 且 y = 9 ,并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ,并把得到的新数字保存在 b 中。
现在,我们有 a = 999 和 b = 111 ,最大差值为 888

示例 2:

输入:num = 9
输出:8
解释:第一次选择 x = 9 且 y = 9 ,并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ,并把得到的新数字保存在 b 中。
现在,我们有 a = 9 和 b = 1 ,最大差值为 8

示例 3:

输入:num = 123456
输出:820000

示例 4:

输入:num = 10000
输出:80000

示例 5:

输入:num = 9288
输出:8700

提示:

  • 1 <= num <= 10^8
题解

要让 a-b 最大,那么最大化 a ,最小化 b 即可。

最大化:让从左到右第一个不是 9 的数变成 9

最小化:如果最高位不是 1,那么变成 1 即可,否则找第一个不是 0 的数变成 0

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

class Solution {
public:
    string solve(string s, char c, int k) {
        int p = 0, n = s.length();
        if(k == 0) {
            while(p < n && s[p] == c) p++;
        } else {
            while(p < n && s[p] <= c + 1) p++;
        }
        if(p != n) {
            char q = s[p];
            for(int i = 0; i < n; i++) {
                if(s[i] == q) s[i] = c;
            }
        }
        return s;
    }
    int maxDiff(int num) {
        string a = to_string(num);
        string b = to_string(num);
        a = solve(a, '9', 0);
        if(b[0] == '1') b = solve(b, '0', 1);
        else {
            char q = b[0];
            for(auto& c : b) if(c == q) c = '1';
        }
        return atoi(a.c_str()) - atoi(b.c_str());
    }
};

检查一个字符串是否可以打破另一个字符串

给你两个字符串 s1 和 s2 ,它们长度相等,请你检查是否存在一个 s1  的排列可以打破 s2 的一个排列,或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y (两者长度都为 n )需满足对于所有 i(在 0 到 n - 1 之间)都有 x[i] >= y[i](字典序意义下的顺序)。

示例 1:

输入:s1 = "abc", s2 = "xya"
输出:true
解释:"ayx" 是 s2="xya" 的一个排列,"abc" 是字符串 s1="abc" 的一个排列,且 "ayx" 可以打破 "abc" 。

示例 2:

输入:s1 = "abe", s2 = "acd"
输出:false 
解释:s1="abe" 的所有排列包括:"abe","aeb","bae","bea","eab" 和 "eba" ,s2="acd" 的所有排列包括:"acd","adc","cad","cda","dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

示例 3:

输入:s1 = "leetcodee", s2 = "interview"
输出:true

提示:

  • s1.length == n
  • s2.length == n
  • 1 <= n <= 10^5
  • 所有字符串都只包含小写英文字母。
题解

让各字符串排列成最小字典序的形式,然后进行整体判断。

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

class Solution {
public:
    string solve(string s) {
        map<char, int> total;
        string now;
        for(auto c : s) total[c]++;
        for(auto x : total) {
            for(int i = 0; i < x.second; i++)
                now += x.first;
        }
        return now;
    }
    bool check(string s1, string s2) {
        if(s1 > s2) {
            for(int i = 0; i < s1.length(); i++) {
                if(s1[i] < s2[i]) return false;
            }
            return true;
        } else if(s1 < s2) {
            for(int i = 0; i < s1.length(); i++) {
                if(s1[i] > s2[i]) return false;
            }
            return true;
        } else return true;
    }
    bool checkIfCanBreak(string s1, string s2) {
        string now_s1 = solve(s1);
        string now_s2 = solve(s2);
        return check(now_s1, now_s2);
    }
};

每个人戴不同帽子的方案数

总共有 n 个人和 40 种不同的帽子,帽子编号从 140

给你一个整数列表的列表 hats ,其中 hats[i] 是第 i 个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子,确保每个人戴的帽子跟别人都不一样,并返回方案数。

由于答案可能很大,请返回它对 10^9 + 7 取余后的结果。

示例 1:

输入:hats = [[3,4],[4,5],[5]]
输出:1
解释:给定条件下只有一种方法选择帽子。
第一个人选择帽子 3,第二个人选择帽子 4,最后一个人选择帽子 5。

示例 2:

输入:hats = [[3,5,1],[3,5]]
输出:4
解释:总共有 4 种安排帽子的方法:
(3,5),(5,3),(1,3) 和 (1,5)

示例 3:

输入:hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
输出:24
解释:每个人都可以从编号为 1 到 4 的帽子中选。
(1,2,3,4) 4 个帽子的排列方案数为 24 。

示例 4:

输入:hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
输出:111

提示:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • hats[i] 包含一个数字互不相同的整数列表。
题解

动态规划:设 \(dp_{s,k}\) ,其中 s 为每个人状态(否是选了帽子),k 为从 \([1,k]\) 种帽子中选。

有动态转移方程:\(dp_{s,k}=\sum dp_{s \oplus (1<<x),k-1}\)

空间优化可以使用滚动数组。

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

const int MOD = 1E9 + 7;
class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size(), m = (1 << n) - 1;
        vector<int> dp(m + 1);
        vector<set<int>> who(41);
        for(int i = 0; i < n; i++) {
            for(auto x : hats[i]) who[x].insert(i);
        }
        dp[0] = 1;
        for(int i = 1; i <= 40; i++) {
            for(int s = m; 0 <= s; s--) {
                for(auto p : who[i]) {
                    if((s & (1 << p))) continue;
                    int y = s | (1 << p);
                    dp[y] = (dp[y] + dp[s]) % MOD;
                }
            }
        }
        return dp[m];
    }
};
Share

You may also like...

发表评论

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