建设企业网站流程,潍坊网站建设教程,网站备案的好处有哪些,网站无障碍建设6-周赛332总结
过了Q1和Q2#xff0c;Q2知道用二分但是边界处理的不是很好#xff0c;迷迷糊糊过的#xff08;手动再移动了下返回值…#xff09;
Q3知道将子字符串的值取出来#xff0c;将最短位置放在哈希表中#xff0c;然后异或在哈希表中找值。但是我这个猪头脑袋…6-周赛332总结
过了Q1和Q2Q2知道用二分但是边界处理的不是很好迷迷糊糊过的手动再移动了下返回值…
Q3知道将子字符串的值取出来将最短位置放在哈希表中然后异或在哈希表中找值。但是我这个猪头脑袋直接将值用Integer.parseInt(s)取值然后右移取余移了大半天很蠢就是了…然后就没有时间做第四题了
继续努力继续努力
下文为自己的题解总结参考其他题解写成取其精华做以笔记如有描述不清楚或者错误麻烦指正不胜感激不喜勿喷
找出数组的串联值【LC2562】 给你一个下标从 0 开始的整数数组 nums 。 现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。 例如15 和 49 的串联是 1549 。 nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空 如果 nums 中存在不止一个数字分别选中 nums 中的第一个元素和最后一个元素将二者串联得到的值加到 nums 的 串联值 上然后从 nums 中删除第一个和最后一个元素。如果仅存在一个元素则将该元素的值加到 nums 的串联值上然后删除这个元素。 返回执行完所有操作后 nums 的串联值。 思路使用双指针匹配数组中的元素并将元素进行串联累加至结果中直至数组中没有元素剩余 如果前后指针指向同个元素直接将值累加至结果如果前后指针指向两个元素nums1,nums2nums1,nums2nums1,nums2那么串联值为num1∗nums2的位数nums2num1*nums2的位数nums2num1∗nums2的位数nums2 实现 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(n)O(n)空间复杂度O(1)O(1)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)nums[0,i)nums[0,i)范围内使用二分查找另一个数小于lower−nums[i]lower-nums[i]lower−nums[i]或者小于等于upper−nums[i]upper-nums[i]upper−nums[i]的个数记为left和right那么符合条件的公平数对为right−leftright-leftright−left 可以转换为使用二分查找另一个数大于等于lower−nums[i]lower-nums[i]lower−nums[i]或者大于upper−nums[i]upper-nums[i]upper−nums[i]的第一个数的下标可以转换为使用二分查找另一个数大于等于lower−nums[i]lower-nums[i]lower−nums[i]或者大于等于upper−nums[i]1upper-nums[i]1upper−nums[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(nlogn)O(nlogn)O(nlogn)空间复杂度O(1)O(1)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 时对于第iii个查询可以找到答案答案即为哈希表的key值 实现 注意由于 数值大小10923010^92^{30}109230因此我们可以只需要计算 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];MapInteger, 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;}
} 复杂度 时间复杂度O(nlogUq)O(nlogU q)O(nlogUq)其中 nnn 为 s 的长度Umax(queries)Umax(queries)Umax(queries)qqq 为 queries 的长度。空间复杂度O(nlogU)O(nlogU)O(nlogU)
最少得分子序列【LC2565】 给你两个字符串 s 和 t 。 你可以从字符串 t 中删除任意数目的字符。 如果没有从字符串 t 中删除字符那么得分为 0 否则 令 left 为删除字符中的最小下标。令 right 为删除字符中的最大下标。 字符串的得分为 right - left 1 。 请你返回使 t 成为 s 子序列的最小得分。 一个字符串的 子序列 是从原字符串中删除一些字符后也可以一个也不删除剩余字符不改变顺序得到的字符串。比方说 ace 是 ***a\***b***c\***d***e\*** 的子序列但是 aec 不是。 思路 删除[left,right][left,right][left,right]之间的字符不会影响最终结果因为删除不影响得分并且更能让剩余字符成为s的子串因此可以视为删除子串【没想到】删除后t中剩余的字符为t[:,left),(right,:][:,left),(right,:][:,left),(right,:]。假设s的一个前缀字符串s[0,i]s[0,i]s[0,i]可以匹配该前缀字符串s的一个后缀字符串s[i1,:]s[i1,:]s[i1,:]可以匹配该后缀字符串那么表明t中剩余的字符是s的子序列得分为right−left1right-left1right−left1反而言之我们可以枚举iii求得s[0,i]s[0,i]s[0,i]能够匹配t的最长前缀字符串的结束位置下标l以及s[i1,:]s[i1,:]s[i1,:]能够匹配t的最长后缀字符串的开始位置r那么此时需要删除的位置即为[l1,r−1][l1,r-1][l1,r−1]得分为r−l−1r-l-1r−l−1取最小值返回节课 实现 预处理后缀数组suff[i]s的一个后缀字符串s[i,:]s[i,:]s[i,:]可以匹配t的最长后缀字符串的开始位置预处理前缀数组pre[i1]s的一个前缀字符串s[0,i]s[0,i]s[0,i]可以匹配t的最长前缀字符串的结束位置 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)O(n)空间复杂度O(n)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;}
}
