Leetcode刷题记录第二周

2996 大于等于顺序前缀和的最小缺失整数

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ,那么我们称这个前缀是一个 顺序前缀 。特殊情况是,只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ,满足 x 大于等于 最长 顺序前缀的和。

class Solution:
    def missingInteger(self, nums: list[int]) -> int:
        sum = 0
        prev = 0
        for i, num in enumerate(nums):
            if (num - prev ==1 or i ==0):
                sum = sum + num
                prev = num
                continue
            break
        hash=set(nums)
        while(sum in hash):
            sum = sum + 1
        return sum

先计算这个顺序前缀和,然后直接建哈希表检测数组中有没有这个数字,有就累加直至没有。

关键就两处,一个是启动的边界条件i ==0 一个是语法 hash=set(nums) 复杂度是O(n)

2958 最多K个重复元素的最长子数组

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ,那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

class Solution:
    def maxSubarrayLength(self, nums: list[int], k: int) -> int:
        cnt = {}
        left = 0
        ans = 0
        for right, x in enumerate(nums):
            cnt[x] = cnt.get(x, 0) + 1
            while cnt[x] > k:
                cnt[nums[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

经典的滑动数组+哈希表,记住左边界变动的时候一定要同步更新哈希表

2213 由单个字符重复的最长字符串

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ,一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ,这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ,其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: list[int]) -> list[int]:
        self.t = [None] * (4 * len(s) + 5)
        self.build(1, 0, len(s) - 1, s)
        ans = []
        for c, i in zip(queryCharacters, queryIndices):
            self.update(1, 0, len(s) - 1, i, c)
            ans.append(self.t[1][5])          # 改③:tuple 下标 5 = best
        return ans

    def pull(self, L, R):
        # 改②:解包代替 dict 查找。顺序固定 (lc, rc, sz, pre, suf, best)
        ll, lr, lsz, lp, ls, lb = L
        rl, rr, rsz, rp, rs, rb = R
        pre, suf, best = lp, rs, lb if lb > rb else rb
        if lp == lsz and lr == rl:            # ① 左整体 + 边界接上 → pre 穿过
            pre = lp + rp
        if rs == rsz and lr == rl:            # ② 右整体 + 边界接上 → suf 穿过
            suf = rs + ls
        if lr == rl:                          # ③ 边界接上 → best 跨界
            v = ls + rp
            if v > best:
                best = v
        return (ll, rr, lsz + rsz, pre, suf, best)

    def build(self, i, l, r, s):
        if l == r:
            c = s[l]
            self.t[i] = (c, c, 1, 1, 1, 1)    # 改①:叶子也是 tuple
            return
        m = (l + r) // 2
        self.build(i * 2, l, m, s)
        self.build(i * 2 + 1, m + 1, r, s)
        self.t[i] = self.pull(self.t[i * 2], self.t[i * 2 + 1])

    def update(self, i, l, r, pos, ch):
        if l == r:
            self.t[i] = (ch, ch, 1, 1, 1, 1)  # 改①:叶子换新账本
            return
        m = (l + r) // 2
        if pos <= m:
            self.update(i * 2, l, m, pos, ch)
        else:
            self.update(i * 2 + 1, m + 1, r, pos, ch)
        self.t[i] = self.pull(self.t[i * 2], self.t[i * 2 + 1])
print(Solution().longestRepeating("babacc", "bcb", [1, 3, 3]))  # [3, 3, 4]
print(Solution().longestRepeating("aabaa", "a", [2]))           # [5]

一个非常典型的线段树题目。

假如暴力查询的话复杂度为O(len(s)) * O(k), 在本题目的数据规模中完全不可接受。

关键是对每个线段需要保存的信息和合并时的关键边界条件需要细心处理。
一个线段需要记载其左右两侧的字母及其重复数量、总长度及中间的最长重复数量。

边界条件包括左侧全部重复需要合并、右侧全部重复需要合并、仅合并几种情况

另外就是线段树的左分支地址乘2,右分支地址乘2加1,所以在极端恶劣前提下,房间数量可以达到4n-1,需要留好裕度。

一个有趣的事情是第一次提交使用了哈希表,这造成了一个严重的问题那就是查表运算次数太多了,取得了执行时间前95%的好成绩,改用元组即可。

3090 每个字符最多出现两次的最长字符串

给你一个字符串 s ,请找出满足每个字符最多出现两次的最长子字符串,并返回该子字符串的 最大 长度。

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        hash={}
        l = 0
        r = 0
        sum = 0
        ans = 0
        for r, c in enumerate(s):
            sum += 1
            if c not in hash:
                hash[c] = 1
            else:
                hash[c] += 1
                if hash[c] > 2:
                    while(s[l] != c):
                        hash[s[l]] -= 1
                        l +=1
                        sum -=1
                    l += 1
                    sum -= 1
                    hash[c] -= 1
            ans = max(ans, sum)
        return ans

条件清晰的滑动窗口,难度不大。甚至可以不用哈希表。

3072 按位异或非零的最长子序列

超级坑人的一把,费劲千辛万苦把复杂度从2n2^n 降到 n2n^2 然后发现小丑了,这是一个脑筋急转弯,作为一个电路设计人员没有第一时间发现异或的性质深感完全不是人。

以下为基于DP的超时解

class Solution:
    def longestSubsequence(self, nums: list[int]) -> int:
        if max(nums) == 0:
            return 0

        DP = [[0, 0, 0] for _ in range(len(nums))]
        for i, n in enumerate(nums):
            DP[i] = [nums[i], 1, 1]
            for j in range(0,i):
                if n == 0:
                    if n ^ DP[j][0]  != 0:
                        if DP[i][1]<DP[j][1] + 1:
                            DP[i][0] = DP[j][0]
                            DP[i][1] = DP[j][1] + 1
                    else:
                        DP[i][2] = max(DP[i][2], DP[j][2]+1)
                else:
                    if n ^ DP[j][0]  != 0:
                        if DP[i][1]<DP[j][1] + 1:
                            DP[i][0] = DP[j][0] ^ n
                            DP[i][1] = DP[j][1] + 1
                        if DP[i][1]<DP[j][2] + 1:
                            DP[i][0] = DP[j][0]
                            DP[i][1] = DP[j][2] + 1
                    else:
                        DP[i][2] = max(DP[i][2], DP[j][1]+1)

        return max(row[1] for row in DP)

像区一样,以下为正解

class Solution:
    def longestSubsequence(self, nums: list[int]) -> int:
        n = len(nums)
        total_xor = 0
        for x in nums:
            total_xor ^= x
        
        if total_xor != 0:
            return n
        
        # total_xor == 0
        if any(x != 0 for x in nums):   # 存在非零元素
            return n - 1
        else:
            return 0

逻辑我都不想写,shame…….

这是中等题吗?

Related Posts