100166. Check if Bitwise OR Has Trailing Zeros
给你一个 正整数 数组 nums 。
你需要检查是否可以从数组中选出 两个或更多 元素,满足这些元素的按位或运算( OR)结果的二进制表示中 至少 存在一个尾随零。
例如,数字 5 的二进制表示是 "101",不存在尾随零,而数字 4 的二进制表示是 "100",存在两个尾随零。
如果可以选择两个或更多元素,其按位或运算结果存在尾随零,返回 true;否则,返回 false 。
测试样例:
输入:nums = [1,2,3,4,5]
输出:true
解释:如果选择元素 2 和 4,按位或运算结果是 6,二进制表示为 "110" ,存在一个尾随零。
解答:这道题目范围很小,直接按照题意双循环暴力运算。
class Solution {
public boolean hasTrailingZeros(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
int tmp = nums[i] | nums[j];
if (tmp % 2 == 0) {
return true;
}
}
}
return false;
}
}
100184. Find Longest Special Substring That Occurs Thrice II
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc" 不是特殊字符串,而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
测试样例:
输入:s = "aaaa"
输出:2
解释:出现三次的最长特殊子字符串是 "aa" :子字符串 "aaaa"、"aaaa" 和 "aaaa"。可以证明最大长度是 2 。
解答:第二题和第三题一样,我就只放一道题目的题解了。按照测试集合,我们知道字符串中,最长的连续自数组的长度 - 2必然是一个解。还有一种情况是类似aabaabaa,由于一个b隔断了,会导致aa还是最长字符串。为了解决这种情况,我们需要记录连续字符串的长度,并且排序。有一段逻辑会计算不同长度的结果。
class Solution {
public int maximumLength(String s) {
PriorityQueue<Integer>[] maxMem = new PriorityQueue[26];
for (int i = 0; i < 26; ++i) {
maxMem[i] = new PriorityQueue<>();
}
int last = -1, len = 0;
for (int i = 0; i <= s.length(); ++i) {
if (i == s.length() || s.charAt(i) != last) {
if (last != -1) {
maxMem[last - 'a'].add(len);
if (maxMem[last - 'a'].size() > 3) {
maxMem[last - 'a'].poll();
}
}
if (i < s.length()) {
last = s.charAt(i);
len = 1;
}
} else {
++len;
}
}
int res = -1;
for (PriorityQueue<Integer> t : maxMem) {
ArrayList<Integer> list = new ArrayList<>();
while (!t.isEmpty()) {
list.add(t.poll());
}
for (int i = 0; i < list.size(); ++i) {
res = Math.max(res, list.get(i) - 2);
if (list.size() > i + 2) {
res = Math.max(res, list.get(i));
} else if (i + 1 < list.size()) {
res = Math.max(res, list.get(i) - 1);
if (list.get(i + 1) > list.get(i)) {
res = Math.max(res, list.get(i));
}
}
}
}
return res <= 0 ? -1 : res;
}
}
100129. Palindrome Rearrangement Queries
给你一个长度为 偶数 n ,下标从 0 开始的字符串 s 。
同时给你一个下标从 0 开始的二维整数数组 queries ,其中 queries[i] = [ai, bi, ci, di] 。
对于每个查询 i ,你需要执行以下操作:
- 将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
- 将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。
对于每个查询,你的任务是判断执行操作后能否让 s 变成一个 回文串 。
每个查询与其他查询都是 独立的 。
请你返回一个下标从 0 开始的数组 answer ,如果第 i 个查询执行操作后,可以将 s 变为一个回文串,那么 answer[i] = true,否则为 false 。
- 子字符串 指的是一个字符串中一段连续的字符序列。
- s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。
测试样例:
输入:s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
输出:[true,true]
解释:- a0 = 1, b0 = 1, c0 = 3, d0 = 5
- 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
- 为了让 s 变为回文串,s[3:5] 可以重新排列得到 => abccba 。
- 现在 s 是一个回文串。所以 answer[0] = true 。
第二个查询:
- a1 = 0, b1 = 2, c1 = 5, d1 = 5.
- 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
- 为了让 s 变为回文串,s[0:2] 可以重新排列得到 => cbaabc 。
- 现在 s 是一个回文串,所以 answer[1] = true 。
解答:这道题目,难在编程上。需要很细心(多WA几次,就知道需要考虑的场景了。。。)。因为这个条件0 <= ai <= bi < n / 2,n / 2 <= ci <= di < n。我们可以知道,query的区间必然不重叠。又因为我们需要知道字符串是否可以变成回文,所以我们需要把ci和di映射回去,变成mci和mdi。映射关系为 mp = len - 1 - p。
- 如果映射回去的区间和原来a, b完全没有重叠,或者是一个字区间的关系,这种情况还是比较简单的,我们只要比较不能变动的范围内是否是回文字符串,同时可以变动的区间,字母数前缀和一致。
- 否则,我们需要判断重叠区间的长度,并且判断a,b和mc,md的超级区间是否前缀和一致。最后非重叠部分的字符,也能出现在区间内。
class Solution {
public class RollingHash61 {
static final long mod = (1L << 61) - 1;
public long M;
public long[] pows;
public long[] hs;
public int hp;
public RollingHash61(long M, int n) {
assert M > 0;
assert n > 0;
this.M = M;
this.pows = makePows(M, n);
this.hs = new long[n + 1];
this.hp = 0;
}
public long mul(long a, long b) {
long al = a & (1L << 31) - 1, ah = a >>> 31;
long bl = b & (1L << 31) - 1, bh = b >>> 31;
long low = al * bl;
long mid = al * bh + bl * ah;
long high = ah * bh + (mid >>> 31);
long ret = mod(mod(2 * high + low) + ((mid & (1L << 31) - 1) << 31));
return ret;
}
public long mod(long a) {
while (a >= mod) a -= mod;
while (a < 0) a += mod;
return a;
}
private long[] makePows(long M, int n) {
long[] ret = new long[n + 1];
ret[0] = 1;
for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], M);
return ret;
}
public void add(long x) {
hs[hp + 1] = mul(hs[hp], M) + x;
if (hs[hp + 1] >= mod) hs[hp + 1] -= mod;
hp++;
}
public long h(int l, int r) {
assert l <= r;
return mod(hs[r] - mul(hs[l], pows[r - l]));
}
}
private static final int mod = 1_000_000_007;
public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
int len = s.length();
int mid = len / 2;
RollingHash61 left = new RollingHash61(mod, mid), right = new RollingHash61(mod, mid);
int[][] charMem = new int[len + 1][26];
for (int i = 0; i < len; ++i) {
int o = s.charAt(i) - 'a';
if (i < len / 2) {
left.add(o);
right.add(s.charAt(len - i - 1) - 'a');
}
for (int j = 0; j < 26; ++j) {
charMem[i + 1][j] = charMem[i][j];
if (j == o) {
charMem[i + 1][j] += 1;
}
}
}
boolean[] res = new boolean[queries.length];
for (int i = 0; i < queries.length; ++i) {
int a = queries[i][0], b = queries[i][1], c = queries[i][2], d = queries[i][3];
int mc = len - 1 - d, md = len - 1 - c;
boolean unMovedEqu;
if (isColl(a, b, mc, md)) {
int ml = Math.min(a, mc), mr = Math.max(b, md);
unMovedEqu = left.h(0, ml) == right.h(0, ml) && left.h(mr + 1, mid) == right.h(mr + 1, mid);
if (unMovedEqu) {
if ((ml == a && mr == b) || (ml == mc && mr == md)) {
unMovedEqu = diffNum(charMem, ml, mr, len) == 0;
} else {
int shared = Math.min(b, md) - Math.max(mc, a) + 1;
unMovedEqu = diffNum(charMem, ml, mr, len) == 0 && diffNum(charMem, a, b, len) <= shared;
if (unMovedEqu) {
if (a < mc) {
unMovedEqu = diffNumLarge(charMem, a, b, a, mc - 1, len)
&& diffNumLarge(charMem, c, d, b + 1, md, len);
} else {
unMovedEqu = diffNumLarge(charMem, a, b, md + 1, b, len)
&& diffNumLarge(charMem, c, d, mc, a - 1, len);
}
}
}
}
} else {
int[] ml = {Math.min(a, mc), Math.min(b, md)}, mr = {Math.max(a, mc), Math.max(b, md)};
unMovedEqu = left.h(0, ml[0]) == right.h(0, ml[0]) && left.h(ml[1] + 1 , mr[0]) == right.h(ml[1] + 1 , mr[0])
&& left.h(mr[1] + 1, mid) == right.h(mr[1] + 1, mid);
if (unMovedEqu) {
unMovedEqu = diffNum(charMem, a, b, len) == 0 && diffNum(charMem, c, d, len) == 0;
}
}
res[i] = unMovedEqu;
}
return res;
}
private boolean isColl(int a, int b, int c, int d) {
return !(a > d || b < c);
}
private int diffNum(int[][] charMem, int l, int r, int len) {
int mc = len - 1 - r, md = len - 1 - l;
int add = 0;
for (int i = 0; i < 26; ++i) {
int n1 = charMem[r + 1][i] - charMem[l][i];
int n2 = charMem[md + 1][i] - charMem[mc][i];
if (n1 > n2) {
add += n1 - n2;
}
}
return add;
}
private boolean diffNumLarge(int[][] charMem, int l1, int r1, int l2, int r2, int len) {
int t = len - 1 - r2;
r2 = len - 1 - l2;
l2 = t;
for (int i = 0; i < 26; ++i) {
int n1 = charMem[r1 + 1][i] - charMem[l1][i];
int n2 = charMem[r2 + 1][i] - charMem[l2][i];
if (n1 < n2) {
return false;
}
}
return true;
}
}