Jiankychen's Blog

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

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

# 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： 输入：l1 = [9,9,9,9,9,9,9],...

算法复杂度旨在描述 输入数据量 NNN 时，算法的 时间使用 和 空间使用 情况 时间：假设各操作的运行时间为固定常数，统计算法运行的 计算操作的数量 ，以代表算法运行所需时间 空间：统计在最差情况下 ，算法运行所需使用的 最大空间 输入数据大小 NNN 指算法处理的输入数据量，根据不同算法，具有不同的定义，例如： 排序算法：NNN 代表需要排序的元素数量 搜索算法：NNN 代表搜索范围的元素总数，例如数组大小、矩阵大小、二叉树节点数、图节点和边数等 # 时间复杂度 统计的是算法的 计算操作数量 ，而不是 运行的绝对时间 计算操作数量 和 运行绝对时间...

树：用来模拟具有树状结构性质的数据集合 二叉树 （Binary Tree）：每个节点 最多有两个子树 的树结构，通常子树被称作 “左子树” 和 “右子树” 注意：二叉树必须严格区分左右子树，即使只有一棵子树，也要说明它是左子树还是右子树 # 二叉树的种类 # 满二叉树 满二叉树：一棵高度为 kkk 并具有 2k−12^k - 12k−1 个节点的二叉树 # 完全二叉树 完全二叉树：在满二叉树的最底层自右至左依次（注意：不能跳过任何一个节点）去掉若干个节点得到的二叉树 完全二叉树的特点： 所有的叶节点都出现在最低的两层上 对任一节点，如果其右子树的高度为 k ，则其左子树的高度为...

# 表达式基础 表达式 通常由 运算符 和 运算对象 组成 字面值 和 变量 是最简单的表达式 # 基本概念 一元运算符：作用于一个运算对象的运算符，如取地址符 & 和解引用符 * 二元运算符：作用于两个运算对象的运算符，如相等运算符 == 和乘法运算符 * 三元运算符：作用于三个运算对象，如条件运算符 _ ? _ : _ # 组合运算符和运算对象 表达式的求值结果，依赖于运算符的 优先级 、结合律 以及 运算对象的求值顺序 优先级：例如， * 优先级高于 + 结合律：通常是从左往右，遇到括号时则是由内到外 求值顺序：例如， f1() + f2() ，对于 f1() 和...

# LeetCode 278. 第一个错误的版本 LeetCode 278 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 示例 1： 输入：n = 5, bad =...

二分查找 （binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序数组中查找某一元素的算法 以在一个升序数组中查找一个数为例：它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么查找右侧；如果中间元素大于所查找的值，查找左侧 时间复杂度： 最优时间复杂度为 O(1)O(1)O(1) 最坏和平均时间复杂度为 O(log⁡n)O(\log{n})O(logn) 空间复杂度： 迭代版本的二分查找算法，空间复杂度为...

# 命名空间的 using 声明 std::cin 的意思就是要使用命名空间 std 中的名字 cin using 声明具有如下的形式： using namespace::name; 一旦声明了上述语句，就可以直接访问命名空间中的名字 例如： #include <iostream> // using declaration; when we use the name cin, we get the one from the namespace std using std::cin; int main() { int i; cin...