笺札

Python面向对象编程与依赖管理 一、实验目的 掌握Python基本语法，能够独立编写带输入输出、循环判断的脚本。 理解面向对象三大特性（封装、继承、多态），能够自定义类并实现继承和方法重写。 熟练使用pip管理第三方依赖，掌握虚拟环境的创建与激活。 二、实验环境 操作系统：Windows Python版本：3.x 开发工具：VS Code 第三方库：见 requirements.txt（包含FastAPI、Uvicorn等，本次实验仅验证依赖管理能力） 三、实验内容 3.1 编写带输入输出、循环判断的Python脚本 文件：guess_num.py 该程序实现一个猜数字游戏： 程序随机生成1~100之间的整数。 用户通过控制台输入猜测的数字。 程序判断并提示“太大”、“太小”或“正确”。 循环直到猜中，并统计猜测次数。 核心代码分析： 1234567891011121314151617181920import randomclass GuessNumber: def __init__(self): self.guess_number ...

二叉树的中序遍历 🎯 问题描述（来源于LeetCode） 描述： 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 说明： 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 示例： 示例 1： 12输入：root = [1,null,2,3]输出：[1,3,2] 示例 2： 12输入：root = []输出：[] 💻 解题思路 思路1：递归算法 思路1：代码实现 1234567891011121314151617# 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 = rightclass Solution: def inorderTraversal(self, root: Opt...

二叉树的后序遍历 🎯 问题描述（来源于LeetCode） 描述： 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 说明： 树中节点的数目在范围 [0, 100] 内 -100 <= Node.val <= 100 示例： 示例 1： 12输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[4,6,7,5,2,9,8,3,1] 示例 2： 12输入：root = []输出：[] 💻 解题思路 思路1：递归 思路1：代码实现 1234567891011121314151617# 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 = rightclass Solution: def ...

二叉树的层序遍历 🎯 问题描述（来源于LeetCode） 描述： 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 说明： 树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000 示例： 示例 1： 12输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]] 示例 2： 12输入：root = [1]输出：[[1]] 💻 解题思路 思路1：递归 思路1：代码实现 12345678910111213141516171819# 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 = rightclass S...

二叉树的前序遍历 🎯 问题描述（来源于LeetCode） 描述： 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 说明： 树中节点数目在范围 [0, 100] 内 -100 <= Node.val <= 100 示例： 示例 1： 12输入：root = [1,null,2,3]输出：[1,2,3] 示例 2： 12输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[1,2,4,5,6,7,3,8,9] 💻 解题思路 思路1：递归 思路1：代码实现 1234567891011121314151617# 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 = rightclass Solut...

二叉树的最大深度 🎯 问题描述（来源于LeetCode） 描述： 给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 说明： 树中节点的数量在 [0, 104] 区间内。 -100 <= Node.val <= 100 示例： 示例 1： 12输入：root = [3,9,20,null,null,15,7]输出：3 示例 2： 12输入：root = [1,null,2]输出：2 💻 解题思路 思路1：递归 思路1：代码实现 12345678910111213141516171819# 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 = rightclass Solut...

实现Trie(前缀树） 🎯 问题描述（来源于LeetCode） 描述： Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。 请你实现 Trie 类： Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。 说明： 1 <= word.length, prefix.length <= 2000 word 和 prefix 仅由小写英文字母组成 insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次 示例： 示...

键值映射 🎯 问题描述（来源于LeetCode） 描述： 设计一个 map ，满足以下几点: 字符串表示键，整数表示值 返回具有前缀等于给定字符串的键的值的总和 实现一个 MapSum 类： MapSum() 初始化 MapSum 对象 void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。 int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。 说明： 1 <= key.length, prefix.length <= 50 key 和 prefix 仅由小写英文字母组成 1 <= val <= 1000 最多调用 50 次 insert 和 sum 示例： 示例 1： 1234567891011输入：["MapSum", "insert",...

字符串（String） 基本概念 字符串（String）是由零个或多个字符组成的有限序列，通常记为 s = a₁a₂…aₙ (0 ≤ n < ∞)。 名称：如 s 是变量名。 值：字符序列，常用双引号括起。 长度：字符个数 n。 空串：长度为 0 的字符串 ""。 子串：字符串中任意连续字符组成的序列，包括前缀（从首开始）和后缀（到末结束）。 主串：包含子串的字符串。 数据结构的三要素 逻辑结构 线性结构，字符之间呈线性关系，每个字符有唯一前驱和后继（除首尾外）。 存储结构 顺序存储 用一组地址连续的存储单元存放字符，如定长数组。 支持随机访问，时间复杂度 O(1)，空间利用率高。 链式存储 每个节点存放一个或多个字符，通过指针链接。 插入、删除灵活，但随机访问效率低（O(n)）。 各语言实现 C：字符数组 + \0 结尾，string.h 提供操作。 C++：string 类，封装动态数组。 Java：String 类，不可变。 Python：str 类型，不可变，支持切片等操作。 数据的运算 比较：按字符编码逐...

优先队列 基本概念 优先队列（Priority Queue）：是一种为每个元素分配优先级的特殊队列结构。每次访问或移除元素时，总是优先处理优先级最高的元素。 优先队列与普通队列的核心区别在于 出队顺序： 普通队列按照「先进先出（First In, First Out）」原则，元素按入队顺序依次出队。 优先队列则根据元素的优先级决定出队顺序，优先级高的元素先出队，优先级低的元素后出队，遵循 「优先级高者先出」 的规则，与入队顺序无关。 内部实现： 优先队列的基本操作与普通队列类似，主要包括 「入队」 和 「出队」，但在出队时会优先移除优先级最高的元素。 优先队列的实现方式主要有三种：数组（顺序存储）、链表（链式存储） 和 二叉堆结构。其中，最常用且高效的是基于二叉堆的实现。下面简要对比三种方案： 数组（顺序存储）：入队时直接将元素插入数组末尾，时间复杂度为 O(1)；出队时需遍历整个数组以找到优先级最高的元素并删除，时间复杂度为 O(n)。 链表（链式存储）：链表内元素按优先级有序排列，入队时需找到合适插入位置，时间复杂度为 O(n)；出队时直接移除链表头节点，时间复杂...