标签： medium

目标

现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

排名规则如下：

• 参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
• 如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。

给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。

请你返回能表示按排名系统 排序后 的所有团队排名的字符串。

示例 1：

输入：votes = ["ABC","ACB","ABC","ACB","ACB"]
输出："ACB"
解释：
A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
B 队获得两票「排位第二」，三票「排位第三」。
C 队获得三票「排位第二」，两票「排位第三」。
由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。

示例 2：

输入：votes = ["WXYZ","XYZW"]
输出："XWYZ"
解释：
X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W 没有获得「排位第二」。

示例 3：

输入：votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
输出："ZMNAGUEDSJYLBOPHRQICWFXTVK"
解释：只有一个投票者，所以排名完全按照他的意愿。

说明：

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length for 0 <= i, j < votes.length
• votes[i][j] 是英文 大写 字母
• votes[i] 中的所有字母都是唯一的
• votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中，其中 1 <= j < votes.length

思路

投票人对所有团队的排名用一个字符串 votes[i] 表示，团队的先后顺序就代表排名。根据所有投票人的排名对团队排名，排名第一次数最多的为第一名，如果相同则根据排名第二的次数排名，以此类推，如果最终都相同，则以团队名在字母表的先后顺序排名。

考虑自定义数据结构，维护团队在每一个名次的得票数，然后使用优先队列自定义排序。

代码

/**
 * @date 2024-12-29 18:36
 */
public class RankTeams1366 {

    public static class Rank {
        public int name;
        public int[] cnt;

        public Rank(int name, int[] cnt) {
            this.name = name;
            this.cnt = cnt;
        }
    }

    public String rankTeams(String[] votes) {
        int n = votes[0].length();
        PriorityQueue<Rank> q = new PriorityQueue<>((a, b) -> {
            int[] cnta = a.cnt;
            int[] cntb = b.cnt;
            int i = 0;
            while (i < n && cnta[i] == cntb[i]) {
                i++;
            }
            if (i == n) {
                return a.name - b.name;
            }
            return cntb[i] - cnta[i];
        });

        int[][] cnt = new int[26][n];
        for (String vote : votes) {
            for (int i = 0; i < vote.length(); i++) {
                int c = vote.charAt(i) - 'A';
                cnt[c][i]++;
            }
        }
        for (int i = 0; i < 26; i++) {
            q.offer(new Rank(i, cnt[i]));
        }
        char[] chars = new char[n];
        int i = 0;
        while (i < n) {
            chars[i++] = (char) (q.poll().name + (int) 'A');
        }
        return new String(chars);
    }

}

性能

目标

有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。

给你整数 m ，n 和两个数组：

• horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
• verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。

一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：

1. 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
2. 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。

每次操作后，这块蛋糕都被切成两个独立的小蛋糕。

每次操作的开销都为最开始对应切割线的开销，并且不会改变。

请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。

示例 1：

输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出：13
解释：
沿着垂直线 0 切开蛋糕，开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。

示例 2：

输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出：15
解释：
沿着水平线 0 切开蛋糕，开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
总开销为 7 + 4 + 4 = 15 。

说明：

• 1 <= m, n <= 20
• horizontalCut.length == m - 1
• verticalCut.length == n - 1
• 1 <= horizontalCut[i], verticalCut[i] <= 10^3

思路

有一块 m x n 的蛋糕，horizontalCut[i] 表示水平切第 i 行的开销，verticalCut[i] 表示垂直切第 i 列的开销。求将蛋糕切成 1 x 1 小块的最小代价。

需要注意每次切的蛋糕必须是整块的，并不能将几块蛋糕排到一起切。

我们应该先沿着代价最大的位置切吗？比如大小为 2 x 100 的蛋糕，水平切的代价为 99，垂直切每一列的代价为 100。先切每一列代价为 99 * 100，然后对切开的 100 块水平切 100 次，代价为 100 * 99，总代价为 2 * 99 * 100。如果先水平切一次，代价为 99。然后需要垂直切 2 * 99 次，代价为 2 * 99 * 100，总代价为 99 + 2 * 99 * 100。这种贪心策略应该是可行的，因为每切一次块数会增加，现在不切代价大的，后面再切的时候代价会增加。

选择沿某一水平或垂直线切割时，需要记录水平 和 垂直方向蛋糕块的数量，用来计算代价。每切一次，横向与纵向的蛋糕块就会增加一个。

