标签： todo

2940.找到Alice和Bob可以相遇的建筑

目标

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

示例 1：

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出：[2,5,-1,5,2]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

示例 2：

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出：[7,6,-1,4,6]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

说明：

  • 1 <= heights.length <= 5 * 10^4
  • 1 <= heights[i] <= 10^9
  • 1 <= queries.length <= 5 * 10^4
  • queries[i] = [ai, bi]
  • 0 <= ai, bi <= heights.length - 1

思路

有一个数组 heights 表示建筑的高度，另有一个二维数组，其元素 queries[i] = [ai, bi] 表示 Alice 和 Bob 当前所在建筑的下标，规定可以从左向右移动到比当前建筑高的建筑，求 Alice 和 Bob 可以相遇的建筑下标，如果有多个取最左侧的那个。

这个问题的关键在于求出 [max(ai, bi), n) 范围内，高度大于等于 max(heights[ai], heights[bi]) 的建筑下标最小值。暴力求解会超时，考虑使用单调栈，记录下一个高度大于当前建筑的下标。类似于跳表，从较高的建筑出发，查找第一个下标大于等于max(ai, bi)的建筑即可。它存在的问题是如果(ai, bi)之间有极大值，后面还得遍历查找。最坏的情况下，数据依次递增，而满足条件的值在最后，这时退化为暴力求解。

碰巧过了。// todo 研究一下官网题解

代码

/**
 * @date 2024-08-10 19:56
 */
public class LeftmostBuildingQueries2940 {

    public int[] leftmostBuildingQueries_v1(int[] heights, int[][] queries) {
        int num = heights.length;
        int[] next = new int[num];
        Arrays.fill(next, -1);
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // 单调栈
        for (int i = 0; i < num; i++) {
            while (!stack.isEmpty() && heights[i] > heights[stack.peek()]) {
                next[stack.pop()] = i;
            }
            stack.push(i);
        }
        int n = queries.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            if (a == b) {
                res[i] = a;
                continue;
            } else if (a < b && heights[a] < heights[b]) {
                res[i] = b;
                continue;
            } else if (a > b && heights[a] > heights[b]) {
                res[i] = a;
                continue;
            }
            int leftNext = Math.min(a, b);
            int rightNext = Math.max(a, b);
            if (next[leftNext] > rightNext || next[leftNext] == -1) {
                res[i] = next[leftNext];
                continue;
            }
            int height = Math.max(heights[a], heights[b]);
            while (next[rightNext] != -1) {
                if (heights[next[rightNext]] > height) {
                    res[i] = next[rightNext];
                    break;
                } else {
                    rightNext = next[rightNext];
                }
            }
        }
        return res;
    }
}

性能

3129.找出所有稳定的二进制数组 I/II

目标

给你 3 个正整数 zero ，one 和 limit 。

一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

  • 0 在 arr 中出现次数 恰好 为 zero 。
  • 1 在 arr 中出现次数 恰好 为 one 。
  • arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。

请你返回 稳定 二进制数组的 总 数目。

由于答案可能很大，将它对 10^9 + 7 取余 后返回。

示例 1：

输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

示例 2：

输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

说明：

  • 1 <= zero, one, limit <= 200 medium
  • 1 <= zero, one, limit <= 1000 hard

提示：

  • Let dp[a][b][c = 0/1][d] be the number of stable arrays with exactly a 0s, b 1s and consecutive d value of c’s at the end.
  • Try each case by appending a 0/1 at last to get the inductions.

思路

有 zero 个 0 和 one 个 1 组成的数组，满足所有长度大于 limit 的子数组同时包含0和1的数组有多少个。

首先考虑由 zero 个 0 和 one 个 1 组成的数组有多少个。C(zero + one, zero) 从 zero + one 个位置中选出 zero 或者 one 个。根据题目中的范围 1 ~ 200，C(400, 200) 大概在 10^119 ~ 10^120之间。不可能枚举所有组合，更别提枚举每种组合的所有子数组了。我们必须自底向上寻求解决方案。

