动态规划动态规划（Dynamic Programming, 简称 DP）是计算机科学中一种重要的算法设计思想，常用于解决具有 重叠子问题 和 最优子结构 性质的问题。以下是动态规划相关的知识点总结： 动态规划的核心思想 重叠子问题 问题可以被分解为子问题，子问题之间有重复计算。 示例：斐波那契数列，F(n) = F(n-1) + F(n-2)，需要重复计算子问题。 最优子结构 一个问题的最优解可以由其子问题的最优解组合得到。 示例：最短路径问题，某个节点的最短路径由其前驱节点的最短路径加上路径长度决定。 状态转移方程 明确当前状态与之前状态之间的关系。 示例：dp[i] = dp[i-1] + dp[i-2]（斐波那契数列）。 动态规划的分类1. 按解题顺序分类 自顶向下（记忆化搜索） 通过递归实现，配合缓存避免重复计算。 示例：斐波那契数列递归实现，使用数组存储中间结果。 自底向上（迭代） 从最小子问题开始计算，逐步推导出原问题的解。 示例：斐波那契数列用循环计算。 2. 按问题类型分类 线性动态规划 问题有线性结构，例如：最长递增子序列、斐波那契数列。 ...
数据结构15-图的创建及其遍历方法(BFS+DFS)1.使用邻接矩阵表示第一种小写法: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include<iostream>using namespace std;#define max_vexs 100#define max_number 9999typedef struct Graph { char vexs[max_vexs]; int arcs[max_vexs][max_vexs]; int vexsnumber; int arcsnumber;};// 初始化的是这个有权图的顶点数目已经这个有权图的边的数目,还有这个有权图的边进行初始化Graph* InitGraph(int vexs,int arcs) { // 初始化这个有权图 Graph* G = new Graph; G->vex ...
链表23. 合并 K 个升序链表 给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode[]} lists * @return {ListNode} */var mergeKLists = function(lists) { if(!lists||lists.length===0){ return ...
SetJavaScript中的Set是一种内建的数据结构，类似于数组，但具有以下几个特点： 元素唯一性：Set中的每个元素都是唯一的，不允许重复。 顺序性：元素按插入顺序排序。 可迭代性：Set是可迭代的，可以使用for...of进行遍历。 值类型：Set只关心元素的值是否相等，而不关心其类型。 创建一个Set1let mySet = new Set(); 可以通过传入一个可迭代对象来初始化一个Set。 12let numbers = new Set([1, 2, 3, 4]);console.log(numbers); // Set { 1, 2, 3, 4 } 元素唯一性Set 中的所有元素都是唯一的，不能重复。例如： 12const mySet = new Set([1, 2, 2, 3]);console.log(mySet); // 输出：Set(3) { 1, 2, 3 } 可以接受可迭代对象（例如数组）作为参数创建 Set 时，可以直接将一个数组或其他可迭代对象传入： 123const numbers = [1, 2, ...
Map map 的全部方法 方法 说明 构造函数 创建 map 容器，支持多种初始化方式。 empty() 检查容器是否为空。 size() 返回容器中元素的数量。 clear() 清空容器中的所有元素。 insert() 插入单个元素或范围。 erase() 按键或迭代器删除元素。 find() 查找指定键的迭代器。 count() 返回指定键的数量（始终为 0 或 1）。 at() 访问指定键对应的值，不存在时抛出异常。 operator[] 访问或插入指定键的值。 swap() 交换两个 map 容器的内容。 lower_bound() 返回第一个不小于指定键的迭代器。 upper_bound() 返回第一个大于指定键的迭代器。 equal_range() 返回一对迭代器，表示键的范围。 emplace() 原地构造并插入元素。 key_comp() 返回键比较函数对象。 value_comp() 返回值比较函数对象。 1. 添加和删除元素的方法1.1 insert 功能：在 map 中插入键值对。 ...
二叉排序树一、二叉排序树的定义 性质： 对于每个节点 N，满足： 若左子树不为空，则左子树中所有节点的值均小于 N 的值。 若右子树不为空，则右子树中所有节点的值均大于 N 的值。 左右子树本身也必须是二叉排序树。 特点： 中序遍历的结果是一个升序排列的序列。 数据存储动态且可扩展，适合频繁的插入、删除和查找操作。 二、二叉排序树的基本操作1. 定义节点结构二叉排序树的节点通常包括数据值和左右子树指针： 1234567struct TreeNode { int value; // 节点的值 TreeNode* left; // 指向左子树的指针 TreeNode* right; // 指向右子树的指针 TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}}; 2. 插入节点插入节点时递归定位插入位置，保持二叉排序树的性质： 12345678TreeNode* inser ...
一、概念与原理分块查找（Block Search），又称为索引顺序查找，是对顺序查找的优化。其核心思想是将数据划分成若干“块”，通过构建每块的索引表来快速定位目标数据所在的块，再在对应的块中顺序查找目标值。 二、算法特点 适用场景： 数据量较大，且查询频繁。 数据较为稳定（修改较少）。 优势： 提高查找效率：先通过索引缩小范围，再在小范围内查找。 易于实现，结构简单。 劣势： 动态更新数据时，重新构建索引的开销较大。 三、算法实现步骤1. 数据分块将数据按照一定规则划分为若干块： 每块的数据可以是连续的。 每块的数据数量相同或接近。 数据可以按照大小排序（便于构建索引）。 2. 构建索引为每块构建索引表，索引存储以下信息： 每块的范围（例如，块的最大值）。 每块的起始位置（方便快速访问）。 3. 查找流程 索引查找：利用索引定位目标值所在块。 块内查找：在定位的块内，顺序查找目标值。 四、算法时间复杂度 构建索引：O(n)O(n)O(n) （只需遍历数据一次）。 查找时间： 索引查找：O(n)O(\sqrt{n})O(n) （如果块数是 n\sqrt{n} ...
JavaScript
未读JavaScript常用小知识一.Number.MAX_SAFE_INTEGER在 JavaScript 中，Number.MAX_SAFE_INTEGER 是一个常量，表示 JavaScript 中能够安全表示的最大整数值，其值为 9007199254740991。这是因为 JavaScript 的数字是基于 IEEE 754 双精度浮点数（64 位），安全整数范围是从 −253+1-2^{53} + 1−253+1 到 253−12^{53} - 1253−1。超出这个范围的整数可能会导致精度丢失。 1let minDiff = Number.MAX_SAFE_INTEGER; 总结 通过使用 Number.MAX_SAFE_INTEGER 初始化变量，开发者确保了在后续比较中，所有合法的差值都会比初始值小，从而正确更新 minDiff。 二.解构赋值1. 解构赋值基础解构赋值是一种从数组或对象中提取值，并将其赋值给变量的语法。 数组的解构赋值123let arr = [1, 2, 3];let [a, b] = arr;console.log(a, b); // 输出: 1 2 ...
MapMap 是 JavaScript 中的一种新型数据结构，它存储键值对（key-value pairs），与对象类似，但具有更多的特性和更高的灵活性。Map 是 ES6 引入的，它的键可以是任何数据类型，而对象的键只能是字符串或符号（虽然它们会被自动转换为字符串）。以下是 Map 的详细用法及其相关知识点： 1. 创建 Map你可以使用 new Map() 来创建一个空的 Map 实例，或者传入一个二维数组来初始化它。 123456789// 创建一个空的 Mapconst map1 = new Map();// 创建并初始化 Mapconst map2 = new Map([ ['name', 'John'], ['age', 30], ['country', 'USA']]); 2. Map 常用方法2.1 set(key, value)set 方法用于将一个键值对添加到 Map 中。如果键已存在，则更新该键的值。 1234const map = new Map();ma ...
Math基础概述Math 是 JavaScript 的内置对象，提供数学常数和函数。Math 不像其他对象那样可以构造实例，它是全局对象，所有方法直接通过 Math 调用。 常用的数学常量 Math.PI表示圆周率（π）。值： 3.141592653589793 1console.log(Math.PI); // 3.141592653589793 Math.E表示自然对数的底数（e）。值： 2.718281828459045 1console.log(Math.E); // 2.718281828459045 Math.LN2表示 2 的自然对数。值： 0.6931471805599453 Math.LN10表示 10 的自然对数。值： 2.302585092994046 Math.LOG2E表示以 2 为底的 e 的对数。值： 1.4426950408889634 Math.LOG10E表示以 10 为底的 e 的对数。值： 0.4342944819032518 Math.SQRT2表示 2 的平方根。值： 1.4142135623730951 Math.SQRT1 ...
