寄
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;
}
}