6354. Find the Array Concatenation Value
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
- 例如，15 和 49 的串联是 1549 。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：
- 如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
- 如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
测试样例
输入：nums = [7,52,2,4]
输出：596
解释：
在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 。
- 在第一步操作中：我们选中第一个元素 7 和最后一个元素 4 。二者的串联是 74 ，将其加到串联值上，所以串联值等于 74 。接着我们从 nums 中移除这两个元素，所以 nums 变为 [52,2] 。
- 在第二步操作中：
我们选中第一个元素 52 和最后一个元素 2 。
二者的串联是 522 ，将其加到串联值上，所以串联值等于 596 。
接着我们从 nums 中移除这两个元素，所以 nums 变为空。
由于串联值等于 596 ，所以答案就是 596 。
解答：按照题意，利用双指针硬编码即可。
class Solution {
public long findTheArrayConcVal(int[] nums) {
long res = 0;
int l = 0, r = nums.length - 1;
while (l <= r) {
if (l == r) {
res += concate(nums[l], - 1);
} else {
res += concate(nums[l], nums[r]);
}
++l;
--r;
}
return res;
}
private long concate(int f, int l) {
String tmp = String.valueOf(f);
if (l != -1) {
tmp += String.valueOf(l);
}
return Long.valueOf(tmp);
}
}6355. Count the Number of Fair Pairs
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
- 0 <= i < j < n，且
- lower <= nums[i] + nums[j] <= upper
测试样例：
输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：
共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
解答: 如果是用队列原来的循序搜索其实蛮困难的。所以我们首先利用排序，然后利用双指针搜索满足要求的区间。
class Solution {
public long countFairPairs(int[] nums, int lower, int upper) {
Arrays.sort(nums);
int l = nums.length - 1, r = nums.length - 1;
long res = 0;
for (int i = 0; i < nums.length; ++i) {
l = Math.max(i, l);
while (l > i && nums[i] + nums[l] >= lower) {
--l;
}
while (r > i && nums[i] + nums[r] > upper) {
--r;
}
if (r - l >= 0) {
res += (r - l);
} else {
break;
}
}
return res;
}
}6356. Substring XOR Queries
给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。
对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。
第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。
请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。
子字符串 是一个字符串中一段连续非空的字符序列。
测试样例
输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：
第一个查询，端点为 [0,2] 的子字符串为 "101" ，对应十进制数字 5 ，且 5 ^ 0 = 5 ，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11" ，对应十进制数字 3 ，且 3 ^ 1 = 2 。所以第二个查询的答案为 [2,3] 。
解答：这道题是一道脑筋急转弯的题目，看着搜索空间很大，其实有一个重要的提示：
- 0 <= firsti, secondi <= 10^9
所以每个s的位置记录向前的31位数字就可以了。这个时候最多保存31 * s.length()的数字。为了避免手贱溢出，我直接就用了Long了
class Solution {
private static final int[] noExist = {-1,-1};
public int[][] substringXorQueries(String s, int[][] queries) {
HashMap<Long, int[]> map = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
long tmp = 0, mul = 1;
for (int j = i; j >= 0; --j) {
tmp += mul * (s.charAt(j) - '0');
mul *= 2;
if (tmp >= Integer.MAX_VALUE) {
break;
} else if (!map.containsKey(tmp)) {
map.put(tmp, new int[]{j, i});
}
}
}
int[][] res = new int[queries.length][];
for (int i = 0; i < queries.length; ++i) {
long tmp = queries[i][1] ^ queries[i][0];
res[i] = map.getOrDefault(tmp, noExist);
}
return res;
}
}6357. Subsequence With the Minimum Score
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：
- 令 left 为删除字符中的最小下标。
- 令 right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "abcde" 的子序列，但是 "aec" 不是）。
测试样例
输入：s = "abacaba", t = "bzaa"
输出：1
解释：
这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。
字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
解答：这道题目又是一道脑筋急转弯的题目。如果需要right - left + 1最小，换个思路就是让right尽量的小，left尽量的大。那么这道题目可以换成2部分
- 从t的最后一个字符开始，逐步往前添加(right逐渐减小)，查看最多可以覆盖多少个前缀字符(贪婪，寻找最大left)
- 从t的第一个一个字符开始，逐步往后添加(left逐渐增大)，查看最多可以覆盖多少个后缀字符(贪婪，寻找最小right)
这道题目的code写的着实很烂，search1和search2完全硬编码实现了2个搜索。之后我有空的时候，会重写一下这道题目。
class Solution {
public int minimumScore(String s, String t) {
return Math.min(serach1(s, t), serach2(s, t));
}
private int serach1(String s, String t) {
int sl = s.length(), tl = t.length();
TreeMap<Integer, Integer> search = new TreeMap<>();
int sp = 0;
for (int i = 0; i < tl; ++i) {
char c = t.charAt(i);
while (sp < sl && s.charAt(sp) != c) {
++sp;
}
if (sp >= sl) break;
else search.put(sp++, i);
}
int min = tl;
sp = sl - 1;
for (int i = tl - 1; i >= 0; --i) {
char c = t.charAt(i);
while (sp >= 0 && s.charAt(sp) != c) {
--sp;
}
if (sp < 0) break;
else {
Map.Entry<Integer, Integer> lower = search.lowerEntry(sp--);
if (lower == null) {
min = Math.min(min, i);
} else {
min = Math.min(min, Math.max(0, i - lower.getValue() - 1));
}
}
}
return min;
}
private int serach2(String s, String t) {
int sl = s.length(), tl = t.length();
TreeMap<Integer, Integer> search = new TreeMap<>();
int sp = sl - 1;
for (int i = tl - 1; i >= 0; --i) {
char c = t.charAt(i);
while (sp >= 0 && s.charAt(sp) != c) {
--sp;
}
if (sp < 0) break;
else search.put(sp--, i);
}
int min = tl;
sp = 0;
for (int i = 0; i < tl; ++i) {
char c = t.charAt(i);
while (sp < sl && s.charAt(sp) != c) {
++sp;
}
if (sp >= sl) break;
else {
Map.Entry<Integer, Integer> higher = search.higherEntry(sp++);
if (higher == null) {
min = Math.min(min, tl - i - 1);
} else {
min = Math.min(min, Math.max(0, higher.getValue() - i - 1));
}
}
}
return min;
}
}