6354. 找出数组的串联值
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
例如,15 和 49 的串联是 1549 。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空:
如果 nums 中存在不止一个数字,分别选中 nums 中的第一个元素和最后一个元素,将二者串联得到的值加到 nums 的 串联值 上,然后从 nums 中删除第一个和最后一个元素。
如果仅存在一个元素,则将该元素的值加到 nums 的串联值上,然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
解答:双指针
class Solution {
public long findTheArrayConcVal(int[] nums) {
long res=0;
int l=0,r=nums.length-1;
while(l<=r){
if(l!=r){
res+=help(nums[l]*1L,nums[r]*1L);
}
else res+=nums[l];
l++;r--;
}
return res;
}
long help(long a,long b){
String s=String.valueOf(b);
int len=s.length();
a*=(int)Math.pow(10,len);
return a+b;
}
}
6355. 统计公平数对的数目
给你一个下标从 0 开始、长度为 n 的整数数组 nums ,和两个整数 lower 和 upper ,返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况,则认为它是一个 公平数对 :
0 <= i < j < n,且
lower <= nums[i] + nums[j] <= upper
解答:排序+双指针
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. 子字符串异或查询
给你一个 二进制字符串 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 个查询的答案。
子字符串 是一个字符串中一段连续非空的字符序列。
示例 1:
输入: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] 。
示例 2:
输入:s = "0101", queries = [[12,8]]
输出:[[-1,-1]]
解释:这个例子中,没有符合查询的答案,所以返回 [-1,-1] 。
示例 3:
输入:s = "1", queries = [[4,5]]
输出:[[0,0]]
解释:这个例子中,端点为 [0,0] 的子字符串对应的十进制值为 1 ,且 1 ^ 4 = 5 。所以答案为 [0,0] 。
解答:哈希表+遍历,这道题是一道脑筋急转弯的题目,看着搜索空间很大,其实有一个重要的提示:
- 0 <= firsti, secondi <= 10^9
所以每个s的位置记录向前的31位数字就可以了。
class Solution {
public int[][] substringXorQueries(String s, int[][] queries) {
int n=s.length();
Map<Long,int[]> map=new HashMap<>();
for(int i=0;i<n;i++){
long sum=0,t=1;
for(int j=i;j>=0;j--){
int a=s.charAt(j)-'0';
sum+=a*t;
t*=2;
if(sum>=Integer.MAX_VALUE){
break;
}
else if(!map.containsKey(sum)){
map.put(sum,new int[]{j,i});
}
}
}
int[][] res=new int[queries.length][];
for(int i=0;i<queries.length;i++){
int[] q=queries[i];
long num=q[0]^q[1];
res[i]=map.getOrDefault(num,new int[]{-1,-1});
}
return res;
}
}
2565. 最少得分子序列
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符,那么得分为 0 ,否则:
令 left 为删除字符中的最小下标。
令 right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后(也可以一个也不删除),剩余字符不改变顺序
得到的字符串。(比方说 "ace" 是 "abcde" 的子序列,但是 "aec" 不是)。
示例 1:
输入:s = "abacaba", t = "bzaa"
输出:1
解释:这个例子中,我们删除下标 1 处的字符 "z" (下标从 0 开始)。
字符串 t 变为 "baa" ,它是字符串 "abacaba" 的子序列,得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
示例 2:
输入:s = "cde", t = "xyz"
输出:3
解释:这个例子中,我们将下标为 0, 1 和 2 处的字符 "x" ,"y" 和 "z" 删除(下标从 0 开始)。
字符串变成 "" ,它是字符串 "cde" 的子序列,得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。
提示:
1 <= s.length, t.length <= 105
s 和 t 都只包含小写英文字母。
解答:前后缀和+双指针
class Solution {
//前后缀和+双指针
public int minimumScore(String s, String t) {
int m=s.length(),n=t.length();
int[] suf=new int[m+1];
//统计后缀和
suf[m]=n;
for(int i=m-1,j=n-1;i>=0;i--){
if(j>=0&&s.charAt(i)==t.charAt(j))j--;
suf[i]=j+1;
}
int res=suf[0];
if(res==0)return 0;
//统计前缀和
for(int i=0,j=0;i<m;i++){
//后缀和-前缀和-1;
//j:前缀和
// 注意 j 不会等于 m,因为上面 suf[0]>0 表示 t 不是 s 的子序列
if(s.charAt(i)==t.charAt(j)){
res=Math.min(res,suf[i+1] - ++j);
}
}
return res;
}
}