宣传型网站,给自己做网站,东莞做微网站建设价格,知果果网站谁做的文章目录 周赛372[2937. 使三个字符串相等](https://leetcode.cn/problems/make-three-strings-equal/)模拟#xff08;正难则反#xff09; [2938. 区分黑球与白球](https://leetcode.cn/problems/separate-black-and-white-balls/)枚举 贪心 [2939. 最大异或乘积](https:/… 文章目录 周赛372[2937. 使三个字符串相等](https://leetcode.cn/problems/make-three-strings-equal/)模拟正难则反 [2938. 区分黑球与白球](https://leetcode.cn/problems/separate-black-and-white-balls/)枚举 贪心 [2939. 最大异或乘积](https://leetcode.cn/problems/maximum-xor-product/)位运算 - 异或性质 [2940. 找到 Alice 和 Bob 可以相遇的建筑](https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/)离线 单调栈 周赛372
2937. 使三个字符串相等
简单
给你三个字符串 s1、s2 和 s3。 你可以根据需要对这三个字符串执行以下操作 任意次数 。
在每次操作中你可以选择其中一个长度至少为 2 的字符串 并删除其 最右位置上 的字符。
如果存在某种方法能够使这三个字符串相等请返回使它们相等所需的 最小 操作次数否则返回 -1。
示例 1
输入s1 abcs2 abbs3 ab
输出2
解释对 s1 和 s2 进行一次操作后可以得到三个相等的字符串。
可以证明不可能用少于两次操作使它们相等。示例 2
输入s1 dacs2 bacs3 cac
输出-1
解释因为 s1 和 s2 的最左位置上的字母不相等所以无论进行多少次操作它们都不可能相等。因此答案是 -1 。提示
1 s1.length, s2.length, s3.length 100s1、s2 和 s3 仅由小写英文字母组成。
模拟正难则反
class Solution {/**要求三个字符串相等删除比较困难则直接从i0开始比较字符是否相等*/public int findMinimumOperations(String s1, String s2, String s3) {int minlen Math.min(s1.length(), Math.min(s2.length(), s3.length()));int res 0;int samepos 0;for(; samepos minlen; samepos){if(s1.charAt(samepos) ! s2.charAt(samepos) ||s1.charAt(samepos) ! s3.charAt(samepos)){break;}}if(samepos 0) return -1;return s1.length() - samepos s2.length() - samepos s3.length() - samepos;}
}比赛写的正的丑陋代码
class Solution {public int findMinimumOperations(String s1, String s2, String s3) {String[] strs new String[3];strs[0] s1;strs[1] s2;strs[2] s3;Arrays.sort(strs, (a, b) - a.length() - b.length());int cnt 0, len strs[0].length();if(strs[0].length() ! strs[2].length()){int tmp strs[2].length();cnt tmp - len;strs[2] strs[2].substring(0, len);}if(strs[0].length() ! strs[1].length()){int tmp strs[1].length();cnt tmp - len;strs[1] strs[1].substring(0, len);}while(len 0 (!strs[0].equals(strs[1]) || !strs[0].equals(strs[2]))){len - 1;strs[0] strs[0].substring(0, len);strs[1] strs[1].substring(0, len);strs[2] strs[2].substring(0, len);cnt 3;}if(len 0) return -1;return cnt;}
}2938. 区分黑球与白球
中等
桌子上有 n 个球每个球的颜色不是黑色就是白色。
给你一个长度为 n 、下标从 0 开始的二进制字符串 s其中 1 和 0 分别代表黑色和白色的球。
在每一步中你可以选择两个相邻的球并交换它们。
返回「将所有黑色球都移到右侧所有白色球都移到左侧所需的 最小步数」。
示例 1
输入s 101
输出1
解释我们可以按以下方式将所有黑色球移到右侧
- 交换 s[0] 和 s[1]s 011。
最开始1 没有都在右侧需要至少 1 步将其移到右侧。示例 2
输入s 100
输出2
解释我们可以按以下方式将所有黑色球移到右侧
- 交换 s[0] 和 s[1]s 010。
- 交换 s[1] 和 s[2]s 001。
可以证明所需的最小步数为 2 。示例 3
输入s 0111
输出0
解释所有黑色球都已经在右侧。提示
1 n s.length 105s[i] 不是 0就是 1。
枚举 贪心
class Solution {/**倒序枚举什么时候会将黑色球进行移动当枚举到i位时是黑球就要移动到靠近黑球的位置移动几次 i右边白球出现的次数*/public long minimumSteps(String s) {long res 0;int cntw 0, n s.length();for(int i n-1; i 0; i--){if(s.charAt(i) 0){cntw 1;continue;}res cntw;}return res;}
}2939. 最大异或乘积
中等
给你三个整数 a b 和 n 请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 x 2n。
由于答案可能会很大返回它对 109 7 取余 后的结果。
注意XOR 是按位异或操作。
示例 1
输入a 12, b 5, n 4
输出98
解释当 x 2 时(a XOR x) 14 且 (b XOR x) 7 。所以(a XOR x) * (b XOR x) 98 。
98 是所有满足 0 x 2n 中 (a XOR x) * (b XOR x) 的最大值。示例 2
输入a 6, b 7 , n 5
输出930
解释当 x 25 时(a XOR x) 31 且 (b XOR x) 30 。所以(a XOR x) * (b XOR x) 930 。
930 是所有满足 0 x 2n 中 (a XOR x) * (b XOR x) 的最大值。示例 3
输入a 1, b 6, n 3
输出12
解释 当 x 5 时(a XOR x) 4 且 (b XOR x) 3 。所以(a XOR x) * (b XOR x) 12 。
12 是所有满足 0 x 2n 中 (a XOR x) * (b XOR x) 的最大值。提示
0 a, b 2500 n 50
位运算 - 异或性质 https://leetcode.cn/problems/maximum-xor-product/solutions/2532915/o1-zuo-fa-wei-yun-suan-de-qiao-miao-yun-lvnvr/ class Solution {/**位运算 (a XOR x) * (b XOR x) 1. a和b 对于同一个比特位 如果一个是0 另一个是1那么无论x填0还是1这个比特位的结果总是0或者12. 推论1 在把同为 0 的比特位 改成 1 后1 的总数是不变的3. 推论2 ax a^x ; bx b^x ax bx 是一个定值 问题转化为在 ax bx是一个定值的情况下求 ax * bx 的最大值均值定理 基本不等式 让 ax 和 bx 尽量接近差的绝对值尽量小分配方案如果大于等于n的比特位 ab那么把最高位的1给ax其余的1给bx如果大于等于n的比特位 ab那么把低于n的1都给b*/public int maximumXorProduct(long a, long b, int n) {if (a b) {// 保证 a blong temp a;a b;b temp;}long mask (1L n) - 1;long ax a ~mask; // 第 n 位及其左边无法被 x 影响先算出来long bx b ~mask;a mask; // 低于第 n 位能被 x 影响b mask;long left a ^ b; // 可分配a XOR x 和 b XOR x 一个是 1 另一个是 0long one mask ^ left; // 无需分配a XOR x 和 b XOR x 均为 1ax | one; // 先加到异或结果中bx | one;// 现在要把 left 分配到 ax 和 bx 中// 根据基本不等式均值定理分配后应当使 ax 和 bx 尽量接近乘积才能尽量大if (left 0 ax bx) {// 尽量均匀分配例如把 1111 分成 1000 和 0111long highBit 1L (63 - Long.numberOfLeadingZeros(left));ax | highBit;left ^ highBit;}// 如果 a ~mask 更大则应当全部分给 bx注意最上面保证了 abbx | left;final long MOD 1_000_000_007;return (int) (ax % MOD * (bx % MOD) % MOD); // 注意不能直接 long * long否则溢出}
}2940. 找到 Alice 和 Bob 可以相遇的建筑
困难
给你一个下标从 0 开始的正整数数组 heights 其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i 且存在 i j 的建筑 j 满足 heights[i] heights[j] 那么这个人可以移动到建筑 j 。
给你另外一个数组 queries 其中 queries[i] [ai, bi] 。第 i 个查询中Alice 在建筑 ai Bob 在建筑 bi 。
请你能返回一个数组 ans 其中 ans[i] 是第 i 个查询中Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i Alice 和 Bob 不能相遇令 ans[i] 为 -1 。
示例 1
输入heights [6,4,8,5,2,7], queries [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出[2,5,-1,5,2]
解释第一个查询中Alice 和 Bob 可以移动到建筑 2 因为 heights[0] heights[2] 且 heights[1] heights[2] 。
第二个查询中Alice 和 Bob 可以移动到建筑 5 因为 heights[0] heights[5] 且 heights[3] heights[5] 。
第三个查询中Alice 无法与 Bob 相遇因为 Alice 不能移动到任何其他建筑。
第四个查询中Alice 和 Bob 可以移动到建筑 5 因为 heights[3] heights[5] 且 heights[4] heights[5] 。
第五个查询中Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] ! -1 ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] -1 不存在 Alice 和 Bob 可以相遇的建筑。示例 2
输入heights [5,3,8,2,6,1,4,6], queries [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出[7,6,-1,4,6]
解释第一个查询中Alice 可以直接移动到 Bob 的建筑因为 heights[0] heights[7] 。
第二个查询中Alice 和 Bob 可以移动到建筑 6 因为 heights[3] heights[6] 且 heights[5] heights[6] 。
第三个查询中Alice 无法与 Bob 相遇因为 Bob 不能移动到任何其他建筑。
第四个查询中Alice 和 Bob 可以移动到建筑 4 因为 heights[3] heights[4] 且 heights[0] heights[4] 。
第五个查询中Alice 可以直接移动到 Bob 的建筑因为 heights[1] heights[6] 。
对于 ans[i] ! -1 ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] -1 不存在 Alice 和 Bob 可以相遇的建筑。提示
1 heights.length 5 * 1041 heights[i] 1091 queries.length 5 * 104queries[i] [ai, bi]0 ai, bi heights.length - 1
离线 单调栈 https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/solutions/2533058/chi-xian-zui-xiao-dui-pythonjavacgo-by-e-9ewj/ class Solution {/**给定一组询问通常可思考离线做法将询问分组按某一种顺序进行回答题意左边矮跳到右边高分类讨论 对于每个询问 i 和 j假设 i j1. 如果 i j答案就是 j2. 如果 heights[i] heights[j], i 可以直接跳到j答案就是j3. 如果 heights[i] heights[j],左边高右边矮怎么跳按照j分类 [0,1],[0,3],[2,4],[3,4],[2,2]j 1 [0, 1]j 2 无需回答答案就是2j 3 [0, 3]j 4 [2, 4],[3, 4]整理好询问后从左到右遍历建筑如果发现当前 idx 建筑高度 之前需要回答的一个询问的建筑高度那么这个询问的答案就是 idx需要一个最小堆去维护这些询问每次取出最小的 heights[i]去和 heights[idx] 比较如果 heights[i] heights[idx] 就立刻回答 (答案就是 idx)最后堆中剩下的询问 答案都是-1*/public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int[] ans new int[queries.length];Arrays.fill(ans, -1);Listint[][] left new ArrayList[heights.length];Arrays.setAll(left, e - new ArrayList());for(int qi 0; qi queries.length; qi){int i queries[qi][0], j queries[qi][1];if(i j){ // 保证 i jint tmp i; i j; j tmp;}if(i j || heights[i] heights[j]){ans[qi] j; // i 直接跳到 j}else{left[j].add(new int[]{heights[i], qi});}}PriorityQueueint[] pq new PriorityQueue((a, b) - a[0] - b[0]);for (int i 0; i heights.length; i) { // 从小到大枚举下标 iwhile (!pq.isEmpty() pq.peek()[0] heights[i]) {ans[pq.poll()[1]] i; // 可以跳到 i此时 i 是最小的}for (int[] p : left[i]) {pq.offer(p); // 后面再回答}}return ans;}
}
