medium – 第 8 页 – shelterofly

目标

现有一个下标从 1 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

(a, b) 表示白色车的位置。
(c, d) 表示白色象的位置。
(e, f) 表示黑皇后的位置。

假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
皇后不能移动。

示例 1：

输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。
由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。

示例 2：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：可以通过以下任一方式移动 1 次捕获黑皇后：
- 将白色车移动到 (5, 2) 。
- 将白色象移动到 (5, 2) 。

说明：

1 <= a, b, c, d, e, f <= 8
两枚棋子不会同时出现在同一个格子上。

思路

有一个 8 x 8 的棋盘，上面有车、象、皇后三个棋子。其中车和象是白色，皇后是黑色。车走横线与竖线，象走斜线，皇后固定不动。问白棋捕获黑皇后所需的最小移动次数，所谓捕获指任意白棋走到黑皇后所在的位置。注意，沿着某一方向移动多个格子算一步。

当我们移动一个白棋的时候另一个白棋是不动的，所以就可能存在一个白棋被另一个白棋挡住的情况。如果不考虑碰撞，白棋捕获黑皇后最多走两步，并且有两种走法，对于车来说可以先走到同一行或者同一列。这时如果另一个白棋出现在其中一条路径上，我们只需选另一条路径即可，最多走两步。因此白棋阻挡只会对初始时可以一步捕获的情况产生影响，这时我们只需要将阻挡的棋子移开，然后另一个棋子可以一步直达，还是两步。

根据上面的分析，如果某个白棋可以直接捕获黑皇后(路径上没有阻挡)，那么只需要移动一次，否则需要移动两次。

题解中给出了另一种写法来判断是否产生阻挡的情况，如果 (m − l) * (m − r) > 0，那么整数 m 不在整数 l 和 r 之间。如果在它们之间，符号一定相异，l 与 r 换位置也不影响，这样无需比较二者的最大最小值。

代码


/**
 * @date 2024-12-05 10:06
 */
public class MinMovesToCaptureTheQueen3001 {

        public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // 车与皇后在同一行，象没有在同一行，或者在同一行却不在二者之间
        if (a == e && (a != c || d < Math.min(b, f) || d > Math.max(b, f))) {
            return 1;
        }
        // 车与皇后在同一列，象没有在同一列，或者在同一列却不在二者之间
        if (b == f && (b != d || c < Math.min(a, e) || c > Math.max(a, e))) {
            return 1;
        }
        // 象与皇后在同一斜线，车没有在同一斜线，或者在同一斜线却不在二者之间
        if (c + d == e + f && (a + b != c + d || a < Math.min(c, e) || a > Math.max(c, e))) {
            return 1;
        }
        if (c - d == e - f && (a - b != c - d || a < Math.min(c, e) || a > Math.max(c, e))) {
            return 1;
        }
        return 2;
    }

}

性能

目标

给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

colors[i] == 0 表示第 i 块瓷砖的颜色是红色。
colors[i] == 1 表示第 i 块瓷砖的颜色是蓝色。

环中连续 k 块瓷砖的颜色如果是交替颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它左边和右边的颜色都不同），那么它被称为一个交替组。

请你返回交替组的数目。

注意，由于 colors 表示一个环，第一块瓷砖和最后一块瓷砖是相邻的。

示例 1：

输入：colors = [0,1,0,1,0], k = 3
输出：3

解释：

交替组包括：

示例 2：

输入：colors = [0,1,0,0,1,0,1], k = 6
输出：2

解释：

交替组包括：

示例 3：

输入：colors = [1,1,0,1], k = 4
输出：0

解释：

说明：

3 <= colors.length <= 10^5
0 <= colors[i] <= 1
3 <= k <= colors.length

思路

有一个环形二进制数组（认为首尾相邻），如果连续的 k 个元素除了第一个与最后一个元素外，内部元素与它左边和右边的元素不同，则称这 k 个元素为一个交替组，求交替组的个数。

如果 k 取 3 就变成了 3206.交替组I。

昨天的题枚举的是中间元素，今天这道题我们可以枚举左端点。将其视为一个特殊的滑动窗口问题，特殊之处在于窗口内元素需要满足的条件是不存在连续相等的元素。显然，如果新移入窗口的元素使得条件不满足，即窗口内后两个元素相等，那么只要窗口内包含这个新移入的元素条件就总是无法满足。

