Datawhale组队学习笔记task1——leetcode面试题

写在前面

教程内容来自Datawhale
开源教程：https://github.com/datawhalechina/leetcode-notes/blob/main/docs/ch07/index.md
在线学习网站：https://www.datawhale.cn/learn/summary/67

刷题流程

刷题技巧

• 五分钟思考法
• 重复刷题
• 按专题分类刷题
• 写解题报告
• 坚持刷题
  
  

Day1题目

1、0003.无重复字符的最长子串

解答：

1.思考 emmm不太会
2.看题解
1、暴力解
长度为N的字符串有[（N+1）*N]/2种子串，然后判断长度为N的子串是否有重复字符，时间复杂度为O(n^3)。
2、滑动窗口+哈希表
思路：
指针j遍历字符s，哈希表统计字符s[j]最后一次出现的索引。
每轮更新左指针i，保证区间【i+1，j】内无重复字符且最大
更新结果res，取res和本轮双指针区间【i+1，j】的最大值

class Solution:
def length0fLongestSubstring(self,s:str)c-> int:dic,res,i = {},0,-1for j in range(len(s)):if s[j] in dic:i = max(dic[s[j]],i) #更新左指针idic[s[j]] = j #哈希表记录res = max(res,j - i) #更新结果return res

复杂度分析
时间复杂度：O(N)，N为字符串长度，动态规划需遍历计算dp列表
空间复杂度：O(1)

3、动态规划+哈希表

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:dic = {}res = tmp = 0for j in range(len(s)):i = dic.get(s[j],-1) #获取索引idic[s[j]] = j #更新哈希表tmp = tmp + 1 if tmp < j - i else j - i #dp[j-1] -> dp[j]res = max(res,tmp) #max(dp[j-1],dp[j])return res

Python 的 get(key, default) 方法和 Java 的 getOrDefault(key, default) ，代表当哈希表包含键 key 时返回对应 value ，不包含时返回默认值 default

2.00004 寻找两个正序数组的中位数

解答：

1.思考：使用归并排序将两个数组num1+num2排序成一个有序数组，如果数组长度为奇数，则为[(num1+num2)/2]+1，如果为偶数则为[(num1+num2)/2]的两个数的平均值。

def merge(nums1,nums2):m = len(nums1) - 1n = len(nums2) - 1i = 0j = 0merge_C = []while i <= m and j <= n:if nums1[i] < nums2[j]:merge_C.append(nums1[i])i += 1else:merge_C.append(nums2[j])j += 1while i <= m:merge_C.append(nums1[i])i += 1while j <= n:merge_C.append(nums2[j])j += 1return merge_Cclass Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:merge_C = merge(nums1,nums2)x = len(merge_C) // 2if len(merge_C) % 2 == 0:median = (merge_C[x] + merge_C[x-1]) / 2else:median = merge_C[x]return median

时间复杂度：O(nlogn)
空间复杂度：O(n)

2 题解：二分法
使用二分法，每次排除一半，使用迭代优化，使用一遍处理，不需要再算一遍偶数.

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:m = len(nums1)n = len(nums2)odd = True if (m + n) % 2 == 1 else Falsek = (m + n) // 2 - 1while True:if m < n:nums1,nums2,m,n = nums2,nums1,n,mif n == 0:if odd:return nums1[k+1]else:return (nums1[k] + nums1[k+1]) / 2if k==0:nums =sorted(nums1[:2] + nums2[:2])if odd:return nums[1]else:return (nums[0] + nums[1]) / 2remove_num = min(k // 2,n) if k > 1 else 1if nums1[remove_num - 1] < nums2[remove_num - 1]:nums1,k = nums1[remove_num:],k - remove_numelse:nums2,k = nums2[remove_num:],k - remove_numm = len(nums1)n = len(nums2)       

时间复杂度：O(log(m+n))
空间复杂度：O(1)

3.0005.最长回文子串

解答

思考：只会暴力解
题解：动态规划——状态转移方程
动态规划：填dp表、当前ij状态、过去ij状态、如何联合得到输出、边界条件

• 定义状态：题目让我们求什么，就把什么设置为状态
  题目求s中最长的回文子串，那就判断所有子串是否为回文子串，选出最长的
  因此：dp[i][j]表示s[i:j+1]是否为回文子串（这里+1是为了构造闭区间）
• 状态转移方程：对空间进行分类讨论（当前ij状态、过去ij状态 如何联合得到输出）
• 当前ij状态：头尾必须相等（s[i]==s[j]）
• 过去ij状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）
• 边界条件：只要是找过去ij状态的时候，就会涉及边界条件（即超出边界情况处理）
  当i==j时一定是回文
  j-1-(i+1)<=0,即j-i<=2时，只要当s[i]==s[j]时就是回文，不用判断dp[i+1][j-1]
  dp[i][j] 为截取的子串
