LeetCode - Google 校招100题 第7天 序列(数据结构贪心) (15题)

class Solution:
    def isValid(self, s: str) -> bool:
        """
        有效括号，()[]{}，时间O(N)，空间O(N)
        """
        stack = []
        pair_list = [['(', ')'], ['{', '}'], ['[', ']']]
        for c in list(s):
            if c in ['(', '{', '[']:
                stack.append(c)
                continue
            if not stack:
                return False
            for p in pair_list:
                if c == p[1]:
                    if stack.pop() != p[0]:
                        return False
        return True if not stack else False

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        """
        最长有效括号, stack+flags更清晰，格式正确且连续，时间O(n), 空间O(n)
        """
        n = len(s)
        flags = [False] * n # dp
        stack = []  # 使用stack保存索引值
        for i in range(n):
            if s[i]=='(':
                stack.append(i)
            else:
                if stack:
                    j = stack.pop(-1)
                    flags[i], flags[j] = True, True # 匹配成功时标记   
        val, res = 0, 0
        for flag in flags:    # 计算连续1出现的最大次数
            if flag:
                val += 1
            else:          #遇到0时中断，进行对比，并重置
                res = max(res, val)  
                val = 0
        res = max(res, val) #最后一次统计可能未终断，多做一次对比
        return res

