【题解】—— 每日一道题目栏

上接：【题解】—— LeetCode一周小结9

4.用栈实现队列

题目链接：232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：

[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]

解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

提示：

1 <= x <= 9

最多调用 100 次 push、pop、peek 和 empty

假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

题解：
方法：两个栈来模拟队列
        入队操作直接将元素压入输入栈。出队或获取队首元素时，如果输出栈为空，则将输入栈的元素依次弹出并压入输出栈，这样输出栈的栈顶元素即为队首元素。

import java.util.ArrayDeque;
import java.util.Deque;

class MyQueue {
    Deque<Integer> inStack; // 输入栈，用于入队操作
    Deque<Integer> outStack; // 输出栈，用于出队操作

    /** Initialize your data structure here. */
    public MyQueue() {
        inStack = new ArrayDeque<Integer>(); // 初始化输入栈
        outStack = new ArrayDeque<Integer>(); // 初始化输出栈
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        inStack.push(x); // 将元素入栈
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (outStack.isEmpty()) { // 如果输出栈为空，则将输入栈的元素转移到输出栈
            in2out();
        }
        return outStack.pop(); // 从输出栈中出栈元素
    }

    /** Get the front element. */
    public int peek() {
        if (outStack.isEmpty()) { // 如果输出栈为空，则将输入栈的元素转移到输出栈
            in2out();
        }
        return outStack.peek(); // 查看输出栈的栈顶元素
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty(); // 输入栈和输出栈都为空时，队列为空
    }

    // 将输入栈的元素转移到输出栈
    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

5.到达目的地的方案数

题目链接：1976. 到达目的地的方案数

你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

示例 1：

输入：n = 7, roads =
[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]

输出：4

解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。

四条花费 7 分钟的路径分别为：

• 0 ➝ 6
• 0 ➝ 4 ➝ 6
• 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
• 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

示例 2：

输入：n = 2, roads = [[1,0,10]]

输出：1

解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。

提示：

1 <= n <= 200

n - 1 <= roads.length <= n * (n - 1) / 2

roads[i].length == 3

0 <= ui, vi <= n - 1

1 <= timei <= 109

ui != vi

任意两个路口之间至多有一条路。

从任意路口出发，你能够到达其他任意路口。

题解：
方法：朴素 Dijkstra（适用于稠密图）
        计算从起点到终点的路径数量。使用了 Dijkstra 算法来计算最短路径，同时记录了每个节点处的路径数量。

import java.util.Arrays;

class Solution {
    public int countPaths(int n, int[][] roads) {
        long[][] g = new long[n][n]; // 邻接矩阵
        for (long[] row : g) {
            Arrays.fill(row, Long.MAX_VALUE / 2); // 防止溢出
        }
        for (int[] r : roads) {
            int x = r[0];
            int y = r[1];
            int d = r[2];
            g[x][y] = d;
            g[y][x] = d;
        }

        long[] dis = new long[n];
        Arrays.fill(dis, 1, n, Long.MAX_VALUE / 2);
        int[] f = new int[n];
        f[0] = 1;
        boolean[] done = new boolean[n];
        while (true) {
            int x = -1;
            for (int i = 0; i < n; i++) {
                if (!done[i] && (x < 0 || dis[i] < dis[x])) {
                    x = i;
                }
            }
            if (x == n - 1) {
                // 不可能找到比 dis[n-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
                return f[n - 1];
            }
            done[x] = true; // 最短路长度已确定（无法变得更小）
            for (int y = 0; y < n; y++) { // 尝试更新 x 的邻居的最短路
                long newDis = dis[x] + g[x][y];
                if (newDis < dis[y]) {
                    // 就目前来说，最短路必须经过 x
                    dis[y] = newDis;
                    f[y] = f[x];
                } else if (newDis == dis[y]) {
                    // 和之前求的最短路一样长
                    f[y] = (f[y] + f[x]) % 1_000_000_007;
                }
            }
        }
    }
}

方法：堆优化 Dijkstra（适用于稀疏图）
        计算从起点到终点的路径数量。使用了 Dijkstra 算法来计算最短路径，并在遍历过程中记录了每个节点处的路径数量。

import javafx.util.Pair;

import java.util.*;

class Solution {
    public int countPaths(int n, int[][] roads) {
        List<int[]>[] g = new ArrayList[n]; // 邻接表
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] r : roads) {
            int x = r[0];
            int y = r[1];
            int d = r[2];
            g[x].add(new int[]{y, d});
            g[y].add(new int[]{x, d});
        }

