2020-2-28 刷题记录

0X00 leetcode 刷题 5 道

• leetcode 312. Burst Balloons
• leetcode 443. String Compression
• leetcode 209. Minimum Size Subarray Sum
• leetcode 3. Longest Substring Without Repeating Characters
• leetcode 76. Minimum Window Substring

0X01 每道题的小小记录

312. Burst Balloons

区间型动态规划, 大致思路就是

• 首先这是一种「消去型」的问题,要将问题转换成左右子问题
• 添加两个不能扎破的气球
• dp[i][j] 代表 [i+1 j-1] 区间内的最大得分,也就是说当长度为 2 的时候为 0 因为不能扎破
• 长度递增,再枚举中间分割的气球

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # 区间型动态规划
        # 消去型的问题,不能按着题目意思来
        # 一定要想成左边右边的子问题
        # dp[i][j] 代表 i+1 j-1 的最大 coins
        # 所以要加上两端不能扎破的气球

        if len(nums) == 0: return 0
        m = len(nums) + 2
        coins = [0] * m
        for i in range(m):
            if i == 0 or i == m-1: coins[i] = 1
            else: coins[i] = nums[i-1]
        
        dp = [[0] * m for _ in range(m+1)]

        # len 2 全是 0
        # 从 len 3 开始
        for l in range(3, m+1):
            for i in range(m - l + 1):
                j = i + l - 1
                dp[i][j] = float("-inf")
                # 遍历比 l 小的长度
                for k in range(i+1, j):
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + coins[i] * coins[k] * coins[j])
                
        
        return dp[0][-1]

443. String Compression

双指针的变种,因为没有理解题目,坑了我很久

class Solution:
    def compress(self, chars: List[str]) -> int:
        if len(chars) == 0: return 0

        # 三指针去做这个
        m = len(chars)
        i = j = w = 0
        while i < m:
            j += 1
            if j == m:
                chars[w] = chars[i]
                if j - i != 1:
                    t = str(j - i)
                    for k in range(len(t)):
                        w += 1
                        chars[w] = t[k]
                w += 1
                break
            else:
                if chars[i] != chars[j]:
                    chars[w] = chars[i]
                    if j - i != 1:
                        t = str(j - i)
                        for k in range(len(t)):
                            w += 1
                            chars[w] = t[k]
                    w += 1
                    i = j
        return w

坑在:

• 返回最后长度而且要在原 array 上修改
• i, j 记录子串 w 记录写在哪

209. Minimum Size Subarray Sum

接下来的三道题都是滑动窗口的题目

这是一道经典的滑动窗口的题目,废话不多说,直接上代码:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        m = len(nums)
        j = 0
        ans = float("inf")
        for i in range(m):
            while j < m and target > 0:
                target -= nums[j]
                j += 1
            if target <= 0:
                ans = min(ans, j - i )
                target += nums[i]
        
        return ans if ans != float("inf") else 0

其中用到的小技巧就是 正数 -

滑动窗口的模板就是

for i in range(m):
    while j < m and target > 0:
        target -= nums[j]
        j += 1
        if target <= 0:
            ans = min(ans, j - i )
            target += nums[i]

注意这里的 j 不是索引,要比索引大 1

3. Longest Substring Without Repeating Characters

滑动窗口题目,用 set 优化

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0: return 0
        look_up = set()
        left, max_len, cur_len = 0, 0, 0
        for c in s:
            cur_len += 1
            while c in look_up:
                look_up.remove(s[left])
                cur_len -= 1
                left += 1
            max_len = max(max_len, cur_len)
            look_up.add(c)

        return max_len

76. Minimum Window Substring

难一点的滑动窗口题目,里面用了一个小技巧

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "": return ""

        sourceHash = [0] * 256
        targetHash = [0] * 256

        # init 
        for c in t:
            targetHash[ord(c)] += 1
        
        minStr = ""
        ans = float("inf")

        j = 0
        for i in range(len(s)):
            while not self.valid(sourceHash, targetHash) and j < len(s):
                sourceHash[ord(s[j])] += 1
                j += 1
            if self.valid(sourceHash, targetHash):
                if ans > j - i:
                    minStr = s[i:j]
                    ans = j - i

            sourceHash[ord(s[i])] -= 1
        
        return minStr
    
    def valid(self, sourceHash, targetHash):
        for i in range(256):
            if targetHash[i] > sourceHash[i]:
                return False
        return True

这里的时间复杂度是 O(256n),因为所有的字符都是 ASIIC 所以用 256, 而且这里有一个比较坑的东西是

target 里面可以有重复...所以要记录每个字母的出现数量