class Solution:
    def decodeString(self, s: str) -> str:
        """
        栈操作，类似3[a]2[bc]，时间O(S+|s|)，空间复杂度O(S)
        """
        stack = []
        res = ""
        for c in s:
            if c != "]":  # 不等于
                stack.append(c)
            else:  # 解码"]"
                tmp = ""
                while stack[-1] != "[":
                    item = stack.pop()
                    tmp += item[::-1]  # 内部需要翻转，防止嵌套括号
                tmp = tmp[::-1]  # 整体进行翻转
                stack.pop()
                times = ""
                while stack and stack[-1].isdigit():
                    times += stack.pop()
                tmp = tmp * int(times[::-1])
                stack.append(tmp)
        res = "".join(stack)
        return res

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        """
        最高温度出现在第几天之后，输入列表，返回列表。
        单调栈，当前大于栈内最大值，则更新结果之后出栈
        时间O(n)，空间O(n)
        """
        n = len(temperatures)
        stack = []  # 单调栈
        res = [0] * n
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                res[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return res

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        最长连续序列，不考虑顺序，只考虑是否+1(连续)，哈希表，依次判断是否存在，
        时间O(N)，空间O(N)
        """
        res = 0
        n_set = set(nums)
        for num in n_set:
            if (num - 1) not in n_set:  # 避免重复计算
                tmp = 1  # 连续值
                val = num
                while (val+1) in n_set:
                    tmp += 1
                    val += 1
                res = max(res, tmp)
        return res

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        排序key的字典，时间O(n*klogk), 空间(nk)
        """
        mp = collections.defaultdict(list)
        for s in strs:
            x = "".join(sorted(s))
            mp[x].append(s) # 组成字典
            
        res = []
        for k in mp.keys():
            res.append(mp[k])  # 添加原始数据
        return res

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """
        前缀和 + 哈希表优化: pre[i]-pre[j-1]=k -> pre[j-1]=pre[i]-k
        pre[i]是前n项的和, pre[j-1]是之前出现的和，统计哈希表中pre[j-1]出现的次数，即可。
        时间复杂度O(N), 空间O(N)
        """
        n = len(nums)
        presum = 0  # presum[i]，前缀值
        res = 0
        mp = collections.defaultdict(int) # 统计前缀值出现的次数
        mp[0] = 1 # 注意，初始化前缀值0是1
        for i in range(n):
            presum += nums[i]
            tmp = presum - k  # pre[j-1]的值
            if tmp in mp.keys():  # 这个值出现过，加入这个值出现的次数
                res += mp[tmp]
            mp[presum] += 1  # 加入新值
        return res

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
        跳跃游戏1，是否成功，贪心，最大跳跃长度，超越数组，时间O(n)，空间O(1)
        """
        n = len(nums)
        max_v = 0  # 到达的最远距离
        for i in range(n):
            if i <= max_v:  # 判断当前点能否到达
                max_v = max(max_v, nums[i]+i) # nums[i]+i 跳跃的最大长度
                if max_v >= n-1:  # 大于最后一个位置
                    return True
            else:
                break
        return False

class Solution:
    def jump(self, nums: List[int]) -> int:
        """
        跳跃游戏2，最小跳跃次数，贪心，时间O(n)，空间O(1)
        """
        n = len(nums)
        max_v = 0  # 到达的最远距离
        res, max_end = 0, 0
        for i in range(n-1):
            if i <= max_v:  # 小于一次最远位置
                max_v = max(max_v, nums[i]+i)  # 当前最远的位置
                if i == max_end:  # i到达边界步数
                    max_end = max_v  # 更新最大边界，同时跳跃次数+1
                    res+=1  # 步数+1，一次一次的更新
        return res

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        """
        运行环路一周，贪心算法，gas是加油数量，cost是花费，选择起始位置
        燃料最低点的下一个开始，时间O(n), 空间O(1)
        """
        n = len(gas)
        val = 0
        min_v= float("inf")
        min_i = 0  # 燃料最低点的位置
        for i in range(n):
            val += gas[i] - cost[i]  # 累计剩余燃料
            if val <= min_v:  # 保存剩余燃料最低值
                min_v = val
                min_i = i
        if val < 0:
            return -1
        return (min_i+1) % n  # 最低燃料的下一个开始

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        买卖股票1，只在一只赚钱，时间O(n)，空间O(1)
        """
        prev = prices[0]
        res = 0
        n = len(prices)
        for i in range(n):
            res = max(res, prices[i]-prev)
            prev = min(prev, prices[i])
        return res

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        买卖股票2，赚差价，贪心，累加区间最大值，时间O(n)，空间O(1)
        """
        n = len(prices)
        res=0
        for i in range(1, n):
            res + = max(0, prices[i]-prices[i-1])
        return res

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        水平翻转(上下翻转)、对角线翻转，即是旋转图像
        时间O(n^2)，空间O(1)
        """
        if not matrix or not matrix[0]:
            return
        m = len(matrix)
        n = len(matrix[0])
        # 水平翻转
        for i in range(m//2):
            for j in range(n):
                matrix[i][j], matrix[m-i-1][j] = matrix[m-i-1][j], matrix[i][j]
        # 对角矩阵翻转
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:        
        """
        4个指针 + 上右不用判断，下左需要判断边界，时间O(mn), 空间O(1), 空间排除输出之外的复杂度
        """
        if not matrix or not matrix[0]:
            return []
        m = len(matrix)
        n = len(matrix[0])
        res = []
        left, right, top, bottom = 0, n-1, 0, m-1
        while left <= right and top <= bottom:
            for i in range(left, right+1):
                res.append(matrix[top][i])
            for i in range(top+1, bottom+1):
                res.append(matrix[i][right])
            # 非常重要的边界判断，否则会重复
            if left < right and top < bottom:
                for i in range(right-1, left-1, -1):
                    res.append(matrix[bottom][i])
                for i in range(bottom-1, top, -1):
                    res.append(matrix[i][left])
            left += 1
            right -= 1
            top += 1
            bottom -= 1
        return res

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        """
        螺旋矩阵2，生成矩阵
        与 剑指 Offer 29. 顺时针打印矩阵 类似，注意：
        外层是while left <= right and top <= bottom，有等于
        内层是if left < right and top < bottom，没有等于
        时间复杂度是O(n^2)，空间是O(1)
        """
        left, right = 0, n-1
        top, bottom = 0, n-1
        matrix = [[0] * n for _ in range(n)]
        num = 0
        while left <= right and top <= bottom:
            for i in range(left, right+1):
                num += 1
                matrix[top][i] = num
            for i in range(top+1, bottom+1):
                num += 1
                matrix[i][right] = num
            if left < right and top < bottom:
                for i in range(right-1, left-1, -1):
                    num += 1
                    matrix[bottom][i] = num
                for i in range(bottom-1, top, -1):
                    num += 1
                    matrix[i][left] = num
            left += 1
            right -= 1
            top += 1
            bottom -= 1
        return matrix