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)continueif not stack:return Falsefor p in pair_list:if c == p[1]:if stack.pop() != p[0]:return Falsereturn 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 # dpstack = []  # 使用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, 0for flag in flags:    # 计算连续1出现的最大次数if flag:val += 1else:          #遇到0时中断，进行对比，并重置res = max(res, val)  val = 0res = 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] * nfor 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 = 0n_set = set(nums)for num in n_set:if (num - 1) not in n_set:  # 避免重复计算tmp = 1  # 连续值val = numwhile (val+1) in n_set:tmp += 1val += 1res = 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]-kpre[i]是前n项的和, pre[j-1]是之前出现的和，统计哈希表中pre[j-1]出现的次数，即可。时间复杂度O(N), 空间O(N)"""n = len(nums)presum = 0  # presum[i]，前缀值res = 0mp = collections.defaultdict(int) # 统计前缀值出现的次数mp[0] = 1 # 注意，初始化前缀值0是1for 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 Trueelse:breakreturn 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, 0for 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  # 更新最大边界，同时跳跃次数+1res+=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 = 0min_v= float("inf")min_i = 0  # 燃料最低点的位置for i in range(n):val += gas[i] - cost[i]  # 累计剩余燃料if val <= min_v:  # 保存剩余燃料最低值min_v = valmin_i = iif val < 0:return -1return (min_i+1) % n  # 最低燃料的下一个开始

class Solution:def maxProfit(self, prices: List[int]) -> int:"""买卖股票1，只在一只赚钱，时间O(n)，空间O(1)"""prev = prices[0]res = 0n = 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=0for 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]:returnm = 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-1while 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 += 1right -= 1top += 1bottom -= 1return 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-1top, bottom = 0, n-1matrix = [[0] * n for _ in range(n)]num = 0while left <= right and top <= bottom:for i in range(left, right+1):num += 1matrix[top][i] = numfor i in range(top+1, bottom+1):num += 1matrix[i][right] = numif left < right and top < bottom:for i in range(right-1, left-1, -1):num += 1matrix[bottom][i] = numfor i in range(bottom-1, top, -1):num += 1matrix[i][left] = numleft += 1right -= 1top += 1bottom -= 1return matrix