周赛 - 🏆 第 282 场力扣周赛 - 《学习笔记》

6008. 统计包含给定前缀的字符串
6009. 使两字符串互为字母异位词的最少步骤数
6010. 完成旅途的最少时间
6011. 完成比赛的最少时间

今天脑子不清醒，写完复盘后睡一觉。
今天的题很容易溢出，第三题long都能爆掉，第四题也一样，都需要特判。

6008. 统计包含给定前缀的字符串

给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为前缀的字符串的数目。
字符串 s 的前缀就是 s 的任一前导连续字符串。

示例 1：
输入：words = [“pay”,”at_tention”,”practice”,”attend”], pref = “at” 输出：2 解释：以 “at” 作为前缀的字符串有两个，分别是：”attention” 和 “at_tend” 。
示例 2：
输入：words = [“leetcode”,”win”,”loops”,”success”], pref = “code” 输出：0 解释：不存在以 “code” 作为前缀的字符串。

提示：

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] 和 pref 由小写英文字母组成

思路：
考察substring函数

class Solution {
    public int prefixCount(String[] w, String p) {
        int n = p.length();
        int cnt = 0;
        for (String s : w) {
            if (s.length() >= n && s.substring(0, n).equals(p))
                cnt++;
        }
        return cnt;
    }
}

6009. 使两字符串互为字母异位词的最少步骤数

给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。
返回使 s 和 t 互为 字母异位词 所需的最少步骤数。
字母异位词 指字母相同但是顺序不同（或者相同）的字符串。

示例 1：
输入：s = “leet_code“, t = “coats“ 输出：7 解释： - 执行 2 步操作，将 “as” 追加到 s = “leetcode” 中，得到 s = “leetcodeas“ 。 - 执行 5 步操作，将 “leede” 追加到 t = “coats” 中，得到 t = “coatsleede_” 。 “leetcodeas” 和 “coatsleede” 互为字母异位词。总共用去 2 + 5 = 7 步。可以证明，无法用少于 7 步操作使这两个字符串互为字母异位词。
示例 2：
输入：s = “night”, t = “thing” 输出：0 解释：给出的字符串已经互为字母异位词。因此，不需要任何进一步操作。

提示：

1 <= s.length, t.length <= 2 * 105
s 和 t 由小写英文字符组成

思路：
哈希

class Solution {
    public int minSteps(String s, String t) {
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        for (int i = 0; i < s.length(); i++) {
            c1[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            c2[t.charAt(i) - 'a'] ++;
        }
        int res = 0;
        for (int i = 0; i < 26; i++) {
            res += Math.abs(c1[i] - c2[i]);
        }
        return res;
    }
}

6010. 完成旅途的最少时间

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车总共需要完成的旅途数目。请你返回完成至少 totalTrips 趟旅途需要花费的最少时间。

示例 1：
输入：time = [1,2,3], totalTrips = 5 输出：3 解释： - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。已完成的总旅途数为 1 + 0 + 0 = 1 。 - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。已完成的总旅途数为 2 + 1 + 0 = 3 。 - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。已完成的总旅途数为 3 + 1 + 1 = 5 。所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2：
输入：time = [2], totalTrips = 1 输出：2 解释： 只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。所以完成 1 趟旅途的最少时间为 2 。

提示：

1 <= time.length <= 105
1 <= time[i], totalTrips <= 107

思路：
二分，注意溢出问题

class Solution {
    public long minimumTime(int[] time, int tot) {
        long l = 1, r = (long)(1e14 + 10);
        while (l < r) {
            long mid = l + ((r - l) >> 1);
            long cnt = 0;
            for (int x : time) {
                cnt += mid / x;
                if (cnt >= tot) {
                    break;
                }
            }
            System.out.println(mid + " " + cnt);
            if (cnt < tot)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }
}

:::danger 要么上界取合适一点，要么在内层循环中加入判断当cnt已经大于等于tot时退出循环 :::

6011. 完成比赛的最少时间

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。

比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 2 = 6 秒，完成第 3 圈耗时 3 22 = 12 秒，依次类推。

同时给你一个整数 changeTime 和一个整数 numLaps 。
比赛总共包含 numLaps 圈，你可以选择任意一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒换成任意一种轮胎（也可以换成当前种类的新轮胎）。
请你返回完成比赛需要耗费的最少时间。

示例 1：
输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4 输出：21 解释： 第 1 圈：使用轮胎 0 ，耗时 2 秒。第 2 圈：继续使用轮胎 0 ，耗时 2 3 = 6 秒。第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。第 4 圈：继续使用轮胎 0 ，耗时 2 3 = 6 秒。总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。完成比赛的最少时间为 21 秒。
示例 2：
输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5 输出：25 解释： 第 1 圈：使用轮胎 1 ，耗时 2 秒。第 2 圈：继续使用轮胎 1 ，耗时 2 2 = 4 秒。第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。第 4 圈：继续使用轮胎 1 ，耗时 2 2 = 4 秒。第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。完成比赛的最少时间为 25 秒。

提示：

1 <= tires.length <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000

思路：
每个轮胎最长的使用圈数注定不会太长，因为min(ri) == 2故最多log2(100000) + 1次就会结束，因为fi <= 100000
预处理出k, 1 <= k <= 20(差不多)圈的最小耗时(考虑更换轮胎的时间，最后减去一个更换时间即可)
比赛中我也做到了这里然后去贪心了，只能过一半。
赛后看别人题解才察觉接下来是完全背包问题，背包容量为圈数，物品数为k圈，每个都能选无数次，代价为耗时。
转移方程f[i] = f[i - j] + w[j]
含义是：考虑前i圈，最后一次跑j圈，代价为w[j]

class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int m) {
        int min = 0x3f3f3f3f;
        for (int[] p : tires) {
            min = Math.min(min, changeTime + p[0]);
        }
        int n = tires.length;
        boolean[] st = new boolean[n];
        Arrays.fill(st, true);
        int[] w = new int[20];
        Arrays.fill(w, 0x3f3f3f3f);
        for (int i = 1; i < 20; i++) {
            boolean flag = false;
            for (int j = 0; j < n; j++) {
                if (!st[j]) continue;
                flag = true;
                if (1.0 * (changeTime + tires[j][0]) <= tires[j][0] * Math.pow(tires[j][1], i - 1)) {
                    st[j] = false;
                } else {
                    double sum = changeTime;
                    for (int k = 1; k <= i; k++)
                        sum += tires[j][0] * Math.pow(tires[j][1], k - 1);
                    w[i] = Math.min(w[i], (int)sum);   
                }
            }
            if (!flag) break;
        }
        int[] f = new int[m + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 1; i < 20; i++) {
            for (int j = i; j <= m; j++)
                f[j] = Math.min(f[j], f[j - i] + w[i]);
        }
        return f[m] - changeTime;  
    }
}