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

. . . . . .

区间内第K大元素查询（基于快速选择算法的变种）

**区间内第K大元素查询（基于快速选择算法的变种）** **题目描述** 给定一个整数数组和多个查询，每个查询包含三个参数：区间左边界L、区间右边界R和整数K。要求返回每个查询区间[L,R]内第K大的元素值。注意是第K大（从大到小排序后的第K个），而不是第K小。 **解题过程** 1. **问题分析** - 直接思路：对每个查询区间内的子数组排序，然后取第K个元素。时间复杂度为O(Q * n log n)，其中Q是查询次数，n是数组长度。当Q或n较大时效率很低。 - 核心挑战：

2025-10-26 14:24:19

奇偶排序（Odd-Even Sort）

**奇偶排序（Odd-Even Sort）** **题目描述** 给定一个整数数组，使用奇偶排序算法将其按升序排列。奇偶排序是一种基于冒泡排序的并行排序算法，通过多轮操作完成排序：在每一轮中，分别对数组中奇数索引对（第1个与第2个、第3个与第4个…）和偶数索引对（第0个与第1个、第2个与第3个…）进行比较和交换，直到整个数组有序。 --- **解题过程** **1. 算法核心思想** - 奇偶排序将排序过程分为两个重复执行的阶段： - **奇数阶段**：比较所

2025-10-26 14:19:07

戳气球问题（基础版本）

**戳气球问题（基础版本）** **题目描述** 给定一个长度为 n 的整数数组 nums，表示一排气球，每个气球上的数字。当你戳破一个气球 i 时，你可以获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币（假设超出边界的数字为 1）。戳破后，气球 i 消失，左右气球相邻。求戳破所有气球能获得的最大硬币数。 **解题思路** 1. **问题分析**：若按顺序戳气球，每一步的得分依赖当前剩余气球的相邻关系，决策顺序会影响后续得分。直接枚举戳气球的顺序（n! 种

2025-10-26 14:13:50

自适应辛普森积分法的误差控制与递归实现

**自适应辛普森积分法的误差控制与递归实现** **题目描述** 自适应辛普森积分法是一种通过递归细分区间并自动控制误差的数值积分方法。给定函数 \( f(x) \) 在区间 \([a, b]\) 上的积分 \( I = \int_a^b f(x) \, dx \)，要求以指定精度 \( \epsilon \) 近似计算其值。核心思想是：若当前区间用辛普森公式的近似结果与左右子区间辛普森公式之和的差值超过误差容限，则递归细分区间。 --- **解题过程** 1. **辛普森公式回

2025-10-26 14:08:37

非线性规划中的修正牛顿法基础题

**非线性规划中的修正牛顿法基础题** **题目描述** 考虑非线性规划问题：最小化 \( f(x) = x_1^4 + 2x_2^4 + x_1^2 x_2^2 - 5x_1 \) 初始点 \( x^{(0)} = [1, 1]^T \)，使用**修正牛顿法**求解该问题。要求说明修正牛顿法与标准牛顿法的区别，并详细展示迭代过程。 --- **解题过程** ### 1. 修正牛顿法的核心思想标准牛顿法直接使用目标函数的Hessian矩阵（二阶导数矩阵）的逆来更新迭代

2025-10-26 14:03:18

LeetCode 51. N 皇后

**LeetCode 51. N 皇后** **题目描述** 在一个 N×N 的棋盘上放置 N 个皇后，要求它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。给定整数 N，返回所有不同的解决方案（用棋盘布局表示）。 --- **解题过程** ### 1. 问题分析 - **关键约束**： 1. 每行只能放一个皇后（因为 N 个皇后放在 N 行，每行必有一个）。 2. 每列只能放一个皇后。 3. 每条对角线（主对角线和副对角线）上

2025-10-26 13:57:53

GMRES算法解非对称线性方程组

**GMRES算法解非对称线性方程组** **题目描述** 给定一个大型稀疏非对称线性方程组 Ax = b，其中 A 是 n×n 的非对称矩阵，b 是 n 维向量。请使用广义最小残量（GMRES）算法求解未知向量 x。该算法特别适用于系数矩阵 A 非对称且可能非正定的情况。 **解题过程** GMRES 算法的核心思想是在一个不断扩大的 Krylov 子空间中，寻找一个向量，使得其对应的残差范数最小。这个过程可以循序渐进地理解。 **第一步：问题转化与核心思想** 1. **初始猜测

2025-10-26 13:52:29

非线性规划中的序列线性规划法基础题

**非线性规划中的序列线性规划法基础题** **题目描述** 考虑非线性规划问题：最小化 \( f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2 \) 满足约束： \( g_1(x) = x_1^2 - x_2 \leq 0 \) \( g_2(x) = x_1^2 + x_2^2 - 2 \leq 0 \) 初始点 \( x^{(0)} = (0, 1)^T \)，采用序列线性规划法求解该问题。 **解题过程** 序列线性规划法的核心思想是将非线性规划问题在迭代点

2025-10-26 13:46:58

哈希算法题目：两数之和 III - 数据结构设计

**哈希算法题目：两数之和 III - 数据结构设计** **题目描述** 设计一个数据结构 `TwoSum`，支持以下两种操作： 1. `add(number)`：向数据结构添加一个数 `number`。 2. `find(value)`：检查是否存在任意一对数字，其和等于 `value`。若存在返回 `true`，否则返回 `false`。注意： - 添加的数可能包含重复值（例如多次添加同一个数）。 - 在 `find` 操作中，需要确保找到的两个数可以是同一个数（但必须是添加

2025-10-26 13:36:14

非线性规划中的分支定界法基础题

**非线性规划中的分支定界法基础题** **题目描述** 考虑非线性规划问题： \[ \min f(x) = (x_1 - 1.5)^2 + (x_2 - 0.5)^2 \] 满足约束： \[ x_1 + x_2 \leq 2, \quad x_1 - x_2 \leq 1, \quad x_1, x_2 \in \mathbb{Z} \] 要求使用分支定界法求解该整数非线性规划问题。 --- **解题过程** **1. 问题分析** - 目标函数 \( f(

2025-10-26 13:31:02

区间动态规划例题：最长湍流子数组问题

**区间动态规划例题：最长湍流子数组问题** **题目描述** 给定一个整数数组 `arr`，如果某个子数组满足相邻元素的比较符号在“大于”和“小于”之间交替出现（例如 `arr[k-1] arr[k+1]` 或 `arr[k-1] > arr[k] < arr[k+1]`），则称该子数组为“湍流子数组”。要求返回最长的湍流子数组的长度。 **示例** 输入：`arr = [9,4,2,10,7,8,8,1,9]` 输出：`5` 解释：最长的湍流

2025-10-26 13:25:39

快速选择算法（Quickselect）

**快速选择算法（Quickselect）** 题目描述：给定一个未排序的整数数组和一个整数k，设计算法找到数组中第k小的元素。要求平均时间复杂度为O(n)，最坏情况下为O(n²)，空间复杂度为O(1)。解题过程： 1. **问题分析** - 这是选择问题的一种，与排序密切相关但不需要完全排序 - 直接排序后取第k个元素需要O(n log n)时间，但我们希望更高效 - 快速选择基于快速排序的分区思想，但每次只处理包含目标的那部分 2. **算法核心思想** -

2025-10-26 13:20:15

跳转到页