Skip to content

第 86 场双周赛

比赛链接

A 和相等的子数组

使用字典记录之前的相邻二元组之和，时间复杂度 \(O(n)\)。

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++) {
            if(i > 0) {
                int sum = nums[i] + nums[i - 1];
                if(mp.count(sum)) return true;
            }
            if(i > 0) {
                mp[nums[i] + nums[i - 1]] = 1;
            }
        }
        return false;
    }
};

class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        st = {}
        for i in range(1, len(nums)):
            s = nums[i] + nums[i - 1]
            if s in st:
                return True
            st[s] = 1
        return False

B 严格回文的数字

模拟，时间复杂度 \(O(n\log n)\)

Note

如果注意到任意数字 \(n\) 在 \(n-2\) 进制表示下都是 \(12\)，那么可以直接 false。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isStrictlyPalindromic(int n) {
        auto check = [&](int n, int b) {
            string s = "";
            while(n) {
                s += to_string(n % b);
                n /= b;
            }
            string t = s;
            reverse(t.begin(), t.end());
            return s == t;
        };
        for(int i = 2; i <= n - 2; i ++) {
            if(!check(n, i)) return false;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
def isStrictlyPalindromic(self, n: int) -> bool:
    def get(n, b):
        s = ""
        while n:
            s += str(n % b)
            n //= b
        return s
    for i in range(2, n - 1):
        s = get(n, i)
        if s != reversed(s):
            return False
    return True

C 被列覆盖的最多行数

二进制枚举，复杂度 \(O(2^mnm)\)

 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
class Solution {
public:
    int maximumRows(vector<vector<int>>& mat, int cols) {
        int n = mat.size(), m = mat[0].size();
        int res = 0;
        for(int i = 0; i < (1 << m); i++) {
            int cnt = 0;
            for(int j = 0; j < m; j++) if(i >> j & 1) cnt ++;
            if(cnt != cols) continue;
            int num = 0;
            for(int k = 0; k < n; k++) {
                bool fg = true;
                for(int j = 0; j < m; j++) {
                    if(mat[k][j] == 1 && !(i >> j & 1)) {
                        fg = false;
                        break;
                    }
                }
                if(fg) num ++;
            }
            res = max(res, num);
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
def maximumRows(self, mat: List[List[int]], cols: int) -> int:
    n, m = len(mat), len(mat[0])
    res = 0
    for mask in range(1 << m):
        if bin(mask).count('1') != cols:
            continue
        cnt = 0
        for i in range(n):
            fg = True
            for j in range(m):
                if mat[i][j] == 1 and not (mask >> j & 1):
                    fg = False
                    break
            if fg:
                cnt += 1
        res = max(res, cnt)
    return res

D 预算内的最多机器人数目

对于每个 \(i\)，找到左侧最远的 \(j\) 使得 \(i\sim j\) 中的机器人都选。可以想到随着 \(i\) 递增，\(j\) 也是递增的。所以我们可以用一个多重集维护 \(i\sim j\) 之间的 chargeTimes，再用一个变量 \(sum\) 记录 \(i\sim j\) 之间的和即可。

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

 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 maximumRobots(vector<int>& c, vector<int>& r, long long b) {
        int n = c.size();
        ll sum = 0;
        multiset<int> st;
        int res = 0;
        for(int i = 0, j = 0; i < n; i++) {
            sum += r[i];
            st.insert(c[i]);
            while(j < i && sum * (i - j + 1) + *st.rbegin() > b) {
                sum -= r[j];
                st.erase(st.find(c[j]));
                j ++;
            }
            if(sum * (i - j + 1) + *st.rbegin() <= b) res = max(res, i - j + 1);
        }
        return res;
    }
};
本文访问 次