爱豆文档 - 信息安全文档下载平台 - idocdown.com （部分文档，免费下载）

. . . . . .

计数逆序对（Count Inversions）的进阶应用：利用归并排序高效统计全局逆序数

**计数逆序对（Count Inversions）的进阶应用：利用归并排序高效统计全局逆序数** **题目描述** 给定一个整数数组 `nums`，统计数组中逆序对的数量。逆序对的定义为：在数组中的两个元素 `(i, j)`，如果满足 `i nums[j]`，则称 `(i, j)` 为一个逆序对。要求设计一个时间复杂度优于 O(n²) 的算法。 **解题过程** 1. **暴力法的局限性** 最直接的方法是遍历所有可能的 `(i, j)`

2025-10-26 22:54:28

哈希算法题目：最长回文串

**哈希算法题目：最长回文串** **题目描述** 给定一个包含大写字母和小写字母的字符串 s，返回可以通过这些字母构建的最长回文串的长度。需要注意的是，区分大小写，例如 "Aa" 在这里不视为相同的字符。示例：输入: s = "abccccdd" 输出: 7 解释: 最长回文串为 "dccaccd"（或 "dccbccd" 等），长度为 7。 **解题过程** 1. **理解回文串的字符构成规律** - 回文串是正读反读都相同的字符串，其字符分布具有

2025-10-26 22:43:42

寻找数组中的众数（Boyer-Moore 投票算法）

**寻找数组中的众数（Boyer-Moore 投票算法）** **题目描述** 给定一个大小为 n 的数组 nums，请找出其中出现次数超过 ⌊n/2⌋ 的元素（即众数）。假设数组非空，且众数一定存在。 **解题思路** 常规解法可能使用哈希表统计频率，但需要 O(n) 额外空间。Boyer-Moore 投票算法可以在 O(1) 空间内解决该问题。其核心思想是通过**抵消**策略：将众数视为“支持票”，其他数视为“反对票”，由于众数数量超过一半，最终剩下的候选人一定是众数。 **步

2025-10-26 22:27:54

快速排序的优化：三数取中法（Median-of-Three）

**快速排序的优化：三数取中法（Median-of-Three）** 题目描述：在标准快速排序中，如果总是选择第一个或最后一个元素作为基准（pivot），在数组已经有序或逆序时会导致最坏情况时间复杂度O(n²)。请实现使用"三数取中法"选择基准的快速排序优化版本，即从子数组的首、中、尾三个元素中选取中位数作为基准。解题过程： 1. **问题分析** - 标准快速排序的最坏情况发生在每次划分都极不平衡时 - 三数取中法通过选择更接近中位数的基准，减少最坏情况发生的概率 -

2025-10-26 22:01:21

在排序数组中查找元素的第一个和最后一个位置

**在排序数组中查找元素的第一个和最后一个位置** 题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。要求算法时间复杂度必须是 O(log n) 级别。解题过程： 1. 问题分析由于数组是排序的，我们需要高效地找到目标值的起始和结束位置。O(log n) 的时间复杂度要求提示我们使用二分查找算法。但标准的二分查找只能找到一个位置，而我们需要找到两个边界位置。

2025-10-26 21:28:30

寻找旋转排序数组中的最小值 II

**寻找旋转排序数组中的最小值 II** **题目描述** 已知一个长度为 n 的数组，预先按照升序排列，但我们在某个未知的下标 k (0 <= k < n) 上进行了旋转，使得数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。例如，数组 [0,1,4,4,5,6,7] 可能变为 [4,5,6,7,0,1,4]。重要的是，数组中可能包含重复的元素。请你找出并返回数组中的最小元素。 **解

2025-10-26 20:57:01

LeetCode 980. 不同路径 III

**LeetCode 980. 不同路径 III** **题目描述** 在二维网格 `grid` 上，有 4 种类型的方格： * `1` 表示起点方格。且只有一个起点方格。 * `2` 表示终点方格。且只有一个终点方格。 * `0` 表示我们可以走过的空方格。 * `-1` 表示我们无法跨越的障碍方格。要求：返回在网格中从起点到终点的**不同路径**的数目，其中**每一条路径应该走过每一个空方格恰好一次**。 **示例 1：** 输入：grid = [[1,0,0,0]

2025-10-26 20:51:38

睡眠排序（Sleep Sort）

**睡眠排序（Sleep Sort）** ### 题目描述给定一个非负整数数组，要求使用“睡眠排序”算法对数组进行升序排序。该算法的核心思想是为每个数字创建一个独立的线程（或计时任务），让每个线程睡眠与数字值成正比的时间，然后在线程醒来时将数字输出。最终输出的顺序即为排序结果。 --- ### 解题思路 1. **基本思想** - 每个数字启动一个异步任务（如线程或定时器），任务中设置睡眠时间为数字的值（需乘以一个缩放系数，避免过大或过小的值影响实际效果）。

2025-10-26 19:10:56

基数排序（Radix Sort）

**基数排序（Radix Sort）** 题目描述：给定一个非负整数数组，要求使用基数排序算法将其按升序排列。要求时间复杂度为O(n*k)，其中n是数组长度，k是数字的最大位数。解题过程： 1. 理解基数排序的基本思想基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行比较排序。从最低有效位（个位）开始，到最高有效位结束。 2. 算法步骤详解步骤1：找到数组中的最大值，确定需要排序的轮数（最大位数） - 遍历数组找到最大值 - 计算最大值

2025-10-26 19:00:40

循环排序（Cyclic Sort）的进阶应用：寻找缺失的第一个正数

**循环排序（Cyclic Sort）的进阶应用：寻找缺失的第一个正数** 题目描述：给定一个未排序的整数数组 nums，请找出其中没有出现的最小的正整数。要求算法的时间复杂度为 O(n)，并且只能使用常数级别的额外空间。解题过程： 1. 问题分析：我们需要找到最小的缺失正整数，这个数字一定在 1 到 n+1 的范围内（n 是数组长度）。如果数组包含了 1 到 n 的所有数字，那么缺失的就是 n+1。 2. 关键思路：使用循环排序的思想，尝试将每个正整数放到它应该在的位置上。具体来说，如

2025-10-26 18:55:28

LeetCode 773. 滑动谜题

**LeetCode 773. 滑动谜题** **题目描述** 在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空位（用 0 表示）。一次移动定义为选择 0 这个空格，将其与相邻的方块（上下左右）进行交换。给定棋盘的初始状态 `board`（一个 2x3 的二维数组），例如 `[[1,2,3],[4,0,5]]`，你的任务是计算出需要的最少移动次数，使得棋盘变为目标状态 `[[1,2,3],[4,5,0]]`。如果无法完成这个转换，则返回 -1。 **解题过程*

2025-10-26 18:39:27

LeetCode 1306. 跳跃游戏 III

**LeetCode 1306. 跳跃游戏 III** **题目描述** 这里有一个非负整数数组 `arr`，你一开始位于数组的起始下标 `start` 处。当你位于下标 `i` 时，你可以跳到 `i + arr[i]` 或者 `i - arr[i]`。请你判断自己是否能够跳到**任意**一个对应元素值为 0 的**任意**位置。注意： 1. 任何时候你都不能跳到数组之外。 2. `1 <= arr.length <= 5 * 10^4` 3. `0 <= arr[i] < arr

2025-10-26 18:28:54

跳转到页