Leetcode 0010. Regular Expression Matching (python)
10. Regular Expression Matching题目Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: 123Input: s = "aa", p = "a"Output: falseExplanation: "a" does not match the entire string "aa". Example 2: 123Inp...
C++ 关联容器（map 与 set）解析
一、关联容器的底层数据结构特性C++ 标准库中的map和set均属于关联容器，其底层实现基于红黑树（Red-Black Tree）—— 一种自平衡的二叉搜索树。这种数据结构具有以下核心特性： 有序性：元素按照键值的比较规则进行排序存储 自平衡性：通过特定的旋转和着色操作，保证树的高度始终保持在 O (log n) 级别 迭代效率：支持高效的顺序访问和范围查询 红黑树的平衡机制确保了所有基本操作（插入、删除、查找）都能在O(log n) 的时间复杂度内完成，这使得关联容器在需要频繁查找和有序遍历的场景中表现优异。 二、map 与 set 的存储机制差异虽然map和set共享相同的底层实现机制，但它们的存储方式存在本质区别： 特性 set map 存储内容 仅存储键（key） 存储键值对（key-value） 元素唯一性 键值唯一，不允许重复 键值唯一，不允许重复 访问方式 只能通过键访问元素 可通过键访问对应的值 模板参数 std::set<Key, Compare, Allocator> std::map<Key, Value,...
Leetcode 0637. Average of Levels in Binary Tree
637. Average of Levels in Binary TreeGiven the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Example 1: 1234Input: root = [3,9,20,null,null,15,7]Output: [3.00000,14.50000,11.00000]Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.Hence return [3, 14.5, 11]. Example 2: 12Input: root = [3,9,20,15,7]Output: [3.00000,14.50000,11.00000...
Python函数定义：def关键字与缩进规则
Python的函数定义使用def关键字，与C++等语言不同，Python不使用大括号来标记函数体，而是依靠缩进来区分代码块。本文将详细介绍Python函数定义的方式和特点。 一、Python函数定义的基本语法1. 基本结构123456# Python函数定义def greet(): print("Hello, World!")# 调用函数greet() # 输出：Hello, World! 2. 带参数的函数123456789101112# 带参数的函数def greet(name): print(f"Hello, {name}!")greet("Alice") # 输出：Hello, Alice!# 多个参数def add(a, b): return a + bresult = add(3, 5)print(result) # 输出：8 3. 默认参数值123456789# 默认参数def greet(name, greeting="Hello"): ...
C++ Map 容器
一、核心数据结构：红黑树C++ 标准库中std::map的底层实现采用红黑树（Red-Black Tree），这是一种自平衡的二叉搜索树（BST）。红黑树通过特定的规则保证树的高度始终维持在 O (log n) 级别，从而确保各种操作的高效性。 1具体见前一篇 C++ 标准库中的 set 容器 二、map 容器的核心组件2.1 迭代器实现std::map的迭代器是双向迭代器，其实现本质上是红黑树节点的指针封装，并提供了遍历树的操作。 2.2 内存管理机制std::map通常使用内存池（memory pool）或分配器（allocator）管理节点内存，而非频繁调用new和delete： 采用 slab 分配策略，预先分配一批节点内存 节点释放时不直接归还给系统，而是放入空闲列表 下次分配时优先从空闲列表获取，减少系统调用开销 三、核心操作实现3.1 插入操作（insert）插入操作流程： 按照二叉搜索树规则找到插入位置 插入新节点并标记为红色 执行修复操作（rebalance），可能包括： 变色（recoloring） 旋转（rotation）：左旋、...
Leetcode 0009. Palindrome Number (python)
9. Palindrome Number题目Given an integer x, return true if x is a palindrome, and false otherwise. Example 1: 123Input: x = 121Output: trueExplanation: 121 reads as 121 from left to right and from right to left. Example 2: 123Input: x = -121Output: falseExplanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: 123Input: x = 10Output: falseExplanation: Reads 01 from right to left. Therefore it is not a palindrome. Constra...
Leetcode 0626. 换座位
626. 换座位表: Seat 123456789+-------------+---------+| Column Name | Type |+-------------+---------+| id | int || student | varchar |+-------------+---------+id 是该表的主键（唯一值）列。该表的每一行都表示学生的姓名和 ID。ID 序列始终从 1 开始并连续增加。 编写解决方案来交换每两个连续的学生的座位号。如果学生的数量是奇数，则最后一个学生的id不交换。 按 id 升序 返回结果表。 查询结果格式如下所示。 示例 1: 1234567891011121314151617181920212223输入: Seat 表:+----+---------+| id | student |+----+---------+| 1 | Abbot || 2 | Doris || 3 | Emerson || 4 | Green || 5 | Jeames |+----+---...
Leetcode 0008. String to Integer (atoi) (python)
8. String to Integer (atoi)题目Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The algorithm for myAtoi(string s) is as follows: Whitespace: Ignore any leading whitespace (" "). Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity if neither present. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is rea...
Leetcode 0611. Valid Triangle Number
611. Valid Triangle NumberGiven an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: 123456Input: nums = [2,2,3,4]Output: 3Explanation: Valid combinations are: 2,3,4 (using the first 2)2,3,4 (using the second 2)2,2,3 Example 2: 12Input: nums = [4,2,3,4]Output: 4 题目大意给定一个整数数组 nums，返回数组中可作为三角形三条边长度的三元组数量。三角形三条边需满足：任意两边之和大于第三边。 核心解题思路：排序 + 双指针三角形三边的核心条件是：两边之和大于第三边。对于排序后的数组，可简化为： 设三条边为 a ≤ b...
Python数值处理：round()函数四舍五入机制
Python的round()函数是处理浮点数四舍五入的重要工具。本文将详细介绍round()函数的使用方法以及常见的精度问题。 一、round()函数的基本用法1. 基本语法1round(number, ndigits) number：要四舍五入的数字 ndigits：保留的小数位数（可选，默认为0） 2. 基本示例12345# 基本四舍五入print(round(3.14159)) # 输出：3print(round(3.5)) # 输出：4print(round(3.14159, 2)) # 输出：3.14print(round(3.14159, 4)) # 输出：3.1416 3. 负数四舍五入1234567# 负数四舍五入到整数print(round(-3.5)) # 输出：-4print(round(-3.4)) # 输出：-3# 负数四舍五入到小数位print(round(-3.14159, 2)) # 输出：-3.14print(round(-3.14159, 3)) # 输出：-3.1...
C++ 标准库中的 set 容器
一、set 容器的本质与底层数据结构C++ 标准库中的std::set是一种关联式容器，其核心特性是自动排序和唯一性。与序列式容器（如 vector、list）不同，set 中的元素是按照特定的排序规则进行存储的，这使得 set 具有高效的查找、插入和删除操作。 std::set的底层实现采用了红黑树（Red-Black Tree） 这一自平衡二叉搜索树数据结构。红黑树通过一系列规则保证了树的平衡性，从而确保了基本操作（插入、删除、查找）的时间复杂度均为 O (logN)，其中 N 为树中元素的数量。 在 C++ 标准库中，红黑树的实现通常被封装在_Rb_tree类模板中，而 set 则是该类模板的一个特化应用，专门用于存储键值对中的键（在 set 中，键和值是同一个概念） 二、红黑树的结构解析2.1 红黑树节点的构成红黑树的每个节点通常包含以下几个部分： 键（key）：即存储的元素值，用于节点间的比较 左孩子指针（left child）：指向当前节点的左子节点 右孩子指针（right child）：指向当前节点的右子节点 父节点指针（parent）：指向当前节点的父节点...
Leetcode 0007. Reverse Integer (python)
7. Reverse Integer题目Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned). Example 1: 12Input: x = 123Output: 321 Example 2: 12Input: x = -123Output: -321 Example 3: 12Input: x = 120Output: 21 Constraints: -2³¹ <= x <= 2³¹ - 1 题目大意将一个 32 位有符号整数的数字部分反转。如果反转后的整数溢出 32 位有符号整数范围...
Leetcode 0572. Subtree of Another Tree
572. Subtree of Another TreeGiven the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself. Example 1: 12Input: root = [3,4,5,1,2], subRoot = [4,1,2]Output: true Example 2: 12Input: root = [3,4,5,1,2,null,null,nu...
Python类型转换机制及与C++对比
Python和C++在类型转换方面有着显著的不同。Python是一种动态类型语言，类型转换通常发生在运行时；而C++是一种静态类型语言，类型转换需要在编译时明确指定。本文将详细介绍Python中的类型转换方式及其与C++的区别。 一、Python类型转换的基本方式1. 隐式类型转换Python在某些情况下会自动进行类型转换： 12345678910# 整数和浮点数运算时，整数自动转换为浮点数result = 10 + 3.5print(result) # 输出：13.5print(type(result)) # 输出：<class 'float'># 布尔值与整数运算result = True + 5print(result) # 输出：6result = False + 10print(result) # 输出：10 2. 显式类型转换（强制类型转换）Python使用构造函数进行显式类型转换： 123456789101112# 转换为整数print(int(3.7)) # 输出：3print(int("42")) ...
C++ 标准库中 pair 的实现原理与应用解析
一、pair 的模板定义与类型参数设计1.1 基本模板定义C++ 标准库中的std::pair是一个模板类，用于存储两个异构对象作为一个单元。其基本定义如下： 123456789101112namespace std { template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; // 构造函数及其他成员函数... };} 这个定义展示了pair的核心特征： 两个模板类型参数T1和T2，分别指定了两个成员的类型 公开的成员变量first和second，分别存储第一个和第二个元素 类型别名first_type和second_type，用于获取元素类型 1.2 类型推导机制在 C++11 及以后的标准中，引入了std::make_pair函数，它能够自动推导pair的模板参...
Leetcode 0570. 至少有5名直接下属的经理
570. 至少有5名直接下属的经理表: Employee 123456789101112+-------------+---------+| Column Name | Type |+-------------+---------+| id | int || name | varchar || department | varchar || managerId | int |+-------------+---------+id 是此表的主键（具有唯一值的列）。该表的每一行表示雇员的名字、他们的部门和他们的经理的id。如果managerId为空，则该员工没有经理。没有员工会成为自己的管理者。 编写一个解决方案，找出至少有五个直接下属的经理。 以 任意顺序 返回结果表。 查询结果格式如下所示。 示例 1: 123456789101112131415161718输入: Employee 表:+-----+-------+------------+-----------+| id | name | department ...
Leetcode 0006. Zigzag Conversion (python)
6. Zigzag Conversion题目The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) 123P A H NA P L S I I GY I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: 1string convert(string s, int numRows); Example 1: 12Input: s = "PAYPALISHIRING", numRows = 3Outpu...
Leetcode 0515. Find Largest Value in Each Tree Row
515. Find Largest Value in Each Tree RowGiven the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed). Example 1: 12Input: root = [1,3,2,5,3,null,9]Output: [1,3,9] Example 2: 12Input: root = [1,2,3]Output: [1,3] 题目大意给定一棵二叉树的根节点 root，返回一个数组，其中每个元素是二叉树对应行（从 0 开始索引）中的最大值。 例如： 输入二叉树 [1,3,2,5,3,null,9]，第 0 行最大值为 1，第 1 行最大值为 3，第 2 行最大值为 9，因此返回 [1,3,9]。 解题思路要找到每一行的最大值，核心是按层遍历二叉树，并在遍历过程中记录每层的最大值。具体步骤如下： 层序遍历初始化：若根节点为空，直接返回空数组；否则将根节点入队。 逐层处理节点： 记录当前队列...
C++ 短字符串优化（SSO）
引言：字符串性能的关键挑战在 C++ 开发中，std::string作为最常用的容器之一，其性能直接影响整体程序效率。传统字符串实现采用动态内存分配策略，无论字符串长度如何，都需要在堆上分配空间，这会带来： 内存分配 / 释放的开销 缓存局部性不佳 小字符串场景下的效率低下 短字符串优化（Short String Optimization, SSO）正是为解决这些问题而生的关键技术，已成为现代 C++ 标准库（如 libstdc++、libc++）的标配实现策略。 一、SSO 的核心原理1.1 传统字符串实现的缺陷传统std::string（C++11 之前）通常采用 "胖指针" 结构： 123456// 传统字符串实现（概念模型）struct String { char* data; // 指向堆内存的指针 size_t length; // 字符串长度 size_t capacity; // 已分配容量}; 这种结构对短字符串极不友好，例如存储 "hello" 这...
Python交互式编程环境使用指南
Python的交互式编程是学习和实验Python代码的强大工具。通过Python的交互式解释器（REPL），开发者可以逐行执行代码、即时查看结果，非常适合初学者入门和快速原型开发。 一、Python交互式解释器1. 启动交互式解释器在终端或命令行中直接输入python或python3即可启动： 1234$ pythonPython 3.11.0 (default, ...)Type "help" for more information.>>> 2. 基本操作12345678910111213# 直接计算>>> 2 + 24# 变量赋值>>> x = 10>>> y = 20>>> x + y30# 调用函数>>> print("Hello, World!")Hello, World! 3. 退出交互式解释器1234>>> exit()# 或者>>> quit()# 或者按 Ctrl+D（Lin...
Leetcode 0005. Longest Palindromic Substring (python)
5. Longest Palindromic Substring题目Given a string s, return the longest palindromic substring in s. Example 1: 123Input: s = "babad"Output: "bab"Explanation: "aba" is also a valid answer. Example 2: 12Input: s = "cbbd"Output: "bb" Constraints: 1 <= s.length <= 1000 s consist of only digits and English letters. 题目大意在给定字符串中找出最长的回文子串（palindromic substring）。回文串是指正读反读都一样的字符串。若存在多个等长的最长回文子串，返回任意一个即可。字符串长度上限为 1000，仅包含数字和英文字母。 你选用何种方法解题？本题的核...
Leetcode 0513. Find Bottom Left Tree Value
513. Find Bottom Left Tree ValueGiven the root of a binary tree, return the leftmost value in the last row of the tree. Example 1: 12Input: root = [2,1,3]Output: 1 Example 2: 12Input: root = [1,2,3,4,null,5,6,null,null,7]Output: 7 题目大意给定一棵二叉树的根节点 root，返回树的最后一行中最左边的节点值。即需要找到二叉树最深一层的最左侧节点的值。 例如： 输入二叉树 [2,1,3]，最深层是第 2 层，最左侧节点值为 1，返回 1； 输入二叉树 [1,2,3,4,null,5,6,null,null,7]，最深层是第 4 层，最左侧节点值为 7，返回 7。 解题思路找到树左下角的值，关键是确定最深层和该层的最左侧节点。主要有两种实现方法： 1. 层序遍历（BFS） 按层遍历二叉树，记录每一层的第一个节点值； 最后一层的第一个节点值即为结果...
Leetcode 0509. Fibonacci Number
509. Fibonacci Number题目The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1. Given N, calculate F(N). Example 1: Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1. Example 2: Input: 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2. Example 3: Input: 4 Output: 3 Explanation: F(4) ...
C++ 写时复制 (Copy-on-Write)
一、写时复制核心概念写时复制 (简称 COW) 是一种资源管理优化技术，其核心思想是：当多个对象需要共享同一资源时，直到其中一个对象需要修改资源前，都不需要真正复制资源，仅在修改时才创建资源的私有副本。 这种机制通过延迟复制操作，减少了不必要的内存分配和数据拷贝，从而提高程序性能，尤其适用于： 频繁复制但很少修改的场景 内存资源宝贵的环境 大型数据结构的共享访问 二、写时复制实现三要素1. 共享数据存储需要一个独立的共享数据结构，存储实际的数据内容。 1234567template <typename T>struct SharedData { T* data; // 实际数据指针 size_t size; // 数据大小 size_t ref_count; // 引用计数 // 其他元数据...}; 2. 引用计数机制通过引用计数跟踪当前有多少对象共享该资源： 当新对象共享资源时，引用计数 + 1 当对象销毁或不再共享时，引用计数 - 1 当引用计数为 0 时，释放共享资源 ...
Leetcode 0004. Median of Two Sorted Arrays (python)
4. Median of Two Sorted Arrays题目Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: 123Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2. Example 2: 123Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. 题目大意给定两个已排序的数组 nums1 和 nums2，找出这两个有序数组的中位数。...