        long[] dis = new long[n];
        Arrays.fill(dis, 1, n, Long.MAX_VALUE);
        int[] f = new int[n];
        f[0] = 1;
        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
        pq.offer(new Pair<>(0L, 0));
        while (true) {
            Pair<Long, Integer> pair = pq.poll();
            long dx = pair.getKey();
            int x = pair.getValue();
            if (x == n - 1) {
                // 不可能找到比 dis[n-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
                return f[n - 1];
            }
            if (dx > dis[x]) {
                continue;
            }
            for (int[] e : g[x]) { // 尝试更新 x 的邻居的最短路
                int y = e[0];
                long newDis = dx + e[1];
                if (newDis < dis[y]) {
                    // 就目前来说，最短路必须经过 x
                    dis[y] = newDis;
                    f[y] = f[x];
                    pq.offer(new Pair<>(newDis, y));
                } else if (newDis == dis[y]) {
                    // 和之前求的最短路一样长
                    f[y] = (f[y] + f[x]) % 1_000_000_007;
                }
            }
        }
    }
}

题单：Dijkstra 算法

743. 网络延迟时间
2642. 设计可以求最短路径的图类
1514. 概率最大的路径
1631. 最小体力消耗路径 做法不止一种
1368. 使网格图至少有一条有效路径的最小代价 可以 0-1 BFS
1786. 从第一个节点出发到最后一个节点的受限路径数
1976. 到达目的地的方案数
2662. 前往目标的最小代价
2045. 到达目的地的第二短时间 可以 BFS
882. 细分图中的可到达节点
2203. 得到要求路径的最小带权子图
2577. 在网格图中访问一个格子的最少时间
2699. 修改图中的边权
2093. 前往目标城市的最小费用（会员题）
2473. 购买苹果的最低成本（会员题）
2714. 找到最短路径的 K 次跨越（会员题）
2737. 找到最近的标记节点（会员题）
LCP 35. 电动车游城市

6.找出数组中的 K-or 值

题目链接：2917. 找出数组中的 K-or 值

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

nums 中的 K-or 是一个满足以下条件的非负整数：

只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。
返回 nums 的 K-or 值。

注意 ：对于整数 x ，如果 (2ⁱAND x) == 2ⁱ ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4

输出：9

解释： nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。

nums[0] 和 nums[5] 的第 1 位的值为 1 。

nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。

nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。

只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6

输出：0

解释：因为 k == 6 == nums.length ，所以数组的 6-or 等于其中所有元素按位与运算的结果。因此，答案为 2 AND12 AND 1 AND 11 AND 4 AND 5 = 0 。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1

输出：15

解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11OR 6 OR 8 = 15 。

提示：

1 <= nums.length <= 50

0 <= nums[i] < 2³¹

1 <= k <= nums.length

题解：
方法：位运算
        目的是找到数组 nums 中的元素的二进制表示中，每一位上出现次数至少为 k 次的位。它通过逐位检查数组中所有元素的二进制表示，统计每一位上为 1 的个数，如果某一位上为 1 的个数不小于 k，则将结果中对应位置为 1。