因此可以直接将左端点移到右边界，省去了移出元素的滑动过程。在向右扩展的时候可以对窗口内的元素计数，如果大于等于 k 则计入结果，直到右端点无法再继续扩展，重置计数器，然后以右边界为左端点继续该过程。

可以省略维护左边界的指针，重置计数器就相当于从当前位置重新计数。

我们可以通过偏移下标然后取余来处理环形数组的遍历。也可以参考 134.加油站两次循环。

代码


/**
 * @date 2024-11-26 9:31
 */
public class NumberOfAlternatingGroups3208 {

    /**
     * 两次循环1ms
     */
    public int numberOfAlternatingGroups_v2(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int prev = colors[n - k + 1];
        int size = 1;
        for (int i = n - k + 2; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
        }
        for (int i = 0; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

    /**
     * 5ms
     */
    public int numberOfAlternatingGroups_v1(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int size = 1;
        for (int i = n - k + 2; i < 2 * n; i++) {
            if (colors[i % n] == colors[(i - 1) % n]) {
                size = 1;
            } else {
                size++;
            }
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

}

性能

目标

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

说明：

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都互不相同（即，不含重复边）

思路

有一个 n 个节点的有向图，节点标记为 1 ~ n，求从其中某个节点 k 出发访问到所有其它节点的最短时间。

即从 k 出发求出到达所有其它节点的最短路径，然后取其中的最大值。

Floyd 算法的基本思想是动态规划。定义 dp[i][j] 表示从节点 i 到节点 j 的最短路径，对于所有其它中间节点 m，更新 dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m][j])，时间复杂度 O(n^3)。

如果 i -> j 有直接的通路则初始化 dp[i][j] 为路径的权值，否则为 INF。

但是本题不需要其它起点的最短路径，因此可以使用 Dijkstra 算法、Bellman-Ford 算法或者 SPFA 算法。

图的表示可以使用邻接矩阵、邻接表、前向星、链式前向星等结构。

代码


/**
 * @date 2024-11-25 9:08
 */
public class NetworkDelayTime743 {

    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] dp = new int[n + 1][n + 1];
        for (int[] cost : dp) {
            Arrays.fill(cost, 20000);
        }
        for (int[] edge : times) {
            dp[edge[0]][edge[1]] = edge[2];
        }
        for (int m = 1; m <= n; m++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j || i == m || j == m) {
                        continue;
                    }
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m][j]);
                }
            }
        }
        int res = -1;
        for (int i = 1; i <= n; i++) {
            if (i == k) {
                continue;
            }
            res = Math.max(dp[k][i], res);
        }
        return res == 20000 ? -1 : res;
    }

}

性能

目标

给你两个正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的真因数。

如果一个数字恰好仅有两个真因数，则称该数字为特殊数字。例如：

数字 4 是特殊数字，因为它的真因数为 1 和 2。
数字 6 不是特殊数字，因为它的真因数为 1、2 和 3。

返回区间 [l, r] 内不是特殊数字的数字数量。

示例 1：

输入： l = 5, r = 7
输出： 3
解释：
区间 [5, 7] 内不存在特殊数字。

示例 2：

输入： l = 4, r = 16
输出： 11
解释：
区间 [4, 16] 内的特殊数字为 4 和 9。

说明：

1 <= l <= r <= 10^9

提示：

A special number must be a square of a prime number.
We need to find all primes in the range [sqrt(l), sqrt(r)].
Use sieve to find primes till sqrt(10^9).

思路

返回给定区间 [l, r] 内不是特殊数字的数字个数，所谓特殊数字指除了它本身恰好有两个正因数的数字。

一看到数据范围是 10^9 就不可能使用使用暴力解法去判断每一个数字是不是 l 或 r 的因数，要么使用二分要么预处理。特殊数字是确定的，它除了自身以外只有两个因数，1 一定是一个，即除了 1 和它本身只有一个因数。看了提示说特殊数字是质数的平方，我们需要找到所有在 [√l, √r] 范围内的质数，可以预处理 √10^9 内的质数。二分查找 [l, r] 范围内质数的个数，然后减掉即可。

埃氏筛的基本思想是创建一个 boolean[] 标记查询范围内的数是否为质数，初始时均标记为 true。从 2 开始遍历（0和 1 后面直接过滤掉了)，直到 i < √end 即 i * i < end。在循环内部，如果当前值是质数，则将 i * i，i * (i + 1)，i * (i + 2)，…… 标记为非质数。比如在 2 的循环内，所有大于 2 的偶数都被标为非质数，以此类推，像筛子一样将质数筛选出来。

