标签： bfs

目标

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

• i + minJump <= j <= min(i + maxJump, s.length - 1) 且
• s[j] == '0'.

如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

示例 1：

输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

示例 2：

输入：s = "01101110", minJump = 2, maxJump = 3
输出：false

说明：

• 2 <= s.length <= 10^5
• s[i] 要么是 '0' ，要么是 '1'
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

思路

有一个长度为 n 的二进制字符串 s，开始在位置 0 且该位置的值为 0，从该位置出发每次可以跳跃到 [i + minJump, min(i + maxJump, n - 1)] 中元素值为 0 的位置 j，判断能否到达 n - 1。

定义 dp[i] 表示能否到达下标 i，如果 dp[i] = true，标记 [Math.max(j, i + minJump), Math.min(n - 1, i + maxJump)] 中元素值为 '0' 的下标，其中 j 表示之前可覆盖的最大下标 + 1。

代码

/**
 * @date 2026-05-25 8:50
 */
public class CanReach1871 {

    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        char[] chars = s.toCharArray();
        if (chars[n - 1] != '0') {
            return false;
        }
        boolean[] dp = new boolean[n];
        dp[0] = true;
        int j = 1;
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                for (j = Math.max(j, i + minJump); j <= Math.min(n - 1, i + maxJump); j++) {
                    dp[j] = chars[j] == '0';
                }
            }
        }
        return dp[n - 1];
    }

}

性能

目标

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

你从下标 0 开始，目标是到达下标 n - 1。

在任何下标 i 处，你可以执行以下操作之一：

• 移动到相邻格子：跳到下标 i + 1 或 i - 1，如果该下标在边界内。
• 质数传送：如果 nums[i] 是一个质数 p，你可以立即跳到任何满足 nums[j] % p == 0 的下标 j 处，且下标 j != i 。

返回到达下标 n - 1 所需的 最少 跳跃次数。

质数 是一个大于 1 的自然数，只有两个因子，1 和它本身。

示例 1:

输入: nums = [1,2,4,6]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 1 跳一步。
在下标 i = 1，nums[1] = 2 是一个质数。因此，我们传送到索引 i = 3，因为 nums[3] = 6 可以被 2 整除。
因此，答案是 2。

示例 2:

输入: nums = [2,3,4,7,9]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 i = 1 跳一步。
在下标 i = 1，nums[1] = 3 是一个质数。因此，我们传送到下标 i = 4，因为 nums[4] = 9 可以被 3 整除。
因此，答案是 2。

示例 3:

输入: nums = [4,6,5,8]
输出: 3
解释:
由于无法进行传送，我们通过 0 → 1 → 2 → 3 移动。因此，答案是 3。

说明:

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 10^6

思路

有一个数组 nums，从下标 0 开始移动，目标是到达下标 n - 1。每次移动可以移动到相邻的位置，如果 nums[i] 是质数，可以直接移动到满足 nums[j] % nums[i] == 0 的位置。返回最少移动次数。

枚举 2 ~ MAX，为每一个数记录质因子，得到哈希表 (num，primeFactorList)，枚举数组中的元素，获取 primeFactorList，为其中的每一个质数建立一个跳转列表 jumpIndexList，将当前下标加进去。从 0 开始 bfs，记录跳转次数，直到到达下标 n - 1。

代码

/**
 * @date 2026-05-08 16:55
 */
public class MinJumps3629 {

    public static final int MAX = 1000000;
    public static Map<Integer, List<Integer>> primeFactorMap = new HashMap<>();

    static {
        primeFactorMap.computeIfAbsent(1, k -> new ArrayList<>());
        for (int i = 2; i <= MAX; i++) {
            if (primeFactorMap.get(i) == null) {
                for (int j = i; j <= MAX; j += i) {
                    primeFactorMap.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> jumpIndexList = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> primeFactors = primeFactorMap.get(nums[i]);
            for (Integer prime : primeFactors) {
                jumpIndexList.computeIfAbsent(prime, k -> new ArrayList<>()).add(i);
            }
        }
        boolean[] visited = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int res = 0;
        here:
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer index = q.poll();
                if (visited[index]) {
                    continue;
                }
                visited[index] = true;
                if (index == n - 1) {
                    break here;
                }
                int next = index + 1;
                int prev = index - 1;
                if (next < n) {
                    q.offer(next);
                }
                if (prev >= 0) {
                    q.offer(prev);
                }
                if (jumpIndexList.get(nums[index]) != null) {
                    q.addAll(jumpIndexList.get(nums[index]));
                    jumpIndexList.get(nums[index]).clear();
                }
            }
            res++;
        }
        return res;
    }

}

