开源笔记：数据结构与算法
该笔记主要包含两方面：
数据结构：
阅读了书籍《数据结构（Python版）》和《数据结构（C语言版）》，其中实现了常用的数据结构如链表、栈、队列、树等，以及常见的内排序算法。目前只实现了 Python 版，后续会陆续更新 C++ 版。
算法：
算法方面主要是通过编程的方式，在各大 OJ 编程网站中实战学习。遇到不会的知识点就解决不会的知识点。坚信见识的多了，就能将知识点串起来，整理成体系。
后续会陆续为每一道题目增加知识点标签，并增加 C++ 的解决方案，持续更新中！
该笔记的展示如下:
简单函数实现
| int2str | str2int | strcat | strcmp | strcpy | memcpy | strstr | swapInt |
|---|---|---|---|---|---|---|---|
| swapStr | strlen |
常用排序算法
| 排序算法 | 平均 | 最好 | 最坏 | 空间复杂度 | 稳定性 | 实现 | 实现 | 适用的数据规模 |
|---|---|---|---|---|---|---|---|---|
| 直接插入 | n^2 | n | n^2 | 1 | 稳定 | Python | C++ | 少 |
| 希尔排序 | n^1.3 | n | n^2 | 1 | 不稳定 | Python | C++ | |
| 直接选择 | n^2 | n^2 | n^2 | 1 | 不稳定 | Python | C++ | 少 |
| 堆排序 | nlog2n | nlog2n | nlog2n | 1 | 不稳定 | C++ | 多 | |
| 冒泡排序 | n^2 | n | n^2 | 1 | 稳定 | Python | C++ | 少 |
| 快速排序 | nlog2n | nlog2n | n^2 | nlog2n | 不稳定 | Python | C++ | 多 |
| 归并排序 | nlog2n | nlog2n | nlog2n | n | 稳定 | Python | C++ | 多 |
数据结构
| 数据结构 | 实现 | 实现 |
|---|---|---|
| 链表 | Python | C++ |
| 双向链表 | Python | |
| 栈 | Python | |
| 队列 | Python | C++ |
| 双向队列 | Python | |
| 循环队列 | Python | |
| 二叉树 | Python | |
| 二叉排序树 | C++ |
栈与队列
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 |
|---|---|---|---|---|---|
| 用两个栈实现队列 | 剑指-9 | Python | C++ | ||
| 包含min函数的栈 | 剑指-30 | Python | C++ | ||
| 栈的压入弹出序列 | 剑指-31 | Python | C++ |
链表
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 | | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———————————————————-: | :——: | :–: | | 反向打印链表 | 剑指-6 | Python | C++ | | | | 删除链表的结点 | 剑指-18 | Python | C++ | | | | 删除链表的重复结点 | 剑指-18扩展 | Python | C++ | | | | 链表的中间节点 | 力扣-876 | | C++ | 快慢指针 | 1 | | 回文链表 | 力扣-234 | | | 快慢指针 | 2 | | 链表中倒数第k个节点 | 剑指-22 | Python | C++ | 快慢指针 | 2 | | 链表中环的入口结点 | 剑指-23 | Python | C++ | | | | 反转链表 | 剑指-24 | Python | C++ | | | | 合并两个排序的链表 | 剑指-25 | Python | C++ | | | | 两数相加 | 力扣-2 | Python | C++ | | | | 两个列表的第一个公共结点 | 剑指-52 | Python | C++ | 快慢指针 | 2 | | 对链表进行插入排序 | 力扣-147 | | | | |
树
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 | | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———————————————————-: | :——: | :–: | | 重建二叉树 | 剑指-7 | Python | C++ | | | | 二叉树的下一个结点 | 剑指-8 | Python | | | | | 树的子结构 | 剑指-26 | Python | C++ | | | | 二叉树的镜像 | 剑指-27 | Python | C++ | | | | 对称二叉树 | 剑指-28 | Python | C++ | | | | 从上到下打印二叉树 | 剑指-32 | Python | C++ | | | | 按层打印二叉树 | 剑指-32扩展 | Python | C++ | | | | 按“之”字形打印二叉树 | 剑指-32扩展 | Python | C++ | | | | 二叉搜索树的后序遍历 | 剑指-33 | Python | | | | | 二叉树中和位某一值的路径 | 剑指-34 | Python | C++ | | | | 二叉搜索树与双向链表 | 剑指-36 | Python | | | | | 二叉搜索树的第k大节点 | 剑指-54 | Python | | 树的遍历 | 2 | | 二叉树的深度 | 剑指-55 | Python | | 递归 | 1 |
图与回溯
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 | | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———————————————————-: | :————–: | :–: | | 矩阵中的路径 | 剑指-12 | Python | | | 3 | | 机器人的运动范围 | 剑指-13 | Python | C++ | | 2 | | 岛屿数量 | 力扣-200 | Python | C++ | DFS，BFS，并查集 | 4 |
数组与字符串
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 |
|---|---|---|---|---|---|
| 字符串的全排列 | 剑指-38 | Python | C++ | 2 | |
| 顺时针打印矩阵 | 剑指-29 | Python | 2 | ||
| 替换空格 | 剑指-5 | Python | 1 | ||
| 两数之和 | 力扣-1 | Python | C++ | 哈希 | 1 |
| 三数之和 | 力扣-15 | 双指针 | |||
| 四数相加 II | 力扣-454 | ||||
| 两数之和之数组有序 | 剑指-57，力扣-167 | Python | 双指针 | 1 | |
| 验证回文串 | 力扣-125 | Python | C++ | 双指针 | 1 |
| 删除排序数组中的重复项 | 力扣-26 | Python | C++ | 1 | |
| 实现strStr | 力扣-28 | Python | C++ | ||
| 旋转图像 | 力扣-48 | Python | |||
| 加一 | 力扣-66 | Python | C++ | 1 | |
| 旋转数组 | 力扣-189 | Python | C++ | ||
| 两个数组的交集 | 力扣-349 | Python | |||
| 两个数组的交集扩展 | 力扣-350 | Python | |||
| 字符串中的第一个唯一字符 | 力扣-387 | Python | C++ | 哈希 | 1 |
| 判断子序列 | 力扣-392 | Python | C++ | ||
| 反转单词顺序 | 剑指-58 | 1 | |||
| 左旋转字符串 | 剑指58-扩展 | 1 | |||
| 最长公共前缀 | 力扣-14 | 1 | |||
| 寻找峰值 | 力扣-162 | 二分 | |||
| 递增的三元子序列 | 力扣-334 | ||||
| 跳跃游戏 | 力扣-55 | ||||
| 根据身高重建队列 | 力扣-406 | ||||
| 接雨水 | 力扣-42 | 3 |
排序与搜索
动态规划
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 | | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———-: | :–: | | 剪绳子 | 剑指-14 | Python | C++ | | 1 | | 连续子数组的最大和 | 剑指-42 | Python | C++ | | 1 | | 连续子数组的最大积 | 力扣-152 | | | | | | 01背包无价值 | 领扣-92 | Python | C++ | | 1 | | 01背包有价值 | 领扣-125 | Python | C++ | | 1 | | 完全背包 | 领扣 | Python | C++ | | 1 | | 01背包返回方案数 | 领扣-563 | Python | C++ | | 2 | | 完全背包返回方案数 | 领扣-562 | Python | C++ | | 2 | | 买卖股票的最佳时机 | 力扣-121 | Python | C++ | | 1 | | 买卖股票的最佳时机2 | 力扣-122 | Python | C++ | | 1 | | 买卖股票的最佳时机3 | 力扣-123 | Python | C++ | | 3 | | 最长回文子串 | 力扣-5 | Python | C++ | | 3 | | 最长回文子序列 | 力扣-516 | | | | | | 不同路径 | 力扣-62 | Python | C++ | | 1 | | 最小路径和 | 剑指-47，力扣-64 | Python | C++ | | 1 | | 交错字符串 | 力扣-97 | Python | | | 4 | | 打家劫舍 | 力扣-198 | Python | C++ | | 1 | | 零钱兑换 | 力扣-322 | Python | C++ | 完全背包变种 | 2 | | 分割等和子集 | 力扣-416 | Python | C++ | 01背包变种 | 2 | | 一和零 | 力扣-474 | Python | C++ | 多维01背包 | 3 | | 目标和 | 力扣-494 | Python | C++ | 01背包变种 | 3 | | 无重复字符的最长子串 | 剑指-48，力扣-3 | | C++ | | 3 | | 最长上升子序列 | 力扣-300 | | | | 1 | | 最长公共子序列 | 力扣-1143 | | | | |
巧妙
| 题目 | 题目出处 | 实现 | 实现 | 知识点 | 难度 | | :———————————————————-: | :———————————————————-: | :———————————————————-: | :———————————————————-: | :—-: | :–: | | 二进制中1的个数 | 剑指-15 | Python | C++ | 位运算 | | | 汉明距离 | 力扣-461 | | | 位运算 | | | 数值的整数次方 | 剑指-16 | Python | C++ | 递归 | | | x的平方根 | 力扣-69 | Python | | 二分 | | | 有效的完全平方数 | 力扣-367 | Python | | | | | 出现一次的数字 | 力扣-136 | Python | C++ | 位运算 | | | 缺失数字 | 力扣-268 | | | 位运算 | | | 存在重复元素 | 力扣-217 | Python | C++ | | | | 大数加法 | | | | | |