1061.按字典序排列最小的等效字符串

目标

给出长度相同的两个字符串s1 和 s2 ,还有一个字符串 baseStr 。

其中 s1[i] 和 s2[i] 是一组等价字符。

  • 举个例子,如果 s1 = "abc" 且 s2 = "cde",那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等价字符遵循任何等价关系的一般规则:

  • 自反性 :'a' == 'a'
  • 对称性 :'a' == 'b' 则必定有 'b' == 'a'
  • 传递性 :'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如, s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样,那么 baseStr = "eed" , "acd" 或 "aab",这三个字符串都是等价的,而 "aab" 是 baseStr 的按字典序最小的等价字符串

利用 s1 和 s2 的等价信息,找出并返回 baseStr 的按字典序排列最小的等价字符串。

示例 1:

输入:s1 = "parker", s2 = "morris", baseStr = "parser"
输出:"makkek"
解释:根据 A 和 B 中的等价信息,我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的,并按字典序排列。所以答案是 "makkek"。

示例 2:

输入:s1 = "hello", s2 = "world", baseStr = "hold"
输出:"hdld"
解释:根据 A 和 B 中的等价信息,我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd',最后答案为 "hdld"。

示例 3:

输入:s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出:"aauaaaaada"
解释:我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组,因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a',最后答案为 "aauaaaaada"。

说明:

  • 1 <= s1.length, s2.length, baseStr <= 1000
  • s1.length == s2.length
  • 字符串s1, s2, and baseStr 仅由从 'a' 到 'z' 的小写英文字母组成。

思路

定义 s1[i]s2[i] 是等价字符,返回 baseStr 字典序最小的等价字符串。

可以使用并查集,用字典序小的字符代表等价字符,然后逐个替换 baseStr 即可。

代码


/**
 * @date 2025-06-05 0:15
 */
public class SmallestEquivalentString1061 {

    public class UnionFind {
        private int[] father;

        public UnionFind() {
            this.father = new int[26];
            Arrays.setAll(father, i -> i);
        }

        public void merge(int a, int b) {
            int x = find(a);
            int y = find(b);
            if (x == y) {
                return;
            }
            if (x < y) {
                father[y] = x;
            } else {
                father[x] = y;
            }
        }

        public int find(int a) {
            if (father[a] != a) {
                father[a] = find(father[a]);
            }
            return father[a];
        }
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int n = s1.length();
        UnionFind uf = new UnionFind();
        for (int i = 0; i < n; i++) {
            uf.merge(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }
        StringBuilder sb = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            sb.append((char) ('a' + uf.find(c - 'a')));
        }
        return sb.toString();
    }

}

性能

3403.从盒子中找出字典序最大的字符串I

目标

给你一个字符串 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];
    }

}

性能

1298.你能从盒子里获得的最大糖果数

目标

给你 n 个盒子,每个盒子的格式为 [status, candies, keys, containedBoxes] ,其中:

  • 状态字 status[i]:整数,如果 box[i] 是开的,那么是 1 ,否则是 0 。
  • 糖果数 candies[i]: 整数,表示 box[i] 中糖果的数目。
  • 钥匙 keys[i]:数组,表示你打开 box[i] 后,可以得到一些盒子的钥匙,每个元素分别为该钥匙对应盒子的下标。
  • 内含的盒子 containedBoxes[i]:整数,表示放在 box[i] 里的盒子所对应的下标。

给你一个 initialBoxes 数组,表示你现在得到的盒子,你可以获得里面的糖果,也可以用盒子里的钥匙打开新的盒子,还可以继续探索从这个盒子里找到的其他盒子。

请你按照上述规则,返回可以获得糖果的 最大数目 。

示例 1:

输入:status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
输出:16
解释:
一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。
盒子 1 目前状态是关闭的,而且你还没有对应它的钥匙。所以你将会打开盒子 2 ,并得到里面的 4 个糖果和盒子 1 的钥匙。
在盒子 1 中,你会获得 5 个糖果和盒子 3 ,但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。
你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。

示例 2:

输入:status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
输出:6
解释:
你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。
打开这些盒子,你将获得所有盒子的糖果,所以总糖果数为 6 个。

示例 3:

输入:status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1]
输出:1

示例 4:

输入:status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = []
输出:0

示例 5:

输入:status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
输出:7

说明:

  • 1 <= status.length <= 1000
  • status.length == candies.length == keys.length == containedBoxes.length == n
  • status[i] 要么是 0 要么是 1 。
  • 1 <= candies[i] <= 1000
  • 0 <= keys[i].length <= status.length
  • 0 <= keys[i][j] < status.length
  • keys[i] 中的值都是互不相同的。
  • 0 <= containedBoxes[i].length <= status.length
  • 0 <= containedBoxes[i][j] < status.length
  • containedBoxes[i] 中的值都是互不相同的。
  • 每个盒子最多被一个盒子包含。
  • 0 <= initialBoxes.length <= status.length
  • 0 <= initialBoxes[i] < status.length

思路

