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

6167. 检查相同字母间的距离
6168. 恰好移动 k 步到达某一位置的方法数目
6169. 最长优雅子数组
6170. 会议室 III

寄

6167. 检查相同字母间的距离

给你一个下标从 0 开始的字符串 s ，该字符串仅由小写英文字母组成，s 中的每个字母都恰好出现两次。另给你一个下标从 0 开始、长度为 26 的的整数数组 distance 。
字母表中的每个字母按从 0 到 25 依次编号（即，’a’ -> 0, ‘b’ -> 1, ‘c’ -> 2, … , ‘z’ -> 25）。
在一个匀整字符串中，第 i 个字母的两次出现之间的字母数量是 distance[i] 。如果第 i 个字母没有在 s 中出现，那么 distance[i] 可以忽略。
如果 s 是一个匀整字符串，返回 true ；否则，返回 false 。

示例 1：
输入：s = “abaccb”, distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 输出：true 解释： - ‘a’ 在下标 0 和下标 2 处出现，所以满足 distance[0] = 1 。 - ‘b’ 在下标 1 和下标 5 处出现，所以满足 distance[1] = 3 。 - ‘c’ 在下标 3 和下标 4 处出现，所以满足 distance[2] = 0 。注意 distance[3] = 5 ，但是由于 ‘d’ 没有在 s 中出现，可以忽略。因为 s 是一个匀整字符串，返回 true 。
示例 2：
输入：s = “aa”, distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 输出：false 解释： - ‘a’ 在下标 0 和 1 处出现，所以两次出现之间的字母数量为 0 。但是 distance[0] = 1 ，s 不是一个匀整字符串。

提示：

2 <= s.length <= 52
s 仅由小写英文字母组成
s 中的每个字母恰好出现两次
distance.length == 26
0 <= distance[i] <= 50

思路：
暴力

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int n = s.length();
        boolean[] st = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (st[i]) continue;
            char c = s.charAt(i);
            int d = 0;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(j) == c) {
                    st[j] = true;
                    d = j - i - 1;
                    break;
                }
            }
            if (distance[c - 'a'] != d)
                return false;
        }
        return true;
    }
}

6168. 恰好移动 k 步到达某一位置的方法数目

给你两个正整数 startPos 和 endPos 。最初，你站在无限数轴上位置 startPos 处。在一步移动中，你可以向左或者向右移动一个位置。
给你一个正整数 k ，返回从 startPos 出发、恰好移动 k 步并到达 endPos 的不同方法数目。由于答案可能会很大，返回对 109 + 7 取余的结果。
如果所执行移动的顺序不完全相同，则认为两种方法不同。
注意：数轴包含负整数。

示例 1：
输入：startPos = 1, endPos = 2, k = 3 输出：3 解释：存在 3 种从 1 到 2 且恰好移动 3 步的方法： - 1 -> 2 -> 3 -> 2. - 1 -> 2 -> 1 -> 2. - 1 -> 0 -> 1 -> 2. 可以证明不存在其他方法，所以返回 3 。
示例 2：
输入：startPos = 2, endPos = 5, k = 10 输出：0 解释：不存在从 2 到 5 且恰好移动 10 步的方法。

提示：

1 <= startPos, endPos, k <= 1000

思路：
方法1：记忆化搜索
方法2：组合数学

class Solution {
    int N = 4010, M = 1010;
    int INF = (int)(1e9 + 7);
    int[][] f = new int[N][M];
    public int numberOfWays(int s, int e, int k) {
        for (int i = 0; i < N; i++)
            Arrays.fill(f[i], -1);
        s += k;
        e += k;
        dfs(s, e, k);
        return f[s][k] == -1 ? 0 : f[s][k];
    }
    int dfs(int s, int e, int k) {
        if (f[s][k] != -1) return f[s][k];
        if (Math.abs(s - e) > k || (k - Math.abs(s - e)) % 2 != 0) {
            f[s][k] = 0;
            return 0;
        }
        if (s == e && k == 0) return 1;
        int res = 0;
        res += dfs(s + 1, e, k - 1);
        res %= INF;
        res += dfs(s - 1, e, k - 1);
        res %= INF;
        f[s][k] = res;
        return res;
    } 
}