知识点：从集合论到位运算，常见位运算技巧分类总结！

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        // 遍历每一位（从最低位到最高位）
        for (int i = 0; i < 31; i++) {
            int cnt1 = 0;
            // 统计数组中当前位为 1 的个数
            for (int x : nums) {
                cnt1 += x >> i & 1;
            }
            // 如果当前位为 1 的个数不小于 k，则在结果中将当前位置为 1
            if (cnt1 >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

7.找出字符串的可整除数组

题目链接：2575. 找出字符串的可整除数组

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

如果 word[0,…,i] 所表示的 数值 能被 m 整除，div[i] = 1
否则，div[i] = 0
返回 word 的可整除数组。

示例 1：

输入：word = “998244353”, m = 3

输出：[1,1,0,0,0,1,1,0,0]

解释：仅有 4 个前缀可以被 3 整除：“9”、“99”、“998244” 和 “9982443” 。

示例 2：

输入：word = “1010”, m = 10

输出：[0,1,0,1]

解释：仅有 2 个前缀可以被 10 整除：“10” 和 “1010” 。

提示：

1 <= n <= 10⁵

word.length == n

word 由数字 0 到 9 组成

1 <= m <= 10⁹

题解：
方法：模运算
        计算给定字符串的模 m 可被整除的前缀长度数组。通过从左到右遍历 word。

        设 a=k₁m+r₁, b=k₂m+r₂。

        那么 (a+b) mod m=(r₁+r₂) mod m=(a mod m+b mod m) mod m

        初始化 x=0，每遇到一个数字 d，就把 x 更新为 (10x+d) mod m。

class Solution {
    /**
     * 计算给定字符串的模 m 可被整除的前缀长度数组。
     * 从左到右计算每个前缀的模运算结果，并记录下能整除 m 的前缀长度。
     * @param word 给定的字符串
     * @param m 给定的模数
     * @return 每个前缀的模 m 可被整除的长度数组
     */
    public int[] divisibilityArray(String word, int m) {
        char[] s = word.toCharArray();
        int[] ans = new int[s.length]; // 用于存放结果的数组
        long x = 0; // 存放当前前缀的模 m 的结果
        for (int i = 0; i < s.length; i++) {
            x = (x * 10 + (s[i] - '0')) % m; // 从左到右依次计算前缀的模 m 结果
            if (x == 0) { // 如果当前前缀的模 m 结果为 0，则表示当前前缀可以被 m 整除
                ans[i] = 1; // 标记当前前缀长度为能被 m 整除的长度
            }
        }
        return ans; // 返回结果数组
    }
}

8.找出美丽数组的最小和

题目链接：2834. 找出美丽数组的最小和

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

• nums.length == n.
• nums 由两两互不相同的正整数组成。
• 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 10⁹ + 7。

示例 1：

输入：n = 2, target = 3

输出：4

解释：nums = [1,3] 是美丽数组。

• nums 的长度为 n = 2 。
• nums 由两两互不相同的正整数组成。
• 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。

可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3

输出：8

解释：

nums = [1,3,4] 是美丽数组。

• nums 的长度为 n = 3 。
• nums 由两两互不相同的正整数组成。
• 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。

可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1

输出：1

解释：nums = [1] 是美丽数组。

提示：

1 <= n <= 10⁹

1 <= target <= 10⁹

题解：
方法：O(1) 数学公式

知识点：O(1) 数学公式

class Solution {
    public int minimumPossibleSum(int n, int k) {
        long m = Math.min(k / 2, n);
        return (int) ((m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1_000_000_007);
    }
}

9.2386. 找出数组的第 K 大和

题目链接：2386. 找出数组的第 K 大和

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 0 。

示例 1：

输入：nums = [2,4,-2], k = 5

输出：2

解释：所有可能获得的子序列和列出如下，按递减顺序排列：

-6、4、4、2、2、0、0、-2

数组的第 5 大和是 2 。

示例 2：

输入：nums = [1,-2,3,4,-10,12], k = 16

输出：10

解释：数组的第 16 大和是 10 。

提示：

n == nums.length

1 <= n <= 10⁵

-109 <= nums[i] <= 10⁹

1 <= k <= min(2000, 2ⁿ)

题解：
        题目要计算 nums 中所有非负数的和，记作 sum。

        我们可以看到nums 的任意一个子序列的元素和，都等价于从 sum 中减去某些非负数 / 加上某些负数得到。因为减去非负数和加上负数都相当于减去 ∣nums[i]∣。所以sum 减去的数越小，nums 的子序列和就越大。

        现在要解决得是：

        把每个 nums[i] 取绝对值后，nums 的第 k 小的子序列和是多少？

方法：二分答案 + 爆搜

知识点：二分原理

知识点：子集型回溯

class Solution {
    public long kSum(int[] nums, int k) {
        long sum = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                sum += nums[i];
            } else {
                nums[i] = -nums[i];
            }
            right += nums[i];
        }
        Arrays.sort(nums);

        long left = -1;
        while (left + 1 < right) { // 开区间二分，原理见【前置知识】
            long mid = (left + right) / 2;
            cnt = k - 1; // 空子序列算一个
            dfs(0, mid, nums);
            if (cnt == 0) { // 找到 k 个元素和不超过 mid 的子序列
                right = mid;
            } else {
                left = mid;
            }
        }
        return sum - right;
    }

    private int cnt;

    // 反向递归，增加改成减少，这样可以少传一些参数
    private void dfs(int i, long s, int[] nums) {
        if (cnt == 0 || i == nums.length || s < nums[i]) {
            return;
        }
        cnt--;
        dfs(i + 1, s - nums[i], nums); // 选
        dfs(i + 1, s, nums); // 不选
    }
}

class Solution {
    public long kSum(int[] nums, int k) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                sum += nums[i];
            } else {
                nums[i] = -nums[i];
            }
        }
        Arrays.sort(nums);

        PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(a.getKey(), b.getKey()));
        pq.offer(new Pair<>(0L, 0)); // 空子序列
        while (--k > 0) {
            Pair<Long, Integer> p = pq.poll();
            long s = p.getKey();
            int i = p.getValue();
            if (i < nums.length) {
                // 在子序列的末尾添加 nums[i]
                pq.offer(new Pair<>(s + nums[i], i + 1)); // 下一个添加/替换的元素下标为 i+1
                if (i > 0) { // 替换子序列的末尾元素为 nums[i]
                    pq.offer(new Pair<>(s + nums[i] - nums[i - 1], i + 1));
                }
            }
        }
        return sum - pq.peek().getKey();
    }
}

