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

6160. 和有限的最长子序列
6161. 从字符串中移除星号
6162. 收集垃圾的最少总时间
6163. 给定条件下构造矩阵

第一题看错题，还好稳住了

6160. 和有限的最长子序列

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 _answer ，其中 answer[i] _是 nums 中元素之和小于等于 queries[i] 的 子序列 的最大长度。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：
输入：nums = [4,5,2,1], queries = [3,10,21] 输出：[2,3,4] 解释：queries 对应的 answer 如下： - 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。 - 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。 - 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。
示例 2：
输入：nums = [2,3,4,5], queries = [1] 输出：[0] 解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106

思路：排序 + 二分
数据范围小，二分换成遍历

class Solution {
    public int[] answerQueries(int[] nums, int[] q) {
        int n = nums.length, m = q.length;
        int[] res = new int[m];
        Arrays.sort(nums);
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] + nums[i - 1];
        for (int i = 0; i < m; i++) {
            int x = 0;
            for (int j = 1; j <= n; j++) {
                if (s[j] <= q[i])
                    x = j;
            }
            res[i] = x;
        }
        return res;
    }
}

6161. 从字符串中移除星号

给你一个包含若干星号 * 的字符串 s 。
在一步操作中，你可以：

选中 s 中的一个星号。
移除星号左侧最近的那个 非星号 字符，并移除该星号自身。

返回移除所有星号之后的字符串。
注意：

生成的输入保证总是可以执行题面中描述的操作。
可以证明结果字符串是唯一的。

示例 1：
输入：s = “leetcod*e” 输出：“lecoe” 解释：从左到右执行移除操作： - 距离第 1 个星号最近的字符是 “lee_t_code” 中的 ‘t’ ，s 变为 “leecode” 。 - 距离第 2 个星号最近的字符是 “leecode” 中的 ‘e’ ，s 变为 “lecode” 。 - 距离第 3 个星号最近的字符是 “lecode” 中的 ‘d’ ，s 变为 “lecoe” 。不存在其他星号，返回 “lecoe” 。
示例 2：
输入：s = “erase**“ 输出：“” 解释：整个字符串都会被移除，所以返回空字符串。

提示：

1 <= s.length <= 105
s 由小写英文字母和星号 * 组成
s 可以执行上述操作

思路：双端队列

class Solution {
    public String removeStars(String s) {
        Deque<Character> q = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '*') {
                q.pollLast();
            } else {
                q.offer(s.charAt(i));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty())
            sb.append(q.poll());
        return sb.toString();
    }
}

6162. 收集垃圾的最少总时间

显示英文描述
我的提交返回竞赛

通过的用户数4065
尝试过的用户数4116
用户总通过次数4136
用户总提交次数4636
题目难度Medium

给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ，’P’ 和 ‘G’ ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾一单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有一辆垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车不能做任何事情。
请你返回收拾完所有垃圾需要花费的最少总分钟数。

示例 1：
输入：garbage = [“G”,”P”,”GP”,”GG”], travel = [2,4,3] 输出：21 解释： 收拾纸的垃圾车： 1. 从房子 0 行驶到房子 1 2. 收拾房子 1 的纸垃圾 3. 从房子 1 行驶到房子 2 4. 收拾房子 2 的纸垃圾收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。收拾玻璃的垃圾车： 1. 收拾房子 0 的玻璃垃圾 2. 从房子 0 行驶到房子 1 3. 从房子 1 行驶到房子 2 4. 收拾房子 2 的玻璃垃圾 5. 从房子 2 行驶到房子 3 6. 收拾房子 3 的玻璃垃圾收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
示例 2：
输入：garbage = [“MMM”,”PGM”,”GP”], travel = [3,10] 输出：37 解释： 收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

提示：

2 <= garbage.length <= 105
garbage[i] 只包含字母 ‘M’ ，’P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

思路：模拟

class Solution {
    public int garbageCollection(String[] g, int[] t) {
        int n = g.length;
        int[][] cnt = new int[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < g[i].length(); j++) {
                if (g[i].charAt(j) == 'M')
                    cnt[i][0]++;
                else if (g[i].charAt(j) == 'P')
                    cnt[i][1]++;
                else cnt[i][2]++;
            }
        }
        int res = 0;
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0) p += t[i - 1];
            if (cnt[i][0] != 0) {
                res += cnt[i][0] + p;
                p = 0;
            }
        }
        p = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0) p += t[i - 1];
            if (cnt[i][1] != 0) {
                res += cnt[i][1] + p;
                p = 0;
            }
        }
        p = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0) p += t[i - 1];
            if (cnt[i][2] != 0) {
                res += cnt[i][2] + p;
                p = 0;
            }
        }
        return res;
    }
}

6163. 给定条件下构造矩阵

显示英文描述
我的提交返回竞赛

通过的用户数1310
尝试过的用户数1676
用户总通过次数1451
用户总提交次数3033
题目难度Hard

给你一个正整数 k ，同时给你：

一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。
你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。
矩阵还需要满足以下条件：

对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的行必须在数字 belowi 所在行的上面。
对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的列必须在数字 righti 所在列的左边。

返回满足上述要求的任意矩阵。如果不存在答案，返回一个空的矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] 输出：[[3,0,0],[0,0,1],[0,2,0]] 解释：上图为一个符合所有条件的矩阵。行要求如下： - 数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。 - 数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。列要求如下： - 数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。 - 数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。注意，可能有多种正确的答案。
示例 2：
输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] 输出：[] 解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

2 <= k <= 400
1 <= rowConditions.length, colConditions.length <= 104
rowConditions[i].length == colConditions[i].length == 2
1 <= abovei, belowi, lefti, righti <= k
abovei != belowi
lefti != righti

思路：拓扑排序

class Solution {
    int N = 10010;
    int[] h = new int[N], e = new int[N], ne = new int[N], in = new int[N];
    int idx;
    List<Integer> row = new ArrayList<>();
    List<Integer> col = new ArrayList<>();
    int k;
    public int[][] buildMatrix(int k, int[][] r, int[][] c) {
        this.k = k;
        if (!topo(r, 0) || !topo(c, 1))
            return new int[0][0];
        Map<Integer, Integer> m1 = new HashMap<>();
        Map<Integer, Integer> m2 = new HashMap<>();
        for (int i = 0; i < k; i++) {
            int x = row.get(i);
            m1.put(x, i);
        }
        for (int i = 0; i < k; i++) {
            int x = col.get(i);
            m2.put(x, i);
        }
        // System.out.println(row);
        // System.out.println(col);
        int[][] res = new int[k][k];
        for (int i = 1; i <= k; i++) {
            int x = m1.get(i), y = m2.get(i);
            res[x][y] = i;
        }
        return res;
    }
    boolean topo(int[][] r, int op) {
        Arrays.fill(h, -1);
        idx = 0;
        Arrays.fill(in, 0);
        for (int[] p : r) {
            int a = p[0], b = p[1];
            add(a, b);
        }
        List<Integer> a = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= k; i++) {
            if (in[i] == 0) {
                q.offer(i);
                a.add(i);
            }
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i];
                in[j]--;
                if (in[j] == 0) {
                    q.offer(j);
                    a.add(j);
                }
            }
        }
        if (a.size() != k) return false;
        if (op == 0) row = new ArrayList<>(a);
        else col = new ArrayList<>(a);
        return true;
    }
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        in[b]++;
        h[a] = idx++;
    }
}