// todo 最后也可以使用前缀和计算个数

代码


/**
 * @date 2024-11-22 9:07
 */
public class NonSpecialCount3233 {

    public static int[] primes;

    static {
        List<Integer> primeList = new ArrayList<>();
        int end = (int) Math.ceil(Math.sqrt(1000000001));
        boolean[] isPrime = new boolean[end + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= end; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= end; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // 前面没有将 isPrime[0] isPrime[1] 置为false，这里从2开始
        for (int i = 2; i <= end; i++) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
        int cnt = primeList.size();
        primes = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            primes[i] = primeList.get(i);
        }
    }

    public int nonSpecialCount_v1(int l, int r) {
        int ceilLeft = (int) Math.ceil(Math.sqrt(l));
        int right = (int) Math.sqrt(r);
        if (ceilLeft > right) {
            return r - l + 1;
        }
        int a = Arrays.binarySearch(primes, ceilLeft);
        if (a < 0) {
            // 获取插入点，说明原来该位置的值大于ceilLeft
            a = -a - 1;
        }
        int b = Arrays.binarySearch(primes, right);
        if (b < 0) {
            // 这里多减了1，因为插入点是第一个大于right的位置，减1则小于 right
            b = -b - 2;
        }
//        return r - l + 1 - (b - a + 1);
        return r - l - b + a;
    }

}

性能

3243.新增道路查询后的最短距离I

目标

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

说明：

3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。

思路

有 n 个城市，刚开始每一个城市 i 有一条单项道路通向城市 i + 1，有一个二维数组 queries，queries[i] 表示增加一条从 queries[i][0] 到 queries[i][1] 的单项道路，返回 answer 数组，answer[i] 表示增加了 queries[i] 之后从城市 0 到城市 n - 1 的最短路径。

建图，每次增加路径之后使用BFS计算最短路径。注意过滤重复元素，否则过不了。

也可以使用动态规划来做。

定义 dp[i] 表示从城市 i 到城市 n - 1 的最短路径，每添加一条路径，受影响的只有包括起点在内前面的城市。当增加一条道路 [l, r]，状态转移方程为 dp[l] = Math.min(dp[r] + 1, dp[l])，表示从 r 到达终点加一步与原来值的最小值。我们需要同步更新 l 之前的 dp 值。我们可以倒序遍历 [0, l)，dp[j] = Math.min(dp[j], dp[j + 1] + 1) 取其自身与后面元素 dp 值加一的较小值，同时还要考虑区间内有前面查询新增的道路，比如前面有以 j 为起点的查询，还要再取一个较小值 Math.min(dp[j], dp[end] + 1)，end 表示之前增加的道路的终点。

代码


/**
 * @date 2024-11-19 0:47
 */
public class ShortestDistanceAfterQueries3243 {

    public int[] shortestDistanceAfterQueries_v2(int n, int[][] queries) {
        int[] dp = new int[n];
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < n; i++) {
            dp[i] = n - i - 1;
        }
        Map<Integer, List<Integer>> map = new HashMap<>(ql);
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            dp[l] = Math.min(dp[r] + 1, dp[l]);
            for (int j = l - 1; j >= 0; j--) {
                dp[j] = Math.min(dp[j], dp[j + 1] + 1);
                if (map.containsKey(j)) {
                    for (Integer end : map.get(j)) {
                        dp[j] = Math.min(dp[j], dp[end] + 1);
                    }
                }
            }
            res[i] = dp[0];
            map.putIfAbsent(l, new ArrayList<>());
            map.get(l).add(r);
        }
        return res;
    }

    public int[] shortestDistanceAfterQueries_v1(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
            g[i].add(i + 1);
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            g[queries[i][0]].add(queries[i][1]);
            res[i] = bfs_v1(g);
        }
        return res;
    }

    public int bfs_v1(List<Integer>[] g) {
        int n = g.length;
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[n];
        list.add(0);
        for (int res = 1; ; res++) {
            List<Integer> tmp = list;
            int size = tmp.size();
            list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Integer cur = tmp.get(i);
                for (Integer next : g[cur]) {
                    if (next == n - 1) {
                        return res;
                    }
                    if (!visited[next]) {
                        visited[next] = true;
                        list.add(next);
                    }
                }
            }
        }
    }

    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
            g[i].add(i + 1);
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            g[queries[i][0]].add(queries[i][1]);
            res[i] = bfs(g);
        }
        return res;
    }

    public int bfs(List<Integer>[] g) {
        int res = 0, n = g.length;
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        here:
        while (!q.isEmpty()) {
            int size = q.size();
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                if (cur == n - 1) {
                    break here;
                }
                set.addAll(g[cur]);
            }
            q.addAll(set);
            res++;
        }
        return res;
    }

}

