算法题记录 26

2012.数组美丽值求和（1468）

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：

2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
0，如果上述条件全部不满足
返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

涉及知识点

前缀后缀

解决思路

秒答题，如果单纯做会超时，用前缀、后缀记录最大值最小值比较即可。

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        suf_min = [0] * n  # 后缀最小值
        suf_min[n - 1] = nums[n - 1]
        for i in range(n - 2, 1, -1):
            suf_min[i] = min(suf_min[i + 1], nums[i])

        ans = 0
        pre_max = nums[0]  # 前缀最大值
        for i in range(1, n - 1):
            x = nums[i]
            # 此时 pre_max 表示 [0, i-1] 中的最大值
            if pre_max < x < suf_min[i + 1]:
                ans += 2
            elif nums[i - 1] < x < nums[i + 1]:
                ans += 1
            # 更新后 pre_max 表示 [0, i] 中的最大值
            pre_max = max(pre_max, x)
        return ans

3298.统计重新排列后包含另一个字符串的子字符串数目2（1909）

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。

涉及知识点

滑动窗口

解决思路

熟悉滑动窗口就行，注意引用一个less来判断是否满足要求。

class Solution:
    def validSubstringCount(self, s: str, t: str) -> int:
        if len(s) < len(t):
            return 0

        # t 的字母出现次数与 s 的字母出现次数之差
        diff = defaultdict(int)  # 也可以用 Counter(t)，但是会慢很多
        for c in t:
            diff[c] += 1

        # 窗口内有 less 个字母的出现次数比 t 的少
        less = len(diff)

        ans = left = 0
        for c in s:
            diff[c] -= 1
            if diff[c] == 0:
                # c 移入窗口后，窗口内 c 的出现次数和 t 的一样
                less -= 1
            while less == 0:  # 窗口符合要求
                if diff[s[left]] == 0:
                    # s[left] 移出窗口之前，检查出现次数，
                    # 如果窗口内 s[left] 的出现次数和 t 的一样，
                    # 那么 s[left] 移出窗口后，窗口内 s[left] 的出现次数比 t 的少
                    less += 1
                diff[s[left]] += 1
                left += 1
            ans += left
        return ans

3280.将日期转换为二进制表示（1206）

给你一个字符串 date，它的格式为 yyyy-mm-dd，表示一个公历日期。

date 可以重写为二进制表示，只需要将年、月、日分别转换为对应的二进制表示（不带前导零）并遵循 year-month-day 的格式。

返回 date 的 二进制 表示。

涉及知识点

正则、字符串

解决思路

熟悉正则表达式、库函数、字符串列表的转换即可。

class Solution:
    def convertDateToBinary(self, date: str) -> str:
        a = date.split('-')
        for i in range(len(a)):
            a[i] = bin(int(a[i]))[2:]
        return '-'.join(a)

3192.使二进制数组全部等于1的最少操作次数（1433）

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。

涉及知识点

数组

解决思路

看似是个模拟求最优化、最少操作次数的题，其实跟先前一道题一样，是个伪最优化题。我们会发现如果存在一种翻转策略，无论执行先后结果都一样，所以我们可以从左往右进行，而遇见0则必须翻转一次，使其成为1，后面遇见0也就是原数组同样位置的1又必须翻转一次（因为原数组元素从0变为1，从1变为0了），以此循环。我们计数有多少交替出现的0和1即可。

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        k = 0
        for x in nums:
            if x == k % 2:  # 必须操作
                k += 1
        return k

2274.不含特殊楼层的最大连续楼层数（1333）

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。

给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。

返回不含特殊楼层的 最大 连续楼层数。

涉及知识点

数组

解决思路

排序，涉及底楼顶楼的情况单独讨论，其余的按从小到大计算间隔即可。

class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        special.sort()
        ans = max(special[0] - bottom, top - special[-1])
        for x, y in pairwise(special):
            ans = max(ans, y - x - 1)
        return ans

908.最小差值1（1299）

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

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i 。将 nums[i] 改为 nums[i] + x ，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i ，最多 只能 应用 一次 此操作。

nums 的 分数 是 nums 中最大和最小元素的差值。

在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低 分数 。

涉及知识点

分类讨论

解决思路

秒答题

class Solution:
    def smallestRangeI(self, nums: List[int], k: int) -> int:
        return max(max(nums) - min(nums) - k * 2, 0)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。