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

欢迎关注我的CSDN：https://spike.blog.csdn.net/
本文地址：https://spike.blog.csdn.net/article/details/144744418

相关文章：

LeetCode 合计最常见的 112 题：

1. 校招100题 第1天 链表(List) (19题)
2. 校招100题 第2天 树(Tree) (21题)
3. 校招100题 第3天 动态规划(DP) (20题)
4. 校招100题 第4天 查找排序(Search&Sort) (16题)
5. 校招100题 第5天 双指针(Two Pointers) (11题)
6. 校招100题 第6天 回溯法(Backtracking) (8题)
7. 校招100题 第7天 序列(数据结构&贪心) (15题)
8. 校招100题 第8天 图(Graph) (2题)

序列(数据结构&贪心) 算法包括栈、字典、集合、贪心等，基于不同的数据存储和访问方式的数据结构。栈(Stack) 是一种 后进先出(LIFO) 的数据结构，支持 推入(append) 和 弹出(pop) 操作，常用于处理嵌套问题和回溯算法。字典(Map) 是一种基于键值对的存储结构，提供快速的查找、插入和删除操作，其效率通常与哈希表的实现有关。集合(Set) 是一种无序且元素唯一的数据结构，支持高效的成员检查、添加和删除操作，常用于去重和数学集合操作。

题目(15题)：

1. 栈：20. 有效的括号 (Easy)、32. 最长有效括号 (Hard)、394. 字符串解码、739. 每日温度 (单调栈)
2. 集合：128. 最长连续序列
3. 字典：49. 字母异位词分组、560. 和为 K 的子数组 (前缀树字典)
4. 贪心：55. 跳跃游戏、45. 跳跃游戏 II、134. 加油站、121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II
5. 矩阵模拟：48. 旋转图像、54. 螺旋矩阵、59. 螺旋矩阵 II

1. 栈

1.1 20. 有效的括号 (Easy)

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

1.2 32. 最长有效括号 (Hard)

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

1.3 394. 字符串解码

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

1.4 739. 每日温度

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

2. 集合

2.1 128. 最长连续序列

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

3. 字典

3.1 49. 字母异位词分组

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

3.2 560. 和为 K 的子数组 (前缀和PreSum)

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

4. 贪心

4.1 55. 跳跃游戏

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

4.2 45. 跳跃游戏 II

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

4.3 134. 加油站

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  # 最低燃料的下一个开始

4.4 121. 买卖股票的最佳时机

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

4.5 122. 买卖股票的最佳时机 II

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

5. 矩阵模拟

5.1 48. 旋转图像

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]

5.2 54. 螺旋矩阵

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

5.3 59. 螺旋矩阵 II

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