T1 5772. 检查某单词是否等于两单词之和

题目

字母的 字母值 取决于字母在字母表中的位置，从 0 开始 计数。即，‘a’ -> 0、‘b’ -> 1、‘c’ -> 2，以此类推。
对某个由小写字母组成的字符串 s 而言，其 数值 就等于将 s 中每个字母的 字母值 按顺序 连接 并 转换 成对应整数。

  • 例如，s = “acb” ，依次连接每个字母的字母值可以得到 “021” ，转换为整数得到 21 。
    给你三个字符串 firstWord、secondWord 和 targetWord ，每个字符串都由从 ‘a’ 到 ‘j’ （含 ‘a’ 和 ‘j’ ）的小写英文字母组成。
    如果 firstWord 和 secondWord 的 数值之和 等于 targetWord 的数值，返回 true ；否则，返回 false 。

示例 1：
输入：firstWord = “acb”, secondWord = “cba”, targetWord = “cdb”
输出：true
解释：
firstWord 的数值为 “acb” -> “021” -> 21
secondWord 的数值为 “cba” -> “210” -> 210
targetWord 的数值为 “cdb” -> “231” -> 231
由于 21 + 210 == 231 ，返回 true

示例 2：
输入：firstWord = “aaa”, secondWord = “a”, targetWord = “aab”
输出：false
解释：
firstWord 的数值为 “aaa” -> “000” -> 0
secondWord 的数值为 “a” -> “0” -> 0
targetWord 的数值为 “aab” -> “001” -> 1
由于 0 + 0 != 1 ，返回 false

提示：
1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord、secondWord 和 targetWord 仅由从 ‘a’ 到 ‘j’ （含 ‘a’ 和 ‘j’ ）的小写英文字母组成。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSumEqual(String firstWord, String secondWord, String targetWord){
        int a = getValue(firstWord);
        int b = getValue(secondWord);
        int c = getValue(targetWord);
        return a + b == c;
    }
    public int getValue(String str){
        int len = str.length();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++){
            sb.append(Integer.toString((int)(str.charAt(i) - 'a')));
        }
        return Integer.parseInt(sb.toString());
    }
}

T2 5773. 插入后的最大值

题目

给你一个非常大的整数 n 和一个整数数字 x ，大整数 n 用一个字符串表示。n 中每一位数字和数字 x 都处于闭区间 [1,9][1, 9] 中，且 n 可能表示一个 负数 。
你打算通过在 n 的十进制表示的任意位置插入 x 来 最大化 n 的 数值 ​​​​​​。但 不能 在负号的左边插入 x 。

  • 例如，如果 n = 73 且 x = 6 ，那么最佳方案是将 6 插入 7 和 3 之间，使 n = 763 。
  • 如果 n = -55 且 x = 2 ，那么最佳方案是将 2 插在第一个 5 之前，使 n = -255 。
    返回插入操作后，用字符串表示的 n 的最大值。

示例 1：
输入：n = “99”, x = 9
输出：“999”
解释：不管在哪里插入 9 ，结果都是相同的。

示例 2：
输入：n = “-13”, x = 2
输出：“-123”
解释：向 n 中插入 x 可以得到 -213、-123 或者 -132 ，三者中最大的是 -123 。

提示：
1 <= n.length <= 10^5
1 <= x <= 9
n​​​ 中每一位的数字都在闭区间 [1,9][1, 9] 中。
n 代表一个有效的整数。
当 n 表示负数时，将会以字符 ‘-’ 开始。

题解

自左到右依次匹配，越前对数字大小影响程度越大

  • 若该数为正数，应插入在第一个比x更小的数前
  • 若为负数，应插入在第一个比x更大的数前
  • 实在不行，插在最后

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String maxValue(String n, int x) {
        int len = n.length();
        if(n.charAt(0) == '-'){
            for(int i = 1; i < len; i++){
                if(n.charAt(i) > (char)(x + '0')) 
                    return n.substring(0, i) + (char)(x + '0') + n.substring(i, len);
            }
            return n + (char)(x + '0');
        }
        else{
            for(int i = 0; i < len; i++){
                if(n.charAt(i) < (char)(x + '0')) 
                    return n.substring(0, i) + (char)(x + '0') + n.substring(i, len);
            }
            return n + (char)(x + '0');
        }
    }
}