• 初始状态：这里已经直接判断j-i<=2的情况了，因此用不到初始状态，可以不设
• 输出内容：每次发现新回文都比较一下长度，记录i与长度
• 优化空间提速
  
  代码：

class Solution:def longestPalindrome(self, s: str) -> str:size = len(s)# 特殊处理if size == 1:return s# 创建动态规划dynamic programing表dp = [[False for _ in range(size)] for _ in range(size)]# 初始长度为1，这样万一不存在回文，就返回第一个值（初始条件设置的时候一定要考虑输出）max_len = 1start = 0for j in range(1,size):for i in range(j):# 边界条件：# 只要头尾相等（s[i]==s[j]）就能返回Trueif j-i<=2:if s[i]==s[j]:dp[i][j] = Truecur_len = j-i+1# 状态转移方程 # 当前dp[i][j]状态：头尾相等（s[i]==s[j]）# 过去dp[i][j]状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）else:if s[i]==s[j] and dp[i+1][j-1]:dp[i][j] = Truecur_len = j-i+1# 出现回文更新输出if dp[i][j]:if cur_len > max_len:max_len = cur_lenstart = ireturn s[start:start+max_len]   

时间复杂度：O(n^2)
空间复杂度：O(n^2)

4.0008.字符串转换整数

解答：

思考：不会
题解思路1：
1.先去除前后空格
2.检测正负号
3.读入数字，并用字符串存储数字结果
4.将数字字符串转为整数，并根据正负号转换整数结果
5.判断整数范围，并返回最终结果

代码：

class Solution:def myAtoi(self, s: str) -> int:num_str = ""positive = Truestart = 0s = s.lstrip()if not s:return 0if s[0] == '-':positive = Falsestart = 1elif s[0] == '+':positive = Truestart = 1elif not s[0].isdigit():return 0for i in range(start,len(s)):if s[i].isdigit():num_str += s[i]else:breakif not num_str:return 0num = int(num_str)if not positive:num = -numreturn max(num,-2 ** 31)else:return min(num,2 ** 31 - 1)

时间复杂度：O(n)，其中n是字符串s的长度
空间复杂度：O(1)
解法2：
处理符号（正负号）。
跳过前导空格。
逐步解析数字字符，拼接成一个整数。
处理溢出问题，确保返回的整数在 32 位范围内。
如果遇到非数字字符，停止转换。

class Solution:MAX: int = 2**31 - 1 //32 位带符号整数的最大值MIN: int = -(2**31)  // 32 位带符号整数的最小值def myAtoi(self, s: str) -> int:output:int | None = None //用来存储最终转换后的整数值,初值为nonenegative:bool | None = None //用来标记数字是否是负数,初值为nonefor char in s:if output is None: //意味着还没有开始解析数字部分if char == '+' and negative is None:negative = False//如果当前字符是 '+'，且 negative 尚未确定，则标记 negative = False 表示正数。elif char == '-' and negative is None:negative = True//如果当前字符是 '-'，且 negative 尚未确定，则标记 negative = True 表示负数elif char.isdigit():output = int(char) if not negative else -int(char)//如果当前字符是数字 (isdigit())，并且 output 尚未赋值，则将其转为整数。如果是负数，则乘以 -1elif char != ' ' or negative is not None:break//如果当前字符是空格 ' '，而 negative 尚未确定，继续跳过空格。elif char.isdigit():output *= 10//当 output 已经开始赋值时，字符为数字，则继续拼接数字。每次遇到一个数字，就将当前的 output 乘以 10（即将新数字移到十位、百位、千位等）并加上当前数字。if not negative:output += int(char)if output >= self.MAX:return self.MAXelse:output -= int(char)//如果是负数，则从 output 中减去当前数字if output <= self.MIN:return self.MIN//如果结果超出范围（即大于 MAX 或小于 MIN），直接返回 MAX 或 MIN。else:breakreturn output if output is not None else 0//如果 output 不为 None，则返回结果；如果没有有效的数字被解析（例如输入是空字符串或只有空格），则返回 0。

时间复杂度：O(n)，其中n是字符串s的长度
空间复杂度：O(1)

Day2题目

1.0151.反转字符串中的单词

解答

思考:
分割+倒序
利用 “字符串分割”、“列表倒序” 的内置函数 （面试时不建议使用） ，可简便地实现本题的字符串翻转要求。

