「人生とかホントはいきなり事じゃない」 ———— 2020.03.21悟
算法总结
本页面创立于: 2020年03月22日
页面成立原因: 解决个人算法较差的痛点
Github:
- 算法基础：https://github.com/JasonkayZK/Java_Algorithm
- LeetCode：https://github.com/JasonkayZK/LeetCode_Java
其他:
为了不影响其他文章的阅读，算法文章统一日期1996-07-27
算法可以说一直以来是本人的一个痛点，以下文章可能总结的并不是很好，希望大家能多批评，并提出宝贵意见～
目录
ACM竞赛系列文章
| 文章 | 日期 | 主要内容 | 备注 |
|---|---|---|---|
| ACM集训-STL | 2020-04-04 | Java在OJ中的IO格式 常用的数据结构 |
|
算法分类
数学
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 数值的整数次方 | 2020-03-31 | ☆ | ☆☆☆☆ | 简单的快速幂 |
| 数组中出现次数超过一半的数字 | 2020-04-01 | ☆☆ | ☆☆☆ | 使用摩尔投票法 [求众数] |
| 整数中1出现的次数 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 归纳总结规律 |
| 第N个丑数 | 2020-04-01 | ☆☆☆ | ☆☆☆☆ | 维护2,3,5的乘积队列 |
| 和为S的连续正数序列 | 2020-04-02 | ☆☆ | ☆☆ | 平均数不变 根据序列长度进行搜索 |
| 扑克牌顺子 | 2020-04-02 | ☆☆ | ☆☆ | 根据题目叙述寻找成功条件 |
| 圆圈中最后剩下的数 | 2020-04-02 | ☆ | ☆ | 使用链表直接模拟过程即可 |
| 不用加减乘除做加法 | 2020-04-02 | ☆☆☆ | ☆☆☆☆☆ | 两个数异或即为不进位的和; 两个数与再左移一位即为进位值; 将上述两步的结果相加 |
| 构建乘积数组 | 2020-04-02 | ☆☆ | ☆☆ | 先进行上三角乘法 再进行下三角乘法 |
| Triangle Partition | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 题目条件保证了三个点一定不在同一直线上 对坐标进行排序，先x后y，从小到大 每三个点构成一个三角形 |
| SOLDIERS | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 对于y, 取y[0…n-1]的中位数; 对于x, 取x[i] - i的中位数 |
| Watering Flowers | 2020-04-04 | ☆☆☆ | ☆☆☆☆☆ | 给你n个点和两个圆心的位置 用两个圆覆盖住所有的点，使得r1xr1+r2xr2最小 |
位运算
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 二进制中1的个数 | 2020-03-31 | ☆ | ☆☆☆ | 计算一个数的二进制表示 |
| 不用加减乘除做加法 | 2020-04-02 | ☆☆☆ | ☆☆☆☆☆ | 两个数异或即为不进位的和; 两个数与再左移一位即为进位值; 将上述两步的结果相加 |
动态规划
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 跳台阶 | 2020-03-31 | ☆☆ | ☆☆ | 简单的一维动态规划(斐波那契) |
| 变态跳台阶 | 2020-03-31 | ☆☆ | ☆☆ | 简单的一维动态规划 |
| 连续子数组的最大和 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 简单的动态规划 其中dp[i]表示从a[0]~a[i]的连续子数组的最大值 |
| 剪绳子 | 2020-04-02 | ☆☆☆☆ | ☆☆☆ | dp[i]表示长度为i时的最大乘积 dp[i] = max{dp[k] x dp[i - k]} |
堆
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 最小的K个数 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 求最小的K个数使用最大堆; 求最大的K个数使用最小堆; |
| 数据流中的中位数 | 2020-04-02 | ☆☆☆ | ☆☆☆☆ | 使用一个最大堆和一个最小堆; 保证最大堆和最小堆数据总数之差不超过1; 保证最大堆数值都大于最小堆数值 |
| 滑动窗口的最大值 | 2020-04-02 | ☆☆☆ | ☆☆ | 使用最大堆存储窗口数据 滑动窗口时移除窗口左端的元素 |
二叉树
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 重建二叉树 | 2020-03-31 | ☆☆ | ☆☆☆☆☆ | 利用二叉树前序和中序遍历的特点 通过分治重建二叉树 |
| 树的子结构 | 2020-03-31 | ☆☆ | ☆☆☆ | 通过递归进行判断: 如果A当前节点等于B的根节点, 递归判断是否是子树 |
| 二叉树的镜像 | 2020-03-31 | ☆☆ | ☆☆☆ | 通过先序遍历, 递归的将root的左子树和右子树交换即可 |
| 从上往下打印二叉树 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 简单的二叉树的BFS |
| 二叉搜索树的后序遍历序列 | 2020-04-01 | ☆☆ | ☆☆☆ | 对于二叉树的子树进行递归 拆分左右子树, 判断条件 |
| 二叉树中和为某一值的路径 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 典型的回溯法 每一步结束则对当前节点进行回溯返回 |
| 二叉搜索树与双向链表 | 2020-04-01 | ☆☆ | ☆☆☆ | 对于BST的中序遍历就是有序的 针对双向链表的操作可以参考类似于链表翻转 |
| 二叉树的深度 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 递归: root.height = max(height(root.left), height(root.right)) + 1 |
| 平衡二叉树 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 从下往上遍历 如果子树是平衡二叉树，则返回子树的高度； 如果子树不是平衡二叉树，则直接停止遍历 |
| 二叉树的下一个结点 | 2020-04-02 | ☆☆☆ | ☆☆☆☆ | 根据中序遍历的规则进行各种情况的判断 |
| 对称的二叉树 | 2020-04-02 | ☆☆ | ☆☆☆ | 类似于判断两个二叉树相等; 只不过是递归判断左子树和右子树相等; |
| 按之字形顺序打印二叉树 | 2020-04-02 | ☆☆ | ☆☆☆ | 用两个栈分别用来遍历奇数行和偶数行; |
| 把二叉树打印成多行 | 2020-04-02 | ☆ | ☆☆☆ | 简单的二叉树BFS |
| 序列化二叉树 | 2020-04-02 | ☆☆ | ☆☆☆ | 序列化就是先续的遍历过程, 增加值或者#,即可;反序列化先按照 ,拆分字符串, 然后按照先序遍历的步骤进行树的重建; |
| 二叉搜索树的第k个结点 | 2020-04-02 | ☆☆ | ☆☆☆☆ | 设置一个index, 对二叉树进行中序遍历; 如果index==k则直接返回; |
树
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
查找
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 二维数组中的查找 | 2020-03-31 | ☆☆ | ☆☆ | 利用数组有序的特性进行优化 |
| 旋转数组的最小数字 | 2020-03-31 | ☆☆ | ☆☆☆ | 利用单边的二分法进行查找 关键在于分清不同的情况 |
| 数字在排序数组中出现的次数 | 2020-04-01 | ☆☆ | ☆☆ | 先通过二分找到其中出现的任意一个的索引 然后计算这个这个索引左右两侧的个数即可 |
| 二叉搜索树的第k个结点 | 2020-04-02 | ☆☆ | ☆☆☆☆ | 设置一个index, 对二叉树进行中序遍历; 如果index==k则直接返回; |
双指针
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 链表中倒数第k个结点 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 使用快慢指针 让快指针先走k步 |
递归
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 矩形覆盖 | 2020-03-31 | ☆☆☆ | ☆☆☆ | 利用找规律的方法, 进行递归处理 |
分治
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
回溯
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 二叉树中和为某一值的路径 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 典型的回溯法 每一步结束则对当前节点进行回溯返回 |
| 字符串的排列 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 使用回溯法 通过交换字符串对应的位置进行字符串构建 |
| 矩阵中的路径 | 2020-04-02 | ☆☆ | ☆☆☆☆ | 四个方向的BFS + 回溯法 |
滑窗
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 滑动窗口的最大值 | 2020-04-02 | ☆☆☆ | ☆☆ | 使用最大堆存储窗口数据 滑动窗口时移除窗口左端的元素 |
哈希表
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
矩阵
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
BFS
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 从上往下打印二叉树 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 简单的二叉树的BFS |
DFS
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 正则表达式匹配 | 2020-04-02 | ☆☆☆☆ | ☆☆☆☆☆ | 使用递归的DFS对每一个可能分支进行搜索; |
| 矩阵中的路径 | 2020-04-02 | ☆☆ | ☆☆☆☆ | 四个方向的DFS + 回溯法 |
| 机器人的运动范围 | 2020-04-02 | ☆☆ | ☆☆☆ | 四个方向进行DFS搜索, 访问过得增加标记; 但是不回溯(防止产生重复结果) |
链表
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 从尾到头打印链表 | 2020-03-31 | ☆☆ | ☆☆☆☆☆ | 建立pre, cur两个指针 使用cur拆分链表, pre记录前一链表 |
| 链表中倒数第k个结点 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 使用快慢指针 让快指针先走k步 |
| 合并两个排序的链表 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 类似于归并排序中归并的操作 |
| 复杂链表的复制 | 2020-04-01 | ☆☆ | ☆☆ | 遍历两次. 使用HashMap保存节点 |
| 二叉搜索树与双向链表 | 2020-04-01 | ☆☆ | ☆☆☆ | 对于BST的中序遍历就是有序的 针对双向链表的操作可以参考类似于链表翻转 |
| 两个链表的第一个公共结点 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 设定两个指针分别从list1和list2开始. list1当到达链表1结尾时, 继续从链表2开始; list2同理; |
| 圆圈中最后剩下的数 | 2020-04-02 | ☆ | ☆ | 使用链表直接模拟过程即可 |
| 链表中环的入口结点 | 2020-04-02 | ☆☆ | ☆☆☆☆ | 首先快慢指针都从头开始, 快指针每次两步, 慢指针每次一步; 如果两个指针最终相遇, 则说明链表存在环! 此时快指针从当前继续向前走(每次一步), 而慢指针从链表头开始走(每次一步) 最终两个指针会相遇在入口节点; |
| 删除链表中重复的结点 | 2020-04-02 | ☆☆ | ☆☆☆ | 构建一个哨兵节点scott; 然后建立cur节点和curNext节点 每次判断curNext是否与后面的相同, 进行跳过节点 |
图
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
并查集
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
排序
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 调整数组顺序使奇数位于偶数前面 | 2020-03-31 | ☆☆ | ☆☆ | 类似于稳定的排序 |
| 合并两个排序的链表 | 2020-03-31 | ☆☆ | ☆☆☆☆ | 类似于归并排序中归并的操作 |
| 把数组排成最小的数 | 2020-04-01 | ☆☆ | ☆☆☆ | 按照{arr[i], arr[j]}组合较小的方式进行排序 |
| Triangle Partition | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 题目条件保证了三个点一定不在同一直线上 对坐标进行排序，先x后y，从小到大 每三个点构成一个三角形 |
| Lala Land and Apple Trees | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 如果正负位置数量相同，那么都可取 如果不相同，那么少的一边全取，多的一边取离0近的。 |
| Watering Flowers | 2020-04-04 | ☆☆☆ | ☆☆☆☆☆ | 给你n个点和两个圆心的位置 用两个圆覆盖住所有的点，使得r1xr1+r2xr2最小 |
数组
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 二维数组中的查找 | 2020-03-31 | ☆☆ | ☆☆ | 利用数组有序的特性进行优化 |
| 调整数组顺序使奇数位于偶数前面 | 2020-03-31 | ☆☆ | ☆☆ | 类似于稳定的排序 |
| 顺时针打印矩阵 | 2020-03-31 | ☆ | ☆☆ | 分四个方向遍历即可 |
| 数组中出现次数超过一半的数字 | 2020-04-01 | ☆☆ | ☆☆☆ | 使用摩尔投票法 [求众数] |
| 最小的K个数 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 求最小的K个数使用最大堆; 求最大的K个数使用最小堆; |
| 连续子数组的最大和 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 简单的动态规划 其中dp[i]表示从a[0]~a[i]的连续子数组的最大值 |
| 数组中只出现一次的数字 | 2020-04-01 | ☆☆☆ | ☆☆☆ | 通过异或取得mask 通过mask对数组进行分类 |
| Lala Land and Apple Trees | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 如果正负位置数量相同，那么都可取 如果不相同，那么少的一边全取，多的一边取离0近的。 |
贪心
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 剪绳子 | 2020-04-02 | ☆☆☆☆ | ☆☆☆ | 尽可能的拆分出3 |
线段树
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
栈
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 用两个栈实现队列 | 2020-03-31 | ☆☆ | ☆☆ | 两个栈 一个用来存放入栈的数据, 一个用来存放出栈的数据 |
| 包含min函数的栈 | 2020-03-31 | ☆☆ | ☆☆☆ | 设定两个栈stack和minStack 针对不同的操作保持minStack.peak为最小 |
| 栈的压入、弹出序列 | 2020-03-31 | ☆☆ | ☆☆☆ | 通过一个Stack模拟操作即可 |
队列
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 用两个栈实现队列 | 2020-03-31 | ☆☆ | ☆☆☆ | 两个栈 一个用来存放入栈的数据, 一个用来存放出栈的数据 |
字符串
| 题目 | 添加时间 | 难易度 | 重要度 | 备注 |
|---|---|---|---|---|
| 替换空格 | 2020-03-31 | ☆ | ☆ | |
| 字符串的排列 | 2020-04-01 | ☆☆ | ☆☆☆☆ | 使用回溯法 通过交换字符串对应的位置进行字符串构建 |
| 第一个只出现一次的字符位置 | 2020-04-01 | ☆ | ☆ | 第一遍遍历, 记录每个字符出现的次数; 第二次遍历, 寻找第一个出现一次的; |
| 数组中的逆序对 | 2020-04-01 | ☆☆☆ | ☆☆☆☆☆ | 本质上逆序就是在归并排序的归并过程中产生的数字位置提升的总和数 对数组进行归并排序 |
| 翻转单词顺序列 | 2020-04-02 | ☆☆ | ☆☆ | 先翻转整个字符串 然后再翻转每一个单词 |
| 正则表达式匹配 | 2020-04-02 | ☆☆☆☆ | ☆☆☆☆☆ | 使用递归的DFS对每一个可能分支进行搜索; |
| 表示数值的字符串 | 2020-04-02 | ☆ | ☆☆☆ | 使用正则表达式判断即可 |
| 字符流中第一个不重复的字符 | 2020-04-02 | ☆☆ | ☆☆ | 在HashMap中记录每个字符出现的index 重复时将值设为-1; 取得第一个不重复的字符时 遍历map寻找index最小并且不为-1的即可 |
| 魔法串 | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 然后遍历str1, 当相应位置不对应时, 判断是否可以转换; 如果不能, 则选择删除, 即将str2指针cur2向后移动, 然后继续比较; |
| Right-Left Cipher | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 字符串的还原。 长度为奇数时从左边开始，长度为偶数时从右边开始。 |
| CRB and String | 2020-04-04 | ☆☆☆ | ☆☆☆☆ | 给你两个字符串s和t 可以在字符串s中任意选一个字符c，在该字符c后插入一个字符d(d!=c) 问经过多次此操作，能否将字符串s转化成字符串t; |
请我喝Java
如果觉得博主的项目内容对你有帮助, 可以对本博主打赏哦!
Alipay:
WechatPay:
