Skip to content

第 329 场周赛

比赛链接

Date: 2023-01-22

过年福利场，整体比较简单

A 交替数字和

Python 快乐题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int alternateDigitSum(int n) {
        int res = 0, fg = 1;
        for (auto c : to_string(n)) {
            res += fg * (c - '0');
            fg = -fg;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
class Solution:
    def alternateDigitSum(self, n: int) -> int:
        fg = 1
        res = 0
        for c in str(n):
            res += fg * int(c)
            fg = -fg
        return res

复杂度分析

  • 时间复杂度：\(O(1)\)
  • 空间复杂度：\(O(1)\)

B 根据第 K 场考试的分数排序

自定义排序即可

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k) {
        sort(score.begin(), score.end(), [&](const vector<int>& lth, const vector<int>& rth){
            return lth[k] > rth[k];
        });
        return score;
    }
};

1
2
3
4
class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        score.sort(key = lambda x : -x[k])
        return score

复杂度分析

  • 时间复杂度：\(O(n\log n)\)
  • 空间复杂度：\(O(1)\)

C 执行逐位运算使字符串相等

总共有四种情况

  1. \(0\) 和 \(0\) 变为 \(0\) 和 \(0\)
  2. \(0\) 和 \(1\) 变为 \(1\) 和 \(1\)
  3. \(1\) 和 \(0\) 变为 \(1\) 和 \(1\)
  4. \(1\) 和 \(1\) 变为 \(1\) 和 \(0\)

因此，如果 \(\textit{target}\) 全为 \(0\)，则 \(s\) 也必须全为 0。相反也是一样。因为只靠 \(0\) 无法产生 \(1\)。

对于其他情况，需要变 \(0\) 的则在另外找一个 \(1\)，需要变 \(1\) 的另外找一个 \(1\) 即可。这一定是可以实现的，因为 \(\textit{target}\) 和 \(s\) 中都至少有一个 \(1\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool makeStringsEqual(string s, string target) {
        if (s == target) {
            return true;
        }
        int s0 = 0, s1 = 0;
        for (auto c : s) {
            if (c == '0') s0++;
            else s1++;
        }
        int t0 = 0, t1 = 0;
        for (auto c : target) {
            if (c == '0') t0++;
            else t1++;
        }

        if (t1 == 0 || s1 == 0) {
            return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
def makeStringsEqual(self, s: str, target: str) -> bool:
    if s == target:
        return True
    s0 = sum(1 for c in s if c == '0')
    s1 = sum(1 for c in s if c == '1')
    t0 = sum(1 for c in target if c == '0')
    t1 = sum(1 for c in target if c == '1')
    if s1 == 0 or t1 == 0:
        return False
    return True

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)

D 拆分数组的最小代价

经典 DP。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    using ll = long long;
    int minCost(vector<int>& nums, int k) {
        int n = nums.size();
        vector<ll> d(n + 1, 1e18);
        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            unordered_map<int, int> mp;
            int cnt = 0;
            for (int j = i; j >= 1; j--) {
                int x = nums[j - 1];
                mp[x]++;
                if (mp[x] == 2) cnt += 2;
                else if (mp[x] > 2) cnt++;
                d[i] = min(d[i], d[j - 1] + cnt + k);
            }
        }
        return d[n];
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2)\)
  • 空间复杂度：\(O(n)\)
本文访问 次