性能

825.适龄的朋友

目标

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

说明：

n == ages.length
1 <= n <= 2 * 10^4
1 <= ages[i] <= 120

思路

某社交网站上有 n 个用户，ages[i] 表示用户 i 的年龄，当满足条件 ages[x] >= ages[y] && ages[y] > ages[x] / 2 + 7 时，用户 x 会向 y 发送好友申请。求网站上好友申请的总数。

第三个条件 ages[y] > 100 && ages[x] < 100 即 ages[y] > 100 > ages[x] 与第二个条件重复了，可以不考虑。

ages[x] >= ages[y] > ages[x] / 2 + 7 可以推出 ages[x] > 14 才可以发出好友申请，并且好友申请的对象也要满足 ages[y] > ages[x] / 2 + 7 > 14，

将年龄从大到小排序后，使用滑动窗口计算即可。

瓶颈在于排序，可以使用计数排序。

代码


/**
 * @date 2024-11-17 14:46
 */
public class NumFriendRequests825 {

    public int numFriendRequests_v1(int[] ages) {
        int n = ages.length;
        int[] ageCnt = new int[121];
        for (int i = 0; i < n; i++) {
            ageCnt[ages[i]]++;
        }
        int res = 0, windowCnt = 0;
        int l = 15;
        for (int i = 15; i < 121; i++) {
            windowCnt += ageCnt[i];
            if (l * 2 - 14 <= i) {
                windowCnt -= ageCnt[l++];
            }
            if (windowCnt > 0) {
                res += ageCnt[i] * (windowCnt - 1);
            }
        }
        return res;
    }

    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length;
        int r = n - 1, lowerBounds = ages[r] / 2 + 7;
        int res = 0;
        for (int l = n - 1; l >= 0 && ages[l] > 14; l--) {
            while (ages[l] <= lowerBounds) {
                lowerBounds = ages[--r] / 2 + 7;
            }
            res += r - l;
            int e = l;
            while (e < n - 1 && ages[e] == ages[e + 1]) {
                res++;
                e++;
            }
        }
        return res;
    }
}

性能

3240.最少翻转次数使二进制矩阵回文II

目标

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是回文的。

你可以将 grid 中任意格子的值翻转，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回最少翻转次数，使得矩阵中所有行和列都是回文的，且矩阵中 1 的数目可以被 4 整除。

示例 1：

输入：grid = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]
输出：2

示例 3：

输入：grid = [[1],[1]]
输出：2

说明：

m == grid.length
n == grid[i].length
1 <= m * n <= 2 * 10^5
0 <= grid[i][j] <= 1

思路

有一个二进制矩阵 grid，每次操作可以翻转任意格子，使 0 变为 1，或者使 1 变为 0。求使得矩阵 所有行 和 所有列 变成回文，且矩阵中 1 的数目可以被 4 整除的最少操作次数。

考虑矩阵操作后的最终状态，类似一个 田 或者 日 或者旋转 90 度的 日 字，每一个 口 内的元素完全相同，中间线上如果有元素的话也是对称的。

昨天的题最少翻转次数使二进制矩阵回文I 要求的是所有行或者所有列，当我们保证行是回文的时候，如果遇到不同的元素，翻转哪一个都可以。对于本题，需要同时保证列也是回文的，并且矩阵中 1 的个数能够被 4 整除。在要求操作次数最小的情况下，选择翻转哪一个是有影响的。需要考虑翻转元素后的代价，如果我们在保证行是回文的时候翻转了某个元素导致了该元素所在列的对称位置上的元素不同，那么翻转次数需要多加1，而如果翻转镜像位置的元素刚好可以使所在列对称位置上的元素相同，应该优先选择。实际上矩阵中 1 的数目可以被 4 整除，只需考虑奇数行与奇数列时的中间行与中间列，因为在其它区域出现 1，如果行列是回文的，一定可以被 4 整除。

