LeetCode 第 双周赛补题

使数组成为递增数组的最少右移次数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;}};

删除数对后的最小数组长度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);}};

统计距离为 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;}};

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

• 题意
  
• 思路
  换根DP待补