开始时有一些盒子 initialBoxes 元素值表示盒子下标,盒子的状态用 status 数组表示,0 表示盒子被锁住,1 表示盒子是打开的。盒子中装有糖果、也可能装有其它盒子,或者盒子的钥匙。求能够获得的最大糖果数。

bfs 使用优先队列对盒子状态排序,优先取开着的盒子。将开着的盒子中的盒子放入队列,并且用盒子中的钥匙修改队列中的盒子状态。记录已经开过的盒子,避免重复计数。

代码


/**
 * @date 2025-06-03 20:30
 */
public class MaxCandies1298 {

    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int n = status.length;
        int[][] boxes = new int[n][2];
        for (int i = 0; i < n; i++) {
            boxes[i] = new int[]{i, status[i]};
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int initialBox : initialBoxes) {
            q.offer(boxes[initialBox]);
        }
        int res = 0;
        Set<Integer> visited = new HashSet<>();
        while (!q.isEmpty() && q.peek()[1] == 1) {
            while (!q.isEmpty() && q.peek()[1] == 1) {
                int i = q.poll()[0];
                visited.add(i);
                res += candies[i];
                for (int j : keys[i]) {
                    boxes[j][1] = 1;
                }
                for (int j : containedBoxes[i]) {
                    if (visited.contains(j)) {
                        continue;
                    }
                    q.offer(boxes[j]);
                }
            }
        }
        return res;
    }
}

性能

135.分发糖果

目标

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。

示例 1:

输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2:

输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。

说明:

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4

思路

n 个孩子站成一排,ratings 表示每个孩子的评分。现在需要给孩子分发糖果,要求每个孩子至少分配一个糖果,并且相邻的两个孩子,评分高的孩子分得的糖果大于评分低的孩子分得的糖果,返回需要准备的最少糖果数目。

官网题解提供了一种常数空间复杂度的写法,记录评分严格递增与严格递减序列长度:

  • 当处于严格递增序列时,分配的糖果比前面的多一个即可
  • 如果评分相同,则分配一个糖果并重置序列长度
  • 当处于严格递减序列时,分配递减序列长度个糖果,相当于递增序列的逆过程
  • 需要特殊处理递增序列与递减序列长度相同的情况

看下面的例子:

评分 4 5 4 3 2 1,
    a b c d e f
    1 2 1
当处理到 c 时,处于下降序列,我们给他分配 1 个糖果
    1 3 2 1
当处理到 d 时,仍处于下降序列,需要给 c 多分配一个糖果,即 2 个,发现这时与 b 分配的相同,不满足要求,需要给 b 也多分配一个,共 3 个
    1 4 3 2 1
当处理到 e 时,仍处于下降序列,需要给 b c d 多分配一个,共 4 个
    1 5 4 3 2 1
当处理到 f 时,仍处于下降序列,需要给 b c d e 多分配一个糖果,共 5 个

相当于往递减序列的头部插入递减序列长度个糖果,视为反向的递增,当递增序列与递减序列长度相同时需要特殊处理。

代码


/**
 * @date 2024-12-11 9:18
 */
public class Candy135 {

    public int candy_v3(int[] ratings) {
        int n = ratings.length;
        int increase = 1;
        int decrease = 0;
        int res = 1;
        int prev = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                prev = ratings[i] == ratings[i - 1] ? 1 : prev + 1;
                res += prev;
                increase = prev;
                decrease = 0;
            } else {
                decrease++;
                if (decrease == increase) {
                    decrease++;
                }
                res += decrease;
                prev = 1;
            }
        }
        return res;
    }

}

性能

2929.给小朋友们分糖果II

目标

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友,确保没有任何小朋友得到超过 limit 颗糖果,请你返回满足此条件下的 总方案数 。

示例 1:

输入:n = 5, limit = 2
输出:3
解释:总共有 3 种方法分配 5 颗糖果,且每位小朋友的糖果数不超过 2 :(1, 2, 2) ,(2, 1, 2) 和 (2, 2, 1) 。

示例 2:

输入:n = 3, limit = 3
输出:10
解释:总共有 10 种方法分配 3 颗糖果,且每位小朋友的糖果数不超过 3 :(0, 0, 3) ,(0, 1, 2) ,(0, 2, 1) ,(0, 3, 0) ,(1, 0, 2) ,(1, 1, 1) ,(1, 2, 0) ,(2, 0, 1) ,(2, 1, 0) 和 (3, 0, 0) 。

说明:

  • 1 <= n <= 10^6
  • 1 <= limit <= 10^6

思路

n 颗糖果分给 3 位小朋友,每个小朋友分到的糖果数量不超过 limit,求分配的方案数。注意,糖果必须分完,比如示例 1,不存在分得糖果数量为 0 的情况。

  • 第一个小朋友分到的糖果数为 a ∈ [0, Math.min(n, limit)]
  • 第二个小朋友分到的糖果数为 b ∈ [Math.max(0, n - a - limit), Math.min(n - a, limit)]
  • 第三个小朋友分到的糖果数为 n - a - b

代码


/**
 * @date 2025-06-01 21:49
 */
public class DistributeCandies2929 {

    public long distributeCandies(int n, int limit) {
        long res = 0L;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            res += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
        }
        return res;
    }
}

性能