HespethornのBlog

11. Container With Most Water题目You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. Example 1: 1234Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Explanation: The above vertical...

707. Design Linked ListDesign your implementation of the linked list. You can choose to use a singly or doubly linked list.A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. Implement the MyLinkedList ...

在Python编程中，理解函数副作用（Side Effects）是非常重要的。副作用是指函数在执行过程中，除了返回值之外，对外部状态产生的任何改变。理解副作用有助于编写更清晰、更安全的代码。 一、什么是函数副作用1. 基本定义副作用包括但不限于： 修改全局变量 修改传入的参数 输入/输出操作（打印、读取文件、网络通信等） 修改数据结构 抛出异常 2. 无副作用函数示例1234567# 无副作用：纯函数def add(a, b): return a + bresult = add(3, 5)print(result) # 输出：8# 函数外部没有任何改变 3. 有副作用函数示例12345678910# 有副作用：修改全局变量counter = 0def increment(): global counter counter += 1 return counterprint(increment()) # 输出：1print(counter) # 输出：1（全局变量被修改） 二、常见的副作用场景1. 修改全局变量123456789...

704. Binary Search题目Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Note: You may assume that all elements in nums are un...

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均属于关联容器，其底层实现基于红黑树（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,...

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关键字，与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++ 标准库中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）：左旋、...

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...

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 |+----+---...

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...

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...

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...

一、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）：指向当前节点的父节点...

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...

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 位有符号整数范围...

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")) ...

一、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的模板参...

570. 至少有5名直接下属的经理表: Employee 123456789101112+-------------+---------+| Column Name | Type |+-------------+---------+| id | int || name | varchar || department | varchar || managerId | int |+-------------+---------+id 是此表的主键（具有唯一值的列）。该表的每一行表示雇员的名字、他们的部门和他们的经理的id。如果managerId为空，则该员工没有经理。没有员工会成为自己的管理者。 编写一个解决方案，找出至少有五个直接下属的经理。 以 任意顺序 返回结果表。 查询结果格式如下所示。 示例 1: 123456789101112131415161718输入: Employee 表:+-----+-------+------------+-----------+| id | name | department ...

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...

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++ 开发中，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的交互式解释器（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...

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） 按层遍历二叉树，记录每一层的第一个节点值； 最后一层的第一个节点值即为结果...