数据结构
链表
从尾到头打印链表
- 递归
dfs(){ 空的时候return
dfs()
list.add()
}
- add(0, val)
合并两个排序的链表
- 递归方法
merge函数返回的是合并后的链表的头节点，比较两个链表头节点的值，让小值节点指向，除这个节点外其余部分合并后的头节点
1 | public ListNode Merge(ListNode list1,ListNode list2) { |
- 迭代方法
需要创建两个节点变量，一个当虚拟头节点，用于返回最后合并后链表的头节点。另一个指向合并链表的末尾节点。
用单层循环，遍历两个链表。比较目前两个链表的值，哪个值小就该节点加入到新合并的链表中，并让该链表指针移动一个节点。
循环结束的条件是，有个链表指针移动到空值，这时候需要判断，把合并链表的末尾节点指向不为空的链表
node1.next = node2 链表连接操作
node1 = node1.next 链表遍历操作
反转链表
利用栈 不满足空间O(1)
先把链表依次压入栈中，然后弹栈，反向连接链表，但是记得把最后一个节点的next改为null三指针
previous current next三个指针
previous初始化为空 current 初始化为头 next 初始化为第二个
循环体内部
current.next = previous
previous = current
current = next
next = next.next
循环条件为 next !=null
因为循环体中先把当前节点指向前一个，再移动指针，循环结束时，还要把current.next = previous
对于两个以上节点，如上步骤操作
两个节点情况
一个节点情况
会跳过循环
空链表情况
因为初始化涉及next = head.next，要先判断head是否为空，如果为空，直接返回null
两个链表的第一个公共节点
栈 但不满足空间复杂度O(1)
两个链表都压入栈中，然后循环弹栈，当其中一个栈为空的时候要结束循环变为等长链表
如果是等长链表，就能同时逐个节点移动，一一比较，可以变为等长链表
链表一长度为a，链表二长度为b
a+b 等于 b+a 但是两个链表不能真的连接，不然就成环了，可以通过判断跳转至下一个链表**(发现遍历两个链表，不需要把两个链表连接在一起，自己的操作和要达成的目的并不是充分必要条件，可能会过强，导致一些副作用，可能会过弱，达不到预期目的)**
用while循环遍历两个链表，没发现公共节点的时候，循环结束的条件是两个链表的当前节点都为空，在进行两个链表转换的时候，currentNode1 = currentNode1==null ？head2 ： currentNode1.next，判断的条件不是currentNode1.next == null，这样链表就没有空指针的时候了，循环无法停止
有公共节点的时候，即节点相等的时候，循环同样停止，没公共节点的时候，循环结束条件为都为空指针，也是相等，循环停止的条件变为两个节点相等，然后发现该条件同样也适用于一个链表为空的情况
链表环的入口节点
- Set 不满足空间复杂度O(1)
遍历元素，依次加入Set中，第一个重复的元素就是环的入口节点
有环情况、无环情况、空链表情况 while(current != null) 都可以包含
- 快慢指针
这个分析的是shit，看代码随想录的分析更清楚
https://shimo.im/docs/KlkKVWN7OXtBvMqd
快指针是慢指针的2倍速度
A 头
B 环入口
C 相遇
D 慢到B时快的位置
当快指针与慢指针相遇时，快指针移动到头节点，快慢指针再次相遇时，就是入口节点
即证明 CDB = AB
D 为慢指针到B时，快指针的位置
AB * 2 = ABCD
AB = BCD
快慢指针在C点相遇，相遇前，慢指针从B移动到C，快指针从D移动到C
DC = BC * 2
DB = BC
已知AB = BCD DB = BC
AB = BC + CD
AB = BD + CD
AB = CDB
但是这只是线段的证明，没考虑端点和末尾，相遇后，在把快指针移动到头节点的时候，慢指针也要从C节点向前移动一格，否则不会与快指针相遇了，会落后一个节点
说错了，不会落后一个节点，因为一开始把fast设置成第二个节点了，自己写的屎代码，如果一开始fast 和 slow就相同，循环直接结束了
1 | ListNode slow = head; |
可以设置虚拟头节点，但是写起来代码比较复杂
可以把慢指针初始化头节点，快指针初始化第二个节点，即head.next
但是在使用head.next时需要先判断，head是否为空，为空时直接返回null
对于普通带环的，按如上情况正常运行结束
只有环的，会在入口节点前一个节点相遇，退出第一个循环，都向前进入到入口节点，不会进入第二个循环
一个节点的环，不会进入第一个循环，不会进入第二个循环
空链表直接返回
不带环的链表会在第一个循环发现空指针直接返回
链表中倒数最后k个结点
- 使用数组
遍历链表，逐个加入到数组中
返回list.get(list.size()-k)
判断当k>list.size()时返回null
同时也要判断 k = 0 返回null
链表长度为大于1，如上正常返回
链表长度为1时，k = 1 返回第一个 k>1返回null k= 0 返回null
链表为空 k=0返回null k>0返回null
- 双指针
快慢指针先指向头节点，快指针移动k次，快慢指针再同时移动，当快指针指向空时，相当于在倒数第0个，比慢指针领先k个，慢指针在倒数第k个
链表为空，k>0时
进入第一个for(int i=0; i<k; i++)循环，判断出链表为空，直接返回空
链表为空，k=0时
跳过第一个循环，跳过第二个循环，返回slow，slow指向头节点，为空指针
链表不为空，k=0时
跳过第一个循环，进入第二个循环，slow和fast都指向最后的空指针，并返回
链表不为空，0<k<size
进入第一个循环，移动快指针移动k步，进入第二个循环，慢指针和快指针同时，移动，直到快指针到末尾空指针，慢指针指向快指针后方的，倒数第k个节点
链表不为空，k=size
进入第一个循环，快指针指向空指针，跳过第二个循环，直接返回慢指针，慢指针指向头节点
链表不为空，k>size
进入第一个循环，当快指针移动到末尾空指针时，直接返回
- 记录索引法
先循环遍历一遍，得到链表长度size，然后再次遍历，当索引等于size-k时返回
当链表为空，k=0时，两个循环都不进入，直接返回current，此时current为pHead，为空
当链表为空，k>0时，两个循环都不进入，直接返回current，此时current为pHead，为空
当链表不为空，k=0时，进入第一个循环，得到链表长度，进入第二个循环，i等于size-k=size后，不会break，current指向末尾的null，返回null
当链表不为空，0<k<size时，进入第一个循环，得到链表长度，进入第二个循环，0<size-k<size，链表中的节点
当链表不为空时，k=size时，进入第一个循环，得到链表长度，进入第二个循环，size-k=0,第一个节点
当链表不为空时，k>size时，进入第一个循环，得到链表长度，进入第二个循环，size-k<0,不会break，current最终指向null
复杂链表深拷贝
- List列表 空间O(n) 时间O(n²)
遍历节点，根据每个节点的值创建新的链表节点，并加入到列表中，并把上一个新建的节点指向当前节点
再次遍历节点，获取获取每个节点的random指针，所指向链表的索引，根据索引值，在列表中找到新创建的节点，random指针指向该节点
- 哈希表
利用map把旧的节点和新创建的节点对应起来，这样用map.get(origin).random = map.get(orgin.random)就能很快连接起来
创建map
创建哨兵节点(何时需要创建哨兵节点?在链表循环遍历中，如一开始就需要操作上一个节点的next指针，就需要在循环外初始化一次循环体内部的操作，导致代码复杂，而如果在循环体外就创建虚拟的哨兵节点，就可以正常进入循环运行，无需复杂的初始化过程)
循环中，创建新节点，上一个节点指向新建的节点，新建节点加入map中，上一个节点以及当前节点向后移动一个节点
- 复制链表
一一复制节点，加到原来节点后面
根据旧节点的random指针确定新节点的random指针
删除链表中的旧节点
删除链表中特定值的节点
current.val == val时
previous.next = current.next;
删除链表中重复节点
- map记录数值出现的次数
遍历链表，利用map记录值出现的次数
利用previous与current指向上一个节点与当前节点，current的值只有一个时，current与previous移动一次；current的值大于等于2个时，current移动的次数current值出现的次数相等，previous.next指向current；
由于会对previous.next操作，需要利用哨兵，最后返回virtualHead.next
链表为空时，使用map记录次数的循环与，移动链表的循环，都会跳过，直接返回空
for循环时 i<number 注意这个number是不是一个定值，会不会与刚开始循环的值不一样，比如 i<map.get(current.val) current是会变化的，当current.val别的值时，map.get()也会变化，循环次数不可控制，所以要注意for循环i<number，这个number要是个确定的值，不能随着循环而改变
- set记录重复值或节点
使用previous与current遍历一遍，依次比较相邻节点的值，把值相等的节点加入到set中，就能找到所有相同的值
再次使用previous与current遍历一遍，如果set中有current的值，说明current重复，同时previous.next = current.next删除current节点
- 空间复杂度O(1)方法
关键思想: 使用current.val == current.next.val 判断是否是重复节点，如果是重复节点则循环找到最后一个重复的位置
总体思路: 使用previous与current遍历，利用current.val == current.next.val判断是否是重复变量，但是在current.next.val前还需要加上current.next != null && current.val == current.next.val 利用&&的短路功能，防止空指针异常
当判断是重复后，先向后移动一次current，然后利用循环while(current.next!=null && current.val==current.next.val) {current = current.next}找到最后一个重复节点，结束循环，current = current.next
previous.next = current
当判断不是重复后，current与previous都向后移动一次
二叉树
之字形顺序打印二叉树
- 队列
新建队列树节点类型队列，如果根节点为空返回空，如果不为空，根节点加入队列
进入循环，遍历队列中的节点
新建列表，保存每一层的值，保存当前队列的长度
进入内层循环，遍历当前层所有节点
节点出队
节点值加入列表
判断左节点是否为空，不为空加入队列
判断右节点是否为空，不为空加入队列
层数为偶数，反转列表
层数+1
tree BFS遍历模板
- 无需确定当前层
新建队列，根节点加入队列中
循环 (队列不为空)
节点出队
依次判断该节点的左右节点，节点不为空，则入队
- 需要确定当前层
初始化层数变量
新建队列，根节点加入队列中
循环 (队列不为空)
保存队列size
循环 (size–)
节点出队
依次判断该节点的左右节点，节点不为空，入队
层数+1
二叉树的深度
- 递归（分治法）
分治法简介：求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，然后合并左边，右边的解，从而求得最终解。具体可参考归并排序。
递归结束条件
节点为空时返回 0
节点不为空返回 max(dfs(left), dfs(right)) + 1
- 队列层先遍历
利用队列，层先遍历
判断根节点是否为空，为空返回0
不为空
level=0
新建队列
根节点加入队列
while(队列不为空)
size = 队列长度
while(size– != 0)
出队
如果左节点不为空 入队
如果右节点不为空 入队
level++
return level
二叉树的镜像
- 递归
二叉树的镜像其实就是所有的节点全部左右交换一下，左右子树依次交换
递归结束条件 空指针 或左右指针都为空
交换左右子树
左子树递归
右子树递归
1 | public class Solution { |
- 栈
首先判断根节点是否为空，为空的话直接返回
不为空的话加入栈中
循环(栈不为空)
出栈当作当前节点
左不为空 入栈
右不为空 入栈
交换当前节点左右子树
二叉搜索树的第K个节点
- 递归中序遍历
创建列表类型属性，保存二叉树的值
递归的方式中序遍历，保存二叉树的值
- 非递归中序遍历
current = root
while(current!=null || !stack.isEmpty()) {
while (current != null) {
// list.add() 这是前序遍历的操作位置
stack.push(current)
current = current.left
}
if (!stack.isEmpty()) {
current = stack.pop()
list.add(current.val)
current = current.right;
}
}
- 非递归中序遍历 不用列表
初始化counter为0
把list.add 替换为 if (++counter == k) return -1; 即可
重建二叉树
- 递归
前序遍历根左右，中序遍历左根右
前序遍历的第一个为根，在中序遍历中找到该值，左边为根的左子树，右边为根的右子树
前序遍历左子树部分仍热为前序遍历，前序遍历右子树部分仍为前序遍历
中序遍历左子树部分仍未中序遍历，
把左子树部分的前序遍历与中序遍历列表递归
把右子树部分的前序遍历与中序遍历列表递归
使用Arrays.copyOfRange()函数复制
递归结束条件是列表为空
根据前序遍历根的值创建树节点
找到前序遍历的根在中序遍历中的index值
node.left=fun(Arrays.copyOfRange(pre, 1, index+1), Arrays.copyOfRange(vin, 0, index))
node.right=fun(Arrays.copyOfRange(pre, index+1, pre.length), Arrays.copyOfRange(vin, index+1, vin.length))
0<=index<=length-1
1<=index+1<=length
Arrays.copyOfRange()允许越界至length，即Arrays.copyOfRange(list, length, length)为空
1 | public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { |
树的子结构
- 比较两个二叉树是否一样
原本以为对于一个元素不相同的两棵树，如果中序遍历相同，两棵树就相同，但是会有以下情况，中序遍历结果相同，但是两棵树不同
应该用递归法
isSame(root1, root2) {
if (root1==null || root2==null) {
return root1 == root2;
}
return root1.val==root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}
- 层序遍历+递归比较
递归比较两个树是否相同
递归函数
isSame(root1, root2) {
if (root2 == null) return true; // root2为空时，直接返回true，因为即使root1不为空也不用比较
if (root1 == null) return false; // root2不为空 但是root1为空 不相等
return root1.val==root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}
主函数
先判断root1与root2是否有空，如果有空根据题目直接返回false
遍历root1，依次用isSame()比较
1 | public boolean HasSubtree(TreeNode root1,TreeNode root2) { |
从上往下打印二叉树
- BFS
queue.add(root)
while(!queue.isEmpty()) {
current = queue.remove();
list.add(current.val);
if (current.left != null) queue.add(current.left)
if (current.right != null) queue.add(current.right)
}
4.24看到这里
二叉搜索树的后序遍历序列
- 递归
整体思路
搜索树后续遍历，左右根，最后一个节点是根节点，如果是序列是后续遍历的话，比根节点小的都在开头，是左子树部分，比根节点大的都在中间，是右子树部分，
是后续遍历的条件是开头连续一部分都比根节点小 剩余中间部分都比根节点大 开头与中间也都是后续遍历序列
犯的错误
找到了第一个比根大的index 使用index分左右应该是list.subList(0, index) list.subList(index, size-1)
0<=index<=size-1 不会出现越界问题 但是我写成了list.subList(index+1, size-1)三目运算？的优先级别不如逻辑运算符级别高
本来想表达 逻辑表达式1 && 逻辑表达式2 && (逻辑表达式3 ？true ：false)但是没有加括号，意思变成了
（逻辑表达式1 && 逻辑表达式2 && 逻辑表达式3） ？true ：false
解法
getIndex 找出第一个比根节点大的索引，如果找不到就返回size-1
allIsLarge 是否从第一个比根节点大的索引开始至倒数第二个节点都比根节点大
isBST 递归方法
递归结束条件
size为0返回true
找到index
return allIsLarge && isBST(subList(0, index)) && isBST(subList(index, size-1))
如果index为0， 左树列表为空 如果没有找到大的index 返回size-1 右树列表为空
对称的二叉树
- 递归
二叉树对称，比较对称位置的两个节点值是否相等，比较节点一左孩子和节点二右孩子是否相等，比较节点一右孩子和节点二左孩子是否相等
递归结束条件
有节点为空
return root1.val==root2.val && isSame(root1.left, root2.right) && isSame(root1.right, root2.left)
二叉树中和为某一值的路径(一)
- 递归
创建布尔类型属性，保存结果
递归一开始加上节点
如果是左右孩子都为空，判断是否等于目标值，是的话设置标志位
如果左孩子不为空 递归
如果右孩子不为空 递归
注意是叶子节点，要判断左右孩子是否都为空
- 递归
不创建布尔类型，太麻烦
递归结束条件
如果为空 返回false
sum -= root.val
if (root.left==null && root.right==null && sum==0) return true;
return dfs(root.left, sum) || dfs(root.right, sum)
二叉树中和为某一值的路径(二)
- 递归
dfs(root, currtentNum, tempList) {
// 终止条件
root == null return
// 中间操作
currtentNum -= root.val
tempList.add(root.val)
if (root.left==null && root.right==null && currentNum==0) {
this.result.add(new ArrayList<>(tempList));
}
dfs(root.left, currentNum, tempList)
dfs(root.right, currentNum, tempList)
// 回溯
tempList.remove(size-1)
}
二叉树中和为某一值的路径(三)
- 递归
整体思路：定义helper函数，查找以某个节点为根节点，路径和为目标值的数量。遍历树，把每个节点当成根节点，传入helper函数查找
helper(root, currentSum) {
// 终止条件
if (root == null) return;
currentSum -= root.val
if (currentSum == 0) this.result++;
helper(root.left, currentSum)
helper(root.right, currentSum)
}
判断是不是平衡二叉树
- 递归
平衡二叉树概念
左子树与右子树高度差绝对值小于等于1，且左子树与右子树都是平衡二叉树
二叉树的概念也是递归定义的，所以直接使用递归法判断平衡二叉树比较直接
boolean isBalance(root) {
// 递归结束条件，根据题目要求，空树也是平衡二叉树
if (root==null) return true;
leftDepth = getDepth(root.left)
rightDepth = getDepth(root.right)
return Math.abs(leftDepth-rightDepth)<=1 && isBalance(root.left) && isBalance(root.right);
}
getDepth(node)为递归函数，使用递归的方式求解树的高度
getDepth(node) {
if (node==null) return 0;
return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}
二叉搜索树与双向链表
中序遍历 保存到列表中
二叉搜索树，中序遍历是从小到大，保存到列表中，然后遍历列表，连接左右节点递归中序遍历，不使用列表
private previous;
Convert(root) {
if (root == null) return root;
TreeNode head = root;
// head.left != null 保证遍历停止在最后一个节点，而不是空节点
while (head.left != null) head = head.left
inOrder(root)
return head;
}
inOrder(node) {
if (node == null) return;
inOrder(node.left)
if (previous != null) {
// 上个节点为空的时候，跳过
previous.right = node
node.left = previous
}
previous = node
inOrder(nodel.right)
}
二叉树的下一个节点
- 中序遍历+列表
根据传入的节点，一致迭代next，知道root.next == null 找到根节点
根节点中序遍历，加入列表
遍历列表，找到传入的节点，返回下一个
- 中序遍历+双指针
类似与二叉搜索树与双向链表的解法，递归中序遍历二叉树，使用previous保存上一个节点，如果previous==pNode 返回遍历的当前节点
二叉树打印成多行
- bfs
首先需要判断传入的根节点是否为空，为空直接返回
创建队列，根节点入队
while(!queue.isEmpty()) {
// 外层循环创建size变量
int size = queue.size()
// 外层循环创建临时列表
while (size– > 0) {
// 内层循环创建current节点
Treenode current = queue.remove()
判断是否有左右子树，如果有就入队
}
}
在二叉树中找到两个节点的最近公共祖先
- 前序遍历，回溯，保存两个节点的访问路径，然后找到最后一个相同的节点，就是最近的公共祖先
本思路在牛客上始终通过不了，在leetcode没问题，牛客有问题
关键在于保存路径的列表，如果使用属性采用深拷贝的方式保存，可以不用设置判断条件终止后续的递归与回溯
如果传入列表的引用就需要及时停止对改列表修改，需要定义属性find
1 | private void preOrder(TreeNode node, List<Integer> list, int value) { |
- 递归 后续遍历
int lowestCommonAncestor(TreeNode root, int o1, int o2)
函数的返回类型是整型，利用该值向上父节点传递，如果为-1，表示父节点的这条后代没有目标节点，不为-1，表示有目标节点，如果父节点的左右孩返回的都不为空，表示该父节点就是最近的公共祖先，向上传递父节点的值
1. 确定返回值与参数
int lowestCommonAncestor(TreeNode root, int o1, int o2)
2.确定终止条件
if (root == null) return -1;
if (root.val==o1 || root.val==o2) return root.val;
3.单层递归逻辑
采用后序遍历，可以自底向上回溯
int left = lowerstCommonAncestor(root.left, o1, o2);
int right = lowerstCommonAncestor(root.right, o1, o2);
left表示该节点的左孩子中是否找到目标节点，-1表示没找到，不为-1表示找到了
right表示该节点的右孩子中是否找到目标节点，-1表示没找到，不为-1表示找到了
1 | if (left!=-1 && right!=-1) { |
如果左右都不为-1，说明该父节点就是最近的公共祖先，向上传递
如果一个为-1，一个不为-1，说明找到了目标节点，或者找到了公共祖先，想上传递
如果都为-1，说明什么都没找到，向上传递-1
二叉搜索树的公共祖先
- 前序遍历，递归
如果目标值一个小于等于根节点，一个大于等于根节点，说明在这个节点，两个目标节点分叉的，那么这个节点就是最近的公共祖先
1.确定递归函数返回值与参数
void preOrder(TreeNode root, int p, int q)
2.确定终止条件
if(this.find || root==null) return;
3.确定单层递归逻辑
前序遍历，先处理再递归
1 | // p在左边q在右边，或者q在左边p在右边，两种情况都要考虑 |
对find的检查放到开头，所有已经遍历了左孩子的节点，还要进入右孩子的函数，但是进入后立即返回
- 前序遍历，只遍历一边，把值传递给上层
能理解什么是只遍历一边了，就是二叉树有两边，根据某个条件判断，要搜索的目标是在左边还是在右边，这样就不用全部遍历了
递归函数的作用是找到最近的祖先节点，并返回，因为是二叉搜索树，并且q,p肯定在二叉树节点中，那么肯定能找到父节点
1.递归函数返回值与参数
int lowestCommonAncestor (TreeNode root, int p, int q)
2.确定递归终止条件
因为肯定能找到父节点，终止条件是找到父节点就终止
3.单层递归逻辑
1 | if (p<root.val && q<root.val) { |
- 迭代法
利用循环从根向下寻找，如果目标节点都小于当前节点，说明公共节点在左边，搜索左节点
如果目标节点都大于当前节点，说明公共节点在右边，搜索右节点
如果当前节点落到目标节点的闭区间内，说明当前节点就是最近公共祖先，返回jike
1 | public int lowestCommonAncestor (TreeNode root, int p, int q) { |
序列化二叉树
- 层序遍历
思路
序列化：
如果节点不为空，就把其值加入到字符串列表中，并且左右节点全都入队
如果节点为空，则把#加入到字符串列表中
反序列化：
每次循环从字符串列表中读取两个字符串，作为左右节点的值，如果不为”#”，则创建节点，作为左右孩子节点，并且加入队列中，队列中都是待分配左右节点的节点
注意与**”#”比较不能用==,要用equals**==是比较内存地址是否相等，equals才是比较内容是否相等。
序列化：
层序遍历步骤
- 首先判断根节点是否为空，为空直接返回
- 新建队列，根节点入队
- 其他初始化操作(新建字符串列表，用于保存序列化后的值)
- 进入循环while(!queue.isEmpty())
循环
节点出队
如果当前节点不为空，值变为字符串，加入字符串列表，左右孩子入队
如果当前节点为空，”#”加入字符串队列
使用String.join(“ “, 把字符串列表变成字符串)
1 | String Serialize(TreeNode root) { |
反序列化
空字符串返回空节点
字符串利用split(“ “)拆分成字符串列表
新建队列，用字符串列表第一个值生成根节点，根节点入队
每次循环，队列头节点出队，从字符串列表中取出两个值，用于生成左右孩子节点，如果不为”#”，生成孩子节点，并入队，如果为”#”，不用生成，不用为左右节点赋值，默认为空
1 | TreeNode Deserialize(String str) { |
栈和队列
栈的压入弹出序列
- 辅助栈
新建一个栈，遍历压入序列，每次都把压入序列入栈
循环判断栈顶元素是否和弹出序列元素相等
相等就弹栈，弹出序列向后移动
栈为空返回true 栈不为空返回false
两个栈实现队列
- push的时候直接push到stack1中
- pop的时候分两个情况
- stack2为空时，把stack1中的依次弹出来，压到stack2中，这样栈底就会变成栈顶，先进的也会先出，最后返回stack2弹出的元素
- stack2不为空，直接返回stack2弹出的顶部元素
包含min函数的栈
两个栈
push pop peek正常栈的操作，min的时候依次弹出到临时栈中，找到最小，然后再从临时栈中弹回去两个栈优化
上述方法min函数时间复杂度O(n)，可以改进，辅助栈为最小值栈，对应正常栈的最小值
辅助栈始终保持栈顶是最小值
压入的时候，正常栈压入，辅助栈压入栈顶元素与待压入元素的最小值
弹出的时候都弹出
top时正常栈peek
min时返回最小栈栈顶
反转单词
- 双指针
遍历字符串，根据空格字符与是否到最后，使用i，j索引截取单词，利用substring截取string，压入栈中
依次弹栈，字符串累加得到最后结果
空格的时候不用包含空格，是最后一个字符的时候需要i++，不然会漏掉最后一个字符
substring(j, i)
StringBuilder
使用StringBuilder保持单词，当是空格的时候或者遍历到最后的时候把保存的单词压入栈中，但是是空格的时候空格字符不要加入单词，到最后的时候最后一个字符要加入单词。split() 和 join()
使用words = split(“ “)把字符分成字符数组
然后String.join(“ “, words)连接起来但是要反转数组，反转数组模板
for (int i=0; i<n/2; i++){
temp = array[i];
array[i] = array[n-1-i];
array[n-1-i] = temp;
}
- split() join() 使用Collections.reverse()反转
使用Arrays.asList()把数组转成list
但是转成的是list是Arrays内部定义的一个ArrayList 不支持增删
滑动窗口的最大值
暴力法
找到所有窗口，每个窗口找最大单调队列
思路
- 单调队列就是单调增或单调减的队列，使用单调减队列找窗口最大值
- 单调队列入队时，入队元素大于队尾元素，在队尾弹出，直到队尾元素大于等于入队元素，或者为空，然后把元素入队
- 单调队列出队时，如果出队的元素为队头元素则出队，否则不操作
- 滑动窗口移动时，进滑动窗口的元素入队，出滑动窗口的元素出队，队首就是该窗口的最大值
1 | private class MyQueue { |