刚开始不确定能否使用贪心策略，考虑如何表示哪些切过了，哪些没切，卡了很久。关键点是如何将问题抽象建模，使用分治思想，不要面向过程。每切一次之后，问题转化为切剩余蛋糕的子问题。我们可以使用记忆化搜索解空间，求出最小值。

代码

/**
 * @date 2024-12-25 10:41
 */
public class MinimumCost3218 {

    public int minimumCost_v1(int m, int n, int[] horizontalCut, int[] verticalCut) {
        int horizontalCutPart = 1;
        int verticalCutPart = 1;
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        int h = horizontalCut.length - 1;
        int v = verticalCut.length - 1;
        int res = 0;
        while (h >= 0 || v >= 0) {
            if (h < 0){
                res += horizontalCutPart * verticalCut[v];
                v--;
                continue;
            }
            if (v < 0){
                res += verticalCutPart * horizontalCut[h];
                h--;
                continue;
            }
            if (horizontalCut[h] > verticalCut[v]) {
                res += verticalCutPart * horizontalCut[h];
                horizontalCutPart++;
                h--;
            } else if (horizontalCut[h] <= verticalCut[v]) {
                res += horizontalCutPart * verticalCut[v];
                verticalCutPart++;
                v--;
            }
        }

        return res;
    }

    int[] rowCost;
    int[] colCost;
    int[][][][] mem;

    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        this.rowCost = horizontalCut;
        this.colCost = verticalCut;
        mem = new int[m + 1][m + 1][n + 1][n + 1];
        // rowStart rowEnd colStart colEnd 表示蛋糕的边界
        //   0   1   2   3   4   5  ... n
        // 0  ———————————————————
        //   |   |   |   |   |   |
        // 1  ———————————————————
        //   |   |   |   |   |   |
        // 2  ———————————————————
        //   |   |   |   |   |   |
        // 3 ———————————————————
        //   |   |   |   |   |   |
        // 4 ———————————————————
        //   |   |   |   |   |   |
        // 5  ———————————————————
        // ...
        // m
        return dfs(0, m, 0, n);
    }

    public int dfs(int rowStart, int rowEnd, int colStart, int colEnd) {
        if (rowEnd - rowStart == 1 && colEnd - colStart == 1) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int i = rowStart + 1; i < rowEnd; i++) {
            if (mem[rowStart][i][colStart][colEnd] == 0) {
                mem[rowStart][i][colStart][colEnd] = dfs(rowStart, i, colStart, colEnd);
            }
            if (mem[i][rowEnd][colStart][colEnd] == 0) {
                mem[i][rowEnd][colStart][colEnd] = dfs(i, rowEnd, colStart, colEnd);
            }
            res = Math.min(res, rowCost[i - 1] + mem[rowStart][i][colStart][colEnd] + mem[i][rowEnd][colStart][colEnd]);
        }
        for (int i = colStart + 1; i < colEnd; i++) {
            if (mem[rowStart][rowEnd][colStart][i] == 0) {
                mem[rowStart][rowEnd][colStart][i] = dfs(rowStart, rowEnd, colStart, i);
            }
            if (mem[rowStart][rowEnd][i][colEnd] == 0) {
                mem[rowStart][rowEnd][i][colEnd] = dfs(rowStart, rowEnd, i, colEnd);
            }
            res = Math.min(res, colCost[i - 1] + mem[rowStart][rowEnd][colStart][i] + mem[rowStart][rowEnd][i][colEnd]);
        }
        return res;
    }

}

性能

目标

有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。

给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。

示例 1：

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

示例 2：

输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。

说明：

• apples.length == n
• days.length == n
• 1 <= n <= 2 * 10^4
• 0 <= apples[i], days[i] <= 2 * 10^4
• 只有在 apples[i] = 0 时，days[i] = 0 才成立

思路

有一颗特殊的苹果树，第 i 天会结出 apples[i] 个果子，这些果子将在第 i + days[i] 天腐烂。求每天吃一个未腐烂的苹果，最多可以吃几个。

我们的贪心策略是优先吃快腐烂的苹果，首先将当天结果的苹果个数以及腐烂时间放入最小堆，获取堆顶最近要腐烂的苹果，判断是否已经腐烂，如果没有将苹果个数减一，如果数量减为 0 或者已经腐烂，将其从堆中移出。

