leetcodeapp（LeetCode_单周赛_332）

6354. 找出数组的串联值

题意

将数组首尾元素接在一起    
    
    
  ，就是串联值   
    
    
    
。

串联之后删除    


     


     


     
，如果只剩下一个元素




 




 




 




，加上这个元素即可

双指针   

   

   

 ，从首和尾向中间移动即可

code

注意：

用 long

没看题目用了 int wa了一发 class Solution { public long findTheArrayConcVal(int[] nums) { int n = nums.length; int l = 0, r = n - 1; long ans = 0; while (l < r) { String s = ""; s += nums[l++]; s += nums[r--]; ans += Integer.parseInt(s); } if (l == r) ans += nums[l]; return ans; } }

6355. 统计公平数对的数目

题意

给定 lower 和 upper 找到 数组中 两个不同的数字     

     

     

     ，如果满足 lower <= nums[i] + nums[j] <= upper 就是一组公平数对


     


     


     


  。

求公平数对的个数

我们枚举每个 nums[i] 将 lower <= nums[i] + nums[j] <= upper 变形为：lower - nums[i] <= nums[j] <= upper - nums[i]

所以我们二分找到 第一个大于 upper - nums[i] 的位置




  




  




  




，和 第一个 大于等于 lower- nums[i] 的位置前者减去后者即可得到差 




 




 




 
。

对应的 c++中的函数就是 uppper_bound 和 lower_bound
  


  


  


，Java中么有这俩函数     
     
     
     ，我们自己写一个

并且 




   




   




   



，我们求的是数对

 



 



 



，有重复的                   ，为防止重复  




    




    




    


，我们只搜索下标为 i 的数的 左边的数

















，也避免了 i 被统计进去的情况

code

class Solution { public long countFairPairs(int[] nums, int lower, int upper) { long ans = 0; int n = nums.length; Arrays.sort(nums); // lower <= nums[i] + nums[j] <= upper // 枚举 nums[i] 找 j // lower - nums[i] <= nums[j] <= upper - nums[i] for (int i = 0; i < n; i++) { int a = i, b = i; // upper_bound int l = 0, r = i - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] > upper - nums[i]) r = mid; else l = mid + 1; } if (nums[l] > upper - nums[i]) a = l; // a = l; // if (nums[a] <= upper - nums[i]) a = i; // lower_bound l = 0; r = i - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= lower - nums[i]) r = mid; else l = mid + 1; } if (nums[l] >= lower - nums[i]) b = l; // b = l; // if (nums[b] < lower - nums[i]) b = i; ans += a - b; } return ans; } }

6356. 子字符串异或查询

题意

要满足 val ^ firsti == secondi 等号两边同时 ^ first 得到 val = first ^ second

所以我们只要找 queries数组中的 first 和 second 异或值时候存在于 s 中

因为 异或并不会增加二进制位数                  ，0 <= firsti, secondi <= 109   



     



     



     

，小于 2^30 - 1


















，最多就 31 位    
    
    
  ，所以枚举的时候只需要枚举字符串的连续 30 个即可

s 是 1e4 时间复杂度最多就 1e4 * 30 = 3e5 足够的

后面枚举queries是 1e5

时间复杂度 = 4e5

用 map 预处理    


     


     


     
，存储 s 的二进制子串出现过的 十进制数字




 




 




 




，以及对应的 边界    

   

   

 ，要求存储长度最小的子串

code

class Solution { public int[][] substringXorQueries(String s, int[][] queries) { HashMap<Integer, int[]> mp = new HashMap<>(); int n = s.length(); char[] c = s.toCharArray(); for (int i = 0; i < n; i++) { int x = 0; for (int j = i; j < i + 30 && j < n; j++) { // 计算子串 x = (x << 1) | (c[j] - 0); if (!mp.containsKey(x) || (j - i < mp.get(x)[1] - mp.get(x)[0])) { mp.put(x, new int[]{i, j}); } } } ArrayList<int[]> a = new ArrayList<>(); for (var pr : queries) { int t = pr[0] ^ pr[1]; if (mp.getOrDefault(t, null) != null) a.add(new int[]{mp.get(t)[0], mp.get(t)[1]}); else a.add(new int[]{-1, -1}); } int len = a.size(); int[][] ans = new int[len][2]; for (int i = 0; i < len; i++) { ans[i] = a.get(i); } return ans; } }