T3 5774. 使用服务器处理任务

题目

给你两个 下标从 0 开始 的整数数组 serversservers 和 taskstasks ，长度分别为 nn​​​​​​ 和 mm​​​​​​ 。servers[i]servers[i] 是第 ii​​​​​​​​​​ 台服务器的 权重 ，而 tasks[j]tasks[j] 是处理第 j​​​​​​j​​​​​​ 项任务 所需要的时间（单位：秒）。
你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 jj 项任务在第 jj 秒可以开始处理。处理第 jj 项任务时，你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。如果一台空闲服务器在第 tt 秒分配到第 jj 项任务，那么在 t+tasks[j]t + tasks[j] 时它将恢复空闲状态。
如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早 地处理剩余任务。 如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。
如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。
构建长度为 mm 的答案数组 ansans ，其中 ans[j]ans[j] 是第 jj 项任务分配的服务器的下标。
返回答案数组 ansans​​​​ 。

示例 1：
输入：servers=[3,3,2],tasks=[1,2,3,2,1,2]servers = [3,3,2], tasks = [1,2,3,2,1,2]
输出：[2,2,0,2,1,2][2,2,0,2,1,2]
解释：事件按时间顺序如下：

  • 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。
  • 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。
  • 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。
  • 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。
  • 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。
  • 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

示例 2：
输入：servers=[5,1,4,3,2],tasks=[2,1,2,4,5,2,1]servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出：[1,4,1,4,1,3,2][1,4,1,4,1,3,2]
解释：事件按时间顺序如下：

  • 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。
  • 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。
  • 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。
  • 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。
  • 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。
  • 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。
  • 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

提示：
servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10^5
1 <= servers[i],tasks[j]servers[i], tasks[j] <= 2 * 10^5

题解

维护两个优先队列

  • avail作为可用列表，每次弹出权值最低（相同时下标最小）的可用服务器，存储格式为{权值，服务器下标}
  • occupied作为占用列表，每次弹出最近时间内可以恢复使用的服务器，存储格式为{服务器下标，可用时间}

维护task队列作为任务队列，每次优先处理task内出队的任务，添加任务时也只应该对task队列操作

可能的fst注意点（也可能只是我的paranoia）：

若存在大量服务器排队，理论上说加入occupied队列服务器的弹出时间可能会超出Integer.MAX_VALUE，为了安全可以使用long[]数组进行存储

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        Queue<int[]> task = new ArrayDeque<>();
        PriorityQueue<int[]> avail = new PriorityQueue<>((o1, o2) -> (o1[0] != o2[0] ? o1[0] - o2[0]: o1[1] - o2[1]));
        PriorityQueue<long[]> occupied = new PriorityQueue<>((o1, o2) -> o1[1] > o2[1]? 1: -1);
        for(int i = 0; i < servers.length; i++){
            avail.offer(new int[]{servers[i], i});  //全部服务器加入可用队列
        }
        int len = tasks.length;
        int[] res = new int[len];
        for(int i = 0; i < len; i++){
            task.offer(new int[]{i, tasks[i]});  //将i时刻任务加入任务队列
            while(!occupied.isEmpty() && occupied.peek()[1] == i){  
                //将解除占用的服务器从occupied中全部出队，并加入avail中
                int num = (int)occupied.poll()[0];
                avail.offer(new int[]{servers[num], num});
            }
            while(!task.isEmpty() && !avail.isEmpty()){
                //清算task和avail数组，直到task全部清完或服务器不够用为止
                int[] first = avail.poll();
                int[] cur = task.poll();
                occupied.offer(new long[]{first[1], (long)i + (long)cur[1]});
                res[cur[0]] = first[1];   //分配task任务，并将res数组对应标记
            }
        }
        //任务全部入队，task队列中可能还存在任务
        while(!task.isEmpty() && !occupied.isEmpty()){
            //若while循环满足，则表示清算结束avail数组已空，task中仍有任务
            long time = occupied.peek()[1]; //寻找occupied释放的下一个时间点
            while(!occupied.isEmpty() && occupied.peek()[1] == time){
                //将对应时间的占用服务器全部释放
                long[] new_task = occupied.poll();
                avail.add(new int[]{servers[(int)new_task[0]], (int)new_task[0]});
            }
            while(!task.isEmpty() && !avail.isEmpty()){
                //对task和avail执行清算
                int[] first = avail.poll();
                int[] cur = task.poll();
                occupied.offer(new long[]{first[1], (long)time + (long)cur[1]});
                res[cur[0]] = first[1];
            }
        }
        return res;
    }
}

