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

6112. 装满杯子需要的最短总时长
6113. 无限集中的最小数字
6114. 移动片段得到字符串
6115. 统计理想数组的数目

t4不会，前面还wrong了不少，最近的题做的太少了

6112. 装满杯子需要的最短总时长

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯不同类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的最少秒数。

示例 1：
输入：amount = [1,4,2] 输出：4 解释：下面给出一种方案：第 1 秒：装满一杯冷水和一杯温水。第 2 秒：装满一杯温水和一杯热水。第 3 秒：装满一杯温水和一杯热水。第 4 秒：装满一杯温水。可以证明最少需要 4 秒才能装满所有杯子。
示例 2：
输入：amount = [5,4,4] 输出：7 解释：下面给出一种方案：第 1 秒：装满一杯冷水和一杯热水。第 2 秒：装满一杯冷水和一杯温水。第 3 秒：装满一杯冷水和一杯温水。第 4 秒：装满一杯温水和一杯热水。第 5 秒：装满一杯冷水和一杯热水。第 6 秒：装满一杯冷水和一杯温水。第 7 秒：装满一杯热水。
示例 3：
输入：amount = [5,0,0] 输出：5 解释：每秒装满一杯冷水。

提示：

amount.length == 3
0 <= amount[i] <= 100

思路：
方法1：贪心
时间复杂度：O(n)
如果还有3种类型未装满，选择数量最大的两种装1次
如果还有2种类型未装满，需要的次数为max(a, b)
如果只剩1种类型未装满，装满即可

class Solution {
    public int fillCups(int[] amount) {
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int x : amount) {
            if (x > 0)
                q.offer(x);
        }
        int res = 0;
        while (!q.isEmpty()) {
            if (q.size() != 3) {
                res += q.poll();
                break;
            }
            int a = q.poll(), b = q.poll();
            a--;
            b--;
            if (a > 0) q.offer(a);
            if (b > 0) q.offer(b);
            res++;
        }
        return res;
    }
}

方法2：数学<br />     时间复杂度：`O(1)`<br />设三种类型从小到大依次需要`x, y, z`杯<br />若 `x + y <= z`，装`z`时顺便装满`x, y`，`res = z`<br />若`x + y > z`，令`t = x + y - z`<br />若`t % 2 == 0`，`res = t / 2 + z`<br />若`t % 2 == 1`，`res = t / 2 + z + 1`

class Solution {
    public int fillCups(int[] a) {
        Arrays.sort(a);
        int x = a[0], y = a[1], z = a[2];
        if (x + y <= z) return z;
        else {
            int t = x + y - z;
            if (t % 2 == 0)
                return t / 2 + z;
            else
                return t / 2 + z + 1;
        }
    }
}

6113. 无限集中的最小数字

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。
实现 SmallestInfiniteSet 类：

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。
int popSmallest() 移除并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不存在于无限集中，则将一个 num 添加到该无限集中。

示例：
输入 [“SmallestInfiniteSet”, “addBack”, “popSmallest”, “popSmallest”, “popSmallest”, “addBack”, “popSmallest”, “popSmallest”, “popSmallest”] [[], [2], [], [], [], [1], [], [], []] 输出 [null, null, 1, 2, 3, null, 1, 4, 5] 解释 SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。 smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。 smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。 smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中， // 且 1 是最小的整数，并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。 smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

提示：

1 <= num <= 1000
最多调用 popSmallest 和 addBack 方法共计 1000 次

思路：
统计未在无限集种的正整数即可
时间复杂度：O(n2)
空间复杂度：O(n)

class SmallestInfiniteSet {
    Set<Integer> set = new HashSet<>();
    public SmallestInfiniteSet() {
    }
    public int popSmallest() {
        int x = 1;
        while (set.contains(x))
            x++;
        set.add(x);
        return x;
    }
    public void addBack(int num) {
        if (set.contains(num)) {
            set.remove(num);
        }
    }
}
/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */

6114. 移动片段得到字符串

给你两个字符串 start 和 target ，长度均为 n 。每个字符串仅由字符 ‘L’、’R’ 和 ‘_’ 组成，其中：

