标签： bfs

目标

我们把玻璃杯摆成金字塔的形状，其中 第一层 有 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];
    }

}

性能

目标

给你一个整数 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;
    }

}

性能