class Solution {
    int MOD = (int)(1e9 + 7);
    public int numberOfWays(int s, int e, int k) {
        if (Math.abs(s - e) > k || (k - Math.abs(s - e)) % 2 == 1)
            return 0;
        if (s > e) {
            int t = e;
            e = s;
            s = t;
        }
        int t = e - s + (k - (e - s)) / 2;
        return (int)(1L * fact(k) * infact(t) % MOD * infact(k - t) % MOD);
    }
    int fact(int x) {
        long res = 1;
        while (x > 0) {
            res = res * x % MOD;
            x--;
        }
        return (int)res;
    }
    int infact(int x) {
        long res = 1;
        while (x > 0) {
            res = res * pow(x, MOD - 2, MOD) % MOD;
            x--;
        }
        return (int)res;
    }
    int pow(int a, int b, int p) {
        long res = 1, cur = a;
        while (b > 0) {
            if ((b & 1) == 1)
                res = (res * cur) % p;
            b >>= 1;
            cur = cur * cur % p;
        }
        return (int)(res % p);
    }
}

6169. 最长优雅子数组

给你一个由正整数组成的数组 nums 。
如果 nums 的子数组中位于不同位置的每对元素按位 与（AND）运算的结果等于 0 ，则称该子数组为优雅子数组。
返回最长的优雅子数组的长度。
子数组 是数组中的一个连续部分。
注意：长度为 1 的子数组始终视作优雅子数组。

示例 1：
输入：nums = [1,3,8,48,10] 输出：3 解释：最长的优雅子数组是 [3,8,48] 。子数组满足题目条件： - 3 AND 8 = 0 - 3 AND 48 = 0 - 8 AND 48 = 0 可以证明不存在更长的优雅子数组，所以返回 3 。
示例 2：
输入：nums = [3,1,5,11,13] 输出：1 解释：最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

思路：
按位处理 + 贪心

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        for (int i = 0; i < n; i++)
            f[i] = i + 1;
        for (int k = 0; k < 32; k++) {
            int pre = -1;
            for (int i = 0; i < n; i++) {
                if ((nums[i] >> k & 1) == 1) {
                    f[i] = Math.min(f[i], i - pre);
                    pre = i;
                }
            }
        }
        for (int i = 1; i < n; i++)
            f[i] = Math.min(f[i], f[i - 1] + 1);
        int max = 0;
        for (int x : f)
            max = Math.max(x, max);
        return max;
    }
}

6170. 会议室 III

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。
给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在半闭时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。
会议将会按以下方式分配给会议室：

每场会议都会在未占用且编号最小的会议室举办。
如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间相同。
当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议。

返回举办最多次会议的房间编号。如果存在多个房间满足此条件，则返回编号最小的房间。
半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

示例 1：
输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] 输出：0 解释： - 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。 - 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。 - 在时间 2 ，两个会议室都被占用，第三场会议延期举办。 - 在时间 3 ，两个会议室都被占用，第四场会议延期举办。 - 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。 - 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。
示例 2：
输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] 输出：1 解释： - 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。 - 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。 - 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。 - 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 - 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。 - 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 - 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

提示：

1 <= n <= 100
1 <= meetings.length <= 105
meetings[i].length == 2
0 <= starti < endi <= 5 * 105
starti 的所有值 互不相同

思路：
两个优先队列
一个维护空会议室编号，另一个维护每个被占用会议室的结束时间+编号

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (o1, o2) -> (o1[0] - o2[0]));
        PriorityQueue<Integer> e = new PriorityQueue<>();
        PriorityQueue<long[]> used = new PriorityQueue<>((o1, o2) -> (o1[0] == o2[0] ? (int)(o1[1] - o2[1]) : (o1[0] < o2[0] ? -1 : 1)));
        for (int i = 0; i < n; i++) e.offer(i);
        int[] cnt = new int[n];
        for (int[] p : meetings) {
            long a = p[0], b = p[1] - 1;
            while (!used.isEmpty() && used.peek()[0] < a) {
                int idx = (int)used.poll()[1];
                e.offer(idx);
            }
            if (!e.isEmpty()) {
                int idx = e.poll();
                cnt[idx]++;
                used.offer(new long[]{b, idx});
            } else {
                long[] t = used.poll();
                b = t[0] + 1 + b - a;
                int idx = (int)(t[1]);
                cnt[idx]++;
                used.offer(new long[]{b, idx});
            }
        }
        int max = -1, pos = -1;
        for (int i = 0; i < n; i++)
            if (cnt[i] > max) {
                max = cnt[i];
                pos = i;
            }
        return pos;
    }
}