数据结构
快来分享你的内容吧～
2025-05-28·Java后端大家好，我是算法学长，一个热爱分享算法知识的开发者。算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。冒泡排序算法介绍冒泡排序（Bubble Sort）是一种简单直观的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此重复遍历下去，直查看全文算法学长：算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。611分享
2023-07-23·后端
2023-03-28·后端编程导航学习网站：学编程、做项目、拿 Offer！企业高频面试题库：开始刷题，面试遇原题！精选简历模板大全：1 分钟搞定简历！AI 资源导航网站：获取最新 AI 黑科技！1 对 1 模拟面试：随时随地提升面试能力数据结构和算法求职高频面试题：开始刷题开篇介绍为什么数据结构和算法如此重要？因为：程序 = 数据结构 + 算法数据结构 是一组数据的存储结构和组织方式，使得该组数据便于访问、修改、存储。算查看全文鱼友2917：C++数据结构与算法的课程基本没有诶,全是Java的课,鱼皮哥怎么办.迷茫...27373分享
2022-12-26- 2022-12-26
Go 语言中的数组、切片、Map和List
这篇文章已经放到腾讯智能工作台的知识库啦，链接在这里：[ima.copilot-Go 入门到入土](https://ima.qq.com/wiki/?shareId=6467e4feb4e225ab1acf92d9134ba4baeaf578ed327f9ba285da311f9ea4742a)。要是你有啥不懂的地方，就去知识库找 AI 聊一聊吧。 # 1、数组的基本用法 在前面的博客中，我们主要介绍了 Go 语言的基础数据类型。然而，在实际的软件开发中，我们通常需要一个“容器”来管理和组织这些基础数据，以便更高效地处理批量数据。Go 语言提供了多种集合类型（或称容器）来满足不同的开发需求。 ## 1、Go 语言的核心集合类型 Go 语言内置了四种主要的集合类型数据结构： 1. **数组 (Array)**：存储固定长度、相同类型元素的序列。 2. **切片 (Slice)**：一个动态、灵活的数组视图，是 Go 中最常用的集合类型。 3. **Map**：键值对的无序集合，类似于其他语言中的哈希表或字典。 4. **列表 (List)**：Go 标准库 `container/list` 提供了双向链表的实现。 在这些类型中，**切片 (Slice)** 和 **Map** 的使用频率最高，也是我们后续需要重点掌握的。数组因为其固定长度的特性，使用场景相对有限，而 List 在日常开发中也并不常见。 本节，我们首先深入讲解 Go 语言中的 **数组 (Array)**。 ## 2、 数组的定义与特性 Go 语言中的数组与 C 或 Java 等语言中的数组有显著区别，尤其是在类型系统层面。 ### 2.1 定义语法 数组的定义语法如下： ```go var variableName [size]Type ``` - `var`: 声明变量的关键字。 - `variableName`: 数组变量的名称。 - `[size]`: 数组的长度（元素个数），**这是类型的一部分**。 - `Type`: 数组中存储的元素类型。 请注意，数组的长度 `[size]` 是写在类型 `Type` 前面的，这与其他许多静态语言的习惯不同。 例如，让我们定义一个包含 3 个字符串元素的数组：  ### 2.2 长度是类型的一部分 这是 Go 数组最核心的特性。一个数组的类型由其**长度**和**元素类型**共同决定。这意味着，`[3]string` 和 `[4]string` 是两种完全不同且不兼容的数组类型。 我们可以通过下面的代码来验证这一点：  运行结果：  从输出中可以清晰地看到，编译器将 `[3]string` 和 `[4]string` 识别为不同的类型。因此，不同长度的数组之间不能直接赋值，这大大增强了 Go 语言的类型安全性，但也限制了数组的灵活性。 ## 3、数组的初始化与遍历 ### 3.1 赋值 数组的元素可以通过索引进行访问和赋值，索引从 0 开始。  ### 3.2 遍历 遍历数组最常用的方式是使用 `for...range` 循环。  ## 4、数组 vs 切片：一个重要的区分 有同学可能会想，如果定义时不指定长度，是不是就可以创建一种“通用”的数组类型了？比如 `var a []string`。 这是一个非常关键的概念点：**当你不指定长度时，你创建的不再是数组，而是一个切片（Slice）**。 `[3]string` 是一个**数组类型**，而 `[]string` 是一个**切片类型**。它们是两种不同的数据结构，切片在内部依赖于数组，但提供了更为强大的动态能力。我们将在下一节重点讲解切片。 #### 何时使用数组？ 尽管数组的长度固定，但在某些特定场景下它依然很有用： - **性能**: 当元素个数固定时，数组的性能非常高，因为其内存布局是连续且大小已知的。 - **可预测性**: 用于存储固定集合的数据，例如表示一周七天、颜色（RGB）等。 # 2、数组的初始化和遍历 在 Go 语言中，数组是一种固定长度的、包含相同类型元素的数据结构。正确地初始化和遍历数组是日常开发中的基本功。本文将深入探讨 Go 语言中数组初始化的多种方法以及常用的遍历方式。 ## 1、数组的初始化 Go 语言提供了多种灵活的方式来初始化数组，以适应不同的开发场景。 ### 1.1 基本初始化 在定义数组时，我们可以直接提供一组初始值，从而简化代码。  在上面的例子中，`:=` 是短变量声明操作符，它会根据右侧的值自动推断变量 `courses` 的类型为 `[3]string`。这种写法在 Go 中最为常见和推荐。 ### 1.2 指定索引初始化 有时，我们可能只想初始化数组中的某几个特定元素，而让其他元素保持其类型的**零值**（Zero Value）。对于 `string` 类型，其零值是空字符串 `""`。 这种方法通过 `索引:值` 的形式实现，非常灵活。  这种方式特别适用于需要设置稀疏数据或在特定位置插入初始值的场景。 ### 1.3 使用 `...` 自动推导长度 在初始化时，如果我们希望数组的长度由初始值的数量来决定，可以使用 `...` 省略号。编译器会自动计算元素的数量并设置数组的长度。  **重点**: `...` 并非创建了一个动态数组。数组的长度在编译时就已经确定，并成为其类型的一部分。因此，`[2]string` 和 `[3]string` 是两种**完全不同**的类型。 ## 2、数组的遍历 遍历数组是访问其元素的基本操作。Go 语言同样支持多种遍历方式。 ### 标准 `for` 循环 这是从 C 语言继承而来的传统遍历方式，通过索引来访问数组中的每一个元素。  这种方法直观易懂，并且在需要使用元素索引进行计算时非常有用。建议熟练掌握。 # 3、数组比较与多维数组 本节将探讨 Go 语言中数组的比较规则以及多维数组的定义、初始化和遍历方法。这些是掌握 Go 数据结构的重要基石。 ## 1、 数组的比较 在 Go 语言中，数组可以直接使用相等运算符 `==` 或 `!=` 进行比较，这为我们判断两个数组是否相同提供了极大的便利。但是，能够进行比较需要满足两个核心前提。 **比较的两个前提条件：** 1. **类型相同**：数组的长度是其类型的一部分。因此，只有长度完全相同的数组才能进行比较。例如，一个 `[2]string` 类型的数组和一个 `[3]string` 类型的数组是无法进行比较的，这会在编译时就引发错误。 2. **元素值与顺序完全一致**：当两个数组类型相同时，`==` 会逐一比较其内部的每一个元素。只有当所有对应位置的元素都相等时，两个数组才被认为是相等的。元素的顺序也至关重要。  ## 2、多维数组 当一维数组无法满足我们存储更复杂、结构化数据的需求时，多维数组就派上了用场。例如，我们可以用一个二维数组来存储一个班级所有学生各科的成绩，或者存储一系列课程的详细信息。 ### 2.1 声明与初始化 多维数组的定义非常直观，例如 `[3][4]string` 表示一个3行4列的二维字符串数组。 **💡 实用场景**：假设我们需要存储三门课程的信息，每门课程都包含四个属性：课程名、时长、讲师和简介。  **注意**：像 `courses[0][2] = "NewTeacher"` 这样对单个元素赋值也是完全支持的，但通过整行初始化在许多场景下更为清晰。 ### 2.2 遍历多维数组 遍历多维数组通常需要使用嵌套循环。 #### 方法一：标准 for 循环 通过嵌套两层 `for` 循环，外层循环控制行，内层循环控制列。  #### 方法二：使用 for...range (推荐)  # 4、切片的定义和赋值 本节，我们将深入讲解 Go 语言集合类型中一个至关重要的数据结构——切片（Slice）。切片在 Go 项目中应用极为广泛，为了帮助大家在实际开发中避免可能遇到的问题，我们将详细剖析其核心概念与细节。 ## 1、 切片：Go 语言的动态数组 可以将切片理解为一种“动态数组”，它类似于 Python 中的 `list` 或其他语言中的动态数组（Dynamic Array）。 在许多静态编译型语言中，数组（Array）的长度在定义时就已固定，无法在运行时改变。例如，声明一个长度为 3 的数组后，就不能再向其中添加第四个元素。因此，这类静态数组通常不提供 `append`（追加）等操作。 与此不同，动态语言中的数组或列表（List）通常是动态的，可以随时方便地向其追加元素。 Go 语言在此问题上采取了一种折中的设计方案。它保留了传统意义上的**数组**，但其长度是类型的一部分，这使得不同长度的数组成为不同的类型，从而在一定程度上弱化了其灵活性。为了弥补这一不足并提供动态集合的功能，Go 推出了**切片（Slice）**。 切片的本质是**对底层数组一个连续片段的引用**。可以理解为，Go 在原生数组的基础上构建了功能更丰富的切片，使其具备动态数组的特性，这种设计更符合大多数开发场景的习惯。 ## 2、切片的定义 定义一个切片与定义数组的语法非常相似，关键区别在于**定义切片时不需要指定长度**。  这里的 `[]string` 就表示一个元素类型为 `string` 的切片。切片的元素类型可以是任意的，例如 `int`、`struct`，甚至可以是数组或另一个切片，构成多维结构 ## 3、切片的基本操作 ### 3.1 追加元素 (Append) 向切片中添加元素最常用的方法是使用 Go 的内置函数 `append`。 `append` 函数的用法非常特殊，初学者需要特别注意：**它会返回一个包含新增元素的新切片，这个返回值必须重新赋给原来的切片变量。**  **重点解释 `append` 的工作机制：** 初次接触时，`slice = append(slice, element)` 这种语法可能会令人困惑。为什么不能直接修改原切片，而必须接收返回值？ 这是因为切片在容量（Capacity）不足以容纳新元素时，Go 会分配一个全新的、更大的底层数组，并将原有元素和新元素一并拷贝过去。此时，返回的切片将指向这个新的内存地址。如果不接收返回值，原始的切片变量将仍然指向旧的、较小的底层数组，导致添加操作“丢失”。 这个机制是切片实现动态增长的关键，也是一个常见的面试考点。我们将在后续文章中更深入地探讨其内部原理。 ### 3.2 访问元素 访问切片中的单个元素与访问数组元素的方法完全相同，都是通过索引（index）实现，索引从 0 开始。  ### 3.3 遍历切片 使用 for range 循环遍历切片的方式也和遍历数组一致，这是最常用和推荐的遍历方式。  # 5、切片的多种初始化方式 在前一节中，我们学习了切片的基本定义和如何通过 `append` 函数添加元素。本节，我们将重点介绍初始化切片的三种常用方法。 切片的初始化主要有以下三种方式： 1. **从现有数组或切片创建**：通过截取（slicing）操作生成一个新的切片。 2. **使用切片字面量（Slice Literal）**：在声明时直接提供初始元素，类似于数组的初始化。 3. **使用 `make` 内置函数**：预先分配切片的存储空间，适用于已知大概容量的场景。 这三种方法在实际开发中都非常普遍，掌握它们对于高效使用 Go 语言至关重要。 ## 1、 从数组创建切片 可以从一个已存在的数组中“截取”一部分元素来创建一个新的切片。这种操作不会复制元素，而是创建一个指向原数组部分数据的新切片。 **语法**：`array[low:high]` 这种语法创建一个包含从索引 `low` 到 `high-1` 元素的切片。这是一个**左闭右开**区间，即包含 `low` 索引处的元素，但不包含 `high` 索引处的元素。新切片的长度为 `high - low`。 **示例**： 假设我们有一个包含五门课程的数组，现在希望从中提取前两门课程创建一个切片。  **注意**：Go 的切片操作语法借鉴自 Python，非常灵活。例如，`allCourses[:]` 可以将整个数组转换为一个切片。 ## 2、 使用切片字面量 (Slice Literal) 这是最直接的初始化方式，可以在声明时直接填充元素。其语法与数组字面量非常相似，但**不需要在 `[]` 中指定长度**。  这种方式同样可以用于从一个现有切片创建新切片。 ## 3、使用 `make` 内置函数 当需要在创建切片时预留存储空间，以提高性能（特别是在能预估最终元素数量时），可以使用 `make` 函数。这样做可以避免后续 `append` 操作可能引发的频繁内存重新分配和数据拷贝。 `make` 函数可以接受两个或三个参数： - **`make([]T, length)`**：创建一个类型为 `[]T`，长度（length）为 `length` 的切片。其容量（capacity）也等于 `length`。 - **`make([]T, length, capacity)`**：创建一个类型为 `[]T`，长度为 `length`，容量为 `capacity` 的切片。  **重要对比**： - **使用 `make`**：切片被创建时，其底层数组已经被分配，并且长度被设定。因此，你可以直接通过索引对 `0` 到 `length-1` 范围内的元素进行赋值。 - **仅声明 `var slice []T`**：此时切片的值为 `nil`，其长度和容量都为 0。你不能通过索引直接赋值，因为底层数组不存在。这种情况下，必须使用 `append` 来添加第一个元素。  掌握这三种初始化方法至关重要： - 当需要从现有数组或切片中获取子集时，使用**切片表达式** (`[low:high]`)。 - 当在编码时已知所有初始元素时，使用**切片字面量** (`[]T{...}`) 最为简洁。 - 当可以预估切片所需存储的元素数量时，使用 **`make` 函数**预分配容量，可以获得最佳性能。 由于切片在 Go 编程中的核心地位，请务必熟练掌握并理解这三种基本用法的适用场景。 # 6、切片的数据访问 本节，我们将探讨如何访问 Go 语言切片中的元素。这些是切片非常常用的操作，需要熟练掌握。访问切片元素主要分为两种情况：访问单个元素和访问多个元素（即创建子切片）。 ## 1、访问单个元素 访问切片中的单个元素与访问数组的方法完全相同，都是通过索引（index）来完成。 **语法**：`slice[index]` 需要注意的是，索引必须在有效范围内，即 `0 <= index < len(slice)`。尝试访问超出此范围的索引将导致程序运行时发生 `panic`。  ## 2、访问多个元素（创建子切片） 在更多场景下，我们常常需要获取切片中一个连续的子集。这可以通过**切片表达式 Slicing Expression**来实现，其语法非常灵活。 **基本语法**：`slice[start:end]` - `start`：起始索引（包含该索引对应的元素）。 - `end`：结束索引（**不包含**该索引对应的元素）。 这是一个**左闭右开**的区间。`start` 和 `end` 索引都是可选的。下面我们详细说明其四种主要用法。 假设我们有以下基础切片用于演示：  ### 2.1 指定起始和结束索引 `slice[start:end]` 截取一个明确范围的子集。  ### 2.2 省略结束索引 `slice[start:]` 表示从 `start` 索引开始，一直截取到切片的末尾。  ### 2.3 省略起始索引 `slice[:end]` 表示从切片的开头（索引 0）开始，一直截取到 `end` 索引之前。  ### 2.4 同时省略起始和结束索引 `slice[:]` 这会创建一个包含原切片所有元素的新切片。需要注意的是，这是一种“浅拷贝”：新切片和原切片共享同一个底层数组，但它们是两个独立的切片头结构。  **语法借鉴**：Go 的切片语法很大程度上借鉴了 Python，但功能上是其子集，相对更为简洁，易于学习和使用。 # 7、切片（Slice）的数据添加与合并 在前几节中，我们已经接触了用于向切片添加元素的 `append` 内置函数。本节，我们将深入探讨 `append` 的更多高级用法和细节。 回顾一下 `append` 的两个基本要点： 1. 它是一个内置的全局函数。 2. 它返回一个新的切片，必须用原切片变量接收其返回值，否则添加操作将无效。 ## 1、 一次性追加多个元素 `append` 函数不仅可以一次添加一个元素，还可以通过可变参数（variadic parameter）的形式，一次性添加多个元素。 **示例**： 假设我们有一个初始切片，现在需要同时向其中添加 "Gin"、"MySQL" 和 "Elasticsearch"。  **源码解读**： `append` 函数的定义类似 `func append(slice []T, elements ...T) []T`。 参数 `elements ...T` 表示可以接收零个或多个 `T` 类型的参数。这就是为什么我们可以传入任意数量的元素。 ## 2、 合并两个切片 当需要将一个切片的所有元素添加到另一个切片末尾时，最直观的想法可能是使用 `for` 循环遍历并逐个 `append`。 **传统方法：使用 for 循环**  虽然这种方法可行，但 Go 提供了更为简洁和高效的语法。 **推荐方法：使用 `...` 语法** 我们可以利用 `append` 的可变参数特性，将一个切片“打散”成独立的元素序列，然后一次性追加。这通过在要添加的切片名称后加上 `...` 实现。  这种写法在功能上等同于 `for` 循环，但代码更简洁，可读性更强，是 Go 语言中合并切片的标准做法。 **注意**：你不能直接将一个切片 `append` 到另一个切片中，因为它们的类型不匹配。`append(courseSlice1, courseSlice2)` 会导致编译错误，因为它试图将 `[]string` 类型的 `courseSlice2` 作为一个单一元素添加到只能存放 `string` 的 `courseSlice1` 中。 ## 3、追加另一个切片的子集 `...` 语法同样可以与切片表达式结合使用，从而实现只追加另一个切片的部分元素。 **示例**： 假设 `courseSlice2` 中包含 `{"MySQL", "Elasticsearch", "Gin"}`，我们只想将 "Elasticsearch" 和 "Gin" 追加到 `courseSlice1`。  这种组合用法极大地增强了 `append` 操作的灵活性。 本节我们深入学习了 `append` 函数的高级用法。关键点在于，它不仅可以一次性追加多个独立的元素，更重要的是，可以通过 `...` 语法高效地将一个切片（或其子切片）的所有元素合并到另一个切片中。这是 Go 开发中非常常用且重要的技巧。 # 8、切片（Slice）的删除与复制操作 本节，我们将学习如何在 Go 语言的切片中删除和复制元素。与取值操作的直接性不同，删除操作的实现方式需要特别注意。 ## 1、 从切片中删除元素 Go 没有提供一个直接的内置函数来删除切片中的元素（如 `delete(slice, index)`），这一操作需要通过切片本身的拼接能力来实现。 ### 1.1 删除中间的元素 要删除切片中间的一个或多个元素，核心思路是：**将需要删除的元素“左边”的部分和“右边”的部分拼接在一起，构成一个新的切片。** **实现方法：** 1. 使用切片表达式 `slice[:index]` 获取要删除元素之前的所有元素。 2. 使用切片表达式 `slice[index+1:]` 获取要删除元素之后的所有元素。 3. 使用 `append` 函数将这两部分合并。 **示例**：从以下切片中删除 "MySQL"（索引为 2）。  这种用法虽然看起来有些绕，但它是 Go 中实现“删除”操作的标准模式。 ### 1.2 删除末尾的元素 如果想删除从某个索引开始到末尾的所有元素，操作就简单得多，只需重新切片，保留所需的部分即可。 **示例**：删除 "MySQL" 及之后的所有元素。  **性能说明**：频繁的切片操作看似会影响性能，但由于切片主要操作的是指向底层数组的指针和元数据（长度、容量），而不是大规模复制数据本身，因此在大多数情况下性能是可以接受的。 ## 2、复制切片 复制切片时，必须区分**浅拷贝（Shallow Copy）**和**深拷贝（Deep Copy）**。 - **浅拷贝**：新旧两个切片共享同一个底层数组。修改其中一个切片会影响到另一个。 - **深拷贝**：为新切片创建一个全新的底层数组，并复制所有元素。新旧切片完全独立。 ### 2.1 浅拷贝（赋值与切片表达式） 直接赋值 (`newSlice := oldSlice`) 或使用完整的切片表达式 (`newSlice := oldSlice[:]`) 都只会创建一个新的切片头，它与原切片指向同一个底层数组。 **示例**：  可见，修改 `originalSlice` 会直接影响 `shallowCopy`。 ### 2.2 深拷贝（使用 `copy` 内置函数） 要实现真正的深拷贝，应使用 Go 的内置 `copy` 函数。它将元素从源切片复制到目标切片。 **关键点**：`copy` 函数**不会**为目标切片自动扩容。你必须确保目标切片有足够的**长度**来接收被复制的元素。通常，我们会使用 `make` 函数来创建一个长度与源切片相同的目标切片。 **语法**：`copy(destination, source)` **示例**：  可以看到，`deepCopy` 是一个完全独立的副本，不受对原始切片修改的影响。 理解这些操作的底层机制至关重要。如果不清楚浅拷贝和深拷贝的区别，很可能会在程序中引入难以察觉的 bug。 # 9、切片 (Slice) 的底层实现原理：值传递与引用传递之谜 在 Go 语言中，如果不了解切片（Slice）的底层实现原理，开发过程中极易遇到难以排查的问题。因此，深入理解其工作机制，尤其是在函数调用中的表现，至关重要。这也是一个常见的面试热点。 本节，我们将通过实验现象，引出一个核心问题： > **Go 的切片在作为函数参数传递时，是值传递（Pass-by-Value）还是引用传递（Pass-by-Reference）？** 严格来说，Go 语言中所有函数参数传递都是**值传递**。然而，切片的操作效果却常常呈现出引用传递的特征，但又不完全是。这种模棱两可的表现是初学者最主要的困惑来源。 为了揭示这一现象，我们来看两个截然相反的实验。 ## 1、场景一：在函数内修改切片元素 我们定义一个函数，它接收一个切片作为参数，并尝试修改该切片的某个元素。  **现象分析**： 函数 `modifySlice` 内部对 `data` 第一个元素的修改，成功地反映到了 `main` 函数的原始变量 `courses` 上。从结果来看，这完全符合**引用传递**的特征。 ## 2、场景二：在函数内追加切片元素 现在，我们换一个操作。我们定义另一个函数，尝试向传入的切片中追加（append）新元素。  **现象分析**： 函数 `appendToSlice` 内部成功地向 `data` 追加了新元素 "MySQL"，其长度和容量都发生了变化。然而，当函数返回后，`main` 函数中的原始变量 `courses` **没有任何改变**。这个结果又完全符合**值传递**的特征。 我们观察到了两种完全矛盾的现象： 1. 修改切片内部的元素，会影响到外部的原始切片（类似引用传递）。 2. 在函数内部对切片进行 `append` 操作，却不会影响到外部的原始切片（类似值传递）。 这种“怪异”行为的根源在于切片自身的内部结构。**切片本身是一个小的数据结构（或称“描述符”、“头信息”），它包含了指向底层数组的指针、切片的长度和容量。** 当我们以值传递的方式传递切片时，**实际上传递的是这个描述符结构体的一份拷贝**。 - **场景一**：拷贝的描述符和原始的描述符都指向**同一个**底层数组。因此，通过拷贝的描述符修改底层数组的元素，原始描述符自然能“看到”这个变化。 - **场景二**：当 `append` 操作超出了底层数组的容量时，Go 会分配一个**新的、更大的数组**，并将原数据拷贝过去。函数内的那份描述符拷贝会更新其指针指向这个新数组，但 `main` 函数中的原始描述符对此一无所知，它仍然指向旧的数组。 # 10、深入 Go Slice 的底层原理 要真正掌握 Go 语言的切片（Slice），就必须理解其底层的实现原理。Slice 的设计是 Go 语言的一大特色，但其独特的机制也要求开发者对其内部工作方式有所了解，否则在开发中容易遇到难以排查的“坑”。 Slice 的核心可以理解为一个结构体（struct）。如果你不熟悉结构体，可以暂时将其看作是其他语言中的类（class）或对象（object）。  这个结构体包含三个关键部分： 1. **指针 (Data)**：指向一个连续的内存空间，也就是切片的**底层数组**。所有的数据都存储在这里。 2. **长度 (Len)**：切片中当前包含的元素个数。`len()` 函数返回的就是这个值。 3. **容量 (Cap)**：从切片的起始元素到底层数组的末尾，总共可以容纳的元素个数。`cap()` 函数返回此值。 ## 1、为什么 Slice 兼具“值传递”与“引用传递”的特征？ 这是关于 Slice 最核心、也最容易混淆的问题。 **答案是：Go 的 Slice 本身是“值传递”的，但它的效果常常表现为“引用传递”。** **初始状态：创建一个 Slice** 首先，我们创建一个 Slice。这个 Slice `s1` 包含三个元素 `[A, B, C]`。在内存中，这表现为一个 `sliceHeader` 结构体，它包含一个指向底层数组的**指针 (ptr)**，以及**长度 (len)** 和**容量 (cap)**。  **说明:** - `s1` 的 `sliceHeader` 包含了指向底层数组的指针。 - 底层数组是实际存储数据 `[A, B, C, ...]` 的地方。 - `len` 是 `3`，表示 Slice 当前包含的元素数量。 - `cap` 是 `5`，表示底层数组从指针开始位置到其末尾的总容量。 **函数调用：将 Slice 作为参数传递** 现在，我们将 `s1` 传递给一个函数 `foo(s2)`。Go 会**复制** `s1` 的 `sliceHeader`，创建一个新的 `sliceHeader` `s2`。关键在于，这个新的 `s2` 内部的指针，和 `s1` 的指针指向的是**同一个底层数组**。  **说明:** 1. **值传递 (Pass-by-Value):** `s1` 的 `sliceHeader` 被完整地复制给了 `s2`。`s1` 和 `s2` 是两个独立的结构体变量，它们位于不同的内存区域（例如，在栈上的不同帧中）。 2. **引用效果 (Reference-like Effect):** 尽管 `sliceHeader` 是复制的，但它们内部的指针 `ptr` 具有相同的值。这意味着它们都指向了同一个存储实际数据的底层数组。 **结论** 正是因为这种机制——**“Header 本身是值传递，但内部指针共享同一个底层数组”**——导致了 Slice 的独特行为： - **表现为“引用传递”**：当你在函数内部通过 `s2` 修改底层数组的元素时（例如 `s2[0] = 'X'`），这个修改会通过共享的底层数组反映到 `s1` 上。 - **表现为“值传递”**：如果你在函数内部使用 `append` 操作，导致底层数组因为容量不足而重新分配了内存，那么 `s2` 的指针会指向一个新的底层数组。这时，`s2` 的后续修改将不再影响原始的 `s1`，因为它俩的指针已经指向了不同的地方。这暴露了其“值传递”的本质。  **结果分析**： - **步骤 3**：修改 `s2[0]` 将底层数组中原来的 `5` 改成了 `99`。因为 `s1` 的最后一个元素也指向这里，所以 `s1` 也受到了影响。 - **步骤 4**：`s2` 发生了扩容，它指向了一个全新的底层数组。 - **步骤 5**：再次修改 `s2` 时，它操作的是新数组，与 `s1` 指向的旧数组已经毫无关系。 ## 2、扩容策略 Go 的 Slice 扩容机制旨在平衡内存使用和分配次数： - 当所需容量小于 1024 个元素时，会**翻倍扩容** (newCap = oldCap * 2)。 - 当所需容量超过 1024 个元素时，会**以 1.25 倍**的速度缓慢增长，避免因单次扩容造成巨大的内存浪费。  观察输出，你会清晰地看到容量从 1, 2, 4, 8... 一直翻倍增长，直到超过 1024 后增长速度放缓。 ## 3、核心总结 - **Slice 是一个包含指针、长度和容量的结构体。** - **函数传递 Slice 时，传递的是这个结构体的副本（值传递）。** - **在不发生扩容时，对 Slice 元素的操作会通过指针影响共享的底层数组，表现出“引用传递”的效果。** - **一旦 `append` 操作触发扩容，Slice 的指针会指向新分配的内存，与原来的底层数组“脱钩”，表现出“值传递”的效果。** - 这也解释了为什么 `append` 函数**必须有返回值**并重新赋值给原 Slice (`slice = append(slice, ...)`), 因为扩容后返回的是一个指向全新内存的、完全不同的 Slice 结构体。 # 11、Map 使用详解 在 Go 语言中，`slice` 和 `map` 是使用频率最高、也最为核心的两种集合类数据结构。本节将详细讲解 `map` 的定义、特性及其使用方法。 ## 1、什么是 Map？ `Map` 是一种基于 **键值对（key-value）** 的、**无序**的集合。 - **Key (键)**：作为索引，每个键都是唯一的。 - **Value (值)**：与键相关联的数据。 `Map` 最主要的优势在于其高效的查询性能。与需要通过遍历来查找元素的数组或切片不同，`map` 可以通过键直接定位到值，其查询操作的时间复杂度为 **O(1)**。这使得 `map` 在需要快速存取的场景中表现极为出色。 ## 2、Map 的定义与初始化 ##### **基本定义** 定义 `map` 时，需要指定键（key）和值（value）的数据类型。 ```go // 定义一个键为 string 类型、值为 string 类型的 map var courseMap map[string]string ``` 在上述代码中，`string` 是键的类型，必须放在中括号 `[]` 内；第二个 `string` 是值的类型。 ##### **初始化** `Map` 在使用前 **必须进行初始化**，否则会导致运行时错误（runtime panic）。对一个未初始化的 `nil` map 进行写操作是 Go 语言中的常见错误。 > **错误示例**：向未初始化的 `map` 中添加值会引发 panic。  以下是两种推荐的初始化方式： ### 方式一：使用字面量初始化 在声明的同时，可以通过字面量直接为其赋初值。Go 会自动推断其类型。  **注意**：根据 Go 的语法规定，在使用多行字面量初始化时，最后一个元素后面也必须跟一个逗号。 如果想初始化一个空 `map`，可以这样做：  ### 方式二：使用 `make` 函数 `make` 是 Go 语言的内置函数，专门用于初始化 `slice`、`map` 和 `channel` 这三种引用类型。这是最常用的初始化方式。  **总结**：无论采用哪种方式，关键在于确保在向 `map` 中存入值之前，它已经被成功初始化。 ## 3、 Map 的基本操作 ### 3.1 添加与修改值 `Map` 的赋值操作语法非常简洁。如果键已存在，则会更新其对应的值；如果不存在，则会创建新的键值对。  ### 3.2 获取值  ## 4、 `nil` 在 Map 和 Slice 中的差异 一个值得注意的细节是 `nil` 对 `map` 和 `slice` 的影响不同。 - **`nil` map**：一个未初始化的 `map`，其值为 `nil`。你不能向一个 `nil map` 添加任何元素。 - **`nil` slice**：一个未初始化的 `slice`，其值也为 `nil`。但特殊的是，你可以对一个 `nil slice` 安全地使用内置的 `append` 函数来添加元素。  这个差异是 Go 语言设计中的一个重要细节，在面试和实际开发中都可能遇到。 # 12、Map 的遍历与特性 在 Go 语言中，我们经常需要遍历 `map` 来处理其中的每一个键值对。本节将深入探讨 `map` 的遍历方法、键的类型约束以及其固有的无序性。 ## 1、使用 `for...range` 遍历 Map `for...range` 结构是遍历 `map` 的标准且最便捷的方式。 ##### **同时获取键和值** 在遍历时，`for...range` 会返回两个值：键（key）和与该键对应的值（value）。  ##### **只获取值** 如果只关心 `map` 中的值而不需要键，可以使用**空白标识符** `_` 来忽略键。  ##### **只获取键** `for...range` 还支持一种单返回值形式。当只提供一个变量时，该变量接收到的是 `map` 的**键**。  **实现原理**: Go 编译器会根据 `for...range` 接收变量的数量（一个或两个）来决定底层的实现方式，因此这两种写法都是有效的。尽管两种方式都能实现完整遍历，但直接使用 `for key, value := range ...` 的形式通常更清晰、更高效。 ## 2、Map 的键类型约束 并非所有类型都能作为 `map` 的键。 - **Value（值）**：可以是任意 Go 类型。 - **Key（键）**：键的类型必须是**可比较的（Comparable）**。这意味着该类型的值可以用 `==` 或 `!=` 运算符进行比较。 常见的可比较类型包括： - `bool` - 数值类型（`int`, `float64`, 等） - `string` - 指针 - `channel` - `interface` - **数组（Array）** 而不可比较的类型，因此**不能**作为 `map` 的键，主要包括： - **切片（Slice）** - **Map** - **函数（Function）**  在编写代码时，现代的 IDE 通常会自动检测并提示无效的键类型。 ## 3、Map 的无序性 这是 `map` 最重要的特性之一：**`map` 是无序的**。 当遍历一个 `map` 时，元素的返回顺序是不固定的。Go 语言在设计上特意打乱了遍历的起始点，以防止开发者依赖于某个特定的迭代顺序。   **核心结论**： 1. `Map` 的遍历顺序是**随机**的。 2. **绝不能**依赖 `map` 的遍历顺序来实现业务逻辑。 如果你的应用场景要求数据容器保持有序，那么 `map` 本身无法满足需求。在这种情况下，通常需要将 `map` 与 `slice` 结合使用：例如，将键存储在一个 `slice` 中并对其进行排序，然后根据排好序的 `slice` 来从 `map` 中取值。 # 13、判断Map 中是否存在元素和删除元素 ## 1、获取与判断 Map 中的元素 #### 1.1 直接取值的潜在问题 直接通过键（key）从 Map 中获取值是一种常见操作。  然而，这种方式存在一个重要的模糊性：当指定的键不存在时，Go 会返回该值类型的**零值**。例如，如果值的类型是 `string`，那么在键不存在时会返回一个空字符串 `""`。  这会导致一个问题：我们无法区分 **“键存在，但其对应的值恰好是零值（如空字符串）”** 和 **“键根本不存在”** 这两种情况。仅通过判断返回值是否为零值来确定键是否存在，可能会导致程序逻辑错误（bug）。 #### 1.2 安全的键存在性判断 为了准确地判断一个键是否存在于 Map 中，应该使用支持两个返回值的访问方式。  这种用法会返回两个值： - `value`：与键对应的值。如果键不存在，`value` 会是该类型的零值。 - `ok`：一个布尔值。如果键存在，`ok` 为 `true`；如果键不存在，`ok` 为 `false`。 因此，**检查 `ok` 的值是判断键是否存在的标准方法**。  #### 结合 `if` 的简洁语法 Go 语言允许在 `if` 语句的条件判断前执行一个简短的初始化语句。这种特性与 Map 的键值判断完美结合，可以写出更紧凑、可读性更高的代码。 通过这种方式，从 Map 中获取的 `value` 和 `ok` 变量的作用域被限制在 `if-else` 代码块内部，增强了代码的封装性。  如果只关心键是否存在而不关心其具体值，可以使用空标识符 `_` 来忽略第一个返回值。  ## 2、删除 Map 中的元素 使用 Go 的内置函数 `delete()` 可以方便地从 Map 中移除一个键值对。 **语法**：`delete(map_variable, key_to_delete)`  一个重要的特性是，**尝试删除一个不存在的键不会导致程序错误（panic）**。如果 `delete()` 函数的目标键不存在，该操作不会产生任何效果，程序会继续正常执行。因此，可以放心使用 `delete()` 而无需预先检查键是否存在。 ## 3、重要提示：Map 的线程安全 Go 语言内置的 **`map` 类型不是线程安全的**。 如果在多个协程（goroutine）中并发地对同一个 Map 进行读写操作，将会导致数据竞争，引发不可预测的程序行为甚至运行时崩溃。 对于需要在并发环境中使用的 Map，必须采用同步措施。Go 标准库为此提供了 **`sync.Map`** 类型，它专门为并发访问场景设计，并内置了必要的锁定机制。在并发编程中，应优先使用 `sync.Map` 来保证数据安全。 # 14、list：链表数据结构 本节我们探讨 Go 语言容器中的 `list`，它是一个基于链表实现的数据结构。 ## 1、`list` 与 `slice` 的核心差异 `list` 的设计初衷是为了解决 `slice` 在特定场景下的局限性。`slice` 的本质是动态数组，其核心特点和潜在问题如下： - **连续内存空间**：`slice` 要求其底层数据存储在一块**连续的内存**中。这意味着如果内存中没有足够大的连续空间，就无法分配相应大小的 `slice`。 - **扩容成本**：当向 `slice` 中持续添加数据直至其容量用尽时，会触发**扩容**机制。扩容会分配一块更大的新内存空间，并将所有旧数据完整地**拷贝**到新空间，在高频添加场景下会带来性能开销。 为了应对这些问题，`list`（链表）采用了完全不同的存储模型。 - **非连续内存**：链表中的每个元素（节点）都在内存中独立分配。它们通过**指针**（`next` 和 `prev`，因为 Go 的 `list` 是双向链表）连接起来，而无需在物理上连续存储。 - **空间开销**：这种结构的代价是每个元素都需要额外的空间来存储指向其他元素的指针，因此存在一定的空间浪费。 ## 2、性能特点对比 由于底层原理的巨大差异，`slice` 和 `list` 在不同操作上表现出截然不同的性能。 | | | | | |---|---|---|---| |**操作 (Operation)**|**slice (切片)**|**list (链表)**|**备注 (Remarks)**| |**查询/访问 (Query/Access)**|O(1)|O(n)|`slice` 通过索引可直接计算内存地址，访问速度极快。`list` 必须从头节点开始逐个遍历才能找到目标元素。| |**中间插入/删除 (Mid-list Insertion/Deletion)**|O(n)|O(1)|`slice` 在中间插入或删除元素需要移动该位置之后的所有元素。`list` 仅需修改相邻节点的指针即可，操作非常高效（前提是已持有目标位置的指针）。| 例如，要在 `[1, 2, 3, 4, 5, 6]` 的 `3` 和 `4` 之间插入 `7`： - **对于 `slice`**：需要重新分配一个更大的连续空间，然后将 `1, 2, 3` 拷贝过去，放入 `7`，再将 `4, 5, 6` 拷贝到后面。 - **对于 `list`**：只需新分配一个存放 `7` 的节点，然后将 `3` 的 `next` 指针指向 `7`，`7` 的 `prev` 指针指向 `3`，`7` 的 `next` 指针指向 `4`，`4` 的 `prev` 指针指向 `7` 即可。无需移动任何现有元素。 ## 3、应用场景与总结 尽管 `list` 在插入和删除操作上具有理论优势，但在 Go 的实际开发中，其使用频率远低于 `slice` 和 `map`。 **主要原因在于**： 1. **查询性能差**：`O(n)` 的查询复杂度在绝大多数场景下是不可接受的。 2. **缓存不友好**：`slice` 的连续内存布局具有极佳的**缓存局部性**，CPU 可以高效预取数据，使其遍历性能在实践中远超 `list`。 因此，`slice` 和 `map` 凭借其出色的综合性能，满足了超过 90% 的编程需求。只有在**极少数需要海量、高频地在集合中间进行插入和删除**，且对查询性能要求不高的特定场景下，`list` 才可能成为一个考虑选项。 总而言之，理解 `list` 的原理有助于我们全面地认识 Go 的数据结构，但在日常编码中，应优先选择 `slice` 和 `map`。 # 15、list 的基本使用 本节将演示如何使用 Go 语言标准库中的 `container/list` 包，它提供了一个双向链表的实现。 与 `slice` 和 `map` 不同，`list` 并非 Go 的内置关键字，而是通过导入包来使用。 ```go import ( "container/list" "fmt" ) ``` ## 1、导入与初始化 初始化一个 `list` 有两种主要方式：  ## 2、添加元素 `list` 提供了在链表头部和尾部添加元素的方法。 - `PushBack(v interface{}) *Element`：在链表尾部添加元素。 - `PushFront(v interface{}) *Element`：在链表头部添加元素。  ## 3、 遍历元素 `list` 的遍历不能使用 `for...range` 循环，而需要通过从头（`Front`）或尾（`Back`）节点开始，借助节点的 `Next()` 或 `Prev()` 方法进行移动。 **正序遍历 (从头到尾)**  **逆序遍历 (从尾到头)**  ## 4、插入与删除 `list` 最核心的优势是在指定元素前后进行高效的插入和删除操作。这些操作需要一个指向具体元素（`*list.Element`）的指针作为锚点。 ### 4.1 在指定元素前插入 `InsertBefore(v interface{}, mark *Element)` 方法可以在 `mark` 元素之前插入一个新值 `v`。 首先，我们需要遍历链表以找到这个 `mark` 元素。  ### 4.2 删除指定元素 `Remove(e *Element)` 方法可以从链表中删除一个元素。同样，需要先找到该元素。  ## 5、总结：四种集合类型的回顾 Go 语言中主要的四种集合类型各有其特点和适用场景： 1. **数组 (Array)** - **特点**: 定长，长度是类型的一部分。 - **用途**: 使用较少，通常用于需要精确控制内存布局的底层场景。 2. **切片 (Slice)** - **特点**: 动态数组，使用方便，性能高（缓存友好）。 - **用途**: **最常用**的数据结构，几乎是所有序列数据的首选。 3. **Map** - **特点**: 键值对存储，查找效率高。 - **用途**: **非常常用**的数据结构，用于实现关联数组、哈希表等。它在功能上没有直接的竞争者。 4. **列表 (List)** - **特点**: 双向链表，中间插入/删除效率高，但查询慢。 - **用途**: 使用较少。它的竞争对手是 `slice`。虽然在理论上 `list` 能完成的 `slice` 也能完成，反之亦然，但由于性能和缓存等因素，`slice` 在绝大多数场景下是更优的选择。 **核心建议**: 熟练掌握 `slice` 和 `map`，因为它们构成了 Go 日常开发的基础。仅在确认业务场景高度契合链表特性（如高频的非首尾插入/删除）时，才考虑使用 `list`。若想了解更多方法，可直接查阅 `container/list` 包的官方文档。
一文带你学会"冒泡排序"
大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。 <img src="https://pic.code-nav.cn/migrate_image/27cdd9f248d9db57f9092e7bf252a5a7.webp" alt="image-20250528165506676" style="zoom:50%;" /> # 冒泡排序算法 ## 介绍 冒泡排序（Bubble Sort）是一种简单直观的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此重复遍历下去，直到没有再需要交换的元素，最终完成排序。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像水中气泡上升一样，于是将这种排序算法形象地称为冒泡排序。 ## 算法步骤 1. 比较相邻的元素。如果第一个比第二个大，就交换它们 2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对 3. 这步做完后，最后的元素会是最大的数 4. 针对所有的元素重复以上的步骤，除了已经是最大数的最后一个 5. 持续每次对越来越少(每次重复都会少一个最大数)的元素重复上面的步骤，直到没有任何一对数字需要比较  ## 核心特性 - **稳定性**：冒泡排序是稳定的排序算法，相等元素的相对位置在排序后不会改变 - **原地排序**：只需要常数级的额外空间 - **时间复杂度**：最坏和平均情况为O(n²)，最好情况为O(n) - **比较排序**：基于元素间的比较进行排序 ## 基础实现 接下来大家一起看下冒泡排序的几个主流语言实现： ### 代码实现 ``` public class BubbleSort { public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { // 每次遍历后，最大的i+1个元素已经排好序 for (int j = 0; j < n - i - 1; j++) { // 如果当前元素大于下一个元素，则交换 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } // 打印数组 public static void printArray(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); } // 测试 public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("排序前的数组："); printArray(arr); bubbleSort(arr); System.out.println("排序后的数组："); printArray(arr); } } ``` ## 优化版本 如果是一个已经排好序的数组，上述代码也会循环执行，我们可以针对这一点进行如下优化： ```java public static void optimizedBubbleSort(int[] arr) { int n = arr.length; boolean swapped; for (int i = 0; i < n - 1; i++) { swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // 如果没有发生交换，说明数组已经有序，可以提前退出排序 if (!swapped) { break; } } } ``` ## 优缺点 ### 优点 - 代码简单，容易实现 - 适合小规模数据排序 - 对于几乎已经排好序的数据，效率较高 - 稳定的排序算法 ### 缺点 - 时间复杂度高，为O(n²) - 随着元素数量增加，效率急剧下降 - 每次只能将一个元素移动到其最终位置，效率不高 ## 应用场景 由于效率问题，冒泡排序的应用场景比较少，不过也不是完全没有，比如： - 教学演示：简单直观，常用于算法入门教学 - 小规模数据排序：当数据量较小、空间资源有限时可以使用 - 对于接近有序的数组：有优化版本可以在接近有序的情况下提前终止 - 嵌入式系统或资源受限环境：因为它不需要额外的内存空间 ## 扩展 ### 鸡尾酒排序（双向冒泡排序） 鸡尾酒排序是冒泡排序的一种变体，它从低到高然后从高到低来回排序，比冒泡排序的效率稍微高一点： ```java public static void cocktailSort(int[] arr) { boolean swapped = true; int start = 0; int end = arr.length - 1; while (swapped) { // 从左到右 swapped = false; for (int i = start; i < end; i++) { if (arr[i] > arr[i + 1]) { int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; swapped = true; } } // 如果没有交换，则已经排序完成 if (!swapped) break; // 否则重置swapped标志准备从右到左 swapped = false; end--; // 从右到左 for (int i = end - 1; i >= start; i--) { if (arr[i] > arr[i + 1]) { int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; swapped = true; } } start++; } } ``` ## 测验 1. 冒泡排序的平均时间复杂度是多少？ 2. 冒泡排序是稳定的排序算法吗？ 3. 对于已经排好序的数组，优化版冒泡排序的时间复杂度是多少？ 4. 冒泡排序每一轮遍历后，数组尾部会有什么特点？ 5. 如何优化冒泡排序以提高效率？ > 测验答案 > > 1. 冒泡排序的平均时间复杂度是O(n²)。 > 2. 是的，冒泡排序是稳定的排序算法。因为只有当前一个元素大于后一个元素时才交换，相等元素不会改变相对位置。 > 3. 对于已经排好序的数组，优化版冒泡排序的时间复杂度是O(n)。因为第一轮遍历不会发生交换，优化版会检测到这点并提前终止。 > 4. 冒泡排序每一轮遍历后，数组尾部会有一个元素到达其最终位置，且是当前未排序部分中的最大元素。第i轮结束后，末尾i个元素已排好序。 > 5. 优化冒泡排序的方法: > - 添加标志位跟踪是否发生交换，无交换则提前终止 > - 记录最后一次交换位置，下一轮只遍历到该位置 > - 使用双向冒泡(鸡尾酒排序)，同时将最大值上浮和最小值下沉 ## 相关的 LeetCode 热门题目 下面给大家推荐一些可以用来练手的 LeetCode 题目： - [75. 颜色分类](https://leetcode.cn/problems/sort-colors/) - 可以使用冒泡排序解决，但有更优的解法 - [283. 移动零](https://leetcode.cn/problems/move-zeroes/) - 可以用冒泡排序的思想将零元素"冒泡"到数组末尾 - [912. 排序数组](https://leetcode.cn/problems/sort-an-array/) - 可以使用冒泡排序，但因为数据规模较大，可能会超时 需要注意的是，上述题目使用冒泡排序不一定是最优解，仅使用冒泡排序也可能无法解决问题，不过这些题目都能够直接或间接体现冒泡排序的核心思想，帮助大家熟悉这个算法。 **学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！**
3 月 28 打卡，学习手搓环形数组
## 实现要注意的关键点 1. 定义为左闭右开 [start, end），因为这样定义，只要让 end 移动以为，就包含一个元素 在 index 0 位置，如果设置成 双开 和双闭合，在处理边界条件很麻烦 2. 关键实现 在于 取模运算 的特性，如果 当前index等于数组大小 就会循环到 index 0的位置，因为余数是0，平常时候 index 都会小于数组大小，所以 取模都会返回index 值，因为商是0 ，通过这个特性来形成环的特性 3. 数组有扩容缩容机制，如果数组满了 扩容2倍，如果数组只用了 数组空间的1/4 缩容一半 ```python class CycleArray: def __init__(self, size=1): self.size = size self.arr = [None] * self.size # start 指向第一个元素 self.start = 0 # end 指向最后一个元素，后一位的坐标 self.end = 0 self.count = 0 # 扩容 def resize(self, new_size): # 创建新的数组 new_arr = [None] * new_size # 搬移老的数组数据到新数组 for i in range(self.count): new_arr[i] = self.arr[(self.start + i) % self.size] # 从新定义arr, start, end, size self.arr = new_arr self.start = 0 self.end = self.count self.size = new_size # add_first def add_first(self, val): # 判断 arr 大小够不够 不够扩容为原来的两倍 if self.is_full(): self.resize(self.size * 2) # 因为左闭，所以 先吧 start 改成 start -1 位置， 插入元素 self.start = (self.start - 1 + self.size) % self.size self.arr[self.start] = val self.count += 1 def add_last(self, val): # 判断 arr 大小 if self.is_full(): self.resize(self.size * 2) # 因为是右开所以先赋值，然后移动 end +1 self.arr[(self.end)] = val self.end = (self.end + 1) % self.size self.count += 1 def remove_first(self): # 判断 有无东西可以删除，空的数组不删 if self.is_empty(): raise Exception("Array is Empty") # 因为左闭，所以先去除，后修改 start，去除头部元素，把 start 位置修改 self.arr[self.start] = None self.start = (self.start + 1 - self.size) % self.size # count -1 self.count -= 1 # 查看数组使用率 考虑缩减 if self.count > 0 and self.size//4 == self.count: self.resize(self.size//4) def remove_last(self): #判断是否空数组 if self.is_empty(): raise Exception("Array is empty") #右开，所以先移动到最后一个坐标，然后删除 self.end = (self.end -1 + self.size) // 4 self.arr[self.end] = None #count-1 self.count -=1 #考虑是否缩容 if self.count >0 and self.size//4 == self.count: self.resize(self.size//4) def get_first(self): if self.is_empty(): raise Exception("Array is Empty") return self.arr[self.start] def get_last(self): #判断是否空数组 if self.is_empty(): raise Exception("Array is empyt") #右闭原则 先移位。后取值 end = (self.end - 1 - self.size) % self.size return self.arr[end] #工具函数 def is_empty(self): return self.count == 0 def is_full(self): return self.size == self.count def display(self): count = self.count start = self.start for _ in range(count): print(self.arr[start], end = ",") start = (start + 1 -self.size ) % self.size # print(f"start: {start}") if __name__ == '__main__': ca = CycleArray(size=8) ca.arr = [3,None,None,None,None,None,1,2] ca.count = 3 ca.start = 6 ca.end = 1 ca.add_last("4") ca.add_first("0") ca.remove_last() ca.remove_first() ca.display() print("") print(ca.get_first()) print(ca.get_last()) ```
DAY02 数据结构与算法--栈
# 今天内容 ### 顺序栈 - 其实就是最基础的栈, 包括init, push, pop, isEmpty等功能 ### 双端共享栈 <img src="https://pic.code-nav.cn/post_picture/1675394102406942722/wWjkDaeD-image.webp" alt="image.png" width="337px" /> #### 相较与普通栈的优势 - 能够共享如上图的中间部分, 更好的利用空间 - 能适配一些此消彼长的应用 ### 链栈 #### 相较与普通栈的优势 - 结合了链表的优点, 能够用指针索引到所有的元素, 而不必弹出全部元素 - 能够动态的控制栈的大小 --- 加油, 共勉!
数据结构和算法 - 堆和堆排序
<html> <head></head> <body> <div class="content ql-editor"> <p><span style="font-size: 2em; font-family: PingFangSC-Regular;">一、堆结构的定义</span></p> <p><br></p> <p>堆通常是一个可以被看做一棵 <strong>完全二叉树</strong>的 <strong>数组</strong>对象，<strong>堆是非线性数据结构。</strong>堆总是满足下列性质：</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>堆中的某个节点的值总是不大于或者不小于其父节点的值</li> <li data-list="ordered"><span class="ql-ui"></span>堆总是一个完全二叉树</li> </ol> <p>倘若子树中 子节点中的值都小于父节点 那么这个堆称为小根堆，反之称为大根堆</p> <p><br></p> <p><br></p> <p><br></p> <h1>二、堆的实现、</h1> <p><br></p> <h2>2.1 堆的向上调整算法</h2> <p><br></p> <h3>2.1.1 思路</h3> <p><br></p> <p>数组中新添加进来的元素，与自己的父元素比较 若比自己的父元素大则交换，一直比到索引为 0 或者直到此元素没有自己的父元素大为止</p> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapInsert(int[] arr, int index)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (arr[index] > arr[(index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>]) { </div> <div class="ql-code-block"> swap(arr, index, (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>); </div> <div class="ql-code-block"> index = (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p><br></p> <h2>堆的向下调整算法</h2> <p><br></p> <h3>2.2.1 思路</h3> <p>数组是一个堆，从某个指定的位置开始和自己的左右两个叶节点比较 如果这个位置比某个叶子节点小就交换，直到不比叶子节点小为止，或者已经到了堆的最后位置。</p> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapify(int[] arr, int index, int heapSize)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">left</span> <span class="ql-token hljs-operator">=</span> index << <span class="ql-token hljs-number">1</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (left < heapSize) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">largest</span> <span class="ql-token hljs-operator">=</span> left + <span class="ql-token hljs-number">1</span> < heapSize && arr[left + <span class="ql-token hljs-number">1</span>] > arr[left] ? left + <span class="ql-token hljs-number">1</span> : left; </div> <div class="ql-code-block"> largest = arr[largest] > arr[index] ? largest : index; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (largest == index) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> swap(arr, largest, index); </div> <div class="ql-code-block"> index = largest; </div> <div class="ql-code-block"> left = index << <span class="ql-token hljs-number">1</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <h2>2.3 堆结构完整代码</h2> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> lombok.Data; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Arrays; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-meta">@Data</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Code01_Heap</span> { </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 堆的实现</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-type">int</span>[] heap; </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 堆中元素的个数</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-type">int</span> heapSize; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 容量</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-type">int</span> capacity; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-title">Code01_Heap(int capacity)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-built_in">this</span>.capacity = capacity; </div> <div class="ql-code-block"> <span class="ql-token hljs-built_in">this</span>.heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[capacity]; </div> <div class="ql-code-block"> <span class="ql-token hljs-built_in">this</span>.heapSize = <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 判断堆是否为空</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> *</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * @return true:为空 false:不为空</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isEmpty()</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">return</span> <span class="ql-token hljs-variable">heapSize</span> <span class="ql-token hljs-operator">=</span>= <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 判断堆是否满了</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> *</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * @return true:满了 false:没满</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isFull()</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">return</span> <span class="ql-token hljs-variable">heapSize</span> <span class="ql-token hljs-operator">=</span>= capacity; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">push(int value)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (isFull()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">throw</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">RuntimeException</span>(<span class="ql-token hljs-string">"堆满了"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> heap[heapSize] = value; </div> <div class="ql-code-block"> heapInsert(heap, heapSize++); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">pop()</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (isEmpty()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">throw</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">RuntimeException</span>(<span class="ql-token hljs-string">"堆为空"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> heap[<span class="ql-token hljs-number">0</span>]; </div> <div class="ql-code-block"> heap[<span class="ql-token hljs-number">0</span>] = heap[--heapSize]; </div> <div class="ql-code-block"> heapify(heap, <span class="ql-token hljs-number">0</span>, heapSize); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">peek()</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (isEmpty()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">throw</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">RuntimeException</span>(<span class="ql-token hljs-string">"堆为空"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> heap[<span class="ql-token hljs-number">0</span>]; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapify(int[] arr, int index, int heapSize)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">left</span> <span class="ql-token hljs-operator">=</span> index << <span class="ql-token hljs-number">1</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (left < heapSize) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">largest</span> <span class="ql-token hljs-operator">=</span> left + <span class="ql-token hljs-number">1</span> < heapSize && arr[left + <span class="ql-token hljs-number">1</span>] > arr[left] ? left + <span class="ql-token hljs-number">1</span> : left; </div> <div class="ql-code-block"> largest = arr[largest] > arr[index] ? largest : index; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (largest == index) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> swap(arr, largest, index); </div> <div class="ql-code-block"> index = largest; </div> <div class="ql-code-block"> left = index << <span class="ql-token hljs-number">1</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapInsert(int[] arr, int index)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (arr[index] > arr[(index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>]) { </div> <div class="ql-code-block"> swap(arr, index, (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>); </div> <div class="ql-code-block"> index = (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">swap(int[] arr, int i, int j)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">tmp</span> <span class="ql-token hljs-operator">=</span> arr[i]; </div> <div class="ql-code-block"> arr[i] = arr[j]; </div> <div class="ql-code-block"> arr[j] = tmp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">main(String[] args)</span> { </div> <div class="ql-code-block"> System.out.println(-<span class="ql-token hljs-number">1</span> / <span class="ql-token hljs-number">2</span>); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">Code01_Heap</span> <span class="ql-token hljs-variable">heap</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">Code01_Heap</span>(<span class="ql-token hljs-number">10</span>); </div> <div class="ql-code-block"> heap.push(<span class="ql-token hljs-number">3</span>); </div> <div class="ql-code-block"> heap.push(<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> heap.push(<span class="ql-token hljs-number">5</span>); </div> <div class="ql-code-block"> System.out.println(Arrays.toString(heap.getHeap())); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> </div> <p><br></p> <p><br></p> <p><br></p> <h1>三、堆排序</h1> <p><br></p> <h2>3.1 思路</h2> <p><br></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>heapSort 方法：</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>首先，如果数组为空或者只有一个元素，那么无需排序，直接返回。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>然后，使用 heapify 方法从最后一个非叶子节点开始，向前遍历数组，将每个子树调整为大根堆。这一步的目的是将数组初始化为大根堆。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>在数组被初始化为大根堆之后，开始排序过程。每次将堆顶元素（最大元素）与当前堆的最后一个元素交换，然后将堆的大小减1，并重新调整堆。重复这个过程直到堆的大小为0，此时数组已经排序完成。</li> <li data-list="ordered"><span class="ql-ui"></span>heapify 方法：</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>该方法用于调整以 i 为根节点的子树为最大堆。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>首先，计算左子节点的索引 left。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>然后，进入一个循环，在该循环中，找到 i、左子节点和右子节点中的最大值。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>如果最大值不是 i，那么将最大值与 i 交换，并更新 i 和 left 的值，继续循环。</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>如果最大值就是 i，那么退出循环，此时以 i 为根节点的子树已经是一个最大堆。</li> <li data-list="ordered"><span class="ql-ui"></span>heapInsert 方法：</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>这个方法用于在构建堆的过程中，将新插入的元素插入到正确的位置，以保持堆的性质。但是在这段代码中，heapInsert 方法并没有在 heapSort 方法中被调用，因此这段代码中的 heapInsert 是多余的。也可以使用heapInsert 方法初始化堆结构。</li> <li data-list="ordered"><span class="ql-ui"></span>swap 方法：</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>这个方法用于交换数组中的两个元素。</li> </ol> <p><br></p> <p><br></p> <p><br></p> <h2>3.2 代码</h2> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">package</span> com.zhang.study.chapter06; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Arrays; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> <span class="ql-token hljs-keyword">static</span> com.zhang.util.RandomArrayUtil.generateRandomArray; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 堆排序</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Code02_HeapSort</span> { </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapSort(int[] arr)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (arr == <span class="ql-token hljs-literal">null</span> || arr.length < <span class="ql-token hljs-number">2</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N*logN)</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// for (int i = 0; i < arr.length; i++) {</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// heapInsert(arr, i);</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// }</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N) </span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> arr.length - <span class="ql-token hljs-number">1</span>; i >= <span class="ql-token hljs-number">0</span>; i--) { </div> <div class="ql-code-block"> heapify(arr, i, arr.length); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">size</span> <span class="ql-token hljs-operator">=</span> arr.length; </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N*logN)</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (size > <span class="ql-token hljs-number">0</span>) { <span class="ql-token hljs-comment">// O(N)</span> </div> <div class="ql-code-block"> swap(arr, <span class="ql-token hljs-number">0</span>, --size); <span class="ql-token hljs-comment">// O(1)</span> </div> <div class="ql-code-block"> heapify(arr, <span class="ql-token hljs-number">0</span>, size); <span class="ql-token hljs-comment">// O(logN)</span> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapify(int[] arr, int i, int size)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">left</span> <span class="ql-token hljs-operator">=</span> i * <span class="ql-token hljs-number">2</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (left < size) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">largest</span> <span class="ql-token hljs-operator">=</span> left + <span class="ql-token hljs-number">1</span> < size && arr[left + <span class="ql-token hljs-number">1</span>] > arr[left] ? left + <span class="ql-token hljs-number">1</span> : left; </div> <div class="ql-code-block"> largest = arr[largest] > arr[i] ? largest : i; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (largest == i) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> swap(arr, largest, i); </div> <div class="ql-code-block"> i = largest; </div> <div class="ql-code-block"> left = i * <span class="ql-token hljs-number">2</span> + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapInsert(int[] arr, int index)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (arr[index] > arr[(index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>]) { </div> <div class="ql-code-block"> swap(arr, index, (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>); </div> <div class="ql-code-block"> index = (index - <span class="ql-token hljs-number">1</span>) / <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">swap(int[] arr, int index, int i)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">temp</span> <span class="ql-token hljs-operator">=</span> arr[index]; </div> <div class="ql-code-block"> arr[index] = arr[i]; </div> <div class="ql-code-block"> arr[i] = temp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">main(String[] args)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">maxSize</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">100</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">maxValue</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">1000</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">testTime</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">500000</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < testTime; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] arr1 = generateRandomArray(maxSize, maxValue); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] arr2 = arr1.clone(); </div> <div class="ql-code-block"> heapSort(arr1); </div> <div class="ql-code-block"> Arrays.sort(arr2); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (!Arrays.equals(arr1, arr2)) { </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"Oops!"</span>); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"Nice!"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> </div> <p><br></p> <p><br></p> <p><br></p> <h1>四、堆排序的时间复杂度</h1> <p><br></p> <p><br></p> <p>堆排序的时间复杂度是 (N*logN)</p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapSort(int[] arr)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (arr == <span class="ql-token hljs-literal">null</span> || arr.length < <span class="ql-token hljs-number">2</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N*logN)</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// for (int i = 0; i < arr.length; i++) {</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// heapInsert(arr, i);</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// }</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N) </span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> arr.length - <span class="ql-token hljs-number">1</span>; i >= <span class="ql-token hljs-number">0</span>; i--) { </div> <div class="ql-code-block"> heapify(arr, i, arr.length); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">size</span> <span class="ql-token hljs-operator">=</span> arr.length; </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// O(N*logN)</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (size > <span class="ql-token hljs-number">0</span>) { <span class="ql-token hljs-comment">// O(N)</span> </div> <div class="ql-code-block"> swap(arr, <span class="ql-token hljs-number">0</span>, --size); <span class="ql-token hljs-comment">// O(1)</span> </div> <div class="ql-code-block"> heapify(arr, <span class="ql-token hljs-number">0</span>, size); <span class="ql-token hljs-comment">// O(logN)</span> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p>倘若 是使用 heapInsert 来插入元素，则是这个 for 循环是O(N*logN)，这个操作是将数组转为大根堆</p> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < arr.length; i++) { </div> <div class="ql-code-block"> heapInsert(arr, i); </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p>因为每次插入一个元素需要和自己的父元素作比较，每次比较是 logN级别的所以是(N*logN)</p> <p><br></p> <p>但是这个操作如果数组是一次性全部拿到 而不是一个一个给的，是可以收敛为O(N)的。</p> <p>我们可以把这个数组直接想象成为一个完全二叉树，虽然它不是大根堆。例如：</p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1707418316274003969/sk3v9ado.jpeg"></p> <p><br></p> <p><br></p> <p><br></p> <p>我们想象这个数组就是完全二叉树，然后从下往上遍历，依次是 76 43 5 43 12 32 22 43，依次进行heapify 最后一层就变成了大根堆，然后 再遍历89 23 344 13 依然是heapify 这样倒数第二层以及最后一层都是大根堆，然后依次12 21、10这样下来数组就变成了大根堆的结构。这个操作的时间复杂度是O(N)。为什么呢？</p> <p><br></p> <p>假设数组有 N 个元素，那么叶节点差不多就有N/2个也就是最下面一层，刚刚上述数组有 15 个元素 叶节点有 8 个，即使不是完全满二叉树也是一样的，例如下图：有四个元素，叶节点有两个</p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1707418316274003969/88qhee68.jpeg"></p> <p><br></p> <p><br></p> <p>这些节点在做heapify 时候，只需要判断自己，N/2 * 1，倒数第二层的节点 从数量级来说大概是有N/4个 在做heapify时候，最多需要判断三个单位往下沉的的次数和层数有关，所以是N/4 * 2</p> <p>那么第三层有N/8个节点，最多需要判断 加交换N/8 * 6次</p> <p><br></p> <p>整个时间复杂度 T(N) = N/2 * 1 + N/4 * 2 + N/8 * 4 + N/16 * 6 +...... 相乘后忽略常数项的时间复杂度是 O(N)这个是里面所有操作的时间复杂度。</p> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <h1>五、面试题</h1> <p><br></p> <h2>5.1 题目一</h2> <p><br></p> <p>已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。请选择一个合适的排序策略，对这个数组进行排序。</p> <p><br></p> <p>举例：</p> <p>原始数组 arr = [3,4,1,2,5] k = 2</p> <p>排序后数组 arr = [1,2,3,4,5]</p> <p><br></p> <p>1 排序后从 索引为 2 的位置到 索引为 0 的位置 移动了两个位置</p> <p>2 排序后从 索引为 3 位置移动到 索引为 1 的位置 移动了两个位置</p> <p>3 排序后从 索引为0 位置移动到 索引 2 的位置 移动了两个位置</p> <p>4 排序后从 索引为 1 移动到索引 索引 3 的位置 移动了两个位置</p> <p>5 排序后从索引为 4 的位置移动索引为 4 的位置 移动了零个位置</p> <p><br></p> <p><br></p> <h3>5.1.1 思路</h3> <p><br></p> <p>可以使用小根堆，先将数组的前 k 个值放入 小根堆中 每次弹出的就是最小值 然后弹出一个值 再放入一个值，最后将小根堆中的值全部弹出 。时间复杂度为O(N*logK)k 比 N 小 就是最优解</p> <p><br></p> <p><br></p> <p><br></p> <h3>5.1.2 代码</h3> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Arrays; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.PriorityQueue; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Code03_SortArrayDistanceLessK</span> { </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">sortedArrDistanceLessK(int[] arr, int k)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (arr == <span class="ql-token hljs-literal">null</span> || arr.length < <span class="ql-token hljs-number">2</span> || k < <span class="ql-token hljs-number">1</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// 默认是小根堆</span> </div> <div class="ql-code-block"> PriorityQueue<Integer> queue = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>(); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">index</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (index = <span class="ql-token hljs-number">0</span>; index < Math.min(arr.length , k ); index++) { </div> <div class="ql-code-block"> queue.add(arr[index]); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (; index < arr.length; index++, i++) { </div> <div class="ql-code-block"> queue.add(arr[index]); </div> <div class="ql-code-block"> arr[i] = queue.poll(); </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (!queue.isEmpty()) { </div> <div class="ql-code-block"> arr[i++] = queue.poll(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span>[] randomArrayNoMoveMoreK(<span class="ql-token hljs-type">int</span> maxSize, <span class="ql-token hljs-type">int</span> maxValue, <span class="ql-token hljs-type">int</span> K) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] arr = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[(<span class="ql-token hljs-type">int</span>) ((maxSize + <span class="ql-token hljs-number">1</span>) * Math.random())]; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < arr.length; i++) { </div> <div class="ql-code-block"> arr[i] = (<span class="ql-token hljs-type">int</span>) ((maxValue + <span class="ql-token hljs-number">1</span>) * Math.random()) - (<span class="ql-token hljs-type">int</span>) (maxValue * Math.random()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// 先排个序</span> </div> <div class="ql-code-block"> Arrays.sort(arr); </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// 然后开始随意交换，但是保证每个数距离不超过K</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// swap[i] == true, 表示i位置已经参与过交换</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// swap[i] == false, 表示i位置没有参与过交换</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-type">boolean</span>[] isSwap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">boolean</span>[arr.length]; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < arr.length; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">j</span> <span class="ql-token hljs-operator">=</span> Math.min(i + (<span class="ql-token hljs-type">int</span>) (Math.random() * (K + <span class="ql-token hljs-number">1</span>)), arr.length - <span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (!isSwap[i] && !isSwap[j]) { </div> <div class="ql-code-block"> isSwap[i] = <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> isSwap[j] = <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">tmp</span> <span class="ql-token hljs-operator">=</span> arr[i]; </div> <div class="ql-code-block"> arr[i] = arr[j]; </div> <div class="ql-code-block"> arr[j] = tmp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> arr; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">main(String[] args)</span> { </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"test begin"</span>); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">testTime</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">500000</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">maxSize</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">100</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">maxValue</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">100</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-variable">succeed</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < testTime; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">k</span> <span class="ql-token hljs-operator">=</span> (<span class="ql-token hljs-type">int</span>) (Math.random() * maxSize) + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] copiedOf1 = Arrays.copyOf(arr, arr.length); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[] copiedOf2 = Arrays.copyOf(arr, arr.length); </div> <div class="ql-code-block"> sortedArrDistanceLessK(copiedOf1, k); </div> <div class="ql-code-block"> Arrays.sort(copiedOf2); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (!Arrays.equals(copiedOf1, copiedOf2)) { </div> <div class="ql-code-block"> succeed = <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"K : "</span> + k); </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"arr : "</span> + Arrays.toString(arr)); </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"copiedOf1 : "</span> + Arrays.toString(copiedOf1)); </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"copiedOf2 : "</span> + Arrays.toString(copiedOf2)); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> System.out.println(succeed ? <span class="ql-token hljs-string">"Nice!"</span> : <span class="ql-token hljs-string">"Fucking fucked!"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> </div> <p><br></p> <p><br></p> <p><br></p> <h2>题目二</h2> <p><br></p> <p><br></p> <p><strong style="color: rgb(51, 51, 51);">合并k个已排序的链表</strong></p> <p><a href="https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6" target="_blank">合并k个已排序的链表_牛客题霸_牛客网</a></p> <p><br></p> <p><br></p> <p><br></p> <h2><span style="color: rgb(51, 51, 51);">描述</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(90, 103, 111);">合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。</span></p> <p><br></p> <p><span style="font-size: 14px; color: rgb(90, 103, 111);">数据范围：节点总数 0≤n≤5000，每个节点的val满足 ∣</span><em style="font-size: 14px; color: rgb(90, 103, 111);">val</em><span style="font-size: 14px; color: rgb(90, 103, 111);">∣<=1000</span></p> <p><span style="font-size: 14px; color: rgb(102, 102, 102);">要求：时间复杂度 </span><em style="font-size: 14px; color: rgb(102, 102, 102);">O</em><span style="font-size: 14px; color: rgb(102, 102, 102);">(</span><em style="font-size: 14px; color: rgb(102, 102, 102);">nlogn</em><span style="font-size: 14px; color: rgb(102, 102, 102);">)</span></p> <p><br></p> <h2><span style="color: rgb(51, 51, 51);">示例1</span></h2> <p><br></p> <p><span style="font-size: 14px; background-color: rgb(247, 248, 249); color: rgb(102, 102, 102);">输入：[{1,2,3},{4,5,6,7}]</span></p> <p><span style="font-size: 14px; background-color: rgb(247, 248, 249); color: rgb(102, 102, 102);">返回值：{1,2,3,4,5,6,7}</span></p> <p><br></p> <p><br></p> <p><br></p> <h3>5.2.1 思路</h3> <p><br></p> <p>将每个链表的头节点压入小根堆，然后弹出的第一个元素是需要返回的元素，然后判断弹出元素是否有下个元素，如果有 再压入小根堆 然后直到小根堆中的值全部弹出。</p> <p><br></p> <p><br></p> <h3>5.2.2 代码</h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> ListNode <span class="ql-token hljs-title">mergeKLists(ArrayList<ListNode> lists)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// write code here</span> </div> <div class="ql-code-block"> PriorityQueue<ListNode> heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>(Comparator.comparingInt(o -> o.val)); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (ListNode list : lists) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (list != <span class="ql-token hljs-literal">null</span>) { </div> <div class="ql-code-block"> heap.add(list); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (heap.isEmpty()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">null</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">ListNode</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> heap.poll(); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">ListNode</span> <span class="ql-token hljs-variable">cur</span> <span class="ql-token hljs-operator">=</span> ans; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (cur.next != <span class="ql-token hljs-literal">null</span>) { </div> <div class="ql-code-block"> heap.add(cur.next); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (!heap.isEmpty()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">ListNode</span> <span class="ql-token hljs-variable">next</span> <span class="ql-token hljs-operator">=</span> heap.poll(); </div> <div class="ql-code-block"> cur.next = next; </div> <div class="ql-code-block"> cur = next; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (next.next != <span class="ql-token hljs-literal">null</span>) { </div> <div class="ql-code-block"> heap.add(next.next); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-comment">// 只提交mergeKLists这个方法即可</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">ListNode</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> val; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">ListNode</span> <span class="ql-token hljs-variable">next</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-literal">null</span>; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-title">ListNode(int val)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-built_in">this</span>.val = val; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p><br></p> <h2>题目三</h2> <p><br></p> <p>牛客链接测试：<a href="https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37" target="_blank">线段重合_牛客题霸_牛客网</a></p> <p><br></p> <p><span style="color: black;">给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间</span></p> <p><span style="color: black;">规定：</span></p> <ol> <li data-list="ordered"><span class="ql-ui"></span><span style="color: black;">线段的开始和结束位置一定都是整数值</span></li> <li data-list="ordered"><span class="ql-ui"></span><span style="color: black;">线段重合区域的长度必须>0</span></li> </ol> <p><span style="color: black;">返回线段最多重合区域中，包含了几条线段</span></p> <p><br></p> <h4><span style="color: black;">思路一</span></h4> <p><br></p> <p>使用一个比较笨的办法，我们先将数组排序 求出一个最大值 max 和一个最小值 min,这样就能确定数据是从 min开始 max结束。那么我们求 min + 0.5也就是求 min 到 max 之间每个数加 0.5 有多少个线段在这个数中，最后求出最大值即可。时间复杂度为 O((max-min)*N)</p> <p><img src="https://pic.code-nav.cn/planet_post_image/1707418316274003969/mm3be6ih.jpeg"></p> <p><br></p> <p><br></p> <p><br></p> <h5><span style="font-size: 15px;">代码</span></h5> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">getMaxConvert01(int[][] segments)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segments == <span class="ql-token hljs-literal">null</span> || segments.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">min</span> <span class="ql-token hljs-operator">=</span> Integer.MAX_VALUE; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">max</span> <span class="ql-token hljs-operator">=</span> Integer.MIN_VALUE; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> min = Math.min(min, segment[<span class="ql-token hljs-number">0</span>]); </div> <div class="ql-code-block"> max = Math.max(max, segment[<span class="ql-token hljs-number">1</span>]); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> min + <span class="ql-token hljs-number">0.5</span>; i < max; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">cur</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segment[<span class="ql-token hljs-number">0</span>] < i && segment[<span class="ql-token hljs-number">1</span>] > i) { </div> <div class="ql-code-block"> cur++; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> ans = Math.max(ans, cur); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h4>思路二</h4> <p><br></p> <p>使用堆排序，我们可以将数组的开始位置进行排序，然后依次枚举数组的开始位置 具体操作如下</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>建立一个小根堆，用于存放线段的结束位置</li> <li data-list="ordered"><span class="ql-ui"></span>依次枚举线段，将小根堆中的数小于线段开始位置的数弹出，然后压入线段的结束，计算小根堆中的数的数量</li> <li data-list="ordered"><span class="ql-ui"></span>依次比较求最大值</li> </ol> <p>时间复杂度为 O(N*logN)</p> <p><br></p> <h5><span style="font-size: 15px;">代码</span></h5> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">getMaxConvert02(int[][] segments)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segments == <span class="ql-token hljs-literal">null</span> || segments.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> Arrays.sort(segments, Comparator.comparingInt(o -> o[<span class="ql-token hljs-number">0</span>])); </div> <div class="ql-code-block"> PriorityQueue<Integer> heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>(); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (!heap.isEmpty() && heap.peek() <= segment[<span class="ql-token hljs-number">0</span>]) { </div> <div class="ql-code-block"> heap.poll(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> heap.add(segment[<span class="ql-token hljs-number">1</span>]); </div> <div class="ql-code-block"> ans = Math.max(ans, heap.size()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> </div> <h4>完整代码以及对数器</h4> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Arrays; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Comparator; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.PriorityQueue; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 最大线段重合问题</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 给定很多线段，每个线段都有两个数[start, end]，</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 表示线段开始位置和结束位置，左右都是闭区间</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 规定：</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 1）线段的开始和结束位置一定都是整数值</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 2）线段重合区域的长度必须 >0</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * 返回线段最多重合区域中，包含了几条线段</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Code01_ConvertMax</span> { </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">getMaxConvert01(int[][] segments)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segments == <span class="ql-token hljs-literal">null</span> || segments.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">min</span> <span class="ql-token hljs-operator">=</span> Integer.MAX_VALUE; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">max</span> <span class="ql-token hljs-operator">=</span> Integer.MIN_VALUE; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> min = Math.min(min, segment[<span class="ql-token hljs-number">0</span>]); </div> <div class="ql-code-block"> max = Math.max(max, segment[<span class="ql-token hljs-number">1</span>]); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> min + <span class="ql-token hljs-number">0.5</span>; i < max; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">cur</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segment[<span class="ql-token hljs-number">0</span>] < i && segment[<span class="ql-token hljs-number">1</span>] > i) { </div> <div class="ql-code-block"> cur++; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> ans = Math.max(ans, cur); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">getMaxConvert02(int[][] segments)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (segments == <span class="ql-token hljs-literal">null</span> || segments.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> Arrays.sort(segments, Comparator.comparingInt(o -> o[<span class="ql-token hljs-number">0</span>])); </div> <div class="ql-code-block"> PriorityQueue<Integer> heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>(); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : segments) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (!heap.isEmpty() && heap.peek() <= segment[<span class="ql-token hljs-number">0</span>]) { </div> <div class="ql-code-block"> heap.poll(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> heap.add(segment[<span class="ql-token hljs-number">1</span>]); </div> <div class="ql-code-block"> ans = Math.max(ans, heap.size()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span>[][] generateLines(<span class="ql-token hljs-type">int</span> N, <span class="ql-token hljs-type">int</span> L, <span class="ql-token hljs-type">int</span> R) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">size</span> <span class="ql-token hljs-operator">=</span> (<span class="ql-token hljs-type">int</span>) (Math.random() * N) + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[][] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[size][<span class="ql-token hljs-number">2</span>]; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < size; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">a</span> <span class="ql-token hljs-operator">=</span> L + (<span class="ql-token hljs-type">int</span>) (Math.random() * (R - L + <span class="ql-token hljs-number">1</span>)); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">b</span> <span class="ql-token hljs-operator">=</span> L + (<span class="ql-token hljs-type">int</span>) (Math.random() * (R - L + <span class="ql-token hljs-number">1</span>)); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (a == b) { </div> <div class="ql-code-block"> b = a + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> ans[i][<span class="ql-token hljs-number">0</span>] = Math.min(a, b); </div> <div class="ql-code-block"> ans[i][<span class="ql-token hljs-number">1</span>] = Math.max(a, b); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">main(String[] args)</span> { </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"test begin"</span>); </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">N</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">100</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">L</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">R</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">200</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">testTimes</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">200000</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < testTimes; i++) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span>[][] lines = generateLines(N, L, R); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans1</span> <span class="ql-token hljs-operator">=</span> getMaxConvert01(lines); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans2</span> <span class="ql-token hljs-operator">=</span> getMaxConvert02(lines); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (ans1 != ans2) { </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"Oops!"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> System.out.println(<span class="ql-token hljs-string">"test end"</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> </div> <p><br></p> <h4>牛客提交代码</h4> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Scanner; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.io.*; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Arrays; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.Comparator; </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">import</span> java.util.PriorityQueue; </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// 注意类名必须为 Main, 不要有任何 package xxx 信息</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Main</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">Integer</span> <span class="ql-token hljs-variable">MAX</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">10001</span>; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span>[][] line = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[MAX][<span class="ql-token hljs-number">2</span>]; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">private</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> n; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">main(String[] args)</span> <span class="ql-token hljs-keyword">throws</span> IOException { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">BufferedReader</span> <span class="ql-token hljs-variable">br</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">BufferedReader</span>(<span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">InputStreamReader</span>(System.in)); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">StreamTokenizer</span> <span class="ql-token hljs-variable">in</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">StreamTokenizer</span>(br); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">PrintWriter</span> <span class="ql-token hljs-variable">out</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PrintWriter</span>(<span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">OutputStreamWriter</span>(System.out)); </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (in.nextToken()!=StreamTokenizer.TT_EOF){ </div> <div class="ql-code-block"> n = (<span class="ql-token hljs-type">int</span>)in.nval; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i < n; i++) { </div> <div class="ql-code-block"> in.nextToken(); </div> <div class="ql-code-block"> line[i][<span class="ql-token hljs-number">0</span>] = (<span class="ql-token hljs-type">int</span>)in.nval; </div> <div class="ql-code-block"> in.nextToken(); </div> <div class="ql-code-block"> line[i][<span class="ql-token hljs-number">1</span>] = (<span class="ql-token hljs-type">int</span>)in.nval; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> out.println(getMaxConvert()); </div> <div class="ql-code-block"> out.flush(); </div> <div class="ql-code-block"> br.close(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">getMaxConvert()</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (line == <span class="ql-token hljs-literal">null</span> || line.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> Arrays.sort(line, Comparator.comparingInt(o -> o[<span class="ql-token hljs-number">0</span>])); </div> <div class="ql-code-block"> PriorityQueue<Integer> heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>(); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span>[] segment : line) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (!heap.isEmpty() && heap.peek() <= segment[<span class="ql-token hljs-number">0</span>]) { </div> <div class="ql-code-block"> heap.poll(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> heap.add(segment[<span class="ql-token hljs-number">1</span>]); </div> <div class="ql-code-block"> ans = Math.max(ans, heap.size()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p><br></p> <h2>题目四</h2> <p><br></p> <p><br></p> <p>leetCode2208</p> <p><a href="https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/" target="_blank">https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/</a></p> <p><br></p> <p><br></p> <h3>5.4.1 实现思路</h3> <p><br></p> <p><br></p> <p>题目要求是求出数组总和 sum，然后每次取一个数的一半 累计和 ansSum要求是 求 ansSum需要加多少次才能到达 sum的一半。如果说每次都取数组中的最大值，然后取一半的值加起来 求出次数就是答案</p> <p>使用大根堆，每次弹出最大值，然后取一半 再放进去 直到达到 ansSum>=sum 位置一共加了多少次即可</p> <p><br></p> <h3>5.4.2 实现代码</h3> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">halveArray(int[] nums)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (nums == <span class="ql-token hljs-literal">null</span> || nums.length == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> PriorityQueue<Double> heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">PriorityQueue</span><>((o1, o2) -> o2.compareTo(o1)); </div> <div class="ql-code-block"> <span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">sum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> num : nums) { </div> <div class="ql-code-block"> sum += num; </div> <div class="ql-code-block"> heap.add((<span class="ql-token hljs-type">double</span>) num); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> sum/=<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">count</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">curSum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (curSum < sum && !heap.isEmpty()) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">poll</span> <span class="ql-token hljs-operator">=</span> heap.poll() / <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> curSum += poll; </div> <div class="ql-code-block"> heap.add(poll); </div> <div class="ql-code-block"> count++; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> count; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h3>5.4.3 手动实现堆 代码</h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"> <span class="ql-token hljs-comment">// 手动实现一个堆结构</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">MAX</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">100001</span>; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">long</span>[] heap = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">long</span>[MAX]; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> size; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">halveArray(int[] nums)</span> { </div> <div class="ql-code-block"> size = nums.length; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">long</span> <span class="ql-token hljs-variable">sum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">for</span> (<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> size - <span class="ql-token hljs-number">1</span>; i >= <span class="ql-token hljs-number">0</span>; i--) { </div> <div class="ql-code-block"> heap[i] = (<span class="ql-token hljs-type">long</span>) nums[i] << <span class="ql-token hljs-number">20</span>; </div> <div class="ql-code-block"> sum += heap[i]; </div> <div class="ql-code-block"> heapify(i); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> sum/=<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">count</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-type">double</span> <span class="ql-token hljs-variable">curSum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (curSum < sum ) { </div> <div class="ql-code-block"> heap[<span class="ql-token hljs-number">0</span>] /= <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> curSum += heap[<span class="ql-token hljs-number">0</span>]; </div> <div class="ql-code-block"> count++; </div> <div class="ql-code-block"> heapify(<span class="ql-token hljs-number">0</span>); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">return</span> count; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">heapify(int index)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">left</span> <span class="ql-token hljs-operator">=</span> (index << <span class="ql-token hljs-number">1</span>) + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">while</span> (left < size) { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">largest</span> <span class="ql-token hljs-operator">=</span> left + <span class="ql-token hljs-number">1</span> < size && heap[left + <span class="ql-token hljs-number">1</span>] > heap[left] ? left + <span class="ql-token hljs-number">1</span> : left; </div> <div class="ql-code-block"> largest = heap[largest] > heap[index] ? largest : index; </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">if</span> (largest == index) { </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> swap(largest, index); </div> <div class="ql-code-block"> index = largest; </div> <div class="ql-code-block"> left = (index << <span class="ql-token hljs-number">1</span>) + <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> <span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">swap(int i, int j)</span> { </div> <div class="ql-code-block"> <span class="ql-token hljs-type">long</span> <span class="ql-token hljs-variable">tmp</span> <span class="ql-token hljs-operator">=</span> heap[i]; </div> <div class="ql-code-block"> heap[i] = heap[j]; </div> <div class="ql-code-block"> heap[j] = tmp; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <p><br></p> <p><br></p> </div> </body> </html>
零基础手把手带你阅读Redis源代码系列-ZSet底层原理详解（跳表SkipList）
>之前就说了要来西索Redis，现在来辣！ > >本文的部分内容参考自《小林Coding》，部分地方根据源代码进行剖析。 > >Redis源码地址：https://github.com/redis/redis.git > >更多内容可以看我博客：https://cloud.tencent.com/developer/user/2871589 ## ZSet ### 观其面 和Set类似，但是新增了一个排序字段。  常用操作 ```bash # 往有序集合key中加入带分值元素 ZADD key score member [[score member]...] # 往有序集合key中删除元素 ZREM key member [member...] # 返回有序集合key中元素member的分值 ZSCORE key member # 返回有序集合key中元素个数 ZCARD key # 为有序集合key中元素member的分值加上increment ZINCRBY key increment member # 正序获取有序集合key从start下标到stop下标的元素 ZRANGE key start stop [WITHSCORES] # 倒序获取有序集合key从start下标到stop下标的元素 ZREVRANGE key start stop [WITHSCORES] # 返回有序集合中指定分数区间内的成员，分数由低到高排序。 ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count] # 返回指定成员区间内的成员，按字典正序排列, 分数必须相同。 ZRANGEBYLEX key min max [LIMIT offset count] # 返回指定成员区间内的成员，按字典倒序排列, 分数必须相同 ZREVRANGEBYLEX key max min [LIMIT offset count] ``` 运算操作 ```bash # 并集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积 ZUNIONSTORE destkey numberkeys key [key...] # 交集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积 ZINTERSTORE destkey numberkeys key [key...] ``` ### 应用场景 #### 排行榜 点赞数量和内容ID相关联，最后再根据ID去查，或者异步更新也可以 为什么不存全部数据？部分数据会修改，那么可能导致value伪重复，加大了业务复杂度 #### 电话、姓名区间排序 使用有序集合的 `ZRANGEBYLEX` 或 `ZREVRANGEBYLEX` 可以帮助我们实现电话号码或姓名的排序，我们以 `ZRANGEBYLEX` （返回指定成员区间内的成员，按 key 正序排列，分数必须相同）为例。 **注意：不要在分数不一致的 SortSet 集合中去使用 ZRANGEBYLEX和 ZREVRANGEBYLEX 指令，因为获取的结果会不准确。** *1、电话排序* 我们可以将电话号码存储到 SortSet 中，然后根据需要来获取号段： ```shell > ZADD phone 0 13100111100 0 13110114300 0 13132110901 (integer) 3 > ZADD phone 0 13200111100 0 13210414300 0 13252110901 (integer) 3 > ZADD phone 0 13300111100 0 13310414300 0 13352110901 (integer) 3 ``` 获取所有号码: ```shell > ZRANGEBYLEX phone - + 1) "13100111100" 2) "13110114300" 3) "13132110901" 4) "13200111100" 5) "13210414300" 6) "13252110901" 7) "13300111100" 8) "13310414300" 9) "13352110901" ``` 获取 132 号段的号码： ```shell > ZRANGEBYLEX phone [132 (133 1) "13200111100" 2) "13210414300" 3) "13252110901" ``` 获取132、133号段的号码： ```shell > ZRANGEBYLEX phone [132 (134 1) "13200111100" 2) "13210414300" 3) "13252110901" 4) "13300111100" 5) "13310414300" 6) "13352110901" ``` *2、姓名排序* ```shell > zadd names 0 Toumas 0 Jake 0 Bluetuo 0 Gaodeng 0 Aimini 0 Aidehua (integer) 6 ``` 获取所有人的名字: ```shell > ZRANGEBYLEX names - + 1) "Aidehua" 2) "Aimini" 3) "Bluetuo" 4) "Gaodeng" 5) "Jake" 6) "Toumas" ``` 获取名字中大写字母A开头的所有人： ```shell > ZRANGEBYLEX names [A (B 1) "Aidehua" 2) "Aimini" ``` 获取名字中大写字母 C 到 Z 的所有人： ```shell > ZRANGEBYLEX names [C [Z 1) "Gaodeng" 2) "Jake" 3) "Toumas" ``` ### 究其身 cv完了，现在来看看源码。 Zset 类型的底层数据结构是由**压缩列表或跳表**实现的： - 如果有序集合的元素个数小于 `128` 个，并且每个元素的值小于 `64` 字节时，Redis 会使用**压缩列表**作为 Zset 类型的底层数据结构； - 如果有序集合的元素不满足上面的条件，Redis 会使用**跳表**作为 Zset 类型的底层数据结构； **在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。** listpack和压缩列表在之前讲List的时候就已经讲过了，这里主要来讲一讲跳表。 #### 跳表 跳表是从链表的结构上面改进出来的，可以说是多层链表  图中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来： - L0 层级共有 5 个节点，分别是节点1、2、3、4、5； - L1 层级共有 3 个节点，分别是节点 2、3、5； - L2 层级只有 1 个节点，也就是节点 3 。 下面我们来看看实际的结构 如上图，记录头节点和尾节点~~（图上没有，后面细说）~~，我们封装在一起，成了整个链跳表体 ```c typedef struct zskiplist { struct zskiplistNode *header, *tail; // 头节点、尾节点 unsigned long length; // 跳表长度 int level; // 最高的层级 } zskiplist; ``` 那么节点又是怎么定义的呢？如果让我来做的话，我会用给一个数组来表示下一个节点（详细看上图），不过也确实是这样做的 ```c /* ZSETs use a specialized version of Skiplists */ typedef struct zskiplistNode { sds ele; // 内容 double score; // 用于排序的字段，我们称之为权重 struct zskiplistNode *backward; //后向指针 前继 // level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。 struct zskiplistLevel { struct zskiplistNode *forward; // 每层的前向指针 后继 unsigned long span; // 跨度 } level[]; } zskiplistNode; ``` 这里对前向和后向进行一个解释： 其实就是一个双链表，不过后续指针是一个指针数组，前向指针是后继，后向指针是前继 那么这个跨度是啥？ **跨度** 用于**计算这个节点在跳表中的排位**。具体怎么做的呢？因为跳表中的节点都是按序排列的，那么计算某个节点排位的时候，**从头节点点到该结点的查询路径上，将==沿途访问过==的所有层的跨度累加起来**，得到的结果就是目标节点在跳表中的排位。 没懂？看上图，把这个节点前面的阶段求个前缀和，他们的结果就是跨度，也就是当前节点的编号。 #### 跳表的创建 ```c // 定义最高层数 Redis 7.0 定义为 32，Redis 5.0 定义为 64，Redis 3.0 定义为 32 #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */ /* Create a new skiplist. */ zskiplist *zslCreate(void) { int j; zskiplist *zsl; zsl = zmalloc(sizeof(*zsl)); zsl->level = 1; // 初始只有一层 zsl->length = 0; zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); // 创建一个节点，节点创建在后面讲 // 把每一层都初始化 for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0; } // 初始化跳表 zsl->header->backward = NULL; zsl->tail = NULL; return zsl; } ``` #### 节点创建 ```c /* Create a skiplist node with the specified number of levels. * The SDS string 'ele' is referenced by the node after the call. */ zskiplistNode *zslCreateNode(int level, double score, sds ele) { zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)); zn->score = score; zn->ele = ele; return zn; } ``` #### 跳表的释放 ```c /* Free a whole skiplist. */ void zslFree(zskiplist *zsl) { zskiplistNode *node = zsl->header->level[0].forward, *next; zfree(zsl->header); // 释放头节点 // 在初始化的时候直接指向了第一个元素 while(node) { next = node->level[0].forward; // 释放每一个节点 zslFreeNode(node); node = next; } zfree(zsl); } /* Free the specified skiplist node. The referenced SDS string representation * of the element is freed too, unless node->ele is set to NULL before calling * this function. */ void zslFreeNode(zskiplistNode *node) { sdsfree(node->ele); // 释放member zfree(node); // 释放节点 } /* Free an sds string. No operation is performed if 's' is NULL. */ void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); // s_free就是z_free } // 呃呃呃，这不解释了 void zfree(void *ptr) { #ifndef HAVE_MALLOC_SIZE void *realptr; size_t oldsize; #endif if (ptr == NULL) return; #ifdef HAVE_MALLOC_SIZE update_zmalloc_stat_free(zmalloc_size(ptr)); free(ptr); #else realptr = (char*)ptr-PREFIX_SIZE; oldsize = *((size_t*)realptr); update_zmalloc_stat_free(oldsize+PREFIX_SIZE); free(realptr); #endif } ``` #### 跳表节点查询过程 查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件： - 如果当前节点的权重 < 要查找的权重时，跳表就会访问该层上的下一个节点。 - 如果当前节点的权重 = 要查找的权重时，并且当前节点的 SDS 类型数据 < 要查找的数据时，跳表就会访问该层上的下一个节点。 如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。 举个例子，下图有个 3 层级的跳表。  如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的： - 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点； - 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1]; - 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据 > 要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]； - 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。 ```c // 这里是查找的源码，来自下面新增节点的函数 x = zsl->header; //从顶层开始，遍历开始，每次移动不只是移动头节点的level，是所有节点的level，每次都是从上一次遍历到的节点开始 for (i = zsl->level-1; i >= 0; i--) { /* store rank that is crossed to reach the insert position */ rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; //如果从头开始，跨度为0，否则累加上一层已经计算的跨度 while (x->level[i].forward && (x->level[i].forward->score < score || // 权值小于目标 (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0))) // 当前节点的memer小于目标节点 { rank[i] += x->level[i].span; //计算跨度 x = x->level[i].forward; //到下一个索引位置 } update[i] = x; //记录当前层开始修改的节点的位置 } ``` #### 新增节点 ```c /* Insert a new node in the skiplist. Assumes the element does not already * exist (up to the caller to enforce that). The skiplist takes ownership * of the passed SDS string 'ele'. */ zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; unsigned long rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(!isnan(score)); x = zsl->header; //从顶层开始，遍历开始，每次移动不只是移动头节点的level，是所有节点的level，每次都是从上一次遍历到的节点开始 for (i = zsl->level-1; i >= 0; i--) { /* store rank that is crossed to reach the insert position */ rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; //如果从头开始，跨度为0，否则累加上一层已经计算的跨度 while (x->level[i].forward && (x->level[i].forward->score < score || // 权值小于目标 (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0))) // 当前节点的Memer小于目标节点 { rank[i] += x->level[i].span; //计算跨度 x = x->level[i].forward; //到下一个索引位置 } update[i] = x; //记录当前层开始修改的节点的位置 } /* we assume the element is not already inside, since we allow duplicated * scores, reinserting the same element should never happen since the * caller of zslInsert() should test in the hash table if the element is * already inside or not. */ // 假设要插入的元素在跳跃表中尚不存在，因为跳跃表允许有相同的分值（score）。 // 再次插入相同的元素是不应该发生的，因为调用 zslInsert() 函数的调用者应该在哈希表（或其他数据结构）中先测试元素是否已经存在。 // 在跳跃表中，允许多个节点具有相同的分值，但它们的元素值必须不同。 level = zslRandomLevel(); //随机生成一个层数 if (level > zsl->level) { // 如果这个level达到新高，那么往上面走，走到顶全部初始化（你可以理解为对level进行扩容） for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; // 新的level,那么再old_level到level之间的跨度每层都是length update[i]->level[i].span = zsl->length; } zsl->level = level; } x = zslCreateNode(level,score,ele); // 创建一个新的节点 for (i = 0; i < level; i++) { //插入节点（基础知识：单链表的节点插入），修改第Li层的后继 x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; /* update span covered by update[i] as x is inserted here */ // (rank[0] - rank[i])为新节点到前一层节点的跨度差 // update[i]->level[i].span 表示的是原本前一个节点到后一个节点建的跨度 // 这里新来了一个节点，前一个节点新节点的跨度是rank[0] - rank[i]，另外一个就互补，见一下就可以了 x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); // 修改前一个节点的跨度，但是这个节点本身也算一个系欸但，所以要加1 update[i]->level[i].span = (rank[0] - rank[i]) + 1; } /* increment span for untouched levels */ // 前面我们只修改了同层，上面的每一层因为中间多了一个，所以跨度加一 for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } // 修改x的前继指针 x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; // 只修改最下面一层的 else zsl->tail = x; //把x放在最后 zsl->length++; return x; } ``` #### 删除节点 ```c /* Delete an element with matching score/element from the skiplist. * The function returns 1 if the node was found and deleted, otherwise * 0 is returned. * * If 'node' is NULL the deleted node is freed by zslFreeNode(), otherwise * it is not freed (but just unlinked) and *node is set to the node pointer, * so that it is possible for the caller to reuse the node (including the * referenced SDS string at node->ele). */ int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; int i; x = zsl->header; // 这里再将新增的时候讲过了 for (i = zsl->level-1; i >= 0; i--) { while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0))) { x = x->level[i].forward; } update[i] = x; } /* We may have multiple elements with the same score, what we need * is to find the element with both the right score and object. */ x = x->level[0].forward; if (x && score == x->score && sdscmp(x->ele,ele) == 0) { // 进行节点删除，并且把关联系欸但进行修改 zslDeleteNode(zsl, x, update); if (!node) // 把空间释放 zslFreeNode(x); else *node = x; return 1; } return 0; /* not found */ } ``` ##### 解决连锁反应 ```c void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) { int i; for (i = 0; i < zsl->level; i++) { if (update[i]->level[i].forward == x) { update[i]->level[i].span += x->level[i].span - 1; update[i]->level[i].forward = x->level[i].forward; } else { update[i]->level[i].span -= 1; } } if (x->level[0].forward) { x->level[0].forward->backward = x->backward; } else { zsl->tail = x->backward; } while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL) zsl->level--; zsl->length--; } ```
数据结构和算法学习路线 | 26 年最新零基础到精通一条龙（万人收藏⭐️）
> 编程导航学习网站：[学编程、做项目、拿 Offer！](https://www.codefather.cn) > > 企业高频面试题库：[开始刷题，面试遇原题！](https://www.mianshiya.com) > > 精选简历模板大全：[1 分钟搞定简历！](https://www.laoyujianli.com) > > AI 资源导航网站：[获取最新 AI 黑科技！](https://ai.codefather.cn) > > 1 对 1 模拟面试：[随时随地提升面试能力](https://ai.mianshiya.com) 数据结构和算法求职高频面试题：[开始刷题](https://www.mianshiya.com/bank/1824727406021644290) ## 开篇介绍 为什么数据结构和算法如此重要？因为：**程序 = 数据结构 + 算法** **数据结构** 是一组数据的存储结构和组织方式，使得该组数据便于访问、修改、存储。 **算法** 是操作数据的一组方法，解决问题的一系列步骤。 ### 为什么要学数据结构和算法？ 有些同学可能会因为平时写代码用不到数据结构和算法，就认为它们不重要，这是 **一个错误的认识**！ 其实很多时候，并不是用不到，而是因为你欠缺了一部分知识后，**根本就想不到去用它来优化你的程序**，比如提高性能、节省内存等。 还有一个平时很少用到算法的原因是：其他开发者给你封装好了。但假如有一天，你用的框架或算法库出了问题、或者某个算法效率低下，需要你来优化的时候，如果没学过数据结构和算法你大概率是搞不定的。 换句话说，不是不报，是时候未到。学好算法和数据结构，有助于开拓我们的思路，改变我们思考问题的方式，提高我们的问题解决能力（公司最看重的也是这点）。 至少我觉得，学习数据结构和算法让我受益匪浅，后来在鹅厂的工作中也用到过 N 次。 ### 鱼皮的算法导航网站 在正式学习之前，强烈推荐大家使用鱼皮制作的 **免费交互式算法学习平台 —— 算法导航**！ 网站地址：https://algo.codefather.cn 这是一个通过 **可视化动画和交互** 的方式，帮你轻松理解各种算法和数据结构工作原理的学习平台。相比枯燥的文字教程，动画演示能让你更直观地看到算法的执行过程！  特点： - ✅ 完全免费，无需注册 - ✅ 交互式可视化动画 - ✅ 涵盖排序、查找、动态规划、图论等主流算法 - ✅ 保姆级算法学习路线 - ✅ 每个算法都有详细的时空复杂度分析 网站包含： - 10+ 排序算法：冒泡排序、快速排序、归并排序、堆排序等 - 查找算法：二分查找、哈希查找等 - 字符串匹配：KMP 算法等 - 经典算法：递归、回溯、动态规划、贪心等 - 数据结构：线性结构、树形结构、图结构、哈希等  ### 学习条件 1. 必须要学过至少一门编程语言 2. 需预留至少 2 个月的空余时间，急着找工作的同学可以先不学 ### 什么时候学数据结构和算法？ 时间足够的话，我个人建议 **学完一门编程语言后** 就可以开始刷算法了。一方面是因为算法真的是太重要了；另一方面是用编程语言刷算法还能巩固一下语法基础，避免出现纸上谈兵、后面做项目时因为不熟悉语法导致写不出代码的情况。 完全零基础的话，数据结构和算法不是面试前短短几周就能准备过来的（除非你很聪明）。鱼皮是从大二上开始跟着学校学习数据结构（虽然我没怎么听课，是靠后面自己看书补回来的），并且从大二暑假开始刷题，一年多的时间总共刷了 1000 多道算法题。因为自己准备得早，所以学得还算比较扎实，面试时遇到的算法题目基本都能答出来；也是因为准备得早，每天的压力没那么大。 ### 学习路线图  ## 整体学习建议 1）坚持每天刷题：数据结构和算法不可追求速成（学得快忘得快），而是应该每天坚持刷 2 道以上的题目保持手感。可以在编程导航中打卡分享自己每天所刷的题目，也许会有小伙伴和你一起讨论。 2）多写注释和总结：自己在写算法题目时，要给代码多写一些注释，记录自己当时的思考，并且做过的每道算法题目的代码都要分类保存好，便于自己复习。可以根据实际情况自己写一些题解，写题解的过程中，不仅能检验自己是否真的理解，还能再次巩固、帮助自己复习。 3）用任何编程语言都可以：算法是一种思想，用任何你正在学习或者熟悉的编程语言来写代码均可，可以帮助你复习编程语言的语法和细节。 4）不用担心算法不够：不用因为担心自己算法不够而不敢面试，只要你有了基本的开发技能就足够了，算法可以持续强化。 5）挑战自己：很多同学可能会习惯性地刷自己觉得很简单的题目，而对于中等 / 困难的题目有恐惧感，下意识地回避。这在刚开始入门时没什么问题，但如果已经刷了几百题，不要满足于自己会的知识，要适当挑战，走出舒适圈。 6）善用 AI 辅助学习：遇到不理解的算法或题目，可以问 AI 工具（如 ChatGPT、DeepSeek）让它用通俗的语言解释，或者让它画图演示算法过程。AI 还可以帮你分析代码的时间复杂度和空间复杂度。更多 AI 工具推荐可以看看鱼皮的 [AI 资源导航](https://ai.codefather.cn/)。  7）参加竞赛和考证：有时间的朋友也可以试着参加各种算法竞赛和考证书，比如蓝桥杯、PAT 认证、LeetCode 周赛等。这些比赛没什么门槛，难度也没有 ACM 那么高。可以帮助你集中精神高效做题、提前适应面试的节奏感。 ## 知识体系 ### 数据结构 - **线性结构** - 数组（字符串） - 链表（单向链表、双向链表、循环链表） - 栈 - 队列（普通队列、双端队列） - **散列结构** - 集合 - 映射 - BitMap - **树** - 二叉树 - 二叉查找树 - 多叉树 - 前缀树 - 堆（小顶堆、大顶堆） - **图** - 最短路径 - 并查集 - 最小生成树 - 拓扑排序 ### 算法 - **排序算法** - 冒泡排序、快速排序、插入排序、希尔排序 - 选择排序、堆排序、归并排序 - 计数排序、桶排序、基数排序 - **查找算法** - 有序表查找（二分查找） - 线性表查找 - 树结构查找 - 散列表查找 - **经典算法思想** - 贪心算法 - 分治算法 - 动态规划 - 递归 - 回溯 - 枚举 - **搜索算法** - 深度优先搜索（DFS） - 广度优先搜索（BFS） - **字符串匹配** - KMP 算法 - 前缀树 - **位运算** ### 复杂度分析 - 时间复杂度 - 空间复杂度 ## 学习路线 > 本学习路线适用于所有从 0 开始学算法的同学，但如果是要搞 ACM 算法竞赛的话，只学这些是远远不够的哦。 ### 阶段 1：预热（可选） 学习目标：培养对算法的兴趣，简单入门，不要求真正理解。 #### 学习建议 初学编程、刚开始学习算法时，可以先通过阅读课外书、科普视频来培养兴趣，简单地入门，而不要求真正的理解。 #### 学习资源 - [《算法图解》](https://www.aliyundrive.com/s/MFSC8TP7ANB) 提取码: 73dl：图文并茂的算法入门书 - [《大话数据结构》](https://www.aliyundrive.com/s/MFSC8TP7ANB) 提取码: 73dl：通俗易懂的数据结构入门书 ### 阶段 2：依次学习 学习目标：了解每个数据结构和算法的概念、特点、适用场景、时空复杂度，并且能够自己写代码从 0 到 1 实现一遍每个数据结构和算法。 #### 学习建议 1）按顺序学习：注意要按顺序学习，而不是一次性看完所有的数据结构和算法后才再回过头来写代码！ 2）边学边练：学完某个数据结构和算法后，立刻趁热打铁去做几道相关的题目。 3）重点突出：链表、树是面试重点，要多花时间。图论这一块了解即可，优先级不高，面试考的也不多。 4）使用可视化工具：强烈推荐使用 [算法导航](https://algo.codefather.cn/) 来学习，通过动画演示理解算法的执行过程。 5）多看题解：即使是自己做出的题目，也建议去看下其他同学的题解，多积累一种方法。 #### 学习顺序 推荐直接从 LeetCode 的学习板块 LeetBook 开始刷起，边学边写代码，学的更扎实。 1）算法基础理论和复杂度分析 - [数据结构与算法基础（青岛大学-王卓）](https://www.bilibili.com/video/BV1nJ411V7bd)：看前几节就可以了，后面可以配合着 LeetCode 去看 2）数组和字符串 - [LeetCode 数组和字符串](https://leetcode-cn.com/leetbook/detail/array-and-string/) 3）链表 - [LeetCode 链表](https://leetcode-cn.com/leetbook/detail/linked-list/) 4）队列 & 栈 - [LeetCode 队列 & 栈](https://leetcode-cn.com/leetbook/detail/queue-stack/) 5）哈希表 - [LeetCode 哈希表](https://leetcode-cn.com/leetbook/detail/hash-table/) 6）查找表类算法 - [LeetCode 查找表类算法](https://leetcode-cn.com/leetbook/detail/all-about-lockup-table/) 7）二分查找 - [LeetCode 二分查找](https://leetcode-cn.com/leetbook/detail/binary-search/) 8）二叉树 - [LeetCode 二叉树](https://leetcode-cn.com/leetbook/detail/data-structure-binary-tree/) 9）二叉搜索树 - [LeetCode 二叉搜索树](https://leetcode-cn.com/leetbook/detail/introduction-to-data-structure-binary-search-tree/) 10）前缀树 - [LeetCode 前缀树](https://leetcode-cn.com/leetbook/detail/trie/) 11）N 叉树 - [LeetCode N 叉树](https://leetcode-cn.com/leetbook/detail/n-ary-tree/) 12）数组类算法 - [LeetCode 数组类算法](https://leetcode-cn.com/leetbook/detail/all-about-array/) 13）初级算法 - [LeetCode 初级算法](https://leetcode-cn.com/leetbook/detail/top-interview-questions-easy/) 14）中级算法 - [LeetCode 中级算法](https://leetcode-cn.com/leetbook/detail/top-interview-questions-medium/) #### 完整教程 - ⭐ [数据结构与算法基础（青岛大学-王卓）](https://www.bilibili.com/video/BV1nJ411V7bd)：经典教程，讲解清晰 - [尚硅谷 Java 数据结构与算法](https://www.bilibili.com/video/BV1E4411H73v)：难度和涉及的知识点比面试的要求大一些，**初次学习不建议看**，适合时间充裕、希望更全面学习的朋友来查漏补缺 #### 辅助学习的工具 - ⭐ [算法导航](https://algo.codefather.cn/)：鱼皮的交互式算法学习平台，可视化动画演示 - [VisuAlgo 数据结构和算法动态可视化](https://visualgo.net/zh)：数据结构和算法动态可视化 - [数据结构可视化](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)：算法执行过程可视化 ### 阶段 3：依次练习 学习目标：通过练习巩固每个数据结构和算法的知识。 #### 学习建议 1）限时做题：每道题目给自己一个时间限制，超出时间后就直接去阅读题解（建议看带有图片和动画演示的题解），有一些思路后再试着自己去做题，直到把题目完成写出，并且要真正理解每道题目的解法。 2）多看题解：即使是自己做出的题目，也建议去看下其他同学的题解，多积累一种方法。 3）使用算法导航：做题时可以配合 [算法导航](https://algo.codefather.cn/) 观看算法的动画演示，加深理解。 ### 阶段 4：大量刷题 学习目标：通过大量刷题提升解题能力和速度，为面试做准备。 #### 学习建议 当把每个知识点学完一遍后，可以去 LeetCode 网站的题库中刷题，按照难易度、通过率、热门程度每天坚持刷几道。时间紧张（三个月内）的话也可以直接去刷热门题目集合。 有时间的话，建议大家可以参加 [蓝桥杯竞赛](https://www.lanqiao.cn/)、考 [PAT 认证](https://www.patest.cn/)，检验自己的学习、丰富自己的简历。鱼皮大学的时候都参加过。 #### 刷题顺序 仅供参考，可以有自己的学习方法和习惯。 1. 先按知识点逐个去刷：可以进入 [LeetCode 学习板块](https://leetcode-cn.com/leetbook/)，这里有按知识点分类的教程和题目，比如初级算法、数组、字符串、队列、栈、树等等。每刷完一个知识点，可以再做几道相关的题目，举一反三，每道题目都要做到 100% 通过。 2. 把所有知识点逐个刷完后：可以再按照难度、通过率去自由刷题，刷大概几十道简单题目后，可以去做 [LeetCode 热题 100 道](https://leetcode-cn.com/problem-list/2cktkvj/)。当然，时间紧迫的话，也可以直接刷热题。 3. 建议刷题量：算法最好刷 200 道题以上，每天 2 - 3 道，坚持 2 个月以上，并且还要整理好自己的代码、定期复习。尽量不要去刷冷门的题目！别逞能去刷那么多 Hard 题，性价比不高，不如省点时间去做项目。 4. 巩固强化：刷完 LeetCode 经典题目后，可以去刷刷《剑指 Offer》或者《剑指 Offer 面试精装版》进行巩固。 #### 刷题平台 - ⭐ [LeetCode](https://leetcode-cn.com/)：最主流的算法刷题平台 - [洛谷](https://www.luogu.com.cn/)：适合算法竞赛 #### 推荐题单 - ⭐ [LeetCode 精选 100 道](https://leetcode-cn.com/problem-list/2cktkvj/) - [LeetCode 精选算法 200 题](https://leetcode-cn.com/problem-list/qg88wci/) - [LeetCode 算法高频面试题汇总](https://leetcode-cn.com/leetbook/detail/top-interview-questions/) ### 阶段 5：面试前冲刺 学习目标：在面试前集中复习，提高面试通过率。 #### 学习建议 1）刷热门题目：在面试前，建议刷一遍 LeetCode 热门题目，有时间的话还可以阅读《剑指 Offer》、《剑指 Offer 专项突破版》、《程序员代码面试指南》等书籍，争取面试时撞到原题。 2）刷公司真题：如果有意向公司（比如大厂）的话，可以去刷一下 [历年笔试题目](https://www.nowcoder.com/exam/company)（难度可能比较大，不要因此丧失信心，多练习后就习惯了）。 3）复习算法知识：面试前一定要系统复习一遍常见算法的时间复杂度、空间复杂度、适用场景等。 4）准备手写代码：面试时可能要求现场手写代码，要能快速写出正确的算法。建议提前练习几遍常见算法（如快排、二分查找、DFS/BFS 等）。 5）多看真实面经：[真实面经大全](https://www.codefather.cn/job/experience)，了解不同公司对算法的考察重点。 更多求职干货： - [鱼皮的保姆级求职指南](https://www.codefather.cn/course/job) - [鱼皮的保姆级写简历指南](https://www.codefather.cn/course/1802644557818343425) - [编程导航的求职干货分享](https://www.codefather.cn/learn?category=76&type=2) - [老鱼简历 - 写简历工具](https://www.laoyujianli.com/) - [真实面经大全](https://www.codefather.cn/job/experience) - [几百场真实面试视频](https://www.codefather.cn/mockInterview) - [1 对 1 AI 模拟面试](https://ai.mianshiya.com/) - [面试题讲解视频 - 面试鸭 B 站账号](https://space.bilibili.com/3546383483144655) #### 推荐资源 - ⭐ [图解算法数据结构](https://leetcode-cn.com/leetbook/detail/illustration-of-algorithm/)：图文并茂的算法题解 - [Leetcode 真题解析视频](https://www.bilibili.com/video/BV1a54y1b74k)：视频讲解 LeetCode 经典题目 - [LeetCode 101（C++）](https://github.com/changgyhub/leetcode_101)：C++ 题解汇总 - [LeetCode 题解（C++）](https://github.com/soulmachine/leetcode)：C++ 详细题解 - [LeetCode Cookbook（Go 语言）](https://github.com/halfrost/LeetCode-Go)：Go 语言题解 ### 阶段 6：工作后（可选） 工作之后，如果有兴趣的话，可以通过刷题来帮助自己巩固编程语言、提升思维能力。 ## 面试考察形式 算法面试主要有以下几种形式： 1. 手写算法题：给定题目，现场编写代码（最常见） 2. 口述思路：描述如何用算法解决某个问题 3. 算法优化：给一个低效的算法，让你优化 4. 复杂度分析：分析算法的时间复杂度和空间复杂度 5. 数据结构设计：设计一个数据结构来满足特定需求 ## 面试题库 - ⭐ [算法和数据结构面试题 - 面试鸭](https://www.mianshiya.com/bank/1824727406021644290) - ⭐ [数据结构面试题 - 面试鸭](https://www.mianshiya.com/bank/1824727630718898177) - [大厂算法真题面试题 - 面试鸭](https://www.mianshiya.com/bank/1814979506750275585) - [回溯面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426864626651137) - [Trie 面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426867738824705) - [图面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426868414107650) - [前缀和面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426872692297729) - [字符串面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426873728290818) - [树面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426876085489665) - [栈面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426881391284225) - [位运算面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426884570566658) - [差分面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426888815202305) - [数学面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426889238827009) - [动态规划面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426891520528386) - [遍历面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426898172694529) - [贪心面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426900836077569) - [滑动窗口面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426904673865730) - [排序面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426906175426561) - [双指针面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426908549402626) - [链表面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426910944350209) - [二分法面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426914979270658) - [并查集面试题 - 面试鸭](https://www.mianshiya.com/bank/1824426917294526466) ## 更多学习建议 ### 1、刷题顺序 最直接的就是按照知识点标签选题，从【简单的】题目刷起，从【通过率高】的题目刷起，循序渐进。 ### 2、养成自己的刷题习惯 的确，学算法是枯燥的，想长期坚持非常难，像鱼皮当时刷了 1000 多道不同平台的题目，现在回过头来都觉得不可思议。 分析下我能够坚持刷这么多题的原因，主要是因为养成了自己的刷题习惯，把刷算法当成了像刷牙洗脸一样的日常任务。 怎么养成自己的刷题习惯呢？ 1）每天在固定的时间学习算法。比如我当时每天早上 6 点多就会躺在床上思考没解决的算法题，想到方案后就会拿个枕头靠在床上敲代码做题，其实都有点魔怔了哈哈。 2）给自己定每日的学习目标。比如我每天会花 1 个半小时左右完成 3 道题目，不多也不少。如果没做完，就等其他工作完成后再静下心来思考；如果超前达到目标，那么可以奖励自己一顿番茄炒蛋。 3）分享自己的学习记录。比如我当时每刷几十道题目，就会跟朋友小小 "炫耀" 一下，看着自己的打卡表越来越满，也会有不小的成就感。 ### 3、找到自己的灯塔 如果一个人学算法觉得很累，那么就一定要找到能伴你共同前行的伙伴，或者给你指路的灯塔。 可能是和你一起努力刷题的伙伴，可能是一个算法交流圈子，可能是一位专业的算法导师。 说不定一个问题你自己思考 30 分钟还没办法解决，而请教他人 5 分钟就能解决了，能大大节约你的时间。 至于一些三天打鱼两天晒网、动不动就摆烂的人，还是敬而远之。 ### 4、学会总结 解决学算法学了就忘的最好方法，就是多记录总结，把知识沉淀成电子文档，而不是全部装在大脑里。 不要觉得写总结很麻烦，记录自己的解题思路、或者在代码上补充详细的注释都是可以的。如果你连自己的思路都表述不清楚，那么说明这道题你就没有理解！打回去重做！ 可以通过云文档、GitHub 仓库、或者各平台的发帖来总结分享自己的题解和心得，费曼学习法，能够给别人讲清楚题目的做法，你自己的印象就会更深刻。 这样做了之后，哪怕刷了算法就忘，也能快速通过自己的笔记总结捡起来当时的思路，大幅提高复习效率。 ### 5、利用题解 LeetCode 平台的每道题目都有很多小伙伴给出了题解，讲述如何解决这道题。 **怎么才算利用好题解呢？** 首先，读题解包括两个部分，**读思路** 和 **读代码**，既要理解作者做题的思路和逻辑，也要细致入微地学习他人代码中优秀的写法。即使这道题目你做出来了，击败 100% 了，我也建议去看看别人的题解，学习更多他人解题的思路，帮助自己打开脑洞，做到 **一题多解**。 话说，现在网上的题解实在是太多啦！在刷题时，读个一两份就行了，别给自己太大压力。 除了看题解外，很多同学没有意识到，多写题解才是真正的法宝，把自己的解题思路整理成文，或者讲给别人听。这样做不仅能够加深自己对题目的印象，进一步加深对算法的理解，帮助自己回顾解题过程，从而在面试的时候更容易复述；还能帮助到更多同学。 甚至有一些厉害的同学通过记录和分享自己的题解，还没毕业，就已经出版了自己的书籍，年入几十万或者百万！ 写题解利人利己，何乐而不为呢？ ### 6、精益求精 当你每次成功解题时，LeetCode 系统会生成一份解题报告，告诉你的程序在时间和空间上击败了多少用户。 虽然答出题目就已经很棒了，但还不够。面试的时候，一些面试官就喜欢给你出题目的变种，或者要求你用更优的方式解出题目。所以，在保证完全理解题目解法的基础上，请不断优化你的代码，找到更多的思路和更优解，直到击败 100% 的用户吧。 我们在工作中，虽然未必会直接和算法打交道，但学习算法对工作的帮助真的很大！ 解算法题时，我们要对多种算法分析复杂度，从中选择最优解。而在工作中，也是如此，一个需求有很多种实现方式，经常也要设计几种不同的方案，分析他们的成本、性能等差异，选择其中最好的一种进行实施。 所以，请认真对待每一道算法题目，把它当成一个工程问题来解决，相信你的思维会逐渐打开，并逐渐掌握编写高性能程序的技巧。 ### 7、多实践 #### 参加竞赛 我建议大家多参加算法竞赛，这里的竞赛不是指 ACM 区域赛那种大神级别的，别忘了此时我们的目标只是找工作。 其实，LeetCode 网站每周都会开展一次线上算法竞赛，看看谁能在有限时间内最快最多地解题。 在竞赛的过程中，紧张刺激的环境会使我们的精神保持高度集中，能够激发出我们的思维，从而在有限的时间内进行更多的思考，也能帮助我们适应面试的节奏。多多参加还有机会获得他们官方提供的奖励！ 此外，参加蓝桥杯竞赛也是不错的，我自己也参加了两届，题目的难度和找工作要求的算法题目难度相当，也能发现自身的不足、激励自己进步吧。 #### 考取证书 这几年，[PAT 计算机程序设计能力考试](https://www.patest.cn/) 在逐渐升温，分为顶级、甲级、乙级三个级别。 我亲身参加过甲级和乙级的考试，难度适中，虽然目前这个证书的含金量不高，但在备战考证的过程中，你有一个学习的目标，会更有动力坚持下去。在我看来，过程大于结果。 加油各位优秀的小伙伴们 💪🏻！  ## 程序员必备资源 1）程序员学习交流圈：[极客教程、实战项目、求职宝典](https://www.codefather.cn) 2）程序员面试八股文：[实习/校招/社招高频考点、企业真题解析](https://www.mianshiya.com) 3）程序员写简历神器：[专业模板、丰富例句、直通面试](https://www.laoyujianli.com) 4）AI 知识资源大全：[前沿技术、最新 AI 资讯、提示词大全](https://ai.codefather.cn) 5）1 对 1 模拟面试：[实习/校招/社招面试拿 Offer 必备](https://ai.mianshiya.com)
面试题(二十四)数据结构与算法
<html> <head></head> <body> <div class="content ql-editor"> <p><a href="https://blog.csdn.net/weixin_60257072/article/details/129007222?spm=1001.2014.3001.5501" target="_blank">(1条消息) 面试题(二十四)数据结构与算法_林寻星辰的博客-CSDN博客</a></p> <p><a href="https://www.yuque.com/linxun-bpyj0/linxun/lo06998y6cpqsvql" target="_blank">面试题(二十四)数据结构与算法 副本 (</a><a href="http://yuque.com" target="_blank">yuque.com</a><a href="https://www.yuque.com/linxun-bpyj0/linxun/lo06998y6cpqsvql" target="_blank">)</a></p> <p><br></p> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.1哈希</span></h1> <h2><span style="color: rgb(0, 0, 0);">请谈一谈，hashCode() 和equals() 方法的重要性体现在什么地方？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：JAVA哈希表</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">请说一说，Java中的HashMap的工作原理是什么？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：JAVA哈希表</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">参考回答：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap是以键值对的形式存储元素的，需要一个哈希函数，使用hashcode和eaquels方法，从集合中添加和检索元素，调用put方法时，会计算key 的哈希值，然后把键值对存在集合中合适的索引上，如果键key已经存在，value会被更新为新值。另外HashMap的初始容量是16，在jdk1.7的时候底层是基于数组和链表实现的，插入方式是头插法。jdk1.8的时候底层是基于数组和链表/红黑树实现的，插入方式为尾插法。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">介绍一下，什么是hashmap?</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：哈希表</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap 是一个散列表，它存储的内容是键值对(key-value)。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap 继承于AbstractMap，实现了Map、Cloneable、</span><a href="http://java.io.Serializable" target="_blank" style="font-size: 14px; color: rgb(0, 0, 0);">java.io.Serializable</a><span style="font-size: 14px; color: rgb(0, 0, 0);">接口。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap 的实现不是同步的，所以它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap 的实例有两个参数影响其性能：“初始容量” 和 “负载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。负载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">HashMap在扩容的时候是2的n次幂。</span></li> </ol> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">讲一讲，如何构造一致性哈希算法。</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：哈希算法</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">先构造一个长度为2^32的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 2^32-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2^32-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">请问，Object作为HashMap的key的话，对Object有什么要求吗？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：哈希表</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">要求Object中hashcode不能变。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">请问 HashSet 存的数是有序的吗？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：哈希</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">HashSet是无序的。</span></p> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.2 树</span></h1> <h2><span style="color: rgb(0, 0, 0);">TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：Tree</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">TreeSet要求存放的对象所属的类必须实现</span><strong style="font-size: 14px; color: rgb(0, 0, 0);">Comparable</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">接口，该接口提供了比较元素的</span><strong style="font-size: 14px; color: rgb(0, 0, 0);">compareTo()</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public class Student implements Comparable<Student> { </div> <div class="ql-code-block"> private String name; // 姓名 </div> <div class="ql-code-block"> private int age; // 年龄 </div> <div class="ql-code-block"> public Student(String name, int age) { </div> <div class="ql-code-block"> this.name = name; </div> <div class="ql-code-block"> this.age = age; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> @Override </div> <div class="ql-code-block"> public String toString() { </div> <div class="ql-code-block"> return "Student [name=" + name + ", age=" + age + "]"; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> @Override </div> <div class="ql-code-block"> public int compareTo(Student o) { </div> <div class="ql-code-block"> return this.age - o.age; // 比较年龄(年龄的升序) </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> import java.util.Set; </div> <div class="ql-code-block"> import java.util.TreeSet; </div> <div class="ql-code-block"> class Test01 { </div> <div class="ql-code-block"> public static void main(String[] args) { </div> <div class="ql-code-block"> Set<Student> set = new TreeSet<>(); </div> <div class="ql-code-block"> // Java 7 </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> import java.util.Set; </div> <div class="ql-code-block"> import java.util.TreeSet; </div> <div class="ql-code-block"> class Test01 { </div> <div class="ql-code-block"> public static void main(String[] args) { </div> <div class="ql-code-block"> Set<Student> set = new TreeSet<>(); </div> <div class="ql-code-block"> // Java 7的钻石语法(构造器后面的尖括号中不需要写类型) </div> <div class="ql-code-block"> set.add(new Student("Hao LUO", 33)); </div> <div class="ql-code-block"> set.add(new Student("XJ WANG", 32)); </div> <div class="ql-code-block"> set.add(new Student("Bruce LEE", 60)); </div> <div class="ql-code-block"> set.add(new Student("Bob YANG", 22)); </div> <div class="ql-code-block"> for(Student stu : set) { </div> <div class="ql-code-block"> System.out.println(stu); </div> <div class="ql-code-block"> } // </div> <div class="ql-code-block"> set.add(new Student("Hao LUO", 33)); </div> <div class="ql-code-block"> set.add(new Student("XJ WANG", 32)); </div> <div class="ql-code-block"> set.add(new Student("Bruce LEE", 60)); </div> <div class="ql-code-block"> set.add(new Student("Bob YANG", 22)); </div> <div class="ql-code-block"> for(Student stu : set) { </div> <div class="ql-code-block"> System.out.println(stu); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 输出结果: </div> <div class="ql-code-block"> // Student [name=Bob YANG, age=22] </div> <div class="ql-code-block"> // Student [name=XJ WANG, age=32] </div> <div class="ql-code-block"> // Student [name=Hao LUO, age=33] </div> <div class="ql-code-block"> // Student [name=Bruce LEE, age=60] </div> <div class="ql-code-block"> // } </div> <div class="ql-code-block"> // } </div> <div class="ql-code-block"> // Student [name=Bob YANG, age=22] </div> <div class="ql-code-block"> // Student [name=XJ WANG, age=32] </div> <div class="ql-code-block"> // Student [name=Hao LUO, age=33] </div> <div class="ql-code-block"> // Student [name=Bruce LEE, age=60] </div> <div class="ql-code-block"> // </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">如何打印二叉树每层的节点？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：二叉树</span></p> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">注意</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">：面试中一般写核心代码，另外就是可以问一下面试是输出ArrayList还是int数组。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> /** * Definition for a binary tree node. * </div> <div class="ql-code-block"> * </div> <div class="ql-code-block"> public class TreeNode { </div> <div class="ql-code-block"> int val; </div> <div class="ql-code-block"> TreeNode left; </div> <div class="ql-code-block"> TreeNode right; </div> <div class="ql-code-block"> </div> <div class="ql-code-block"> TreeNode(int x) { </div> <div class="ql-code-block"> val = x; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } */ </div> <div class="ql-code-block"> class Solution { </div> <div class="ql-code-block"> public int[] levelOrder(TreeNode root) { </div> <div class="ql-code-block"> // 如果root为空直接返回 </div> <div class="ql-code-block"> if(root == null){ </div> <div class="ql-code-block"> return new int[0]; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 层次遍历 </div> <div class="ql-code-block"> // 队列 </div> <div class="ql-code-block"> Deque<TreeNode> deque = new LinkedList<>(); </div> <div class="ql-code-block"> // 存每一层节点 </div> <div class="ql-code-block"> ArrayList<Integer> temp = new ArrayList<>(); </div> <div class="ql-code-block"> // 根节点入队 </div> <div class="ql-code-block"> deque.offer(root); </div> <div class="ql-code-block"> while(!deque.isEmpty()){ </div> <div class="ql-code-block"> int size = deque.size(); </div> <div class="ql-code-block"> for(int i=0;i<size;i++) { </div> <div class="ql-code-block"> //层次遍历 </div> <div class="ql-code-block"> TreeNode curroot = deque.pop(); </div> <div class="ql-code-block"> temp.add(curroot.val); </div> <div class="ql-code-block"> // 做节点是否为空 </div> <div class="ql-code-block"> if(curroot.left!=null) </div> <div class="ql-code-block"> deque.offer(curroot.left); </div> <div class="ql-code-block"> if(curroot.right!=null) </div> <div class="ql-code-block"> deque.offer(curroot.right); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 如果要求返回int数组 就写上这一步，如果没有要求可以直接返回temp即可。 </div> <div class="ql-code-block"> int []result = new int[temp.size()]; </div> <div class="ql-code-block"> for(int i=0;i<result.length;i++){ </div> <div class="ql-code-block"> result[i] = temp.get(i); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">如何知道二叉树的深度？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：二叉树</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">求二叉树的深度方式有两种，递归以及非递归。(出自</span><strong style="font-size: 14px; color: rgb(0, 0, 0);">剑指offer</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">)</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">①递归实现：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> /** </div> <div class="ql-code-block"> * public class TreeNode { </div> <div class="ql-code-block"> * int val = 0; </div> <div class="ql-code-block"> * TreeNode left = null; </div> <div class="ql-code-block"> * TreeNode right = null; </div> <div class="ql-code-block"> * public TreeNode(int val) { </div> <div class="ql-code-block"> * this.val = val; </div> <div class="ql-code-block"> * } </div> <div class="ql-code-block"> * } */ </div> <div class="ql-code-block"> public class Solution { </div> <div class="ql-code-block"> public int TreeDepth(TreeNode root) { </div> <div class="ql-code-block"> if(root==null) return 0; </div> <div class="ql-code-block"> int left = TreeDepth(root.left); </div> <div class="ql-code-block"> int right = TreeDepth(root.right); </div> <div class="ql-code-block"> return (left>right)?(left+1):(right+1); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">②非递归实现：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">利用层次遍历的算法，将每一层的所有节点放入队列中，在将每一层节点的左右子节点存入放入到队列中，用一个变量记录树的高度即可。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> import java.util.*; </div> <div class="ql-code-block"> public class Solution { </div> <div class="ql-code-block"> public int TreeDepth(TreeNode root) { </div> <div class="ql-code-block"> if(root==null) </div> <div class="ql-code-block"> return 0; </div> <div class="ql-code-block"> Queue<TreeNode> result = new LinkedList<>(); </div> <div class="ql-code-block"> result.add(root); </div> <div class="ql-code-block"> int height = 0; </div> <div class="ql-code-block"> while(!result.isEmpty()){ </div> <div class="ql-code-block"> //获取当前的根节点 </div> <div class="ql-code-block"> int size = result.size(); </div> <div class="ql-code-block"> while(size>0){ </div> <div class="ql-code-block"> //遍历当前层，将该层的子节点都加入队列中 </div> <div class="ql-code-block"> TreeNode nowroot = result.poll(); </div> <div class="ql-code-block"> if(nowroot.left!=null) </div> <div class="ql-code-block"> result.add(nowroot.left); </div> <div class="ql-code-block"> if(nowroot.right!=null) </div> <div class="ql-code-block"> result.add(nowroot.right); </div> <div class="ql-code-block"> size = size-1;// </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> height += 1; </div> <div class="ql-code-block"> //高度加1 </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return height; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">二叉树任意两个节点之间路径的最大长度</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：树</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> int maxDist(Tree root) { </div> <div class="ql-code-block"> //如果树是空的，则返回0 </div> <div class="ql-code-block"> if(root == NULL) </div> <div class="ql-code-block"> return 0; </div> <div class="ql-code-block"> if(root->left != NULL) { </div> <div class="ql-code-block"> root->lm = maxDist(root->left) +1; </div> <div class="ql-code-block"> } if(root->right != NULL) </div> <div class="ql-code-block"> root->rm = maxDist(root->right) +1; </div> <div class="ql-code-block"> //如果以该节点为根的子树中有最大的距离，那就更新最大距离 </div> <div class="ql-code-block"> int sum = root->rm + root->lm; </div> <div class="ql-code-block"> if(sum > max) { </div> <div class="ql-code-block"> max = sum; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return root->rm > root->lm ?root->rm : root->lm; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：二叉树</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public List<List<Integer>> levelOrder(TreeNode root) { </div> <div class="ql-code-block"> // 存最终结果 </div> <div class="ql-code-block"> List<List<Integer>> result = new ArrayList<List<Integer>>(); </div> <div class="ql-code-block"> // 队列 </div> <div class="ql-code-block"> Queue<TreeNode> queue = new LinkedList<TreeNode>(); </div> <div class="ql-code-block"> if (root == null) { </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> queue.offer(root); </div> <div class="ql-code-block"> // 层次遍历 </div> <div class="ql-code-block"> while (queue.size() != 0) { </div> <div class="ql-code-block"> List<Integer> temp = new ArrayList<Integer>(); </div> <div class="ql-code-block"> int size = queue.size(); </div> <div class="ql-code-block"> for (int i = 0; i < size; i++) { </div> <div class="ql-code-block"> TreeNode temp = queue.poll(); </div> <div class="ql-code-block"> temp.add(temp.val); </div> <div class="ql-code-block"> // 左右子树是否为空 </div> <div class="ql-code-block"> if (temp.left != null) { </div> <div class="ql-code-block"> queue.offer(temp.left); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> if (temp.right != null) { </div> <div class="ql-code-block"> queue.offer(temp.right); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> result.add(temp); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">怎么求一个二叉树的深度?手撕代码?</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：二叉树</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">类似上面求二叉树的深度的题，这里给出递归的方式。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public class Solution { </div> <div class="ql-code-block"> public int TreeDepth(TreeNode root) { </div> <div class="ql-code-block"> if(root==null) </div> <div class="ql-code-block"> return 0; </div> <div class="ql-code-block"> int left = TreeDepth(root.left); </div> <div class="ql-code-block"> int right = TreeDepth(root.right); </div> <div class="ql-code-block"> return (left>right)?(left+1):(right+1); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">请你说一下，B+树和B-树？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：树</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确</span></li> </ol> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.3遍历</span></h1> <h2><span style="color: rgb(0, 0, 0);">二叉树 Z 字型遍历</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：遍历</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> import java.util.*; </div> <div class="ql-code-block"> public class Solution { </div> <div class="ql-code-block"> public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { </div> <div class="ql-code-block"> ArrayList<ArrayList<Integer>> result = new ArrayList<>(); </div> <div class="ql-code-block"> Queue<TreeNode> queue = new LinkedList<TreeNode>(); </div> <div class="ql-code-block"> //标记奇偶层 开始为0层 从左->右遍历 </div> <div class="ql-code-block"> boolean flag = true; </div> <div class="ql-code-block"> if (pRoot == null) { </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> queue.add(pRoot); </div> <div class="ql-code-block"> while (queue.size() != 0) { </div> <div class="ql-code-block"> flag = !flag; </div> <div class="ql-code-block"> int size = queue.size(); </div> <div class="ql-code-block"> ArrayList<Integer> temp = new ArrayList<Integer>(); </div> <div class="ql-code-block"> for (int i = 0; i < size; i++) { </div> <div class="ql-code-block"> TreeNode curroot = queue.poll(); </div> <div class="ql-code-block"> temp.add(curroot.val); </div> <div class="ql-code-block"> if (curroot.left != null) </div> <div class="ql-code-block"> queue.add(curroot.left); </div> <div class="ql-code-block"> if (curroot.right != null) </div> <div class="ql-code-block"> queue.add(curroot.right); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 反转 </div> <div class="ql-code-block"> if (flag) { </div> <div class="ql-code-block"> Collections.reverse(temp); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> result.add(temp); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">编程题：写一个函数，找到一个文件夹下所有文件，包括子文件夹</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：遍历</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> import java.io.File; </div> <div class="ql-code-block"> public class Counter2 { </div> <div class="ql-code-block"> public static void main(String[] args) { </div> <div class="ql-code-block"> //取得目标目录 </div> <div class="ql-code-block"> File file = new File("D:"); </div> <div class="ql-code-block"> //获取目录下子文件及子文件夹 </div> <div class="ql-code-block"> File[] files = file.listFiles(); </div> <div class="ql-code-block"> readfile(files); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> public static void readfile(File[] files) { </div> <div class="ql-code-block"> if(files == null) {// 如果目录为空，直接退出 </div> <div class="ql-code-block"> return; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> for(File f:files) { </div> <div class="ql-code-block"> //如果是文件，直接输出名字 </div> <div class="ql-code-block"> if(f.isFile()) { </div> <div class="ql-code-block"> System.out.println(f.getName()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> //如果是文件夹，递归调用 </div> <div class="ql-code-block"> else if(f.isDirectory()) { </div> <div class="ql-code-block"> readfile(f.listFiles()); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.4链表</span></h1> <h2><span style="color: rgb(0, 0, 0);">现在有一个单向链表，谈一谈，如何判断链表中是否出现了环</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：链表</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">解法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">谈一谈，bucket如果用链表存储，它的缺点是什么？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：链表</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">①查找速度慢，因为查找时，需要循环链表访问</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">②如果进行频繁插入和删除操作，会导致速度很慢。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">有一个链表，奇数位升序偶数位降序，如何将链表变成升序</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：链表</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">思路：将链表按照奇偶数位分成两个链表head1和head2，如1->6->3->4->5->2，得到1->3->5和6->4->2两个链表，将6->4->2反转得到2->4->6，在将两个链表合并。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public class OddIncreaseEvenDecrease { </div> <div class="ql-code-block"> /** </div> <div class="ql-code-block"> * 按照奇偶位拆分成两个链表 </div> <div class="ql-code-block"> * @param head </div> <div class="ql-code-block"> * @return </div> <div class="ql-code-block"> */ </div> <div class="ql-code-block"> // 例子 1 6 3 4 5 2 变成 1 2 3 4 5 6 </div> <div class="ql-code-block"> public static Node[] getLists(Node head){ </div> <div class="ql-code-block"> Node head1 = null; </div> <div class="ql-code-block"> Node head2 = null; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> Node cur1 = null; </div> <div class="ql-code-block"> Node cur2 = null; </div> <div class="ql-code-block"> int count = 1;//用来计数 </div> <div class="ql-code-block"> while(head != null){ </div> <div class="ql-code-block"> // 遇到1 3 5 </div> <div class="ql-code-block"> if(count % 2 == 1){ </div> <div class="ql-code-block"> if(cur1 != null){ </div> <div class="ql-code-block"> cur1.next = head; </div> <div class="ql-code-block"> cur1 = cur1.next; </div> <div class="ql-code-block"> }else{ </div> <div class="ql-code-block"> cur1 = head; </div> <div class="ql-code-block"> head1 = cur1; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> }else{ </div> <div class="ql-code-block"> if(cur2 != null){ </div> <div class="ql-code-block"> cur2.next = head; </div> <div class="ql-code-block"> cur2 = cur2.next; </div> <div class="ql-code-block"> }else{ </div> <div class="ql-code-block"> cur2 = head; </div> <div class="ql-code-block"> head2 = cur2; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> head = head.next; </div> <div class="ql-code-block"> count++; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> //跳出循环，要让最后两个末尾元素的下一个都指向null </div> <div class="ql-code-block"> cur1.next = null; </div> <div class="ql-code-block"> cur2.next = null; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> Node[] nodes = new Node[]{head1,head2}; </div> <div class="ql-code-block"> return nodes; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> /** </div> <div class="ql-code-block"> * 反转链表 </div> <div class="ql-code-block"> * @param head </div> <div class="ql-code-block"> * @return </div> <div class="ql-code-block"> */ </div> <div class="ql-code-block"> public static Node reverseList(Node head){ </div> <div class="ql-code-block"> Node pre = null; </div> <div class="ql-code-block"> Node next = null; </div> <div class="ql-code-block"> while(head != null){ </div> <div class="ql-code-block"> next = head.next; </div> <div class="ql-code-block"> head.next = pre; </div> <div class="ql-code-block"> pre = head; </div> <div class="ql-code-block"> head = next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return pre; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> /** </div> <div class="ql-code-block"> * 合并两个有序链表 </div> <div class="ql-code-block"> * @param head1 </div> <div class="ql-code-block"> * @param head2 </div> <div class="ql-code-block"> * @return </div> <div class="ql-code-block"> */ </div> <div class="ql-code-block"> public static Node CombineList(Node head1,Node head2){ </div> <div class="ql-code-block"> if(head1 == null || head2 == null){ </div> <div class="ql-code-block"> return head1 != null ? head1 :head2; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> Node head = head1.value < head2.value ?head1 : head2; </div> <div class="ql-code-block"> Node cur1 = head == head1 ? head1 :head2; </div> <div class="ql-code-block"> Node cur2 = head == head1 ? head2 :head1; </div> <div class="ql-code-block"> Node pre = null; </div> <div class="ql-code-block"> Node next = null; </div> <div class="ql-code-block"> while(cur1 != null && cur2 !=null){ </div> <div class="ql-code-block"> if(cur1.value <= cur2.value){//这里一定要有=，否则一旦cur1的value和cur2的value相等的话，下面的pre.next会出现空指针异常 </div> <div class="ql-code-block"> pre = cur1; </div> <div class="ql-code-block"> cur1 = cur1.next; </div> <div class="ql-code-block"> }else{ </div> <div class="ql-code-block"> next = cur2.next; </div> <div class="ql-code-block"> pre.next = cur2; </div> <div class="ql-code-block"> cur2.next = cur1; </div> <div class="ql-code-block"> pre = cur2; </div> <div class="ql-code-block"> cur2 = next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> pre.next = cur1 == null ? cur2 : cur1; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> return head; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">随机链表的复制</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：链表</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public RandomListNode copyRandomList(RandomListNode head) { </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> if (head == null) </div> <div class="ql-code-block"> return null; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> RandomListNode p = head; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> // copy every node and insert to list </div> <div class="ql-code-block"> while (p != null) { </div> <div class="ql-code-block"> RandomListNode copy = new RandomListNode(p.label); </div> <div class="ql-code-block"> copy.next = p.next; </div> <div class="ql-code-block"> p.next = copy; </div> <div class="ql-code-block"> p = copy.next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> // copy random pointer for each new node </div> <div class="ql-code-block"> p = head; </div> <div class="ql-code-block"> while (p != null) { </div> <div class="ql-code-block"> if (p.random != null) </div> <div class="ql-code-block"> p.next.random = p.random.next; </div> <div class="ql-code-block"> p = p.next.next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> // break list to two </div> <div class="ql-code-block"> p = head; </div> <div class="ql-code-block"> RandomListNode newHead = head.next; </div> <div class="ql-code-block"> while (p != null) { </div> <div class="ql-code-block"> RandomListNode temp = p.next; </div> <div class="ql-code-block"> p.next = temp.next; </div> <div class="ql-code-block"> if (temp.next != null) </div> <div class="ql-code-block"> temp.next = temp.next.next; </div> <div class="ql-code-block"> p = p.next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> return newHead; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">如何反转单链表</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：链表</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public static Node reverseList(ListNode head){ </div> <div class="ql-code-block"> ListNode pre = null; </div> <div class="ql-code-block"> ListNode next = null; </div> <div class="ql-code-block"> while(head != null){ </div> <div class="ql-code-block"> next = head.next; </div> <div class="ql-code-block"> head.next = pre; </div> <div class="ql-code-block"> pre = head; </div> <div class="ql-code-block"> head = next; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return pre; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.5 数组</span></h1> <h2><span style="color: rgb(0, 0, 0);">写一个算法，可以将一个二维数组顺时针旋转90度，说一下思路。</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：数组</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public void rotate(int[][] matrix) { </div> <div class="ql-code-block"> int n = matrix.length; </div> <div class="ql-code-block"> for (int i = 0; i < n/2; i++) { </div> <div class="ql-code-block"> for (int j = i; j < n-1-i; j++) </div> <div class="ql-code-block"> { </div> <div class="ql-code-block"> int temp = matrix[i][j]; </div> <div class="ql-code-block"> matrix[i][j] = matrix[n-1-j][i]; </div> <div class="ql-code-block"> matrix[n-1-j][i] = matrix[n-1-i][n-1-j]; </div> <div class="ql-code-block"> matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; </div> <div class="ql-code-block"> matrix[j][n-1-i] = temp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">一个数组，除一个元素外其它都是两两相等，求那个元素?</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：数组</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">解法：位运算，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。</span></p> <p></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public static int find1From2(int[] a){ </div> <div class="ql-code-block"> int len = a.length, result = 0; </div> <div class="ql-code-block"> for(int i = 0; i < len; i++){ </div> <div class="ql-code-block"> result = result ^ a[i]; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return result; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">找出数组中和为S的一对组合，找出一组就行</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：数组</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">解法：两数之和经典题，找到一组即可返回，使用HashMap即可。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public int[] twoSum(int[] nums, int target) { </div> <div class="ql-code-block"> HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); </div> <div class="ql-code-block"> int[] a = new int[2]; </div> <div class="ql-code-block"> map.put(nums[0], 0); </div> <div class="ql-code-block"> for (int i = 1; i < nums.length;i++) { </div> <div class="ql-code-block"> if (map.containsKey(target - nums[i])) { </div> <div class="ql-code-block"> a[0] = map.get(target - nums[i]); </div> <div class="ql-code-block"> a[1] = i; </div> <div class="ql-code-block"> return a; </div> <div class="ql-code-block"> } else { </div> <div class="ql-code-block"> map.put(nums[i], i); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return a; </div> <div class="ql-code-block"> } </div> </div> <p><span style="color: rgb(0, 0, 0);">一个数组中连续子向量的最大和</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：数组</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public int maxSubArray(int[] nums) { </div> <div class="ql-code-block"> int sum = 0; </div> <div class="ql-code-block"> int maxSum = Integer.MIN_VALUE; </div> <div class="ql-code-block"> if (nums == null || nums.length == 0) { </div> <div class="ql-code-block"> return sum; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> for (int i = 0; i < nums.length;i++) { </div> <div class="ql-code-block"> sum += nums[i]; </div> <div class="ql-code-block"> maxSum = Math.max(maxSum, sum); </div> <div class="ql-code-block"> if (sum < 0) { </div> <div class="ql-code-block"> sum = 0; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return maxSum; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">寻找一数组中前K个最大的数</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：数组</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">解法：考场排序，可以用堆排序，也可以用快排，面试的时候看面试官怎么要求。这里给出快排的解法，自己也可以尝试其他的方法。</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public int findKthLargest(int[] nums, int k) { </div> <div class="ql-code-block"> if (k < 1 || nums == null) { </div> <div class="ql-code-block"> return 0; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return getKth(nums.length - k +1, nums, 0,nums.length - 1); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 快排模板 </div> <div class="ql-code-block"> public int getKth(int k, int[] nums, int start, int end) { </div> <div class="ql-code-block"> int pivot = nums[end]; </div> <div class="ql-code-block"> int left = start; </div> <div class="ql-code-block"> int right = end; </div> <div class="ql-code-block"> while (true) { </div> <div class="ql-code-block"> while(nums[left] < pivot && left < right) { </div> <div class="ql-code-block"> left++; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> while(nums[right] >= pivot && right > left) { </div> <div class="ql-code-block"> right--; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> if(left == right) { </div> <div class="ql-code-block"> break; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> swap(nums,left, right); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> swap(nums, left, end); </div> <div class="ql-code-block"> if (k == left + 1) { </div> <div class="ql-code-block"> return pivot; </div> <div class="ql-code-block"> } else if (k < left + 1) { </div> <div class="ql-code-block"> return getKth(k, nums, start, left - 1); </div> <div class="ql-code-block"> } else { </div> <div class="ql-code-block"> return getKth(k, nums, left + 1, end); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // 交换元素值 </div> <div class="ql-code-block"> public void swap(int[] nums, int n1, int n2) { </div> <div class="ql-code-block"> int tmp = nums[n1]; </div> <div class="ql-code-block"> nums[n1] = nums[n2]; </div> <div class="ql-code-block"> nums[n2] = tmp; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.6排序</span></h1> <h2><span style="color: rgb(0, 0, 0);">用java写一个冒泡排序？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：冒泡排序</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public static void main(String[] args) { </div> <div class="ql-code-block"> int[] result = {2,4,1,3,6,5}; </div> <div class="ql-code-block"> int temp; </div> <div class="ql-code-block"> System.out.println("----冒泡排序前顺序----"); </div> <div class="ql-code-block"> for (int i : result) { </div> <div class="ql-code-block"> System.out.print(i); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> for(int i=0;i<result.length-1;i++){ </div> <div class="ql-code-block"> for(int j = 0;j<result.length-1-i;j++){ </div> <div class="ql-code-block"> if(result[j+1]<result[j]){ </div> <div class="ql-code-block"> //后一个比前一个小 </div> <div class="ql-code-block"> temp = result[j]; </div> <div class="ql-code-block"> result[j] = result[j+1]; </div> <div class="ql-code-block"> result[j+1] = temp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> System.out.println(); </div> <div class="ql-code-block"> System.out.println("----冒泡排序后结果----"); </div> <div class="ql-code-block"> for (int i : result) { </div> <div class="ql-code-block"> System.out.print(i); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">介绍一下，排序都有哪几种方法？请列举出来。</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：排序</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">排序的方法有：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">插入排序（简单插入排序、希尔排序）</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">交换排序（冒泡排序、快速排序）</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">选择排序（简单选择排序、堆排序）</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">归并排序</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">分配排序（箱排序、基数排序）</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">绍一下，归并排序的原理是什么？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：归并排序</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（1）归并排序是建立在归并操作上的一种有效的排序</span><a href="http://lib.csdn.net/base/datastructure" target="_blank">算法</a><span style="font-size: 14px; color: rgb(0, 0, 0);">。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（2）首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（3）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">介绍一下，堆排序的原理是什么？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：堆排序</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">堆排序分大顶堆和小顶堆，这里以大顶堆为例讲解。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算</span></p> <p></p> <p class="image-uploading"><span><img src="https://pic.code-nav.cn/planet_post_image/1609216259264610306/7d0jlhr8.jpeg"></span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">谈一谈，如何得到一个数据流中的中位数？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：排序</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：快排</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">参考回答：</span></p> <p></p> <p class="image-uploading"><span><img src="https://pic.code-nav.cn/planet_post_image/1609216259264610306/t8b7awwr.jpeg"></span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">快排：快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">而右边的j下标一直往左走（当a[j] > a[center_index]时）。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。</span></p> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.7 堆与栈</span></h1> <h2><span style="color: rgb(0, 0, 0);">请你解释一下，内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法。</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：堆栈</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">堆区:</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">专门用来保存对象的实例(new 创建的对象和数组)，实际上也只是保存对象实例的属性值，属性的类型和对象本身的类型标记等，并不保存对象的方法（方法是指令，保存在Stack中）</span></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">存储的全部是对象，每个对象都包含一个与之对应的class的信息。(class的目的是得到操作指令)</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">jvm只有一个堆区(heap)被所有线程共享，堆中不存放基本类型和对象引用，只存放对象本身.</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。</span></li> </ol> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">栈区:</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">对象实例在Heap 中分配好以后，需要在Stack中保存一个4字节的Heap内存地址，用来定位该对象实例在Heap 中的位置，便于找到该对象实例。</span></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">每个线程包含一个栈区，栈中只保存基础数据类型的对象和自定义对象的引用(不是对象)，对象都存放在堆区</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">每个栈中的数据(原始类型和对象引用)都是私有的，其他栈不能访问。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">栈分为3个部分：基本类型变量区、执行环境上下文、操作指令区(存放操作指令)。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">由编译器自动分配释放 ，存放函数的参数值，局部变量的值等．</span></li> </ol> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">静态区/方法区:</strong></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">方法区又叫静态区，跟堆一样，被所有的线程共享。方法区包含所有的class和</span><a href="https://so.csdn.net/so/search?q=static&spm=1001.2101.3001.7020" target="_blank">static</a><span style="font-size: 14px; color: rgb(0, 0, 0);">变量。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">方法区中包含的都是在整个程序中永远唯一的元素，如class，static变量。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域</span></li> </ol> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">说一说，heap和stack有什么区别。</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：堆与栈</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">1.heap是堆，stack是栈。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">2.stack的空间由操作系统自动分配和释放，heap的空间是手动申请和释放的，heap常用new关键字来分配。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">3.stack空间有限，heap的空间是很大的自由区。在Java中，若只是声明一个对象，则先在栈内存中为其分配地址空间，若再new一下，实例化它，则在堆内存中为其分配地址。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">4.举例：数据类型 变量名；这样定义的东西在栈区。如：Object a =null; 只在栈内存中分配空间new 数据类型();或者malloc(长度); 这样定义的东西就在堆区如：Object b =new Object(); 则在堆内存中分配空间</span></li> </ol> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">介绍一下，堆与栈的不同是什么？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：堆，栈</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（1）Java的堆是一个运行时数据区，类的对象从中分配空间。通过比如：new等指令建立，不需要代码显式的释放，由垃圾回收来负责。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">优点：可以动态地分配内存大小，垃圾收集器会自动回收垃圾数据。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">缺点：由于其优点，所以存取速度较慢。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">（2）栈：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">其数据项的插入和删除都只能在称为栈顶的一端完成，后进先出。栈中存放一些基本类型的 变量 和 对象句柄。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">优点：读取数度比堆要快，仅次于寄存器，栈数据可以共享。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">缺点：比堆缺乏灵活性，存在栈中的数据大小与生存期必须是确定的。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">举例：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">String是一个特殊的包装类数据。可以用：</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">String str = new String("csdn");</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">String str = "csdn";</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">两种的形式来创建，第一种是用new()来新建对象的，它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str，然后查找栈中有没有存放"csdn"，如果没有，则将"csdn"存放进栈，并令str指向”abc”，如果已经有”csdn” 则直接令str指向“csdn”。</span></p> <p><br></p> <h1><span style="color: rgb(51, 51, 51);">9.8队列</span></h1> <h2><span style="color: rgb(51, 51, 51);">什么是Java优先级队列(Priority Queue)？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(51, 51, 51);">考察点：队列</span></p> <p><br></p> <h3><span style="color: rgb(51, 51, 51);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(51, 51, 51);">PriorityQueue是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。</span></p> <p><br></p> <h1><span style="color: rgb(0, 0, 0);">9.9 高级算法</span></h1> <h2><span style="color: rgb(0, 0, 0);">请你讲讲LRU算法的实现原理？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：LRU算法</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">注意</strong><span style="font-size: 14px; color: rgb(0, 0, 0);">：面试可能会让手写LRU算法！</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">①LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，为虚拟页式存储管理服务。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">②达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到 。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">LRU主要的两个函数 </span><strong style="font-size: 14px; color: rgb(0, 0, 0);">获取数据 get</strong><span style="font-size: 14px; color: rgb(0, 0, 0);"> 和 </span><strong style="font-size: 14px; color: rgb(0, 0, 0);">写入数据 put</strong><span style="font-size: 14px; color: rgb(0, 0, 0);"> 。</span></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。</span></li> </ol> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">算法实现的关键</strong></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">命中率：当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">复杂度：实现起来较为简单。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">存储成本：几乎没有空间上浪费。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">代价：命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。</span></li> </ol> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">为什么要设计后缀表达式，有什么好处？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：逆波兰表达式</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">后缀表达式又叫逆波兰表达式，逆波兰记法不需要括号来标识操作符的优先级。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">请你设计一个算法，用来压缩一段URL？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：MD5加密算法</span></p> <p><br></p> <h3><span style="color: rgb(0, 0, 0);">参考回答：</span></h3> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">该算法主要使用MD5 算法对原始链接进行加密（这里使用的MD5 加密后的字符串长度为32 位），然后对加密后的字符串进行处理以得到短链接的地址。</span></p> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">谈一谈，id全局唯一且自增，如何实现？</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：SnowFlake雪花算法</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">参考回答；</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">SnowFlake雪花算法</span></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：</span></p> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">snowflake id生成规则</strong></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号</span></li> </ol> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">优点</strong></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">简单高效，生成速度快。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求。</span></li> </ol> <p><strong style="font-size: 14px; color: rgb(0, 0, 0);">缺点</strong></p> <ol> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。</span></li> <li data-list="bullet"><span class="ql-ui"></span><span style="font-size: 14px; color: rgb(0, 0, 0);">在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况。</span></li> </ol> <p><br></p> <h2><span style="color: rgb(0, 0, 0);">Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted. Could you do both operations in O(1) time complexity?</span></h2> <p><br></p> <p><span style="font-size: 14px; color: rgb(0, 0, 0);">考察点：LFU Cache</span></p> <div class="ql-code-block-container"> <div class="ql-code-block"> public class LFUCache { </div> <div class="ql-code-block"> private class Node{ </div> <div class="ql-code-block"> int value; </div> <div class="ql-code-block"> ArrayList<Integer> set; </div> <div class="ql-code-block"> Node prev; </div> <div class="ql-code-block"> Node next; </div> <div class="ql-code-block"> public Node (int value ){ </div> <div class="ql-code-block"> this.value = value; </div> <div class="ql-code-block"> this.set = new ArrayList<Integer> (); </div> <div class="ql-code-block"> this.prev = null; </div> <div class="ql-code-block"> this.next = null; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> private class item{ </div> <div class="ql-code-block"> int key; </div> <div class="ql-code-block"> int value; </div> <div class="ql-code-block"> Node parent ; </div> <div class="ql-code-block"> public item(int key ,int value, Node parent){ </div> <div class="ql-code-block"> this.key = key ; </div> <div class="ql-code-block"> this.value = value; </div> <div class="ql-code-block"> this.parent = parent; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> private HashMap<Integer, item> map; </div> <div class="ql-code-block"> private Node head,tail; </div> <div class="ql-code-block"> private int capacity; </div> <div class="ql-code-block"> // @param capacity, an integer </div> <div class="ql-code-block"> public LFUCache(int capacity) { </div> <div class="ql-code-block"> // Write your code here </div> <div class="ql-code-block"> this.capacity = capacity; </div> <div class="ql-code-block"> this.map = new HashMap <Integer,item> (); </div> <div class="ql-code-block"> this.head = new Node (0); </div> <div class="ql-code-block"> this.tail = new Node(Integer.MAX_VALUE); </div> <div class="ql-code-block"> head.next = tail; </div> <div class="ql-code-block"> tail.prev = head; </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> // @param key, an integer </div> <div class="ql-code-block"> // @param value, an integer </div> <div class="ql-code-block"> // @return nothing </div> <div class="ql-code-block"> public void set(int key, int value) { </div> <div class="ql-code-block"> // Write your code here </div> <div class="ql-code-block"> if (get(key) != -1 ) { </div> <div class="ql-code-block"> map.get(key).value = value; </div> <div class="ql-code-block"> return ; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> if (map.size() == capacity ){ </div> <div class="ql-code-block"> getLFUitem(); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><br> </div> <div class="ql-code-block"> Node newpar = head.next; </div> <div class="ql-code-block"> if ( newpar.value != 1){ </div> <div class="ql-code-block"> newpar = getNewNode(1,head,newpar); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> item curitem = new item(key,value,newpar); </div> <div class="ql-code-block"> map.put(key,curitem); </div> <div class="ql-code-block"> newpar.set.add(key); </div> <div class="ql-code-block"> return; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> public int get(int key) { </div> <div class="ql-code-block"> // Write your code here </div> <div class="ql-code-block"> if (!map.containsKey(key)){ </div> <div class="ql-code-block"> return -1; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> item cur = map.get(key); </div> <div class="ql-code-block"> Node curpar = cur.parent; </div> <div class="ql-code-block"> if (curpar.next.value == curpar.value + 1){ </div> <div class="ql-code-block"> cur.parent= curpar.next; </div> <div class="ql-code-block"> cur.parent.set.add(key); </div> <div class="ql-code-block"> }else{ </div> <div class="ql-code-block"> Node newpar =getNewNode(curpar.value + 1,curpar,curpar.next); </div> <div class="ql-code-block"> cur.parent = newpar; </div> <div class="ql-code-block"> newpar.set.add(key); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> curpar.set.remove(new Integer(key)); </div> <div class="ql-code-block"> if(curpar.set.isEmpty()){ </div> <div class="ql-code-block"> deleteNode(curpar); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return cur.value; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> private Node getNewNode (int value ,Node prev , Node next){ </div> <div class="ql-code-block"> Node temp = new Node(value); </div> <div class="ql-code-block"> temp.prev = prev; </div> <div class="ql-code-block"> temp.next = next; </div> <div class="ql-code-block"> prev.next = temp; </div> <div class="ql-code-block"> next.prev = temp; </div> <div class="ql-code-block"> return temp; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> private void deleteNode(Node temp){ </div> <div class="ql-code-block"> temp.prev.next = temp.next; </div> <div class="ql-code-block"> temp.next.prev = temp.prev; </div> <div class="ql-code-block"> return ; </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> private void getLFUitem(){ </div> <div class="ql-code-block"> Node temp = head.next; </div> <div class="ql-code-block"> int LFUkey = temp.set.get(0); </div> <div class="ql-code-block"> temp.set.remove(0); </div> <div class="ql-code-block"> map.remove(LFUkey); </div> <div class="ql-code-block"> if (temp.set.isEmpty()){ </div> <div class="ql-code-block"> deleteNode(temp); </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> return; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> </div> </body> </html>
恋上数据结构与算法（第一季）
地址：https://www.bilibili.com/video/BV1yP4y147zw/?spm_id_from=333.999.0.0&vd_source=0442dd11570b238bbab53111cb209e9a
《数据结构与算法（Java版）》
地址：https://www.aliyundrive.com/s/C7FqTcAvN3h