如何保证 limit + 1 的窗口内一定包含 0 和 1 呢？

看了提示说是四维动态规划，直接放弃了。思考过程中卡住的点是不会构建满足条件的解，想不出怎样才能让子数组中同时包含 0 和 1。其实只要保证不出现连续 limit + 1 个 0 或 1 就可以了。想到了动态规划，但是不知道如何进行状态转移。

代码

性能

572.另一棵树的子树

目标

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

说明：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

思路

判断给定的树是否是另一颗树的子树。

刚开始想以某种顺序（先/中/后）遍历给定的树并记录访问节点，然后遍历另一棵树，如果节点值等于给定树的根节点则以同样的顺序记录其子树，再比较记录是否相同。但是这并不能保证结构是相同的。

只能逐个节点比较。进一步优化可以计算树的高度，只比较高度相同的。//todo

看了官网题解可以引入两个null值，进行串匹配的时候可以使用 KMP 或者 Rabin-Karp 算法。//todo

也提供了将树映射为hash值来比较的思路。//todo

代码

/**
 * @date 2024-08-04 15:36
 */
public class IsSubtree572 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (root.val == subRoot.val) {
            if (compare(root, subRoot)) {
                return true;
            }
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean compare(TreeNode root, TreeNode subRoot) {
        if (root.val != subRoot.val) {
            return false;
        }
        boolean res = false;
        if (root.left != null && subRoot.left != null) {
            res = compare(root.left, subRoot.left);
        } else if (root.left == null && subRoot.left == null){
            res = true;
        }
        if (root.right != null && subRoot.right != null) {
            res = compare(root.right, subRoot.right) && res;
        } else if (root.right == null && subRoot.right == null) {
        } else {
            res = false;
        }
        return res;
    }

}

性能

2961.双模幂运算

目标

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

  • 0 <= i < variables.length
  • ((ai^bi % 10)^ci) % mi == target

返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

输入：variables = [[39,3,1000,1000]], target = 17
输出：[]
解释：对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(393 % 10)1000 % 1000 = 1 。
因此，返回 [] 作为答案。

说明：

  • 1 <= variables.length <= 100
  • variables[i] == [ai, bi, ci, mi]
  • 1 <= ai, bi, ci, mi <= 10^3
  • 0 <= target <= 10^3

思路

已知二维数组 variables[i] = [ai, bi, ci, mi]，定义好下标为 ((ai^bi % 10)^ci) % mi == target，返回好下标组成的数组。

尝试使用Math.pow暴力求解，存在精度丢失，例如 Math.pow(31, 12) = 7.8766278378854976 E17 ，mod 10 结果为 0。

提前mod也没用，比如 ai^bi % 10 == 6，6 ^ 83 % 81还是会丢失精度，只能手动循环计算了。

官网题解使用了快速幂。不用一个一个的乘，使用递归，根据幂的奇偶，偶数直接求 x^(n/2) * x^(n/2)，奇数求 x^(⌊n/2⌋) * x^(⌊n/2⌋) * x，直到n为0。时间复杂度为 O(logn)。

//todo 快速幂

代码

/**
 * @date 2024-07-30 9:11
 */
public class GetGoodIndices2961 {

    public List<Integer> getGoodIndices(int[][] variables, int target) {
        List<Integer> res = new ArrayList<>();
        int n = variables.length;
        for (int i = 0; i < n; i++) {
            int[] variable = variables[i];
            int base = variable[0];
            int tmp1 = 1;
            for (int j = 0; j < variable[1]; j++) {
                tmp1 = (tmp1 * base) % 10;
            }
            base = tmp1;
            int tmp = 1;
            for (int j = 0; j < variable[2]; j++) {
                tmp = (tmp * base) % variable[3];
            }
            if (tmp % variable[3] == target) {
                res.add(i);
            }
        }
        return res;
    }
}

性能

3098.求出所有子序列的能量和

目标

给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。

