LeetCode 第113 双周赛补题

使数组成为递增数组的最少右移次数3

class Solution {
public:
    int minimumRightShifts(vector<int>& nums) {
        int n = nums.size();
        int j = -1;
        for (int i = 0;i < nums.size()-1;i ++) {
            if (nums[i+1] < nums[i]) {
                j = i+1;break;
            }
        }
        int k = j+1;
        if (j == -1) return 0;
        for (int i = j;i < n;i ++) {
            if (nums[(i+1)%n] < nums[i%n]) return -1;
        }
        return n-j;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

删除数对后的最小数组长度4

• 题意
  
• 思路
  好 CF。。。
  
• 代码

class Solution {
public:
    int minLengthAfterRemovals(vector<int> &nums) {
        int n = nums.size();
        int x = nums[n / 2];
        int max_cnt = upper_bound(nums.begin(), nums.end(), x) -
                      lower_bound(nums.begin(), nums.end(), x);
        return max(max_cnt * 2 - n, n % 2);
    }
};
1
2
3
4
5
6
7
8
9
10

统计距离为 k 的点对5

• 题意
  
• 思路
  
• 代码

class Solution {
public:
    int countPairs(vector<vector<int>> &coordinates, int k) {
        int ans = 0;
        unordered_map<long long, int> cnt;
        for (auto &p: coordinates) {
            for (int i = 0; i <= k; i++) {
                // 直接 ans += cnt[...] 会插入不存在的点
                auto it = cnt.find((p[0] ^ i) * 2000000LL + (p[1] ^ (k - i)));
                if (it != cnt.end()) {
                    ans += it->second;
                }
            }
            cnt[p[0] * 2000000LL + p[1]]++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以到达每一个节点的最少边反转次数

• 题意
  
• 思路
  换根DP待补