LeetCode周记 EP5

2024-10-12

字数统计: 2.4k字 | 阅读时长: 11分

前言

周赛依然没打～

本周主题：图路径枚举、深度优先搜索、贪心、矩阵枚举

题目：

240702每日一题—Maximum Path Quality of a Graph
240704每日一题—Minimum Moves to Pick K Ones
240707每日一题—Check if Move is Legal
图路径枚举（DFS）

Maximum Path Quality of a Graph

There is an undirected graph with n nodes numbered from 0 to n - 1 (inclusive). You are given a 0-indexed integer array values where values[i] is the value of the ith node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [uj, vj, timej] indicates that there is an undirected edge between the nodes uj and vj, and it takes timej seconds to travel between the two nodes. Finally, you are given an integer maxTime.

A valid path in the graph is any path that starts at node 0, ends at node 0, and takes at most maxTime seconds to complete. You may visit the same node multiple times. The quality of a valid path is the sum of the values of the unique nodes visited in the path (each node’s value is added at most once to the sum).

Return the maximum quality of a valid path.

Note: There are at most four edges connected to each node.

这题直接作为学习枚举图路径的素材了，对于数据范围小的图路径题可以考虑，由于原题通过时间范围限制了路径最大长度为10且每个节点的度数不超过4，则枚举的范围较小。

可以使用递归 + 回溯的方法进行枚举。递归函数记录当前所在的节点编号，已经过的路径的总时间以及节点的价值之和。如果当前在节点 u，我们可以枚举与 u 直接相连的节点 v 进行递归搜索。在搜索的过程中，如果我们回到了节点 0，就可以对答案进行更新；如果总时间超过了 maxTime，我们需要停止搜索，进行回溯。

class Solution {
    int ans = 0;
    int[] values;
    int maxTime;
    List<int[]>[] g; // 第二维可变长的二维数组
    boolean[] visited; // 用于判断是否需要计算价值

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        this.values = values;
        this.maxTime = maxTime;
        int n = values.length;
        g = new List[n]; // 用于存储每个节点的邻接节点与代价
        // 初始化
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<int[]>();
        }
        for (int[] edge : edges) {
            g[edge[0]].add(new int[]{edge[1], edge[2]});
            g[edge[1]].add(new int[]{edge[0], edge[2]});
        }
        
        visited = new boolean[n];
        visited[0] = true;
        
        dfs(0, 0, values[0]); // 初始节点，已经过时间，当前价值和
        return ans;
    }

    public void dfs(int u, int time, int value) {
        if (u == 0) {
            ans = Math.max(ans, value);
        }
        for (int[] arr : g[u]) {
            int v = arr[0], dist = arr[1];
            // 如果时间允许则进行下一步
            if (time + dist <= maxTime) {
                if (!visited[v]) {
                    // 对于初次经过的节点，尝试所有可能路径后回溯
                    visited[v] = true;
                    dfs(v, time + dist, value + values[v]);
                    visited[v] = false;
                } else {
                    // 已经走过就无所谓了反正也不计算value
                    dfs(v, time + dist, value);
                }
            }
            // 时间不允许则结束
        }
    }
}

矩阵枚举

Check if Move is Legal

You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by ‘.’, white cells are represented by ‘W’, and black cells are represented by ‘B’.

Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal).

A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free).

Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.

由题意可知，当前操作合法当且仅当从该点开始的 8 个方向（上下左右与对角线）中，至少有一个方向存在一个以该点为起点的好线段。

那么，我们可以枚举这 8 个方向，并对于每个方向验证是否存在以该点为起点的好线段。如果该点与对应方向下一个相同颜色的格点之间的所有格点（至少一个）均为另一种颜色，那么它们构成一个好线段。

我们用数对 (dx,dy) 来表示每个方向下一个格点相对于当前格点的行列下标变化量，并用函数 check(dx,dy) 来判断该方向是否存在以操作位置为起点的好线段。如果我们寻找到了符合要求的好线段，则返回 true；反之亦然。

class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        // 从 x 轴正方向开始逆时针枚举 8 个方向
        int[] dx = {1, 1, 0, -1, -1, -1, 0, 1};   // 行改变量
        int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};   // 列改变量
        for (int k = 0; k < 8; ++k) {
            if (check(board, rMove, cMove, color, dx[k], dy[k])) {
                return true;
            }
        }
        return false;
    }

    // 判断每个方向是否存在以操作位置为起点的好线段
    public boolean check(char[][] board, int rMove, int cMove, char color, int dx, int dy) {
        int x = rMove + dx;
        int y = cMove + dy;
        int step = 1;   // 当前遍历到的节点序号
        while (x >= 0 && x < 8 && y >= 0 && y < 8) {
            if (step == 1) {
                // 第一个点必须为相反颜色
                if (board[x][y] == '.' || board[x][y] == color) {
                    return false;
                }
            } else {
                // 好线段中不应存在空格子
                if (board[x][y] == '.') {
                    return false;
                }
                // 遍历到好线段的终点，返回 true
                if (board[x][y] == color) {
                    return true;
                }
            }
            ++step;
            x += dx;
            y += dy;
        }
        // 不存在符合要求的好线段
        return false;
    }
}

贪心

题目：Minimum Moves to Pick K Ones