代码

/**
 * @date 2024-12-24 10:35
 */
public class EatenApples1705 {

    public int eatenApples_v2(int[] apples, int[] days) {
        int n = apples.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int res = 0;
        for (int day = 0; day < n || !q.isEmpty(); day++) {
            if (day < n && apples[day] > 0){
                q.offer(new int[]{apples[day], day + days[day]});
            }
            while (!q.isEmpty()) {
                int[] applesInfo = q.peek();
                if (applesInfo[0] == 0 || applesInfo[1] == day) {
                    q.poll();
                    continue;
                }
                if (applesInfo[1] > day && applesInfo[0] > 0) {
                    applesInfo[0]--;
                    res++;
                    break;
                }
            }
        }
        return res;
    }

}

性能

目标

在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。

当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。

示例：

输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：
ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。

说明：

• 1 <= N <= 10^9
• 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
• 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。

思路

有一排座位编号为 0 ~ N - 1，当学生进入考场后可以选择距离其它同学最远的位置坐下。实现 ExamRoom 类，提供 seat() 方法返回合法的座位，以及 leave() 方法允许学生离开考场。

显然下一个进入考场的同学应该坐在当前相邻座位最大距离的中间位置，考虑到允许离开座位，那么端点的座位离开的情况也要考虑。我们需要提供一个类，快速地查询相邻学生座位的最大值，并且支持座位的删减。

使用最大堆，堆中元素为 [距离左边相邻同学的距离，座位编号]，根据 距离/2 排序，除以 2 是为了消除左右距离不等造成的影响。例如 0 4 9 这种情况，区间长度一个是 4，一个是 5，但是 2 ~ 4，4 ~ 6 的距离相同，应该取编号最小的。

计算下一个座位时，需要考虑三种情况：

• 如果是第一个同学进入考场，直接坐在 0 号位置
• 如果只有一个同学在考场，下一个同学需要坐在距离该位置距离最大的端点
• 如果有大于两个同学在考场，我们可以选择两个同学中间的位置，或者两端的位置

如何处理离开考场的情况？如果离开的同学左右位置有人，需要进行区间合并，将合并后的区间放入堆中，并且删除堆中左右两侧区间。但是在堆中查找元素的时间复杂度是 O(n)，由于最多总共调用 10^4 次，leave 最多调用 k = 5 * 10^3 次，堆中元素个数随着调用减少，总复杂度为 O(k^2) 可能勉强通过。

为了快速访问左右的相邻座位以便区间合并以及左右端点的距离判断，使用 TreeSet 记录同学的座位编号。我们可以将删除操作延迟到获取座位的时候处理。

代码

/**
 * @date 2024-12-23 14:28
 */
public class ExamRoom {

    private TreeSet<Integer> occupied;
    // [distance, no]
    private PriorityQueue<int[]> q;
    private int n;

