LeetCode 记录

刷题总是三分钟热度，不知道能坚持多久

以此来记录无聊又有趣的算法生活，更新每日一题的情况

2022/3/4

2104. 子数组范围和

这题之前在周赛的时候做过，不过当时用的 python 且时间复杂度为 $ O(n^{2}) $ 但是超时了，今天的每日一题又遇到它啦，看了看题解好像大部分都是$ O(n^{2}) $ 的解法呀，可能当时代码写的有问题叭，今天再做一遍怎么又超时了！！！

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                ans += max(nums[i:j]) - min(nums[i:j])
        return ans

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            minVal, maxVal = inf, -inf
            for j in range(i, n):
                minVal = min(minVal, nums[j])
                maxVal = max(maxVal, nums[j])
                ans += maxVal - minVal
        return ans

我的做法是用py用多了，老想直接切片，这样耗时太多啦，使用 $ minval $ 和 $ maxval $ 来储存最大最小值能够省下一部分时间。

但是这样还是 $ O(n^{2}) $ 的时间复杂度，怎么样才能进一步优化呢，这里可以使用单调栈，将时间复杂度压缩到 $ O(n) $ 显然我是不会用单调栈了，等啥时候学了再更新方法~

2022/3/5

521. 最长特殊序列 Ⅰ

一个脑筋急转弯，如果两个字符串不相等则最长特殊序列就是两个字符串中较长的那个，否则没有子序列返回-1

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return max(len(a), len(b)) if a != b else -1

2022/3/6

2100. 适合打劫银行的日子

浙江农信银行出的题目，哈哈哈哈，用了前缀和的思想，很简单的一道题

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        g = [0 for i in range(n)]
        for i in range(1,n):
            if security[i] > security[i - 1]:
                g[i] = 1
            elif security[i] < security[i - 1]:
                g[i] = -1
        a,b = [0 for i in range(n+1)],[0 for i in range(n+1)]
        for i in range(1,n+1):
            a[i] = a[i - 1] + (1 if g[i - 1] == 1 else 0)
            b[i] = b[i - 1] + (1 if g[i - 1] == -1 else 0)
        ans = []
        for i in range(time,n-time):
            if a[i - time + 1] == a[i + 1] and b[i + 1] == b[i + time + 1]:
                ans.append(i)
        return ans

2022/3/7

504. 七进制数

一个简单的数学题，由十进制转换成任意进制可以使用基数乘除法，本题指定为整数所以使用除基数取余法即可。虽然简单但是要记得处理 0 和 负数！

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return '0'
        ans = ''
        flag = True
        if num < 0:
            num = - num
            flag = False
        while num:
            ans = str(num % 7) + ans
            num //= 7
        return ans if flag else '-' + ans

2022/3/8

2055. 蜡烛之间的盘子

也是一道前缀和的题目，寻找$ [x, y] $之间的盘子数量可以理解为寻找这个区间内最左边和最右边蜡烛之间共有几个盘子，我们可以预先处理出left，right数组用来记录第 index 的最邻近左边或者右边的第一个盘子，然后用preSum求出到第 index 个字符之前一共有多少个盘子，直接 $ preSum[right] – preSum[left] $ 即可求出答案

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        preSum = [0] * len(s)
        left,right = [0] * len(s), [0] * len(s)
        temp = -1 
        for i in range(len(s)):
            if s[i] == '*':
                preSum[i] = preSum[i-1] + 1
            else:
                preSum[i] = preSum[i-1]
                temp = i
            left[i] = temp
        temp = -1
        for i in range(len(s) - 1,-1,-1):
            if s[i] == '|':
                temp = i
            right[i] = temp
        ans = []
        print(left)
        for i, (x, y) in enumerate(queries):
            x, y = right[x], left[y]
            if x >= 0 and y >= 0 and x < y:
                ans.append(preSum[y] - preSum[x])
            else:
                ans.append(0)
        return ans