这题首先要先读明白题…首先有一个“01串”，目标是用最少的moves捡起k个$1$，起始状态是从串中的某个$1$开始的，我们叫这个$1$的下标为aliceIndex，我们取走这个$1$使该位置变成$0$，此时还差k-1个$1$需要捡。怎么捡其他的$1$呢？我们通过如下两种操作：

随便选一个$0$变成$1$，俗称点石成金，有最大操作数限制maxChanges；
选两个邻接的$1$和$0$，下标分别为$x$和$y$，交换值，如果$y==aliceIndex$则捡起这个$1$。

因此，对于aliceIndex左右两侧有$1$的情况，我们只需要$1$个动作就可以捡起，当两侧都为$0$时，通过点石成金和交换的组合动作来捡$1$，这里的分情况思想比较重要，我第一次做时就错在了从动作角度考虑，实际上分情况时应该注意“普适性”与“靠近终态”（这是我瞎总结的），因此应该从所有的$1$所处的位置考虑。情况如下：

情况一：先将 aliceIndex 邻近的数字设置为 1 ，然后交换数字，只需要两次行动就可以拾起一个 1 。
情况二：令 $n u m s[x]=1$ ，那么需要 $\mid x$-aliceIndex $\mid$ 次行动才可以拾起一个 1 ，根据 $x$ 的取值，又可以区分成两种类型:
- $x \in[$ aliceIndex -1 , aliceIndex +1$]$ ，那么最多需要 1 次行动就可以拾起一个 1 。
- $x \notin[$ aliceIndex -1 , aliceIndex +1$]$ ，那么最少需要 2 次行动才可以拾起一个 1 。

令 $f($ aliceIndex $)$ 表示数组 nums 在区间 $[$ aliceIndex -1 , aliceIndex +1$]$ 内的元素之和。
如果 $f($ aliceIndex $)+maxChanges \geq k$ ，那么最少行动次数肯定是先将区间 [aliceIndex -1 , aliceIndex + 1] 内的所有 1 拾起, 然后剩余的 1 根据情况一来拾起。

如果 $f($ aliceIndex $)+maxChanges <k$ ，那么可以贪心地先拾起情况一的所有 1 ，剩余 $k-maxChanges$个 1 根据情况二拾起。我们使用 $indexSum [i]$ 记录数组 $n u m s$ 在区间 $[0, i)$ 内所有值为 1 的元素下标之和，使用 $sum[i]$ 记录数组 nums 在区间 $[0, i)$ 所有元素之和。要使情况二的行动次数之和最少，那么拾起的 1 距离 aliceIndex 需要尽量近。我们使用二分算法来搜索最短距离 $d$ ，使得区间 $[aliceIndex-d, aliceIndex+d]$ 内的 1 数目大于等于 $k-maxChanges$ 。记选择的区间为 $\left[i_1, i_2\right]$, 那么最少行动次数为:

$\begin{aligned} & \text { indexSum }\left[i_2+1\right]-\text { indexSum }[\text { aliceIndex }+1]-\text { aliceIndex } \times\left(\operatorname{sum}\left[i_2+1\right]-\operatorname{sum}[aliceIndex+1]\right)+\text { aliceIndex } \times \\ & \left(\operatorname{sum}[\text { aliceIndex }+1]-\operatorname{sum}\left[i_1\right]\right)-\left(\text { indexSum }[\text { aliceIndex }+1]-\text { indexSum }\left[i_1\right]\right)+2 \times \text { maxChanges } \end{aligned}$

我们可以枚举 aliceIndex, 然后取所有结果的最小值。

class Solution {
    public long minimumMoves(int[] nums, int k, int maxChanges) {
        int n = nums.length;

        long[] indexSum = new long[n + 1], sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            indexSum[i + 1] = indexSum[i] + nums[i] * i;
            sum[i + 1] = sum[i] + nums[i];
        }
        long res = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (f(i, nums) + maxChanges >= k) {
                if (k <= f(i, nums)) {
                    res = Math.min(res, (long)k - nums[i]);
                } else {
                    res = Math.min(res, (long)2 * k - f(i, nums) - nums[i]);
                }
                continue;
            }
            int left = 0, right = n;
            while (left <= right) {
                int mid = (left + right) / 2;
                int i1 = Math.max(i - mid, 0), i2 = Math.min(i + mid, n - 1);
                if (sum[i2 + 1] - sum[i1] >= k - maxChanges) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            int i1 = Math.max(i - left, 0), i2 = Math.min(i + left, n - 1);
            if (sum[i2 + 1] - sum[i1] > k - maxChanges) {
                i1++;
            }
            long count1 = sum[i + 1] - sum[i1], count2 = sum[i2 + 1] - sum[i + 1];
            res = Math.min(res, indexSum[i2 + 1] - indexSum[i + 1] - i * count2 + i * count1 - (indexSum[i + 1] - indexSum[i1]) + 2 * maxChanges);
        }
        return res;
    }

    public int f(int i, int[] nums) {
        int x = nums[i];
        if (i - 1 >= 0) {
            x += nums[i - 1];
        }
        if (i + 1 < nums.length) {
            x += nums[i + 1];
        }
        return x;
    }
}

参考文献

[1] https://leetcode.cn/problems/minimum-moves-to-pick-k-ones/solutions/2827546/shi-qi-k-ge-1-xu-yao-de-zui-shao-xing-do-1c7m/

后记

首发于 silencezheng.top，转载请注明出处。

前言

图路径枚举（DFS）

矩阵枚举

贪心

参考文献

后记