    public ExamRoom(int n) {
        this.n = n;
        occupied = new TreeSet<>();
        q = new PriorityQueue<>((a, b) -> {
            int compare = b[0] / 2 - a[0] / 2;
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
    }

    public int seat() {
        if (occupied.size() == 0) {
            occupied.add(0);
            return 0;
        } else if (occupied.size() == 1) {
            Integer no = occupied.first();
            int distance = n - 1 - no;
            if (distance > no) {
                q.offer(new int[]{distance, n - 1});
                occupied.add(n - 1);
                return n - 1;
            } else {
                q.offer(new int[]{no, no});
                occupied.add(0);
                return 0;
            }
        } else {
            while (true) {
                int first = occupied.first();
                int last = occupied.last();
                int rd = n - 1 - last;
                int[] dn = q.peek();
                int r = dn[1];
                int l = r - dn[0];
                // 注意第三个条件，可以防止离开座位后又有同学坐下，由于延迟删除，距离并未更新导致的计算错误
                if (!occupied.contains(l) || !occupied.contains(r) || occupied.higher(l) != r) {
                    q.poll();
                    continue;
                }
                int distance = dn[0] / 2;
                if (distance <= first || distance < rd) {
                    if (first < rd) {
                        q.offer(new int[]{rd, n - 1});
                        occupied.add(n - 1);
                        return n - 1;
                    } else {
                        q.offer(new int[]{l, l});
                        occupied.add(0);
                        return 0;
                    }
                } else {
                    q.poll();
                    int m = l + (r - l) / 2;
                    occupied.add(m);
                    q.offer(new int[]{m - l, m});
                    q.offer(new int[]{r - m, r});
                    return m;
                }
            }
        }
    }

    public void leave(int p) {
        if (p != occupied.first() && p != occupied.last()) {
            int l = occupied.lower(p);
            int r = occupied.higher(p);
            q.offer(new int[]{r - l, r});
        }
        occupied.remove(p);
    }
}

性能

目标

我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：

• 如果 x 是偶数，那么 x = x / 2
• 如果 x 是奇数，那么 x = 3 * x + 1

比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。

示例 1：

输入：lo = 12, hi = 15, k = 2
输出：13
解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。

示例 2：

输入：lo = 7, hi = 11, k = 4
输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。

说明：

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

思路

定义整数 x 的权重为 将其变为 1 的操作次数，根据整数的奇偶性，可以执行不同的操作：

• x 为偶数，x -> x / 2
• x 为奇数，x -> 3 * x + 1

返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

根据题意模拟计算出每个数字的权重，将它和数字一起保存起来，然后按照权重、数值排序即可。

可以预处理 1 ~ 1000 内的所有权重，保存中间结果减少重复计算。

看到题目时我们都会有这样的疑问，如何证明 x 最终都会回到 1？有网友提到题目中的操作与考拉兹猜想（Collatz conjecture）的操作一样，由于操作过程与冰雹的形成和下落过程相似，因此也叫冰雹猜想。

代码

/**
 * @date 2024-12-22 16:20
 */
public class GetKth1387 {

    public int getKth(int lo, int hi, int k) {
        int n = hi - lo + 1;
        int[][] w = new int[n][2];
        int c = 0;
        for (int i = lo; i <= hi; i++) {
            w[c++] = new int[]{getWeight(i), i};
        }
        Arrays.sort(w, (a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
        return w[k - 1][1];
    }

    public int getWeight(int x) {
        int cnt = 0;
        while (x > 1) {
            if (x % 2 == 0) {
                x >>= 1;
            } else {
                x = 3 * x + 1;
            }
            cnt++;
        }
        return cnt;
    }
}

性能

目标

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的 最小 可能长度。

同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。

示例 1：

输入：s = "abba"
输出：2
解释：
一个可能的字符串 t 为 "ba" 。

示例 2：

输入：s = "cdef"
输出：4
解释：
一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。

说明：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

思路

字符串 s 由某个字符串 t 以及若干（可以为0） t 的同位字符串 连接 而成，返回字符串 t 最小的可能长度。同位字符串指构成字符串的字符分布完全相同，换句话说就是不同字符的种类与数量完全相同。

特别注意该题与字串的顺序有关，比如 aabb 并不能由 ab 拼接而来，它的同位字符串是 ab 和 ba，只能构成 abba abab baab baba。

注意到子串的长度 length 一定能够被 s.length 整除。将字符串截成 k 个长度为 length 的子字符串，通过计算这些子字符串的字母个数，判断是否是同位字符串，从小到大遍历因数 length，取最小的即可。

代码

/**
 * @date 2024-12-20 9:08
 */
public class MinAnagramLength3138 {

    public int minAnagramLength_v1(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        Map<Integer, int[]> possibleLength = new LinkedHashMap<>();
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            cnt[c]++;
            int length = i + 1;
            if (n % length == 0) {
                int[] composition = new int[26];
                System.arraycopy(cnt, 0, composition, 0, 26);
                possibleLength.put(length, composition);
            }
        }
        char[] chars = s.toCharArray();
        for (Map.Entry<Integer, int[]> entry : possibleLength.entrySet()) {
            int length = entry.getKey();
            if (length == n) {
                return n;
            }
            int[] composition = entry.getValue();
            int loop = n / length;
            boolean find = true;
            here:
            for (int i = 0; i < loop; i++) {
                int[] tmp = new int[26];
                System.arraycopy(composition, 0, tmp, 0, 26);
                for (int j = 0; j < length; j++) {
                    int c = chars[i * length + j] - 'a';
                    tmp[c]--;
                    if (tmp[c] < 0) {
                        find = false;
                        break here;
                    }
                }
            }
            if (find) {
                return length;
            }
        }
        return n;
    }

}

性能