性能

目标

我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）

例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。

现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从0开始）。

示例 1:

输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.00000
解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。

示例 2:

输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1
输出: 0.50000
解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。

示例 3:

输入: poured = 100000009, query_row = 33, query_glass = 17
输出: 1.00000

说明:

• 0 <= poured <= 10^9
• 0 <= query_glass <= query_row < 100

思路

将玻璃杯摆成金字塔，第一层 1 个杯子，第二层 2 个杯子，依次类推。持续向第一层第一杯倒入 poured 杯香槟，当杯子满了之后，会等流量的流向左右两个玻璃杯，返回 query_row 行（从 0 开始计数），第 query_glass 杯（从 0 开始）中的香槟与容积的比例。

模拟香槟左右的流量即可。第 query_row 行有 query_row + 1 个杯子，初始化流量数组 vol，比如，总共倾倒 poured 杯，如果 vol[0] > 1，多余的流量会从左右两侧流下，vol[1] = (vol[0] - 1)/2，vol[0] = (vol[0] - 1)/2，依次类推，直到查询的杯子。

注意由于没有对流量数组分层，需要从后向前遍历才能保证数据更新的正确性。

代码

/**
 * @date 2026-02-25 15:06
 */
public class ChampagneTower799 {

    public double champagneTower(int poured, int query_row, int query_glass) {
        double[] vol = new double[query_row + 1];
        vol[0] = poured;
        for (int i = 0; i < query_row; i++) {
            for (int j = i; j >= 0; j--) {
                if (vol[j] > 1) {
                    vol[j]--;
                    double half = vol[j] / 2.0;
                    vol[j + 1] += half;
                    vol[j] = half;
                } else {
                    vol[j] = 0.0;
                }
            }
        }
        return Math.min(vol[query_glass], 1.0);
    }

}

性能

目标

给你一个字符串 word 和一个整数 numFriends。

Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：

• word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
• 所有分割出的字符串都会被放入一个盒子中。

在所有回合结束后，找出盒子中 字典序最大的 字符串。

示例 1：

输入: word = "dbca", numFriends = 2
输出: "dbc"
解释: 
所有可能的分割方式为：
"d" 和 "bca"。
"db" 和 "ca"。
"dbc" 和 "a"。

示例 2：

输入: word = "gggg", numFriends = 4
输出: "g"
解释: 
唯一可能的分割方式为："g", "g", "g", 和 "g"。

提示:

• 1 <= word.length <= 5 * 10^3
• word 仅由小写英文字母组成。
• 1 <= numFriends <= word.length

思路

将 word 划分为 numFriends 个非空子串，求字典序最大的子串。

找字典序最大的首字母，如果存在多个需要比较后面字符的字典序，还要保证能够划分成非空子串。

先找到字符串中字典序最大的字符集合作为起点，将其后面的字符放入优先队列 [char, index]，根据字符从大到小排序，取队首连续相同的字符，将其后一个字符放到下一轮处理。

也可以不用手动逐个比较字符，枚举字典序最大的字符作为左端点，然后尽可能地扩展字符串长度 n - numFriends + 1，将结果收集后排序即可。

代码

/**
 * @date 2025-06-04 9:19
 */
public class AnswerString3403 {

    public String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }
        int n = word.length();
        List<Integer>[] chars = new ArrayList[26];
        Arrays.setAll(chars, x -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            char c = word.charAt(i);
            chars[c - 'a'].add(i);
        }
        int l = n - numFriends + 1;
        String[] strs = null;
        for (int i = 25; i >= 0; i--) {
            if (chars[i].size() > 0) {
                strs = new String[chars[i].size()];
                for (int j = 0; j < chars[i].size(); j++) {
                    int index = chars[i].get(j);
                    strs[j] = word.substring(index, Math.min(index + l, n));
                }
                break;
            }
        }
        Arrays.sort(strs);
        return strs[strs.length - 1];
    }

}

性能