PeterQwQ
0%

发表于 更新于

博客是2021年就搭建好的，可惜也没有写一些技术类的文章。主要是自己也没什么本事，肚子里也没啥墨水。那还不如在互联网上记录过去一年生活与学习的痕迹，以后还能留个纪念。写流水账

实习

一月份结束了在ChaoWei Xiao老师那里的远程实习，是我第一份科研向实习工作，主要做的是大模型评测代码相关benchmark的搭建。

正如同deepseek宣传的那样，AGI的实现是算力x算法x数据，数据在其中其实扮演着很重要的角色，所以这个工作大部分时间也就在洗数据，测模型，找bad case等。据说benchmark相关的工作就是这样，但是我个人实在是觉得这样的工作没有什么含金量，也没有去继续下去。

虽然这段实习经历就三个月的时间，并没有继续延续下去，但是我觉得这倒是我受益比较多的实习经历。在zqz师兄 （虽然我觉得他情商非常低下） 的指导之下，倒是形成了自己的代码规范，对于面向对象代码的规范，方法的封装，类的继承等都比之前要写的好了很多，技术力upup。同时在做实验的时候还学到了很多分析bad case的方法，以及分析问题的角度与思路，还是蛮不错的。

寒假在家倒是挺爽的，和朋友吃吃喝喝，爽摸一个月。

阅读全文 »

发表于

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号必须闭合对应的左括号。

用一个栈来存储左括号，遇到右括号时，判断栈顶元素是否与之匹配，若匹配则弹出栈顶元素，否则将右括号压入栈中。最后判断栈是否为空即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matched = ["()", "{}", "[]"]

        for st in s:
            if len(stack) == 0:
                stack.append(st)
                continue
            if stack[-1]+st in matched:
                stack.pop()
            else:
                stack.append(st)
                
        if len(stack) == 0:
            return True
        else:
            return False

发表于

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

同时，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

用两个栈来分别存储数字和字符串，遇到数字就更新数字，遇到左括号就将数字和左括号分别入栈，遇到右括号就将栈顶的字符串出栈，直到遇到左括号，然后将字符串翻转后重复数字次入栈。最后将栈中的字符串拼接起来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def decodeString(self, s: str) -> str:
        num_stack, str_stack = [], []
        cur_num = 0
        for st in s:
            if st.isdigit():
                print(cur_num)
                cur_num = cur_num*10 + int(st)
            elif st == '[':
                num_stack.append(cur_num)
                cur_num = 0
                str_stack.append(st)
            elif not st == ']':
                str_stack.append(st)
            else:
                tmp_str = ''
                top = str_stack.pop()
                while top != '[':
                    tmp_str += top
                    top = str_stack.pop()
                tmp_str = tmp_str[::-1]*int(num_stack.pop())
                for tmp in tmp_str:
                    str_stack.append(tmp)
        return ''.join(str_stack)

发表于

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。 路径不需要从根节点开始，也不需要在叶节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

首先用深度优先搜索遍历整个二叉树，将每个节点的父节点保存在字典中。然后遍历字典，对于每个节点，向上遍历到根节点，计算路径和，如果等于目标值，则计数器加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans, parents = 0, {root: None}

        def dfs(node):
            if not node:
                return

            if node.left: parents[node.left] = node
            if node.right: parents[node.right] = node

            dfs(node.left)
            dfs(node.right)
        
        dfs(root)

        for node, parent in parents.items():
            cur_sum = 0
            while node:
                cur_sum += node.val
                if cur_sum == targetSum:
                    ans += 1

                node = parents[node]

        return ans

发表于

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

分类讨论，如果给定的两个节点分别在左右子树中，那么根节点就是最近公共祖先，如果都在左子树中，那么递归左子树，如果都在右子树中，那么递归右子树。如果当前的根节点等于其中一个节点，那么返回当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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: return right
        if not right: return left
        return root

发表于

给定两个整数数组 preorder 和 inorder ，其中 preorder 是前序遍历序列，inorder 是同一棵树的中序遍历序列。请构造并返回二叉树的根节点。

preorder 和 inorder 均无重复元素。

经典的408考研题。按照前序遍历的顺序，根节点一定是第一个元素，然后在中序遍历中找到根节点的位置，左边的元素是左子树，右边的元素是右子树。递归的构建左右子树即可。

这里找到了根节点在中序遍历中的位置，然后递归的构建左右子树。根节点在中序遍历中的位置是root_index，这个位置左边的元素是左子树，右边的元素是右子树。所以可以用这个位置将前序遍历和中序遍历分成两部分，分别递归的构建左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = preorder[0]
        root_index = inorder.index(root)

        return TreeNode(root, self.buildTree(preorder[1:root_index+1], inorder=inorder[:root_index]), self.buildTree(preorder[root_index+1:], inorder[root_index+1:]))

发表于

给定一个二叉树的 根节点 root，想象自己站在它的 右侧 ，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路很简单，就是层序遍历，每次取每一层的最后一个节点的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        stack, ans = [root], []
        while stack:
            tmp = []
            cur = stack[-1]
            ans.append(cur.val)
            for node in stack:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            stack = tmp
        return ans

发表于

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

题目要求和先序遍历的顺序相同，直接使用一个列表存储先序遍历的结果，然后将每个节点的左子树置空，右子树指向下一个节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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 flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root: return
        tmp = []
        def preorder_traversal(root):
            if not root:
                return 
            tmp.append(root)
            preorder_traversal(root.left)
            preorder_traversal(root.right)
        preorder_traversal(root)
        for i in range(1, len(tmp)):
            node = tmp[i]
            root.left = None
            root.right = node
            root = root.right

发表于

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找二叉搜索树中第 k 个最小元素（从 1 开始计数）。

我对于二叉搜索树的遍历还是不够熟练，这里采用了层序遍历的方法，将所有节点的值存入一个列表中，然后对列表进行排序，返回第k个元素即可。

实际上，对于一颗二叉搜索树，中序遍历的结果就是一个有序的列表，所以可以直接对二叉搜索树进行中序遍历，同时记录遍历的节点数，当遍历到第k个节点时，返回该节点的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        queue, ans = [root], []
        while queue:
            tmp =[]
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
                ans.append(node.val)
            queue = tmp
        ans = sorted(ans)
        return ans[k-1]

发表于

给你一个二叉树的根节点 root ，判断其是否是一个有效的 二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

这题目主要是要理解到底什么样才是有效的二叉搜索树。对于一个节点而言，不仅仅是它的左节点要小于它，右节点要大于它，而且它的左节点的左节点也要小于它，右节点的右节点也要大于它。

所以我们需要传递一个上下界，来判断当前节点是否在这个范围内。对于一个节点的左节点，它的上界就是当前节点的值，下界是负无穷。对于一个节点的右节点，它的下界就是当前节点的值，上界是正无穷。那么我们就可以递归的判断每个节点是否在这个范围内。

根节点没有上下界，所以我们可以传入负无穷和正无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check_valid(node, lower, upper):
            if not node:
                return True
            if node.val <= lower or node.val >= upper:
                return False
            return check_valid(node.left, lower, node.val) and check_valid(node.right, node.val, upper)
        return check_valid(root, float('-inf'), float('inf'))