6-周赛332总结-阿里云开发者社区

6-周赛332总结

过了Q1和Q2，Q2知道用二分但是边界处理的不是很好，迷迷糊糊过的（手动再移动了下返回值…）

Q3知道将子字符串的值取出来，将最短位置放在哈希表中，然后异或在哈希表中找值。但是我这

个猪头脑袋直接将值用Integer.parseInt(s)取值，然后右移取余，移了大半天，很蠢就是了…然后就没有时间做第四题了

继续努力继续努力

下文为自己的题解总结，参考其他题解写成，取其精华，做以笔记，如有描述不清楚或者错误麻烦指正，不胜感激，不喜勿喷！

找出数组的串联值【LC2562】

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的串联是由这两个数值串联起来形成的新数字。

例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

思路：使用双指针匹配数组中的元素，并将元素进行串联，累加至结果中，直至数组中没有元素剩余
如果前后指针指向同个元素，直接将值累加至结果
如果前后指针指向两个元素nums1,那么串联值为n u m 1 ∗ n u m s 2 的位数 + n u m s 2

实现

class Solution {
    public long findTheArrayConcVal(int[] nums) {
        int l = 0, r = nums.length - 1;
        long res = 0L;
        while (l <= r){
            if (l == r){
                res += nums[l];
                break;
            }else{
                int n = getN(nums[r]);
                res += Math.pow(10, n) * nums[l] + nums[r];
                l++;
                r--;
            }
        }
        return res;
    }
    public int getN(int num){
        int n = 0;
        while (num != 0){
            num /= 10;
            n++;
        }
        return n;
    }
}

复杂度

时间复杂度：O ( n )

空间复杂度：O ( 1 )

统计公平数对的数目【LC2563】

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且

lower <= nums[i] + nums[j] <= upper

思路：二分查找

将数组按顺序排序后，枚举每一个nums[i],那么在nums[0,i)范围内，使用二分查找另一个数小于lower−nums[i]或者小于等于u p p e r − n u m s [ i ] 的个数，记为left和right，那么符合条件的公平数对为r i g h t − l e f t

可以转换为使用二分查找另一个数大于等于l o w e r − n u m s [ i ] l或者大于u p p e r − n u m s [ i ] ]的第一个数的下标

可以转换为使用二分查找另一个数大于等于l o w e r − n u m s [ i ] 或者大于等于u p p e r − n u m s [ i ] + 1的第一个数的下标

实现

注意：二分查找指定范围内第一个大于等于target的数的下标，左闭右闭

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long res = 0L;
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 1; i < n; i++){
            int left = binarySearch(nums, lower - nums[i], i - 1);// 第一个大于等于 lower - nums[i] 的下标
            int right = binarySearch(nums, upper - nums[i] + 1, i - 1);// 第一个大于等于high nums[i]的下标[0, i - 1] 
            res += right - left;
        }
        return res;       
    }
    // 返回第一个大于等于target的下标
    public int binarySearch(int[] nums, int target, int r){
        int l = 0;// 左闭右闭
        while (l <= r){
            int mid = (l + r) >>> 1;
            if (nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
}

复杂度

时间复杂度：O ( n l o g n )

空间复杂度：O ( 1 )

子字符串异或查询【LC2564】

给你一个 二进制字符串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 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

思路：

首先进行预处理，将二进制字符串所有子字符串对应的十进制整数值存储在哈希表中，哈希表记录该值对应的最短子字符串的起始位置和终止位置

然后遍历循环数组查找结果：根据异或性质，当哈希表中存在值为val = firsti ^ secondi 时，对于第i ii个查询可以找到答案，答案即为哈希表的key值

实现

注意：由于数值大小，因此，我们可以只需要计算 s 中所有长度不超过 30的子字符串即可

class Solution {
    public int[][] substringXorQueries(String s, int[][] queries) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int m = queries.length;
        int[][] res = new int[m][2];
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < m; i++){
            Arrays.fill(res[i], -1);
        }        
        for (int l = 0; l < n; l++){
            int num = 0;
            for (int r = l; r < Math.min(l + 30, n); r++){
                num = (num << 1) + chars[r] - '0';
                if (!map.containsKey(num) || map.get(num)[1] - map.get(num)[0]  > r - l){
                    map.put(num, new int[]{l, r});
                }
            }
        }
        for (int i = 0; i < m; i++){
            int target = (queries[i][0] ^ queries[i][1]);
            if (map.containsKey(target)){
                res[i] = map.get(target);
            }
        }
        return res;
    }
}

最少得分子序列【LC2565】

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

令 left 为删除字符中的最小下标。

令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "***a\***b***c\***d***e\***" 的子序列，但是 "aec" 不是）。

class Solution {
    public int minimumScore(String s, String t) {
        int n = s.length(), m = t.length();
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >= 0; i--){
            if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;
            suf[i] = j + 1;
        }
        int res = suf[0];
        if (suf[0] == 0) return res;// t是s的子序列
        pre[0] = -1;
        for (int i = 1; i <= n; i++){
            if (s.charAt(i - 1) == t.charAt(pre[i - 1] + 1)){
                pre[i] = pre[i - 1] + 1;
            }else{
                pre[i] = pre[i - 1];
            }
            res = Math.min(res, suf[i] - pre[i] - 1);
        }
        return res;
    }
}

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

优化：前缀数组可以用变量代替

class Solution {
    public int minimumScore(String s, String t) {
        int n = s.length(), m = t.length();
        int[] suf = new int[n + 1];
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >= 0; i--){
            if (j >= 0 && s.charAt(i) == t.charAt(j)) j--;
            suf[i] = j + 1;
        }
        int res = suf[0];
        if (suf[0] == 0) return res;// t是s的子序列
        int pre = -1;
        for (int i = 1; i <= n; i++){
            if (s.charAt(i - 1) == t.charAt(pre + 1)){
                pre += + 1;
            }
            res = Math.min(res, suf[i] - pre - 1);
        }
        return res;
    }
}

6-周赛332总结