leetcode contest 378

leetcode contest 378

整体来说题目还算有点难度，不过倒不是特别变态的题目，难度还可以接受。几个题目倒是都不需要什么技巧。

2980. 检查按位或是否存在尾随零

给你一个 正整数 数组 nums 。

你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中 至少 存在一个尾随零。

例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。

如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。

示例 2：

输入：nums = [2,4,8,16]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110"，存在一个尾随零。
其他按位或运算结果存在尾随零的可能选择方案包括：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 以及 (2, 4, 8, 16) 。

示例 3：

输入：nums = [1,3,5,7,9]
输出：false
解释：不存在按位或运算结果存在尾随零的选择方案。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-378/problems/check-if-bitwise-or-has-trailing-zeros/

题意

直接模拟即可

思路

1. 统计数组中偶数的数目是否大于 $1$ 即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def hasTrailingZeros(self, nums: List[int]) -> bool:
        return sum(1 for x in nums if x & 1 == 0) > 1

---

2981. 找出出现至少三次的最长特殊子字符串 I

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

示例 1：

输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。

示例 2：

输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。

示例 3：

输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。

提示：

• 3 <= s.length <= 50
• s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-378/problems/find-longest-special-substring-that-occurs-thrice-ii/

题意

二分查找

思路

1. 给定相同字符串的长度为 $x$, 此时可以组成长度为 $x$ 的字串数目为 $x - l + 1$ 个，我们可以利用二分查找，找到每种字符可以组成数目大于 $3$ 的连续字符串的最大长度即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$，其中 $n$ 表示给定的字符串的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的字符串的长度。

代码

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        cnt = [[] for i in range(26)]
        i, j = 0, 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cnt[ord(s[i]) - ord('a')].append(j - i)
            i = j

        res = -1
        for i in range(26):
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) >> 1
                count = sum(x - mid + 1 for x in cnt[i] if x >= mid)
                if count >= 3:
                    res = max(res, mid)
                    lo = mid + 1
                else:
                    hi = mid - 1
        return res

---

2982. 找出出现至少三次的最长特殊子字符串 II

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

示例 1：

输入：s = "aaaa"
输出：2
解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
可以证明最大长度是 2 。

示例 2：

输入：s = "abcdef"
输出：-1
解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。

示例 3：

输入：s = "abcaba"
输出：1
解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
可以证明最大长度是 1 。

提示：

• 3 <= s.length <= 5 * 105
• s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-378/problems/find-longest-special-substring-that-occurs-thrice-ii/

题意

二分查找

思路

1. 给定相同字符串的长度为 $x$, 此时可以组成长度为 $x$ 的字串数目为 $x - l + 1$ 个，我们可以利用二分查找，找到每种字符可以组成数目大于 $3$ 的连续字符串的最大长度即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$，其中 $n$ 表示给定的字符串的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的字符串的长度。

代码

class Solution:
    def maximumLength(self, s: str) -> int:
        n = len(s)
        cnt = [[] for i in range(26)]
        i, j = 0, 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cnt[ord(s[i]) - ord('a')].append(j - i)
            i = j

        res = -1
        for i in range(26):
            lo, hi = 1, n
            while lo <= hi:
                mid = (lo + hi) >> 1
                count = sum(x - mid + 1 for x in cnt[i] if x >= mid)
                if count >= 3:
                    res = max(res, mid)
                    lo = mid + 1
                else:
                    hi = mid - 1
        return res

---

2983. 回文串重新排列查询

给你一个长度为 偶数 n ，下标从 0 开始的字符串 s 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。

对于每个查询 i ，你需要执行以下操作：

• 将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
• 将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。

对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。

每个查询与其他查询都是 独立的 。

请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。

• 子字符串 指的是一个字符串中一段连续的字符序列。
• s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。

示例 1：

输入：s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
输出：[true,true]
解释：这个例子中，有 2 个查询：
第一个查询：
- a0 = 1, b0 = 1, c0 = 3, d0 = 5
- 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
- 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
- 现在 s 是一个回文串。所以 answer[0] = true 。
第二个查询：
- a1 = 0, b1 = 2, c1 = 5, d1 = 5.
- 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
- 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。
- 现在 s 是一个回文串，所以 answer[1] = true 。

示例 2：

输入：s = "abbcdecbba", queries = [[0,2,7,9]]
输出：[false]
解释：这个示例中，只有一个查询。
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。
无法通过重新排列这些子字符串使 s 变为一个回文串，因为 s[3:6] 不是一个回文串。
所以 answer[0] = false 。

示例 3：

输入：s = "acbcab", queries = [[1,2,4,5]]
输出：[true]
解释：这个示例中，只有一个查询。
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。
为了让 s 变为回文串，s[1:2] 可以重新排列得到 => abccab 。
然后 s[4:5] 重新排列得到 abccba 。
现在 s 是一个回文串，所以 answer[0] = true 。

提示：

• 2 <= n == s.length <= 105
• 1 <= queries.length <= 105
• queries[i].length == 4
• ai == queries[i][0], bi == queries[i][1]
• ci == queries[i][2], di == queries[i][3]
• 0 <= ai <= bi < n / 2
• n / 2 <= ci <= di < n
• n 是一个偶数。
• s 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-378/problems/palindrome-rearrangement-queries/