我们再重新梳理一下，翻转的时候优先选择代价最小的，只需要考虑 四个对称位置上的值哪个占少数就翻转哪个。分别统计中间行与列中 1 的个数，以及变成回文的操作次数。由于中间行、列的翻转是任意的，我们可以计算中间行列中 1 的个数之和 midOneCnt，注意这里需要去除中心元素（即行或列为奇数时的中间元素）后面单独处理。根据 mod = midOneCnt % 4 的值，我们可以确定操作翻转哪个元素：

如果值为 1，将 1 置 0
如果值为 2，都行
如果值为 3，将 0 置 1

需要的操作次数为 Math.min(mod, 4 - mod)。如果保证回文的操作的次数不够使 1 的个数满足条件，就需要额外的操作。注意，这么做的前提条件是 有足够的格子，如果中线的格子总数不够 4 个，比如 3 个格子，里面都是 1 需要补一个 1 是无法操作的，这时操作次数只能取 mod 了。

最后考虑中心元素，它必须为0，否则 1 的总个数不可能被 4 整除。

代码


/**
 * @date 2024-11-15 11:28
 */
public class MinFlips3240 {

    /**
     * 执行通过
     */
    public int minFlips(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        int rowMid = m / 2;
        int colMid = n / 2;
        for (int i = 0; i < rowMid; i++) {
            for (int j = 0; j < colMid; j++) {
                int jj = n - j - 1;
                int ii = m - i - 1;
                int sum = grid[i][j] + grid[i][jj] + grid[ii][j] + grid[ii][jj];
                // 取四个元素中的少数元素个数
                res += Math.min(sum, 4 - sum);
            }
        }
        int midRowOneCnt = 0;
        int midRowOptCnt = 0;
        // 计算奇数行时中间行的操作次数与1的个数
        if (m % 2 == 1) {
            for (int j = 0; j < colMid; j++) {
                int jj = n - j - 1;
                midRowOneCnt += grid[rowMid][j] + grid[rowMid][jj];
                midRowOptCnt += grid[rowMid][j] ^ grid[rowMid][jj];
            }
        }
        int midColOneCnt = 0;
        int midColOptCnt = 0;
        // 计算奇数列时中间列的操作次数与1的个数
        if (n % 2 == 1) {
            for (int i = 0; i < rowMid; i++) {
                int ii = m - i - 1;
                midColOneCnt += grid[i][colMid] + grid[ii][colMid];
                midColOptCnt += grid[i][colMid] ^ grid[ii][colMid];
            }
        }
        int midOpt = midRowOptCnt + midColOptCnt;
        res += midOpt;
        int midOneCnt = midRowOneCnt + midColOneCnt;
        int mod = midOneCnt % 4;
        int remainder;
        // 确保格子数量足够
        if (m + n <= 4) {
            remainder = midOpt - mod;
        } else {
            remainder = midOpt - Math.min(mod, 4 - mod);
        }
        // 如果操作次数不够需要补上
        if (remainder < 0) {
            res += -remainder;
        }
        // 处理中心元素
        if (m % 2 == 1 && n % 2 == 1) {
            res += grid[rowMid][colMid];
        }

        return res;
    }

}

性能

3239.最少翻转次数使二进制矩阵回文I

目标

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是回文的。

你可以将 grid 中任意格子的值翻转，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回最少翻转次数，使得矩阵要么所有行是回文的，要么所有列是回文的。

示例 1：

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：2
解释：
将高亮的格子翻转，得到所有行都是回文的。

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]
输出：1
解释：
将高亮的格子翻转，得到所有列都是回文的。

示例 3：

输入：grid = [[1],[0]]
输出：0
解释：
所有行已经是回文的。

说明：

m == grid.length
n == grid[i].length
1 <= m * n <= 2 * 10^5
0 <= grid[i][j] <= 1

思路

有一个二进制矩阵 grid，每次操作可以翻转任意格子，使 0 变为 1，或者使 1 变为 0。求使得矩阵 所有行 或者 所有列 变成回文的最少操作次数。

由于是所有行或所有列，每种情况下的翻转次数是确定的，直接返回其最小值即可。

优化点：

使用 ⌊n/2⌋ 缩小循环范围，使用 n - 1 - j 代替尾部指针
是使用异或运算代替条件判断

代码


/**
 * @date 2024-11-15 9:05
 */
public class MinFlips3239 {