一个 子序列 的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

由于答案可能会很大，将答案对 10^9 + 7 取余 后返回。

示例 1：

输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

示例 2：

输入：nums = [2,2], k = 2
输出：0
解释：
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。

示例 3：

输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。

说明：

  • 2 <= n == nums.length <= 50
  • -10^8 <= nums[i] <= 10^8
  • 2 <= k <= n

思路

定义数组子序列的能量为子序列中任意两个元素差的绝对值的最小值，求数组长度为k的子序列的能量和。

首先思考，数组 nums 长度为n的子序列有多少？根据每一个元素是否在序列中可知有 2^n种可能。n 最大为50，2^50 = 1125899906842624。那么长度为k的子序列有多少？ C(n,k) = n!/(k!(n-k)!)，当 k=2 时，有 n(n-1)/2 个子序列。

只能考虑动态规划，自底向上地求解。我们可以使用状态压缩来表示子序列，当状态发生转移的时候该如何处理呢？假设我们知道了某k-1子序列的能量，那么再增加一个元素能量会如何变化？比如子序列1,3,6,10，能量为2，再加入一个元素9，能量变为1。还是需要遍历子序列的。那么我们可以根据压缩的状态仅遍历哪些bit位为1的元素。剩下的问题就是如何遍历子序列了。

看了提示，首先要排序，这样差值最小的就两两相邻。刚开始的时候我也在想能不能排序，虽然子序列要保持相对顺序，但本题考虑的是子序列中绝对值差最小的，与顺序无关。

// todo

代码

性能

2101.引爆最多的炸弹

目标

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

示例 1：

输入：bombs = [[2,1,3],[6,1,4]]
输出：2
解释：
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹，右边的炸弹不会被影响。
但如果我们引爆右边的炸弹，两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。

示例 2：

输入：bombs = [[1,1,5],[10,10,5]]
输出：1
解释：
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。

示例 3：

输入：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出：5
解释：
最佳引爆炸弹为炸弹 0 ，因为：
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。

说明：

  • 1 <= bombs.length <= 100
  • bombs[i].length == 3
  • 1 <= xi, yi, ri <= 10^5

思路

坐标平面上有一些炸弹，并且已知炸弹的爆炸范围。现在可以选择引爆其中的一颗炸弹，被引爆炸弹的爆炸范围内的其它炸弹也会被引爆，问最多可以引爆的炸弹数量。

我们可以将问题转换为有向图，一枚炸弹能够波及到的其它炸弹认为是连通的，然后遍历每一枚炸弹，求出连通炸弹数量最多的个数即可。

那么如何建立这个有向图呢？固定一个，依次与其余的节点比较，时间复杂度为O(n^2)，炸弹最多100个，应该可行。

实现过程中需要判断爆炸范围内的是否存在其它炸弹，可以使用炸弹坐标（圆心）之间的距离与各自的引爆半径相比较。这里需要注意防止数据溢出，另外还有一个小技巧，比较 sqrt(dx^2 + dy^2) 与 半径 r 的效率没有 dx^2 + dy^2 与 r^2 高。

网友最快的题解使用的是 Floyd 算法。// todo

代码

/**
 * @date 2024-07-22 9:24
 */
public class MaximumDetonation2101 {