题意

动态规划

思路

1. 题目本身倒不是特别难，但是感觉需要考虑的细节比较多，需要仔细的思考处理好细节，否则非常容易出错的题目，首先我们将数组的前后部分进行预处理，将数组的后半部分进行反转，设 $s = s[0\cdots \frac{n}{2}], t = [\frac{n}{2}\cdots n]$；只需要排序使得 $s =t$ 相等即可，

   • 给定的 $a,b,c,d$，此时需要将其转换为 $s,t$ 中的索引分别为 $l_1 = a,r_1 = b,l_2 = 2m-1-d, r_2 = 2m-1-c$；

   • 此时只需要排序 $s[l_1\cdots r_1],t[l_2\cdots r_2]$ 使得 $s = t$ 相等即可，设 $l = \min(l_1,l_2), r = \max(r_1,r_2)$ 实际分为以下几种情况来检测：

     • 首先我们需要使得两个字符串未进行排序的区域相等，此时需要检测 $s[0\cdots l-1] = t[0\cdots l-1],s[r+1\cdots n-1] = t[r+1\cdots n -1]$,即未排序的部分一定相等；

     • 其次我们检测在需要进行排序的区间 $[l,r]$ 中， $s[l\cdots r]$ 与 $t[l\cdots r]$ 二者的字符种类与数据均相等；

     • 第一种情况区间 $[l_1,r_1],[l_2,r_2]$ 不存在相交的时候，即此时还需要保证 $s[l1\cdots r_1]$ 与 $t[l1\cdots r_1]$ 的字符相等，此时 $s[\min(r_1,r_2) \cdots max(l_1,l_2)] = t[\min(r_1,r_2) \cdots max(l_1,l_2)]$，同时保证 $s[l_2\cdots r_2]$ 与 $t[l_2\cdots r_2]$的字符相等即可，我们利用动态规划记录两个字符串相等的最长长度，同时用前缀和保存当前每个不同字符的前缀和，我们判断中间不相交的部分字符串是否想等，相交的地方字符是否相等即可；

       

     • 第二种情况区间 $[l_1,r_1],[l_2,r_2]$ 在相交，即此时此时我们需要不管需要区间 $[l,r]$ 之间的字符相等，还需要检测是否需要交换位置的字符 $a$，此时是否刚好都分布在两个字符串 $s,t$ 的无法排序交换的部分，比如此时 $’w’$ 刚好分布在字符串 $s$ 无法排序的区域，$’w’$ 同时也分布在 $t$ 的无法排序的区域，此时无法如何排序都无法使得两个字符串相等，

       .png)

1. 复杂度分析:

• 时间复杂度：$O(n + m \times |\Sigma|)$，其中 $n$ 表示给定的字符串的长度，$m$ 表示给查询数组的长度;
• 空间复杂度：$O(n \times |\Sigma|)$，其中 $n$ 表示给定的字符串的长度;

代码

[sol1-C++]

class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        m = len(s) // 2
        t = ''.join(reversed(s[m:]))
        cnt1 = [[0] * 26 for _ in range(m + 1)]
        cnt2 = [[0] * 26 for _ in range(m + 1)]
        for i in range(m):
            cnt1[i + 1] = copy.deepcopy(cnt1[i])
            cnt1[i + 1][ord(s[i]) - ord('a')] += 1
            cnt2[i + 1] = copy.deepcopy(cnt2[i])
            cnt2[i + 1][ord(t[i]) - ord('a')] += 1
        dp = [0] * (m + 1)
        for i in range(m):
            if s[i] == t[i]:
                dp[i + 1] = dp[i] + 1
        
        def check1(l, r):
            return l > r or dp[r + 1] >= r - l + 1
        
        def check2(l, r):
            if l > r:
                return True
            for i in range(26):
                if cnt1[r + 1][i] - cnt1[l][i] != cnt2[r + 1][i] - cnt2[l][i]:
                    return False
            return True
        
        def get(cnt, l, r):
            if l <= r:
                return [cnt[r + 1][i] - cnt[l][i] for i in range(26)]
            else:
                return [0] * 26
        
        ans = []
        for q in queries:
            l1, r1 = q[0], q[1]
            l2, r2 = 2 * m - 1 - q[3], 2 * m - 1 - q[2]
            l, r = min(l1, l2), max(r1, r2)
            LL, RR = min(r1, r2), max(l1, l2)
            
            if not check1(0, l - 1) or not check1(r + 1, m - 1) or not check2(l, r):
                ans.append(False)
                continue
            
            if r1 < l2 or r2 < l1:
                if not check1(LL + 1, RR - 1) or not check2(l, LL) or not check2(RR, r):
                    ans.append(False)
                else:
                    ans.append(True)
            else:
                tot = get(cnt1, l, r)
                diff1 = get(cnt2, l, RR - 1) if l1 < l2 else get(cnt1, l, RR - 1)
                diff2 = get(cnt1, LL + 1, r) if r1 < r2 else get(cnt2, LL + 1, r)
                valid = True
                for i in range(26):
                    if diff1[i] + diff2[i] > tot[i]:
                        valid = False
                        break
                ans.append(valid)
        return ans

欢迎关注和打赏，感谢支持！

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu