Skip to content

第 315 场周赛

比赛链接

Date: 2022-10-16

A 与对应负数同时存在的最大正整数

哈希表暴力

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int findMaxK(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (auto &x : nums) {
            mp[x]++;
        } 
        for (int i = 1000; i >= 1; i--) {
            if (mp.count(i) && mp.count(-i)) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        dt = Counter(nums)
        for x in range(1000, -1, -1):
            if x in dt and -x in dt:
                return x
        return -1

B 反转之后不同整数的数目

翻转每个数字，用 set 维护集合即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int countDistinctIntegers(vector<int>& nums) {
        set<int> st(nums.begin(), nums.end());
        for (auto x : nums) {
            string s = to_string(x);
            reverse(s.begin(), s.end());
            st.insert(stoi(s));
        } 
        return st.size();
    }
};

1
2
3
4
5
6
7
8
9
class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        st = set()
        for x in nums:
            st.add(x)
            s = str(x)
            s = s[::-1]
            st.add(int(s))
        return len(st)

C 反转之后的数字和

这题 C++ 会被卡常。另外需要注意 0 的特殊性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool sumOfNumberAndReverse(int num) {
        for (int i = 0; i <= num; i++) {
            string s = to_string(i);
            auto t = s;
            reverse(t.begin(), t.end());
            if (i + stoi(t) == num) return true;
        } 
        return false;
    }
};

1
2
3
4
5
6
7
8
class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        for x in range(0, num + 1):
            s = str(x)
            t = s[::-1]
            if int(s) + int(t) == num:
                return True
        return False

D 统计定界子数组的数目

恐怕是本套题目中最值得一看的题目了。

数组会被 < minK 和 > maxK 的数字分割开，记录上一次 minK 和 maxK 的出现位置，以及上一次被分割的位置 border。那么对于当前位置作为区间右端点，左端点的合法个数就是 \(\min(lastminkpos, lastmaxkpos) - border + 1\)。

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int last_min_k = -1;
        int last_max_k = -1;
        int border = 0;
        long long res = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                last_min_k = last_max_k = -1;
                border = i + 1;
                continue;
            } 
            if (nums[i] == minK) {
                last_min_k = i;
            }
            if (nums[i] == maxK) {
                last_max_k = i;
            }
            if (last_min_k != -1 && last_max_k != -1) {
                res += min(last_min_k, last_max_k) - border + 1;
            }
        }
        return res;
    }
};

小结

每次比赛用脚本工具去爬题目，在本地IDE写的话，网页端的账号总是会被卡掉。耽误一开始的几秒钟时间去登陆。然后今天发现 C++ 的 stoi 也无法在这个脚本工具的编译环境下使用。

T3 除了因为 C++ 卡常，还有特殊 0 的考虑。
本文访问 次