• 由于split()方法将单词间的 “多个空格看作一个空格” （参考自 split()和split(’ ')的区别 ），因此不会出现多余的 “空单词” 。因此，直接利用 reverse() 方法翻转单词列表 strs ，拼接为字符串并返回即可。

class Solution:def reverseWords(self, s: str) -> str:s = s.strip() #删除首尾空格strs = s.split() #分割字符串strs.reverse() #翻转单词列表return ' '.join(strs) #拼接为字符串并返回

return ' '.join(s.strip().split()[::-1])

时间复杂度：O(N)
空间复杂度：O(N)

2.0043.字符串相乘

解答

思考：能不能直接将num1+num2转为整形，即int(num1)和int(num2)将两数相乘，再转为字符串。（好吧不能题目有规定）
题解：

class Solution:def multiply(self, num1: str, num2: str) -> str:n,m=len(num1),len(num2)res=0# 两个数相乘，数位数多的放上面，数位数少的放下面if n<m:return self.multiply(num2,num1)else: # 先固定下面的数的个位，然后遍历上面的数for j in range(m-1,-1,-1):y=int(num2[j])sum_="" # 当前层的和carry=0 # 当前层的进位for i in range(n-1,-1,-1):x=int(num1[i])temp=x*y+carrycur=temp%10carry=temp//10sum_=str(cur)+sum_# 考虑最后进位多出的carry(carry可以大于等于1)             if carry>=1:             sum_=str(carry)+sum_ # 计算最终结果（整数形式）res=int(sum_)*pow(10,m-j-1)+res  # 每层和进行错位相加,pow(10,m-j-1)=10**(m-j-1),自己可用找一下规律return str(res)          

时间复杂度：O(mxn)，其中m和n分别为nums1和nums2的长度。
空间复杂度：O(m+n)

3.0014最长公共前缀

解答

题解：
使用zip函数取出每个单词相同位置的字母，转化成集合如果字母相同集合长度为1，如果不同就可以直接返回结果啦

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:ans = ''for i in list(zip(*strs)):if len(set(i)) == 1:ans += i[0]else:breakreturn ans

时间复杂度：O(n)
空间复杂度：O(1)

Day3题目

1.0144.二叉树的前序遍历

解答

思考：树的先序递归遍历：先访问根节点，然后递归左子树和右子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def pre(root):if root is None:returnans.append(root.val)pre(root.left)pre(root.right)ans = []pre(root)return ans

时间复杂度 O(n)，空间复杂度 O(n)。其中 n 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

2.0094.二叉树的中序遍历

解答

思考：树的中序递归遍历：先访问左子树，然后递归根节点和右子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(root):if root is None:return      dfs(root.left)ans.append(root.val)dfs(root.right)ans = []dfs(root)return ans

时间复杂度：O(n)
空间复杂度：O(n)

3.0102.二叉树的层序遍历

解答

思考：可以利用广度优先搜索进行遍历
代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []#跟结点入queuequeue = [root]res = []while queue:res.append([node.val for node in queue])#存储当前层的孩子节点列表ll = []#对当前层的每个节点遍历for node in queue:#如果左子结点存在，入队列if node.left:ll.append(node.left)#如果右子节点存在，入队列if node.right:ll.append(node.right)#把queue更新成下一层的节点，继续遍历下一层queue = llreturn res

时间复杂度：O(n^2)
空间复杂度：O(n)

Day4题目

1.0103.二叉树的锯齿形层序遍历

解答

要求：

算法流程：
1、特例处理：当树的根节点为空，则直接返回空列表【】
2、初始化：打印结果空列表res,包含根节点的双端队列deque
3、BFS循坏：当deque为空时跳出
a.新建列表tmp，用于临时存储当前层打印结果
b.当前层打印循坏：循坏次数为当前层节点数（即deque长度）
a.出队：队首元素出队，记为node
b.打印：若为奇数层，将node.val添加至tmp尾部；否则，添加至tmp头部
c.添加子节点：若node的左右子节点不为空，则加入deque
c.将当前层结果tmp转化为list并添加入res
4、返回值：返回打印结果列表res即可
代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []res,deque = [],collections.deque([root])while deque:tmp = collections.deque()for _ in range(len(deque)):node = deque.popleft()if len(res) % 2 == 0:tmp.append(node.val) #奇数层 -> 插入队列尾部else:tmp.appendleft(node.val)#偶数层->插入队列头部if node.left:deque.append(node.left)if node.right:deque.append(node.right)res.append(list(tmp))return res

2.0236.二叉树的最近公共祖先

解答

思考：若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
p=root ，且 q 在 root 的左或右子树中；
q=root ，且 p 在 root 的左或右子树中；

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root == p or root == q: return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if not left and not right: return # 1.if not left: return right # 3.if not right: return left # 4.return root # 2. if left and right:

时间复杂度 O(N) ： 其中 N 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
空间复杂度 O(N) ： 最差情况下，递归深度达到 N ，系统使用 O(N) 大小的额外空间。

3.0104.二叉树的最大深度

解答

思考：树的层序遍历 / 广度优先搜索往往利用 队列 实现。
关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root: return 0queue, res = [root], 0while queue:tmp = []for node in queue:if node.left: tmp.append(node.left)if node.right: tmp.append(node.right)queue = tmpres += 1return res

时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度 O(N) ： 最差情况下（当树平衡时），队列 queue 同时存储 N/2 个节点。