# Algorithms **Repository Path**: qiushaonb/Algorithms ## Basic Information - **Project Name**: Algorithms - **Description**: 邱少的算法小笔记 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-08-21 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 剑指offer算法笔记 ### 字符串 针对字符串的分离组合,可以多用 StringBuilder ,自带有append toString. StringBuffer 为线程安全, #### 字符串匹配 可以利用sunday算法去做 ### 递归 递归本质就是栈. ### 二叉树 **二叉树的前序遍历和中序遍历反推一棵树** 前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序 中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序 后序遍历定义： 节点按照 [ 左子树 | 右子树 | 根节点] 排序 递推 1. 建立根节点root： 值为前序遍历中索引为pre_root的节点值。 搜索根节点root在中序遍历的索引i： 为了提升搜索效率，本题解使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)O(1)。 2. 构建根节点root的左子树和右子树： 通过调用 recur() 方法开启下一层递归。 左子树： 根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。 右子树： 根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right **“i-in_left+preroot+1”，其实就是右子树根节点=(中序根节点坐标-中序左边界）+先序根节点坐标+1，其中括号内=左子树长度,就是在先序列表中计算(左子树+根结点的位置再+1就是右子树的根结点了)** ### 斐波那契数列 ```java F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. ``` 可以用递归的方法,但需要使用map来记录计算过的数,避免重复计算. 涉及到状态转移的最好是利用动态规划,从下到上,直接用a,b,sum来记录前三个数即可. ### 二分法 排序数组的查找问题首先考虑使用 **二分法** 解决 官方的二分法的题解很多都是写的`low + (high - low) // 2 `而不是 `(high + low) // 2` ,这是因为利用减法防止high+low过大儿溢出. ### 深度优先算法 「回溯」只是现象，本质是 DFS 针对数组路径问题,可以使用一个 '/'来顶替当前的值,防止下一次递归中走回头路.参考剑指offer12题 ### 位运算 二进制中，最高位是符号位 1表示负数，0表示正数 与（&）、非（~）、或（|）、 异或（^）:对所有整数取反=本身的相反数-1 <<表示左移移 **>>** 表示右移 二进制先前部位即可![技术分享图片](http://image.mamicode.com/info/201810/20181023221934737312.png) **关于负数或者正数来说，移位的时候是一样的，但是在补位的时候，如果最高位是0就补0，如果最高位是1就补1** ### 大数问题 针对数字超大的数,我们需要用String来存放. 并且针对组合问题,需要使用到全排列. ### 数组内的位置变换问题 使用双指针,可以用快慢指针和首尾双指针.就是一开始的两个指针开始的地方不一样.参考剑指offer21题 ### 栈 针对栈的问题,全部都需要画图,才能理清他们的关系 ### 队列 常用方法 > 　　**add** 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常 > 　　**remove** 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 > 　　**element** 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常 > 　　**offer** 添加一个元素并返回true 如果队列已满，则返回false > 　　**poll** 移除并返问队列头部的元素 如果队列为空，则返回null > 　　**peek** 返回队列头部的元素 如果队列为空，则返回null > 　　**put** 添加一个元素 如果队列满，则阻塞 > 　　**take** 移除并返回队列头部的元素 如果队列为空，则阻塞 ### 动态规划问题 动态规划是聪明的递归,去除重复的计算. 思路:先从递归开始,再到记忆性递归,最后才到动态规划 最重要的还是找到状态转移方程 ### **Top K 问题** 一般解法:两种解法: 堆:Java中有现成的 PriorityQueue 默认小根堆 ,*O*(*N**l**o**g**K*) 快排:只需排出前k个即可,知道范围,不用在细分 ### 并查集 解决图论中「动态连通性」问题 三个核心函数 ```java /* 将 p 和 q 连接 */ public void union(int p, int q); /* 判断 p 和 q 是否连通 */ public boolean connected(int p, int q); /* 返回图中有多少个连通分量 */ public int count(); ``` 用一个一维数组去模拟森林 如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上(修改parent)对应的坐标 优化 1. 平衡性优化:小树接到大树上,添加一个size[] 记录自己的节点数 2. 路径压缩:parent[x]=parent[parent[x]],向上更新父节点,是find函数时间复杂度下降到O(1) ### Java注意事项 #### 小技巧 将二维坐标映射到一维的常用技巧 :二维坐标 `(x,y)` 可以转换成 `x * n + y` `m` 是行数，`n` 是列数 #### 自带函数 ##### PriorityQueue PriorityQueue使用跟普通队列一样，唯一区别是PriorityQueue会根据排序规则决定谁在队头，谁在队尾。 选择排序 , 不是线程安全队列 底层是一个堆,所以我们可以很方便地建立一个堆 重写比较器: compare(Integer o1, Integer o2) > 如果认为01优先级比o2高，先出o1 compare返回<0的整 > > 如果认为02优先级比o1高，先出o2 compare返回>0的整数 int compare(T o1, T o2) 是“比较o1和o2的大小”。返回“负数”，意味着“o1比o2小”；返回“零”，意味着“o1等于o2”；返回“正数”，意味着“o1大于o2”。 直接用lambda表达式来写 ```java new PriorityQueue<>((o1,o2) -> o2 -o1);(大根堆) ``` ##### Deque 双向队列, 既可以当作栈使用，也可以当作队列使用 两种实现 ArrayDeque **循环数组** **非线程安全** **不允许放入null元素**,推荐使用 ![img](https://img-blog.csdnimg.cn/20181222160806422) head指向首端第一个有效元素，tail指向尾端第一个可以插入元素的空位 扩容函数doubleCapacity()，其逻辑是**申请一个更大的数组（原数组的两倍）** ##### LinkedList 链表结构 #### 优化 if(b % 2 == 1)可以改为if(b & 1) 加速 +－一般使用2个CPU时钟 位运算 只要1个 #### Integer 越界问题 Integer.MAX_VALUE，即2147483647 Integer.MIN_VALUE -2147483648 对MAX_VALUE加1,会越界,变成**MIN_VALUE** !! Integer.MAX_VALUE + 1 = Integer.MIN_VALUE 当计算时,要注意int类型溢出, > long tmp = 43024 * 99908; tmp的结果是3474496 > long tmp = (long)43024 * (long)99908; tmp结果是4298441792 #### 逻辑或 ​ 逻辑或有阻断的作用,可以用在return的时候减少遍历的次数 #### 值传递 在 Java 中，参数传递是 **值传递**，对象类型变量在传参的过程中，复制的是变量的地址。这些地址被添加到 `res` 变量，但实际上指向的是同一块内存地址 > 在 `res.add(path);` 这里做一次拷贝即可。 > > res.add(new ArrayList<>(path));