本文主要是介绍周赛372(正难则反、枚举+贪心、异或位运算、离线+单调栈),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 周赛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 = "abc",s2 = "abb",s3 = "ab"
输出:2
解释:对 s1 和 s2 进行一次操作后,可以得到三个相等的字符串。
可以证明,不可能用少于两次操作使它们相等。
示例 2:
输入:s1 = "dac",s2 = "bac",s3 = "cac"
输出:-1
解释:因为 s1 和 s2 的最左位置上的字母不相等,所以无论进行多少次操作,它们都不可能相等。因此答案是 -1 。
提示:
1 <= s1.length, s2.length, s3.length <= 100
s1
、s2
和s3
仅由小写英文字母组成。
模拟(正难则反)
class Solution {/**要求三个字符串相等,删除比较困难则直接从i=0开始比较字符是否相等*/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 <= 105
s[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 < 250
0 <= 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的比特位 a=b,那么把最高位的1给ax,其余的1给bx如果大于等于n的比特位 a>b,那么把低于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(注意最上面保证了 a>=b)bx |= 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 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[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);List<int[]>[] 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});}}PriorityQueue<int[]> 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;}
}
这篇关于周赛372(正难则反、枚举+贪心、异或位运算、离线+单调栈)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!