剑指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就是右子树的根结点了)

斐波那契数列

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

<<表示左移移

>> 表示右移

二进制先前部位即可

关于负数或者正数来说，移位的时候是一样的，但是在补位的时候，如果最高位是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(NlogK)

快排:只需排出前k个即可,知道范围,不用在细分

并查集

解决图论中「动态连通性」问题

三个核心函数

    /* 将 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表达式来写

new PriorityQueue<>((o1,o2) -> o2 -o1);(大根堆)

Deque

双向队列, 既可以当作栈使用，也可以当作队列使用

两种实现

ArrayDeque 循环数组 非线程安全 不允许放入null元素,推荐使用

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));