第 25 场双周赛

Posted on | In , | |
Words count in article: 569 | Reading time ≈ 3

5384. 拥有最多糖果的孩子

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int n = candies.size();
        vector<bool> res(n);
        int maxx = 0;
        for(auto a: candies) maxx = max(maxx, a);
        for(int i=0; i<n; i++) {
            if(extraCandies + candies[i] >= maxx) res[i] = true;
        }
        return res;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxDiff(int num) {
        vector<int> dig(9);
        int z = 0, v = num;
        while(v) {
            dig[z++] = v % 10;
            v /= 10;
        }
        int mi = num, ma = num;
        for(int i=0; i<10; i++) {
            for(int j=0; j<10; j++) {
                int ans = 0;
                for(int o = z-1; o >=0 ;o--) {
                    int cur = dig[o];
                    if(cur == i) cur = j;
                    if(o == z-1 && cur == 0) break;
                    ans = ans * 10 + cur;
                }
                if(ans == 0) continue;
                mi = min(mi, ans);
                ma = max(ma, ans);
            }
        }
        return ma-mi;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool checkIfCanBreak(string s1, string s2) {
        vector<int> v1(26);
        vector<int> v2(26);
        for(auto a: s1) v1[a-'a'] ++;
        for(auto a: s2) v2[a-'a'] ++;
        vector<int> t1 = v1;
        vector<int> t2 = v2;
        int i = 0, j = 0;
        int f1 = 0;
        while(i < 26 && j < 26) {
            while(i < 26 && v1[i] == 0) i++;
            while(j < 26 && v2[j] == 0) j++;
            if(i >= 26 || j >= 26) break;
            if(j < i) {
                f1 = 1; break;
            }
            int ans = min(v1[i], v2[j]);
            v1[i] -= ans;
            v2[j] -= ans;
        }
        if(f1 == 0) return true;
        i = 0, j = 0, f1 = 0, v1 = t1, v2 = t2;
        while(i < 26 && j < 26) {
            while(i < 26 && v1[i] == 0) i++;
            while(j < 26 && v2[j] == 0) j++;
            if(i >= 26 || j >= 26) break;
            if(i < j) {
                f1 = 1; break;
            }
            int ans = min(v1[i], v2[j]);
            v1[i] -= ans;
            v2[j] -= ans;
        }
        if(f1 == 0) return true;
        return false;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
  int numberWays(vector<vector<int>>& hats) {
    int n = hats.size();
    vector<ll> dp(1 << n);
    dp[0] = 1;
    vector<set<int>> s(41);
    for (int i = 0; i < n; ++i)
      for (int hat : hats[i])
        s[hat].insert(i);
    for (int i = 1; i <= 40; ++i) {
      vector<ll> ndp(dp);
      for (int state = (1 << n) - 1; state >= 0; --state) {
        for (int person : s[i]) {
          if (state & (1 << person))
            continue;
          int nxt = state + (1 << person);
          ndp[nxt] += dp[state];
          ndp[nxt] %= MOD;
        }
      }
      swap(dp, ndp);
    }
    return dp[(1 << n) - 1];
  }
};
Donate? comment?