    public int maximumDetonation_v1(int[][] bombs) {
        int n = bombs.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            int ix = bombs[i][0];
            int iy = bombs[i][1];
            long ir = bombs[i][2];
            for (int j = i + 1; j < n; j++) {
                int jx = bombs[j][0];
                int jy = bombs[j][1];
                long jr = bombs[j][2];
                // 防止溢出
                long diffx = ix - jx;
                long diffy = iy - jy;
                long dist = diffx * diffx + diffy * diffy;
                if (ir * ir >= dist) {
                    g[i].add(j);
                }
                if (jr * jr >= dist) {
                    g[j].add(i);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            res = Math.max(res, dfs(i, g, visited));
        }
        return res;
    }

    int dfs(int root, List<Integer>[] g, boolean[] visited) {
        visited[root] = true;
        int res = 1;
        for (Integer next : g[root]) {
            if (visited[next]) {
                continue;
            }
            res += dfs(next, g, visited);
        }
        return res;
    }

}

性能

图中至多有 n^2 条边，dfs的时间复杂度是O(n^2)，然后再遍历n个起点，时间复杂度为O(n^3)。

1186.删除一次得到子数组最大和

目标

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。

注意，删除一个元素后，子数组 不能为空。

示例 1：

输入：arr = [1,-2,0,3]
输出：4
解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。

示例 2：

输入：arr = [1,-2,-2,3]
输出：3
解释：我们直接选出 [3]，这就是最大和。

示例 3：

输入：arr = [-1,-1,-1,-1]
输出：-1
解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

说明：

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i] <= 10^4

思路

有一个数组求其子数组的最大和，允许删除子数组的一个元素，但子数组至少要有一个元素。

暴力解法是，先找出负值元素的下标，依次删除，针对删除后的数组求其子数组的最大和。使用前缀和求出最大子数组的时间复杂度是O(n^2)，再删除负值（将负值置零，和增大），最坏情况下为O(n^3)，会超时。暴力解法要注意，至少保留1个元素。

// todo

代码

性能

2850.将石头分散到网格图的最少移动次数

目标

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。
总共需要 4 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 4 。

说明：

  • grid.length == grid[i].length == 3
  • 0 <= grid[i][j] <= 9
  • grid 中元素之和为 9 。

思路

有一个3 * 3 的二维矩阵，有9个石头散落在其中，每次可以将石头移到相邻的格子里，问每个格子一块石头最少需要移动几次。

有多余石头的格子到没有石头格子移动的次数为其曼哈顿距离，要想使移动次数最小，我们只需要从没有石头的格子向四个方向查找有多余石头的格子即可。

并非是沿四个方向搜索，而是BFS找最短路径。 遍历四个方向，那么只能沿着该方向查找，而BFS则是由内层向外层查找，体会二者的不同。但这题使用BFS也无法保证得到的是最小移动次数，考虑下面的情况：

从0开始取最近的并不能保证得到最优解，比如下面这种情况：

3,2,0      3,1,1      2,1,1      2,1,1      2,1,1      1,1,1
0,1,0  ->  0,1,0  ->  1,1,0  ->  1,1,1  ->  1,1,1  ->  1,1,1
0,3,0      0,3,0      0,3,0      0,2,0      1,1,0      1,1,1
       1          1          2           1          4
左下角的应该从第一个元素取：

3,2,0      3,1,1      2,1,1      2,1,1      1,1,1      1,1,1
0,1,0  ->  0,1,0  ->  1,1,0  ->  1,1,1  ->  1,1,1  ->  1,1,1
0,3,0      0,3,0      0,3,0      0,2,0      1,2,0      1,1,1
       1          1          2           2          1

尽管这题使用BFS求解不了，但还是有一些收获的。BFS很容易错写成每次从队列取一个元素，然后判断该元素是否满足条件，不满足就将其邻接节点加入队列。当需要进行层次计数的时候就不对了，应该在每次循环的第一步记录队列中元素个数 k，本次处理中就循环判断这k个元素，在循环过程中判断是否满足条件，不满足的将其邻接节点加入队列，因为我们已经在前面计数了，因此这些邻接节点将在下一次循环中处理。

如果取最近的多余石头这种贪心策略不行的话，那么问题就不在于最短路径了。而应从整体上考虑从哪里移动到哪里才是最优的，可以尝试记忆化搜索解空间。我们可以很容易枚举出哪些格子没有石头，哪些格子石头多于1个，只需枚举它们的组合并取其曼哈顿距离之和最小值即可。

