LeetCode 332周赛


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 = 11 是能得到的最小得分。
示例 2:

输入:s = "cde", t = "xyz"
输出:3
解释:这个例子中,我们将下标为 012 处的字符 "x""y""z" 删除(下标从 0 开始)。
字符串变成 "" ,它是字符串 "cde" 的子序列,得分为 2 - 0 + 1 = 33 是能得到的最小得分。
 
提示:
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;
    }
}

  目录