字符 ‘L’ 和 ‘R’ 表示片段，其中片段 ‘L’ 只有在其左侧直接存在一个空位时才能向左移动，而片段 ‘R’ 只有在其右侧直接存在一个空位时才能向右移动。
字符 ‘_’ 表示可以被任意 ‘L’ 或 ‘R’ 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。

示例 1：
输入：start = “LRR“, target = “L__RR” 输出：true 解释：可以从字符串 start 获得 target ，需要进行下面的移动： - 将第一个片段向左移动一步，字符串现在变为 “L_RR“ 。 - 将最后一个片段向右移动一步，字符串现在变为 “L_RR“ 。 - 将第二个片段向右移动散步，字符串现在变为 “L__RR” 。可以从字符串 start 得到 target ，所以返回 true 。
示例 2：
输入：start = “RL“, target = “_LR” 输出：false 解释：字符串 start 中的 ‘R’ 片段可以向右移动一步得到 “RL“ 。但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
示例 3：
输入：start = “_R”, target = “R“ 输出：false 解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。

提示：

n == start.length == target.length
1 <= n <= 105
start 和 target 由字符 ‘L’、’R’ 和 ‘_’ 组成

思路：
双指针
时间复杂度：O(n)

class Solution {
    public boolean canChange(String s, String t) {
        int n = s.length();
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        boolean flag = true;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (b[i] == '_')
                continue;
            while (j < n && a[j] == '_')
                j++;
            if (j == n || a[j] != b[i]) {
                flag = false;
                break;
            }
            if (b[i] == 'R' && i < j) {
                flag = false;
                break;
            }
            if (b[i] == 'L' && i > j) {
                flag = false;
                break;
            }
            j++;
        }
        while (j < n) {
            if (a[j] != '_') {
                flag = false;
                break;
            }
            j++;
        }
        return flag;
    }
}

6115. 统计理想数组的数目

给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。

返回长度为 n 的不同理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

示例 1：
输入：n = 2, maxValue = 5 输出：10 解释：存在以下理想数组： - 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5] - 以 2 开头的数组（2 个）：[2,2]、[2,4] - 以 3 开头的数组（1 个）：[3,3] - 以 4 开头的数组（1 个）：[4,4] - 以 5 开头的数组（1 个）：[5,5] 共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。
示例 2：
输入：n = 5, maxValue = 3 输出：11 解释：存在以下理想数组： - 以 1 开头的数组（9 个）： - 不含其他不同值（1 个）：[1,1,1,1,1] - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2] - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3] - 以 2 开头的数组（1 个）：[2,2,2,2,2] - 以 3 开头的数组（1 个）：[3,3,3,3,3] 共计 9 + 1 + 1 = 11 个不同理想数组。

提示：

2 <= n <= 104
1 <= maxValue <= 104

思路：
一开始想的是DP，但时间复杂度是O(n*maxValue*log(maxValue)，会TLE
方法：数论 + 组合数学
先考虑简单的问题，如果不要求序列长度，只要求序列中的每个数各不相同且严格递增，怎么做？
最长的一种是首位为1，后一个数是前一个的2倍，故最长序列的数的个数为len = logm + 1
已知m <= 10000故len <= 14
故可用DP推出f[i][j]，f[i][j]表示以i为结尾，长度为j的满足要求的序列的个数
该子问题时间复杂度为O(mlog2m)
然后考虑对于每一个严格递增序列，如何扩展成长度为n的可重复序列(超过n的不在考虑范围内)
该问题等价于将n个相同的球放入len个盒子中，且每个盒子的球数至少为1，答案为C(n - 1, len - 1)

对每个严格递增序列求组合数，累加求和就是最终的结果

class Solution {
    public int idealArrays(int n, int m) {
        int MOD = (int)(1e9 + 7); 
        int[][] f = new int[m + 1][15];
        for (int i = 1; i <= m; i++)
            f[i][1] = 1;
        for (int j = 1; j < 14; j++) {
            for (int x = 1; x <= m; x++) {
                for (int y = 2 * x; y <= m; y += x) {
                    f[y][j + 1] += f[x][j];
                    f[y][j + 1] %= MOD;
                }
            }
        }
        int[][] c = new int[n][15];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= Math.min(14, i); j++) {
                if (j == 0) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j < 15; j++) {
                res = (int)((res + 1L * c[n - 1][j - 1] * f[i][j]) % MOD);
            }
        }
        return res;
    }
}