LeetCode | 周赛-372 做题记录
status
Published
slug
leetcode-week-372-record
type
Post
category
Technology
date
Nov 21, 2023
tags
LeetCode
笔记
summary
Leetcode周赛372，做题记录和题解
第 372场周赛-链接
AC情况：
✅ ✅ ❌ ❌
1. 使三个字符串相等
给你三个字符串
s1、s2 和 s3。 你可以根据需要对这三个字符串执行以下操作 任意次数 。在每次操作中，你可以选择其中一个长度至少为
2 的字符串 并删除其 最右位置上 的字符。如果存在某种方法能够使这三个字符串相等，请返回使它们相等所需的 最小 操作次数；否则，返回
-1。解题思路：
根据题意，当进行任意操作使得三个字符串相等时，每个字符串左侧保持不变，因此，可以将题意转化为获取三个字符串从下标0开始的最长公共子序列长度。
复杂度：
AC代码：
2. 区分黑球与白球
桌子上有
n 个球，每个球的颜色不是黑色，就是白色。给你一个长度为
n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。在每一步中，你可以选择两个相邻的球并交换它们。
返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。
解题思路：
根据题意分析，从右往左，依次将某一个黑色球都移到右侧时，考虑的最小移动步数其实等于右侧的白球数量。
以case：
1000101为例s[1]已经在序列最右侧，不需要移动s[4]左侧s[5]为0，因此交换s[4]和s[5]，s=1000011s[0]左侧s[1]，s[2]，s[3]，s[4]为0，因此需要依次交换4次右移黑球，s=0000111最小步数为5
计算时只需要逆序遍历，即可统计出每个黑色球右侧的白球数量，求出最小步数
复杂度：
AC代码：
3. 最大异或乘积
给你三个整数
a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2^n。由于答案可能会很大，返回它对
109 + 7 取余 后的结果。注意，
XOR 是按位异或操作。解题思路：
比赛的时候思路大致正确，但是没有注意到a、b的范围会大于x
计
(a XOR x) 和 (b XOR x) 为A 和 B首先采用位运算的方法，将整数a，b转化为二进制数。求成绩最大值，根据异或操作的原理，我们可以很轻易地得出假设：
- 当
a[i] = b[i]时，若要A和B最大，肯定希望A[i]=1,这是的x[i]可以直接确定下来
- 当
a[i] ≠ b[i]时，A[i]和B[i]，必有一一个为1，一个为0，把这些位数表示的数值相加得到的数记为R，不管怎么分配R的和是不会变的。
已知当两数之和固定，乘积最大，本题的问题也就转化为了在
A 和 B之间分配这些不同位数的1，使得A 和 B最相近。由于
0 <= x < 2^n， 需要考虑两种不同的情况- case1：
a ≥ 2^n或b ≥ 2^n时，对于位数i ≥ n的1，异或x之后结果不变，因此，需要将所有0-n位数范围的1分配给最小的数
- case2：
a < 2^n或b < 2^n时，我们只需要把需要分配的最高位数给A，剩余位数分配给B即可
复杂度：
AC代码：
4. 找到 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 。解题思路：
比赛时只想到可以使用离线排序的方式，设置
queries[i][0] < queries[i][1]，从左向右遍历求解，但当时考虑了单调栈（错误思路），以下参考灵神最小堆的题解：首先可以对于
queries[i][0]和queries[i][1]的大小关系不会影响解答，因此默认设置queries[i][0]<queries[i][1]，遍历queries可以获取到Alice和Bob的坐标 和 。当 或者 ，Alice可以直接调到Bob的位置， 就是解答；
否则，我们记录左侧 与其属于的查询编号，最后从小到大遍历建筑时，使用最小堆维护记录
- 遍历到 时，把在下标
i处的「记录」全部加到最小堆中。
- 在加到最小堆之前，我们可以回答左边所有高度小于 的「记录」，其答案就是
i。
复杂度：，
n为heights的长度，k为qureies的长度