月度归档： 2022 年 3 月

疫情终会过去，静候春暖花开。

这一时期的山东疫情要比20年更加猛烈，我记得临沂的确诊数目20年之后从没这么快速增加过，3月14日开始到现在突然增加到17例了，更别说还有青岛和滨州，现在大部分地区应该都停课了，开始上网课，估计只有高三的同学还在教室上课了。这周末我们也接到了网上课程的通知，虽然泰安目前并没有疫情。

今天去老师办公室讨论关于这个设备管理管理的小程序的方案，这算是我在老师手中接到的第一个项目叭，之前老师也给我推过几次小程序的项目，但是都因为我从来没去学过小程序就拒绝了，这次接也是因为这个项目开发周期较长可以边学边做，而且最近确实挺闲的，多学点东西也好~

这当然是先给甲方做做页面啦，跟做PPT似的，做完界面以后再和甲方商量具体要更改的确定后再开发后端功能。

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

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

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

昨天一个朋友推荐的真露混合啤酒一起喝超好喝，咱今天就试了试，呜呜呜有点上头，现在已经晕晕的了

3月6日更新：

呜呜呜，今天早上醒来就头好疼，胃难受，下次再也不能空腹喝酒了！！！

我的酒量有点小呀，之前只喝过啤酒，第一次干了一整瓶烧酒加一瓶啤酒，嗝~