Jiankychen's Blog

# LeetCode 1. 两数之和 LeetCode 1. Two Sum 给定一个整数数组 nums 和一个整数目标值 target ，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1] 示例 2： 输入：nums &

图 由 顶点集 和 边集 组成，即，G=(V,E)G = (V, E)G=(V,E) VVV 是顶点的集合，顶点代表数据元素 EEE 是连接顶点的边的集合，边代表元素间的关系 根据边的方向性，可将图分为 有向图 和 无向图 有向图：边有方向，边用 <> 表示，例如， <A, B> 表示从 A 出发到 B 的一条边 无向图：边无方向，用 () 表示，例如， (A, B) 表示顶点 A 和 B 之间有一条边 另外，可以根据顶点之间的关系为边设置权重 加权图：边被赋予一个权值 W 加权有向图：边表示为 <A, B,

哈希表（Hash table ，也被称为散列表）是根据关键码而直接进行访问的数据结构 一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为 <Key, value> 的键值对 哈希表可以近似理解成数组，哈希表中的关键码就是数组的索引下标，通过下标可以直接访问数组的元素 一般哈希表都是用来快速判断一个元素是否出现集合当中 哈希表 以空间换时间 ，因为需要额外的 数组 、 set 或 map 来存放数据，才能实现快速查找 # 哈希函数 哈希函数（hash function）将关键码映射为哈希表的索引 构造哈希函数的要求： 定义域必须包含全

队列是一个先进先出的线性表 优先级队列：结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队 优先级队列可以基于线性结构实现 按照 优先级 排序 入队：按照优先级插入在合适的位置 - O(N)O(N)O(N) 出队：队头元素 - O(1)O(1)O(1) 按照 到达时间 排序 入队：插入到队尾 - O(1)O(1)O(1) 出队：寻找优先级最高的并删除 - O(N)O(N)O(N) 优先级队列也可以基于 二叉堆 实现 二叉堆指的是父子之间的大小满足一定约束的完全二叉树 最小化堆：父结点的值小于等于儿子结点，也被称之为 小顶堆

# 动态规划 动态规划（Dynamic Programming，DP），一种解决某种最优化问题的方法 动态规划的基本思想：把原问题分解为相对简单的子问题 将原问题分成若干 阶段 ，每个阶段对应若干个子问题，提取这些子问题的特征（状态） 寻找各状态间的相互转移方式（状态转移方程） 按顺序求解每一个阶段的问题 动态规划中每一个状态一定是由上一个状态推导出来的 贪心算法没有状态推导，而是从局部直接选最优的 用动态规划解决问题的三个条件（了解即可）：最优子结构、无后效性、子问题重叠 最优子结构：原问题的最优解，必然是通过子问题的最优解得到的（最优子结构保证了我们能够通过选取子问题的最优解最终

# 递推 递推的基本思想：根据已有信息推出未知信息 递推解题思路： 数学建模 找出递推式与初始条件 # 青蛙跳台阶 剑指 Offer 10- II. 青蛙跳台阶问题 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。结果须对 1000000007 取模 递推解题思路： 假设 f[n] 表示 青蛙从第一个石头跳到第 n 个石头一共有 f[n] 种方案 递推式： f[n] = f[n - 1] + f[n - 2] 从 n - 1 台阶，一次跳 1 级到 n 从 n - 2 台阶，一次跳

简单介绍各种排序算法

数据结构是为实现对计算机数据有效使用的各种数据组织形式，旨在降低各种算法计算的时间与空间复杂度 常见的数据结构可分为 线性数据结构 与 非线性数据结构 ，具体包括：数组 、 链表 、 栈 、 队列 、 树 、 图 、 散列表 、 堆 不要对数据结构的使用浅尝辄止，而要深挖起内部原理 # 数组 数组是将相同类型的元素存储于 连续内存空间 的数据结构，其长度不可变。构建数组时需要在初始化时给定长度，例如： int array[5];int array[] = {2, 3, 1, 0, 2};可变数组 （标准库类型 vector ）是经常使用的数据结构，其基于

本文主要涉及数组、哈希表、排序、二分查找、双指针等内容 存在重复元素 二分查找 有序数组的平方 移除元素 长度最小的子数组 剑指 Offer 03. 数组中重复的数字 下一个排列 多数元素 除自身以外数组的乘积 搜索二维矩阵 II 寻找重复数 找到所有数组中消失的数字 和为 K 的子数组 最短无序连续子数组 # LeetCode 217. 存在重复元素 LeetCode 217. Contains Duplicate 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同

# LeetCode 2. 两数相加 LeetCode 2. Add Two Numbers 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. 示例 2： 输入：l1 = [0], l2 = [0] 输出：[0] 示例 3：