Datawhale组队学习笔记task1—

文章目录

写在前面
- 刷题流程
- 刷题技巧
Day1题目
- 1、0003.无重复字符的最长子串
- 解答：
- 2.00004 寻找两个正序数组的中位数
- 解答：
- 3.0005.最长回文子串
- 解答
- 4.0008.字符串转换整数
- 解答：
Day2题目
- 1.0151.反转字符串中的单词
- 解答
- 2.0043.字符串相乘
- 解答
- 3.0014最长公共前缀
- 解答
Day3题目
- 1.0144.二叉树的前序遍历
- 解答
- 2.0094.二叉树的中序遍历
- 解答
- 3.0102.二叉树的层序遍历
- 解答
- Day4题目
- 1.0103.二叉树的锯齿形层序遍历
- 解答
- 2.0236.二叉树的最近公共祖先
- 解答
- 3.0104.二叉树的最大深度
- 解答

写在前面

教程内容来自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,-1
	for j in range(len(s)):
		if s[j] in dic:
			i = max(dic[s[j]],i) #更新左指针i
		dic[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 = 0
        for j in range(len(s)):
            i = dic.get(s[j],-1) #获取索引i
            dic[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) - 1
    n = len(nums2) - 1
    i = 0
    j = 0
    merge_C = []
    while i <= m and j <= n:
        if nums1[i] < nums2[j]:
            merge_C.append(nums1[i])
            i += 1
        else:
            merge_C.append(nums2[j])
            j += 1
    while i <= m:
        merge_C.append(nums1[i])
        i += 1
    while j <= n:
        merge_C.append(nums2[j])
        j += 1
    return merge_C

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merge_C = merge(nums1,nums2)
        x = len(merge_C) // 2
        if len(merge_C) % 2 == 0:
            median = (merge_C[x] + merge_C[x-1]) / 2
        else:
            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 False
        k = (m + n) // 2 - 1

        while True:
            if m < n:
                nums1,nums2,m,n = nums2,nums1,n,m
            if n == 0:
                if odd:
                    return nums1[k+1]
                else:
                    return (nums1[k] + nums1[k+1]) / 2
            if k==0:
                nums =sorted(nums1[:2] + nums2[:2])
                if odd:
                    return nums[1]
                else:
                    return (nums[0] + nums[1]) / 2
            remove_num = min(k // 2,n) if k > 1 else 1
            if nums1[remove_num - 1] < nums2[remove_num - 1]:
                nums1,k = nums1[remove_num:],k - remove_num
            else:
                nums2,k = nums2[remove_num:],k - remove_num
            m = 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 = 1
        start = 0
        for j in range(1,size):
            for i in range(j):
                # 边界条件：
                # 只要头尾相等（s[i]==s[j]）就能返回True
                if j-i<=2:
                    if s[i]==s[j]:
                        dp[i][j] = True
                        cur_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] = True
                        cur_len = j-i+1
                # 出现回文更新输出
                if dp[i][j]:
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return 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 = True
        start = 0

        s = s.lstrip()
        if not s:
            return 0
        
        if s[0] == '-':
            positive = False
            start = 1
        elif s[0] == '+':
            positive = True
            start = 1
        elif not s[0].isdigit():
            return 0
        
        for i in range(start,len(s)):
            if s[i].isdigit():
                num_str += s[i]
            else:
                break
        if not num_str:
            return 0
        num = int(num_str)
        if not positive:
            num = -num
            return 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 //用来存储最终转换后的整数值,初值为none
        negative:bool | None = None //用来标记数字是否是负数,初值为none
        
        for 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 尚未赋值，则将其转为整数。如果是负数，则乘以 -1
                elif 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.MAX
                else:
                    output -= int(char)//如果是负数，则从 output 中减去当前数字
                    if output <= self.MIN:
                        return self.MIN//如果结果超出范围（即大于 MAX 或小于 MIN），直接返回 MAX 或 MIN。
            else:
                break
        return 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+carry
                    cur=temp%10
                    carry=temp//10
                    sum_=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:
                break
        return 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:
                return
            ans.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 []
        #跟结点入queue
        queue = [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 = ll
        return 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 = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q: return root
        left = 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 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res