第 113 场力扣夜喵双周赛

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

直接从最小值开始判断数组是否递增，或者可以找到第一个递减的位置，然后再判断数组是否递增（因为如果数组满足条件，则其最多只有一个递减段）。

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size(), idx = -1, min = 101;
        for (int i = 0; i < n; i++) {
            if (nums.get(i) < min) {
                min = nums.get(i);
                idx = i;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            int x = (idx + i) % n, y = (x + 1) % n;
            if (nums.get(x) > nums.get(y)) return -1;
        }
        return (n - idx) % n;
    }
}

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

贪心，比赛时我是用双指针做的，前半部分和后半部分进行匹配（当时边界想了很久，真笨！）。其他做法，参考题解：【小羊肖恩】数学 + 贪心：解决较长数组脑筋急转弯问题的关键。（因为 HashMap 很慢，所以用双指针会更快。）

方法一：贪心

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), i = 0;
        for (int j = (n + 1) / 2; j < n; j++) {
            if (nums.get(i) < nums.get(j)) {
                i++;
            }
        }
        return n - i * 2;
    }
}

方法二：贪心 + 数学

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size(), max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            max = Math.max(max, map.merge(x, 1, Integer::sum));
        }
        return 2 * max <= n ? n % 2 : n - (n - max) * 2;
    }
}

统计距离为 k 的点对

枚举 \(x_{1}\oplus x_{2}\) 的值为 \(p\)，可以得到 \(y_{1}\oplus y_{2}\) 的值为 \(k-p\)。可以使用 HashMap 对前缀中的值计数来求解，需要注意循环的顺序，如果调换顺序会使代码变复杂，会花费更多的时间计算答案。

class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int ans = 0;
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (var c : coordinates) {
            int x = c.get(0), y = c.get(1);
            for (int i = 0; i <= k; i++) {
                ans += map.getOrDefault(List.of(x ^ i, y ^ (k - i)), 0);
            }
            map.merge(c, 1, Integer::sum);
        }
        return ans;
    }
}

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

换根 DP，关键是要想到建立反向边，并为边添加相应的边权。

class Solution {
    public int[] minEdgeReversals(int n, int[][] edges) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(new int[]{v, 0});
            g[v].add(new int[]{u, 1});
        }
        int[] ans = new int[n];
        ans[0] = dfs(0, -1, g);
        dfs2(0, -1, g, ans);
        return ans;
    }
    
    private int dfs(int x, int fa, List<int[]>[] g) {
        int res = 0;
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            res += dfs(y, x, g) + w;
        }
        return res;
    }
    
    private void dfs2(int x, int fa, List<int[]>[] g, int[] ans) {
        for (int t[] : g[x]) {
            int y = t[0], w = t[1];
            if (y == fa) continue;
            ans[y] = ans[x] + (w == 0 ? 1 : -1);
            dfs2(y, x, g, ans);
        }
    }
}