    public int minFlips(int[][] grid) {
        int rowOpts = 0;
        int colOpts = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                rowOpts += grid[i][j] ^ grid[i][n - 1 - j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m / 2; j++) {
                colOpts += grid[j][i] ^ grid[m - j - 1][i];
            }
        }
        return Math.min(rowOpts, colOpts);
    }

}

性能

3249.统计好节点的数目

目标

现有一棵无向树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的子树包含的节点数相同，则认为该节点是一个好节点。

返回给定树中好节点的数量。

子树指的是一个节点以及它所有后代节点构成的一棵树。

示例 1：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：7
说明：
树的所有节点都是好节点。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]
输出：6
说明：
树中有 6 个好节点。上图中已将这些节点着色。

示例 3：

输入：edges = [[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]
输出：12
解释：
除了节点 9 以外其他所有节点都是好节点。

说明：

2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
输入确保 edges 总表示一棵有效的树。

思路

树中的任一节点，如果以它的子节点为根的子树包含相同的节点数量，则称该节点为好节点。注意没有要求子节点是好节点，只统计子树整体的节点个数。求给定树的好节点个数。

dfs 获取子树节点数目，判断各子树的节点个数是否相同。叶子节点没有子树，可认为子树节点个数为 0 也是好节点。

代码


/**
 * @date 2024-11-14 9:32
 */
public class CountGoodNodes3249 {
    int res = 0;
    List<Integer>[] g;

    public int countGoodNodes(int[][] edges) {
        g = new List[edges.length + 1];
        int n = g.length;
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }
        dfs(-1, 0);
        return res;
    }

    public int dfs(int parent, int cur) {
        int num = 1;
        int prev = -1;
        boolean equal = true;
        for (Integer next : g[cur]) {
            if (next == parent) {
                continue;
            }
            int childNum = dfs(cur, next);
            if (prev != -1 && prev != childNum) {
                equal = false;
            }
            prev = childNum;
            num += childNum;
        }
        if (equal) {
            res++;
        }
        return num;
    }

}

性能

540.有序数组中的单一元素

目标

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

说明:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

思路

有序整数数组 nums，除了一个元素仅出现一次，其余每个元素都会出现两次，返回这个只出现一次的元素。

直接循环异或每个元素，时间复杂度为 O(n)。

题目要求时间复杂度是 O(logn) 显然需要使用二分查找，但是问题在于如果当前元素与其前/后元素相等，那么我们应该排除哪边？

这道题使用二分法的关键就是意识到中间元素下标的奇偶性与其前后元素的相等关系可以判断只出现一次的元素在中间元素的哪边。

如果不考虑这个唯一元素，数组元素的排列一定是 a a b b c c ……，

如果 mid 为偶数下标，nums[mid] == nums[mid + 1]
如果 mid 为奇数下标，nums[mid - 1] == nums[mid]

现在插入了一个唯一元素，那么该下标后面的关系变为：

如果 mid 为偶数下标，nums[mid - 1] == nums[mid]
如果 mid 为奇数下标，nums[mid] == nums[mid + 1]

根据任意一组关系就可以判断唯一元素下标在 mid 的左侧还是右侧了。当 mid 为偶数，比较 nums[mid] == nums[mid + 1]，如果不相等说明在左侧，当 mid 为奇数，比较 nums[mid - 1] == nums[mid]，如果不等说明在左侧。即相等需要舍弃左边，不等舍弃右边。

官网题解给出了优化细节，省略奇偶性判断，直接比较 mid 与 mid^1 两个元素，当 mid 为奇数时，mid^1 = mid - 1，当 mid 为偶数时， mid^1 = mid + 1。

官网题解还给出了一种判断方法，由于唯一元素的下标一定是偶数，因此可以二分查找偶数下标，唯一元素以及它右侧的所有偶数下标都满足 nums[mid] != nums[mid + 1]，我们只需要找到第一个满足条件的下标即可。查找的过程需要保证 mid 为偶数，这样判断才能成立，通常的做法是得到 mid 之后判断其奇偶性，如果是奇数则减一。这里同样也有个优化细节，即 mid - (mid & 1) 可以保证 mid 为偶数。

代码


/**
 * @date 2024-11-10 14:38
 */
public class SingleNonDuplicate540 {

    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            mid -= mid & 1;
            if (nums[mid] != nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 2;
            }
        }
        return nums[l];
    }

}

2025 年 4 月
一	二	三	四	五	六	日
	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	26	27
28	29	30