LeetCode刷题记录

剑指Offer解题思路大纲

用两个栈实现队列

1. 直接push到栈1，pop的时候如果栈2为空，取出栈1的数据放到栈2

实现包含min函数的栈

1. 自己实现栈，Node中存储min，保存当前Node之前（栈之下）的最小值
2. 两个栈，栈1存储数据，栈2存储当前栈1区间最小值，当被推出的数据是最小值时，栈2也推出最小值，更新最小值为栈2顶部的值
   • 如：栈1=[9,10,7,3,5]，栈2=[9,7,3]，5pop之后，最小值还是3，3pop之后，栈2也要pop，最小值变为7
3. 1个栈，每次push的时候先push当前的最小值，再push数据。pop的时候pop两次。
   • 即每个元素中间插入一个min，表示当前栈底区间的最小值，如[min=max,data=3],[min=3,data=2],[min=2,data=1]

从头到尾打印链表

1. 使用栈，后进先出，遍历压栈再遍历推出
2. 使用列表，遍历存入列表，再倒序取出
3. 先遍历获取链表长度，创建数组，再遍历链表，倒序填入数组
4. 链表反转，再存入数组。
5. 递归将节点加入列表，再转换为数组
6. 使用i记录递推次数，递归到底部创建数组，使用j回溯的时候赋值

反转链表

1. 倒着构造链表，保存已构造好的链表，每次循环创建新的头节点，连接上已构造好的链表
2. 双指针，使用临时变量暂存下一个节点，将当前节点断开指向前一个节点
3. 递归，递归终止返回尾节点，作为新链表的头节点。回溯阶段将下一个节点指向自己，自己指向null
4. 递归，传入前一个节点，回溯阶段将当前节点指向前一个节点

复杂链表的复制

注意点：新链表不能指向原链表节点，需要全部复制

1. 先遍历构造新链表，random指向原链表节点，再双重遍历，同时遍历新链表和旧链表，在原链表中找到random节点，此时也找到了新链表中的random节点
2. 先遍历复制每一个节点，插入到原节点之后，此时新节点random为空，再遍历给新节点random赋值为原节点random的下一个节点。再拆分新旧链表。
   • 复制每一个节点，如：1->2->3变为1->1->2->2->3->3
3. 先遍历复制新节点，使用Map存储原节点对应的新节点。再遍历给next和random赋值，通过key找到对应的节点。

替换字符串中的空格为%20

1. 使用正则
2. 使用Java replace或replaceAll方法
3. 使用Java StringBuilder，遍历拼接
4. 使用辅助char数组，大小为原数组的3倍，遍历填入新数组，再初始化新字符串
5. 使用辅助char数组，先遍历获取空格数量，新数组大小为原长度+空格数量*2，遍历填入新数组，再初始化新字符串

左旋转字符串

1. 遍历计算每一个字符旋转过后的位置，使用char数组存储。位置为(i-n+len)%len，
2. 使用StringBuilder拼接，从n位置拼接到末尾，再从0拼接到n
3. 由于字符串是整段位移，可以切割字符串：s.substring(n, s.length()) + s.substring(0, n)
4. 也可以先复制字符串，再切割：(s + s).substring(n, s.length() + n);

找出数组中任意一个重复的数字

条件：数字小于数组长度

1. 创建大小相等的bool数组，判断对应的位置是否已经存在数字。遍历将数字填入对应的索引位置。（也可以创建int数组，每次填入+1，大于1表示重复）
2. 遍历存入HashSet，判断是否存在
3. 类似思路1，直接在原数组中判断，如果索引位置和值不相等则交换位置，如果相等则表示重复

在排序数组中查找某个数字的个数

关键条件：排序数组

1. 遍历找到目标数字，统计次数，由于是排序数组，因此当新的值大于目标值是可以提前结束遍历
2. 二分查找目标数字的左右边界位置，再相减

递增排序数组中找到0到n-1中缺失的数字

关键条件：递增即不存在相同数字，数组大小为n，数字范围为0到n-1，有n+1个数。 可知：相邻两个数字只能是相差1。 可知：数字等于对应的索引nums[0]=0，找到第一个不等于索引的数字即可找到缺失的数字

1. 判断相邻数字相差是否为1，考虑边缘情况：这个数字在第一个或最后一个
2. 找出值和索引不一样的项，考虑边缘情况：这个数字在第一个或最后一个
3. 由于是排序数组，可以使用二分查找，找到第一个值大于索引的项
4. 数学法：正常等差数列和为sum=n*(n+1)/2，遍历减去数组中所有数字的和，即可得到缺失的值

二维数组中的查找

1. 暴力查找，遍历
2. 从左下角（或者右上角）开始查找，小于目标值则往上搜索，大于目标值则往右搜索。

可以将数组旋转45度观看，类似二叉搜索树，如图

旋转数组中的最小数字

1. 二分查找
2. 遍历找到最小值
3. 数组重新排序之后取第一个元素

第一个只出现一次的字符

注：HashMap取出不一定保证顺序，题目要求找出第一个只出现一次的字符，因此需要用有序哈希表。

1. 第一次遍历使用哈希表保存字符出现次数，第二次遍历字符串，查看出现次数。（也可以保存bool类型，不统计次数）
2. 第一次遍历使用有序哈希表保存字符出现次数，第二次遍历哈希表。
3. 使用HashMap+队列，首次出现则加到队列中，再次出现如果在队头则出队，保证队头是只出现一次的字符

从上到下打印二叉树

1. 广度优先搜索(BFS)需要借助队列

从上到下打印二叉树，每一层打印到一行

1. 使用队列，遍历存储当前层所有节点，同时把下一层节点入队
2. 使用递归，先序遍历。记录当前深度，放到对应层级的列表中

从上到下打印二叉树，之字形打印（第一行从左到右，第二行再从右到左，以此类推）

1. 使用队列，遍历存储当前层所有节点，同时把下一层节点入队
   1. 倒序存储1：偶数行使用Collection反转列表
   2. 倒序存储2：奇数行插入到尾部，偶数行插入到头部。使用LinkedList提高效率
2. 使用递归，先序遍历。记录当前深度，放到对应层级的列表中。递归倒序同理

判断树B是不是树A的子树

递归：判断两棵树是否相等 || 左子树是否等于树B || 右子树是否等于树B

二叉树的镜像

1. 广度优先遍历，借助栈，交换左右节点
2. 广度优先遍历，借助队列，交换左右节点
3. 递归，镜像反转左子树，镜像反转右子树，交换左右子树
4. 递归，新建树B。B右子树等于A的左子树、B左子树等于A的右子树

判断二叉树是否对称

1. 同时递归比较左子树和右子树

斐波那契数列

1. 递归（超时）：效率低，大量重复计算。如计算f(3)，需要计算f(2)和f(1)，计算f(2)又要计算一遍f(1)
2. 递归基础上建一个数组存储f(n)的值，避免重复计算
3. 动态规划，时间复杂度O(N)。状态转移方程：F(N) = F(N - 1) + F(N - 2)

青蛙跳台阶

1. 动态规划：f(n)=f(n-1)+f(n-2)