剑指offer21到30题总览：
- 栈的压入、弹出序列
- 从上往下打印二叉树
- 二叉搜索树的后序遍历序列
- 二叉树中和为某一值的路径
- 复杂链表的复制
- 二叉搜索树与双向链表
- 字符串的排列
- 数组中出现次数超过一半的数字
- 最小的K个数
- 连续子数组的最大和
21、栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解题思路
使用一个辅助栈，先找到第一个pop出的元素popA[0]在pushA中的位置，将该位置记为pushIndex(pushIndex表示曾经入栈过的元素的最远距离)，并将pushA中该元素之前的所有元素入栈。如果下一个popA元素不等于栈顶元素，则看能不能继续入栈：如果可以继续入栈且下一个要入栈的元素就是要pop出的元素，则pushIndex++；如果可以继续入栈但下一个要入栈的元素并不是要pop出的元素，则元素入辅助栈，pushIndex++。如果不能继续入栈，则返回false。
注意事项
- 在找第一个popA[0]时，有可能在pushA中根本没有popA[0]这个元素。
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0){return true;}
boolean flag = true;//flag默认true，如果方法运行完没有发现序列不符合的情况，则返回flag。
Stack<Integer> stack = new Stack<>();
int pushIndex = -1;
for(int i=0; i<pushA.length; i++){//找到第一个pop的数在push序列中的位置，并将其前面的数全部入栈
if(pushA[i] != popA[0]){
stack.push(pushA[i]);
}else{
pushIndex = i;//在pushA中找到了popA[0]，记录下标，表示当前push的最远距离。
break;
}
}
if(pushIndex==-1){return false;}//如果在pushA中没有找到popA[0]，则返回false。
for(int i=1; i<popA.length; i++){
if(popA[i]!=stack.peek()){//当前栈顶元素不是当前要pop的数
if(pushIndex+1 < pushA.length){//pushA还有下一个
if(popA[i]!=pushA[pushIndex+1]){//下一个不是要pop的数，则继续入栈
stack.push(pushA[pushIndex+1]);
pushIndex++;
}else{//下一个就是要pop的数
pushIndex++;
}
}else{//已经全部入栈
return false;
}
}else{//当前栈顶元素就是要pop的数
stack.pop();
}
}
return flag;
}
}
22、从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解题思路
中序遍历
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if(root == null){return list;}//如果root为空，则返回空list
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);//先将根节点入队列
while(!queue.isEmpty()){
TreeNode node = queue.poll();//取队头元素，将val加入list
list.add(node.val);
if(node.left!=null){queue.offer(node.left);}//将其左右子结点如队列
if(node.right!=null){queue.offer(node.right);}
}
return list;
}
}
23、二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路
序列的最后一个数即为数的根节点，其左子树上的结点比根节点小，其右子树上的结点比根节点大。遍历序列找到第一个比根节点大的数，将序列分为左右根三部分。遍历第二部分(对应右子树的部分)，如果发现有比根节点小的，则返回false，如果没有发现比根节点小的，则递归左右子树。
注意事项
- 找到第一个比根节点小的数后，要判断对应右子树的部分是否都比根节点大。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){return false;}//用例规定seq为空时返回false
return verify(sequence, 0, sequence.length);
}
public boolean verify(int[] sequence, int start, int end){
if(end-start<=0){return true;}//如果该段序列长度为0，则返回true
int root = sequence[end-1];
int index = end-1;
for(int i=start; i<end-1; i++){//保存第一个比根节点小的数的下标
if(sequence[i] > root){
index = i;
break;
}
}
for(int i=index; i<end-1; i++){//遍历对应右子树的数是否都比根节点大
if(sequence[i] < root){
return false;
}
}
return verify(sequence, start, index) && verify(sequence, index, end-1);//递归左右子树
}
}
24、二叉树中和为某一值的路径
题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
解题思路
深度遍历，并设置回退机制。每访问一个节点，target减少val，当遇到叶子节点的时候(左右子树均为空)，判断target与叶子节点的值是否相等。如果相等，则将该叶子节点加入list，将path加入最终结果，并将list该叶子节点再取出，回退；如果不相等，则该path并不符合，list中不加入该叶子节点。当遇到非叶子节点的时候，将root.val加入list，target减去root.val，递归。遍历完左子树之后，在遍历右子树之前，要回退一步。
注意事项
- 回退机制。
- list要复制之后再加入最终path中，否则传入的是同一个list的引用。
- 数字均为整数但不一定一定为正数，所以一定需要遍历到最深处。
public class Solution {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();//存储符合要求的path
ArrayList<Integer> list = new ArrayList<>();//list保存当前路径，如果需要回退则remove
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root != null){
if(root.left==null && root.right==null){//如果当前根结点为叶子结点
if(target == root.val){//如果相等，则为符合要求的path
list.add(root.val);//将当前根结点加入list
result.add(new ArrayList<Integer>(list));//初始化一个新list，加入result中
list.remove(list.size()-1);//移除当前根结点，回退
}
}else{//如果当前根结点不是叶子节点，则需要递归左右子树
if(root.left!=null){//左子树不为空
list.add(root.val);//将当前根结点加入list
FindPath(root.left, target - root.val);//递归，target减少
list.remove(list.size()-1);//回退
}
if(root.right!=null){
list.add(root.val);
FindPath(root.right, target-root.val);
list.remove(list.size()-1);
}//写的比较重复，可更简洁
}
}
return result;
}
}
25、复杂链表的复制
题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
对原链表中的每个结点，都新建一个新结点，插入到原结点的后面。所有结点插入完毕后，复制random指针，要注意有的random为空。random指针复制完后，拆分链表。
注意事项
- 有的random指针为空，则不需要复制。
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null){return null;}//如果链表为空，则返回空
RandomListNode p = pHead;
while(p != null){//新建结点插入到每个结点的后面
RandomListNode node = new RandomListNode(p.label);
node.next = p.next;
p.next = node;
p = node.next;
}
RandomListNode head = pHead.next;//head为拷贝的新链表的head
p = pHead;
while(p != null){//拷贝random指针，注意有的random结点为空
if(p.random!=null){
p.next.random = p.random.next;
p = p.next.next;
}else{
p = p.next;
}
}
p = pHead;
RandomListNode q = p.next;
while(p.next.next != null){//拆分链表
p.next = q.next;
p = p.next;
q.next = p.next;
q = q.next;
}
p.next = null;
return head;
}
}
26、二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
中序遍历，前一个pop出的结点为pre，当前结点为curr。
import java.util.Stack;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){return null;}
Stack<TreeNode> stack = new Stack<>();//新建栈
stack.push(pRootOfTree);//根结点入栈
while(pRootOfTree.left!=null){//将从根节点到最左边的节点全部入栈，返回的链表的头节点，就是最左边的结点(最小的结点)
pRootOfTree = pRootOfTree.left;
stack.push(pRootOfTree);
}
TreeNode pre = null;//pre为上一个pop的结点，一开始为null
TreeNode curr = null;//当前节点
while(!stack.empty()){
curr = stack.pop();//pop出栈顶元素
curr.left = pre;//当前结点的上一个结点(left)为pre
if(pre!=null){//pre结点的下一个结点(right)为当前结点
pre.right = curr;
}
pre = curr;//pre变为当前结点
if(curr.right!=null){//访问当前结点的右结点，如果有右结点则入栈
curr = curr.right;
stack.push(curr);
while(curr.left!=null){//将该右结点往下的所有左结点入栈
curr = curr.left;
stack.push(curr);
}
}
}
return pRootOfTree;
}
}
27、字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路
字符的全排列，主要是用交换两个字符的方法进行。要注意如果要交换的两个字符相等，则不需要交换。
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
ArrayList<String> list = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if(str == null || str.length()==0){}
permu(str.toCharArray(), 0);//全排列
Collections.sort(list);//permu方法不管顺序，需要sort
return list;
}
public void permu(char[] chars, int index){
char temp;//temp用来交换字符
if(index==chars.length-1){//chars[index]为当前要确定的字符
list.add(String.valueOf(chars));//到了要确定最后一个字符，已经没有字符可以交换了，可以直接加入list
}else{
for(int i=index; i<chars.length; i++){//从要确定的index位开始
if(i==index){//index位和index位不需要交换，已确定确定index位，递归确定下一位
permu(chars, index+1);//直接递归下一位
}else{//index位与后面的位进行字符交换
if(chars[i]!=chars[index]){//当字符不相同时交换
temp = chars[index];//交换index和i
chars[index] = chars[i];
chars[i] = temp;
permu(chars, index+1);//交换后递归
temp = chars[index];//交换回来
chars[index] = chars[i];
chars[i] = temp;
}
}
}
}
}
}
28、数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路
一种是hashmap，另一种为阵地攻守思想。阵地攻守思想参考牛客网作者：cm问前程https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
阵地攻守的思想：
第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length==0){return 0;}
if(array.length==1){return array[0];}
int result = array[0];//先将第一个元素记做result，count计1
int count = 1;
for(int i=1; i<array.length; i++){//遍历数组，阵地攻守
if(count==0){//如果count被灭为0
result = array[i];//将当前数记为result，count计1
count++;
}else{
if(array[i]!=result){//遇到不同的数则count-1
count--;
}else{//遇到相同的数则count+1
count++;
}
}
}
count = 0;
for(int i=0; i<array.length; i++){//再遍历一次，记录上次遍历找到的result出现的次数，用于检查出现次数是否大于length的一半
if(array[i] == result){
count++;
}
}
if(count <= array.length/2){return 0;}//检查出现次数
return result;
}
}
29、最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
解题思路
堆排序，构造小顶堆，即可找到k个最小值；或者用大数淘汰法，构建一个k个数的大顶堆，每次加入一个数，如果比顶大，则淘汰掉顶，重新调整。
注意事项
- 下面的代码是用k个数的PriorityQueue实现的，
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)，在new一个PriorityQueue的时候可以设置initialCapacity为k，同时可以实现Comparator接口。
- Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。实现了Comparable接口的类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
- Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
- 经过实践，该题返回结果的list不需要升序排列。
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(k==0){return list;}
if(input.length < k){return list;}
//建立一个大顶堆，如果不传入实现的比较器则默认小顶堆
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return b - a;
}
});
for(int i=0; i<input.length; i++){
if(queue.size()<k){//堆不满k个数时直接offer
queue.offer(input[i]);
}else{
if(input[i]<queue.peek()){//遇到了更小的数则poll，offer入新数
queue.poll();
queue.offer(input[i]);
}
}
}
for(Integer i: queue){//实践证明该题不需要将list中的数排序
list.add(i);
}
return list;
}
}
30、连续子数组的最大和
题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解题思路
动态规划思想：牛客网链接：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
：以
为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变。
：所有子数组的和的最大值
示例：数组
：
：
：
：
：
以此类推，最终的值为8。
从上面的例子可以看到，我们计算以i=4为结尾的子数组最大值的时候，得到
，为负数，那么当我们计算
的时候，只要
为整数，那么前面的数加上
一定没有甩开前面的数，直接从
开始的子串数组要大，所以这时我们会从
开始重新计算子数组和。
这个题不需要输出到底是哪个子串，所以只需要实时更新最大的子串就行。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0){}//题目没说数组长度为0时返回什么
int max = array[0];//先对数组下标为0的位置设置0，赋初值
int result = array[0];
for(int i=1; i<array.length; i++){//这里从i=1开始计算
max = Math.max(max+array[i], array[i]);//转移公式，意义是计算是否要丢弃前面的数，从array[i]开始计算子数组
result = Math.max(max, result);//得到更大的result
}
return result;
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