T4 5775. 准时抵达会议现场的最小跳过休息次数

题目

给你一个整数 hoursBeforehoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 nn 条道路。道路的长度用一个长度为 nn 的整数数组 distdist 表示，其中 dist[i]dist[i] 表示第 ii 条道路的长度（单位：千米）。另给你一个整数 speedspeed ，表示你在道路上前进的速度（单位：千米每小时）。
当你通过第 ii 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

  • 例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。
    然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。
  • 例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。
    返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

示例 1：
输入：dist=[1,3,2],speed=4,hoursBefore=2dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 2：
输入：dist=[7,3,5,5],speed=2,hoursBefore=10dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。

示例 3：
输入：dist=[7,3,5,5],speed=1,hoursBefore=10dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。

提示：
nn == dist.lengthdist.length
1 <= nn <= 1000
1 <= dist[i]dist[i] <= 10^5
1 <= speedspeed <= 10^6
1 <= hoursBeforehoursBefore <= 10^7

题解

思路：用dp[i][j]dp[i][j]表示经过了dist[0]dist[0]到dist[i−1]dist[i - 1]的ii段道路，并且跳过了jj次的最短用时
我们得到状态方程
dp[i][j]=min{⌈dp[i−1][j]+dist[i−1]speed⌉,dp[i−1][j−1]+dist[i−1]speed}dp[i][j] = min \{\lceil dp[i - 1][j] + \frac{dist[i - 1]}{speed}\rceil, dp[i - 1][j - 1] + \frac{dist[i - 1]}{speed}\}

初次尝试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int len = dist.length;
        double[][] dp = new double[len + 1][len + 1];
        for(double[] x: dp) Arrays.fill(x, 10000001);
        Arrays.fill(dp[0], 0.0);
        for(int i = 1; i <= len; i++){
            double time = (double)(dist[i - 1]) / speed;
            for(int j = 0; j <= i; j++){
                int num = (int)(dp[i - 1][j] + time);
                dp[i][j] = Math.min(dp[i][j], (dp[i - 1][j] + time == num)? num: num + 1);
                if(j > 0) dp[i][j] = Math.min(dp[i - 1][j - 1] + time, dp[i][j]);
            }
        }
        //for(double[] x: dp) System.out.println(Arrays.toString(x));
        for(int j = 0; j <= len; j++){
            if(dp[len][j] <= hoursBefore) return j;
        }
        return -1;
    }
}

提交WA：

原因：根据 IEEE 754 标准，浮点数在计算机中存储的精度是有限的，而本题中我们不可避免的会使用「浮点数运算」以及「向上取整」运算，如果强行忽略产生的计算误差，会得到错误的结果。

折中解决办法：每一步先暂时不做除法，尽量用乘法代替
原理类似：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int len = dist.length;
        long[][] dp = new long[len + 1][len + 1];
        for(long[] x: dp) Arrays.fill(x, 10000001 * (long)speed);
        Arrays.fill(dp[0], 0);
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= i; j++){
                long num = (long) dist[i - 1];
                dp[i][j] = Math.min(dp[i][j], (dp[i - 1][j] + num) % speed == 0 ? 
                                    dp[i - 1][j] + num:  ((dp[i - 1][j] + num) / speed + 1) * speed);
                if(j > 0) dp[i][j] = Math.min(dp[i - 1][j - 1] + dist[i - 1] , dp[i][j]);
            }
        }
        //for(long[] x: dp) System.out.println(Arrays.toString(x));
        for(int j = 0; j <= len; j++){
            if(dp[len][j] <= (long)(hoursBefore) * speed) return j;
        }
        return -1;
    }
}