这里的核心问题是如何遍历这两个列表的组合，我想到的方法就是使用回溯算法，每向下递归一层就标记为已访问，而返回时再取消其标记。并且如果不保存重复子问题的话，执行会超时。这里的重复子问题是两组数据未访问元素相同，而已访问数据的组合不同。例如： [a,b,c,d,e,f,g] [h,i,j,k,l,m,n] 前面两个元素组合 (a, h) (b, i) 与 (a, i) (b, h) 剩余的元素的组合情况完全相同。

最终使用状态压缩与回溯解出来了。如果不记录重复的子问题的话，dfs方法要调用3705927296次，而使用记忆化搜索只需调用12868次。

官网题解也是类似的思路，只不过遍历组合的方式不同，它是固定一个列表不变，另一个进行全排列。//todo 有空再研究一下官网题解吧

代码

/**
 * @date 2024-07-20 15:55
 */
public class MinimumMoves2850 {

    public int minimumMoves_v2(int[][] grid) {
        List<int[]> zeros = new ArrayList<>();
        List<int[]> more = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) {
                    zeros.add(new int[]{i, j});
                } else if (grid[i][j] > 1) {
                    for (int k = 0; k < grid[i][j] - 1; k++) {
                        more.add(new int[]{i, j});
                    }
                }
            }
        }
        int k = zeros.size();
        int res = Integer.MAX_VALUE;
        int[][] mem = new int[255][255];

        for (int i = 0; i < k; i++) {
            // 状态压缩
            int zerosVisited = 0x000000ff;
            zerosVisited ^= 1 << i;
            int[] zero = zeros.get(i);
            for (int j = 0; j < k; j++) {
                int moreVisited = 0x000000ff;
                moreVisited ^= 1 << j;
                int[] m = more.get(j);
                int distance = Math.abs(zero[0] - m[0]) + Math.abs(zero[1] - m[1]);
                res = Math.min(res, distance + dfs_v2(zeros, more, zerosVisited, moreVisited, 1, mem));
            }
        }
        return res;
    }

    public int dfs_v2(List<int[]> zeros, List<int[]> more, int zerosVisited, int moreVisited, int level, int[][] mem) {
        if (level == zeros.size()) {
            return 0;
        }
        int k = zeros.size();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            if (((zerosVisited >> i) & 1) == 0) {
                continue;
            }
            zerosVisited ^= 1 << i;
            int[] zero = zeros.get(i);
            for (int j = 0; j < k; j++) {
                if (((moreVisited >> j) & 1) == 0) {
                    continue;
                }
                moreVisited ^= 1 << j;
                int[] m = more.get(j);
                int distance = Math.abs(zero[0] - m[0]) + Math.abs(zero[1] - m[1]);
                if (mem[zerosVisited][moreVisited] == 0) {
                    // 重复的子问题是两边剩余的元素均相同
                    mem[zerosVisited][moreVisited] = dfs_v2(zeros, more, zerosVisited, moreVisited, level + 1, mem);
                }
                res = Math.min(res, distance + mem[zerosVisited][moreVisited]);
                // 回溯
                moreVisited ^= 1 << j;
            }
            zerosVisited ^= 1 << i;
        }
        return res;
    }

}

性能

2959.关闭分部的可行集合数目

目标

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。

公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。

两个分部之间的 距离 是通过道路长度之和的 最小值 。

给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。

请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

注意，关闭一个分部后，与之相连的所有道路不可通行。

注意，两个分部之间可能会有多条道路。

示例 1：

输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
输出：5
解释：可行的关闭分部方案有：
- 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。

示例 2：

输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
输出：7
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。
- 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。
- 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 7 种可行的关闭方案。

示例 3：

输入：n = 1, maxDistance = 10, roads = []
输出：2
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0] 。
- 关闭分部集合 [0] ，关闭后没有剩余分部。
总共有 2 种可行的关闭方案。

说明：

  • 1 <= n <= 10
  • 1 <= maxDistance <= 105
  • 0 <= roads.length <= 1000
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 1000
  • 一开始所有分部之间通过道路互相可以到达。

思路

没时间做了// todo

代码

性能