10.猜数字游戏

题目链接：299. 猜数字游戏

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛），
有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 “xAyB” ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = “1807”, guess = “7810”

输出：“1A3B”

解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
“1807”

|
“7810”

示例 2：

输入：secret = “1123”, guess = “0111”

输出：“1A1B”

解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。

“1123”         “1123”

|         or             |
“0111”        “0111”

注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

提示：

1 <= secret.length, guess.length <= 1000

secret.length == guess.length

secret 和 guess 仅由数字组成

题解：
方法：模拟
        对 secret 和 guess 进行诸位比较，统计公牛数量 a 和奶牛数量 b。

        对于字符相同的位置，我们可以直接对 a 进行自增；对于字符不同的位置，使用哈希表进行分别统计 secret 和 guess 的词频，某个数字 x 在两者词频中的较小值，即为该数字对应的奶牛数量，统计所有数字 [0,9]的奶牛数量总和即为 b。

class Solution {
    public String getHint(String secret, String guess) {
        int n = secret.length();
        int a = 0, b = 0;
        int[] cnt1 = new int[10], cnt2 = new int[10];
        for (int i = 0; i < n; i++) {
            int c1 = secret.charAt(i) - '0', c2= guess.charAt(i) - '0';
            if (c1 == c2) {
                a++;
            } else {
                cnt1[c1]++;
                cnt2[c2]++;
            }
        }
        for (int i = 0; i < 10; i++) b += Math.min(cnt1[i], cnt2[i]);
        return a + "A" + b + "B";
    }
}

下接：【题解】—— LeetCode一周小结11