剑指Offer（三）

题目汇总
21.调整数组顺序使奇数位于偶数前面（简单），本题考查代码的完整性
22.链表中倒数第k个结点（简单），本题考查代码的鲁棒性
23.链表中环的入口结点（中等），本题考查链表
24.反转链表（简单），本题考查代码的鲁棒性
25.合并两个排序的链表（简单），本题考查代码的鲁棒性，大量指针操作容易出错。
26.树的子结构（中等），本题考查代码的鲁棒性。含有大量的指针操作，程序容易崩溃，每次使用指针的时候，都要想如果为空该怎么处理。
27.二叉树的镜像（简单），本题考查面试思路， 可以通过画图让抽象形象化
28.对称的二叉树—二叉树的镜像变形（简单），本题考查画图让抽象形象化
29.顺时针打印矩阵（简单），本题考查画图让抽象形象化
30.包含min函数的栈（简单），本题考查举例让抽象形象化

21.调整数组顺序使奇数位于偶数前面（简单），本题考查代码的完整性

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路一：

扫描数组，如果有偶数出现在奇数的面前，就交换他们的顺序

public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-1-i;j++){
                if(array[j]%2==0&array[j+1]%2==1){
                    int t=array[j];
                    array[j]=array[j+1];
                    array[j+1]=t;
                }
            }
        }
    }
}

思路二：

使用两个list集合，一个存奇数，一个存偶数，然后依次将数赋值回原数组

import java.util.ArrayList;
import java.util.List;
public class Solution {
    public void reOrderArray(int [] array) {
        if(array==null||array.length==1)
            return ;
        List list1=new ArrayList<Integer>();
        List list2=new ArrayList<Integer>();
        for(int i:array){//array，每次遍历的对象用i这个对象去接收
            if(i%2==1){//奇数存在list1
                list1.add(Integer.valueOf(i));
            }else{//偶数存在list2
                list2.add(Integer.valueOf(i));
            }
        }
        list1.addAll(list2);
        for(int i=0;i<array.length;i++){
            array[i]=((Integer)list1.get(i)).intValue();//取出list1中第i个元素,把Integer类型转化为int类型
        }     
    }
}

22.链表中倒数第k个结点（简单），本题考查代码的鲁棒性

输入一个链表，输出该链表中倒数第k个结点。例如，一个链表有6个结点，从头结点开始，他们的值依次是1、2、3、4、5、6，这个链表的倒数第三个结点是值为4的结点。
相关知识点：代码的鲁棒性
鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理，并不是所有的与鲁棒性相关的问题都只是检查输入的参数这么简单。
“链表中倒数第k个结点”这里隐藏着一个条件，即链表中结点的个数大于k，如果链表中结点的数目不是大于k个，那么代码会出现什么问题。

思路一：

倒数第k个结点即为正数第n-k+1个结点，遍历链表两次，第一次从头开始遍历链表，每经过一个结点，计数器加1，统计出链表结点的个数n，第二次找到倒数第k个结点。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        int n = 0;
        if(head!=null){
            n++;
        }else{
            return null;
        }
         // 计算总结点数
        ListNode currentNode = head.next;
        while(currentNode != null){
            n++;
            currentNode = currentNode.next;
        }
        if(n < k){
            return null;
        }
        // 倒数第k个为正数第n-k+1个
        ListNode resultNode = head;
        for(int i=1; i<=n-k; i++){
            resultNode = resultNode.next;
        }
        return resultNode;
    }
}

思路二：

只遍历链表一次。定义两个指针，第一个指针从头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。两个指针的距离保持在k-1，当第一个指针到达链表的尾结点时，第二个指针正好指向倒数第k个结点。
关于鲁棒性的三种情况在程序中进行了处理
1.输入的ListNode为空指针
2.输入的k为0
3.输入的链表的结点总数少于k

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0 ){
            return null;
        }
        ListNode pFast=head;
        for(int i=0;i<k-1;i++){
            if(pFast.next!=null){
                pFast=pFast.next;
            }
            else{
                return null;
            }
        }
        ListNode pSlow=head;
        while(pFast.next!=null){
            pFast=pFast.next;
            pSlow=pSlow.next;
        }
        return pSlow;
    }
}

举一反三

当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步）或者让他先在链表上走若干步。

23.链表中环的入口结点（中等），本题考查链表

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：

第一步是确定一个链表中包含环。定义两个指针，同时从链表的头结点出发，快指针一次走两步，慢指针一次走一步。如果快指针追上了慢指针，那么链表就包含环；如果快指针走到了链表的末尾都没有追上慢指针，那么链表就不包含环。
第二步是找到环的入口。定义两个指针指向链表的头结点，如果链表中的环有n个结点，则第一个指针先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈，又回到了入口结点。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null)
            return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean flag = false;
        //确定一个链表中包含环
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                flag = true;
                break;
            }
        }
        if(!flag){
            return null;
        }
        else{//得到环中结点数目n
            int n = 1;
            fast = fast.next;
            while(fast!=slow){
                fast = fast.next;
                n++;
            }
             //找到环的入口结点
            ListNode p1 = pHead;
            ListNode p2 = pHead;
            //移动p1，次数为环中结点的个数
            for(int i=0;i<n;i++){
                p1 = p1.next;
            }
            //再移动p1和p2
            while(p1 != p2){
                p2 = p2.next;
                p1 = p1.next;
            }
            return p2;
        } 
    }
}

24.反转链表（简单），本题考查代码的鲁棒性

输入一个链表，反转链表后，输出新链表的表头。

思路：

摘自牛客网题解，自己写不明白

思路.jpg

见网址https://blog.nowcoder.net/n/2b3b3f502ee84080a1874f1d3ebb896e?f=comment

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
       // 判断链表为空或长度为1的情况
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = null; // 当前节点的前一个节点
        ListNode next = null; // 当前节点的下一个节点
        while( head != null){
            next = head.next; // 记录当前节点的下一个节点位置；
            head.next = pre; // 让当前节点指向前一个节点位置，完成反转
            pre = head; // pre 往右走
            head = next;// 当前节点往右继续走
        }
        return pre;
    }
}

25.合并两个排序的链表（简单），本题考查代码的鲁棒性，大量指针操作容易出错。

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

合并两个排序链表的过程.png

思路一：迭代

链接：https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337?answerType=1&f=discussion

来源：牛客网

• 如果 list1和 list2，均没遍历完：
  • 如果 list1.val <= list2.val，那么当前结点的 next 指向 list1。并且移动 list1指针。
  • 否则，当前 结点的 next 指向 list2，移动 list2指针。
  • 移动 cur指针
  • 继续循环
• 否则，结束循环：
  • 如果 list1未遍历完，当前结点的 next 指向 list1
  • 如果 list2未遍历完，当前结点的 next 指向 list2

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)
            return list2;
        else if(list2==null)
            return list1;
        ListNode h = new ListNode(0);
        ListNode cur = h;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1=list1.next;
            }
            else{
                cur.next=list2;
                list2=list2.next;
            }
             cur = cur.next;
        }
        if(list1!=null) cur.next = list1;
        if(list2!=null) cur.next = list2;
        return h.next;
    }
}

思路二：递归

当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，因此合并的步骤和之前的步骤是一样的，这是一个递归过程，可以定义递归函数完成这一合并过程。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)
            return list2;
        else if(list2 == null)
            return list1;
        ListNode cur = null;
        if(list1.val<list2.val){
            cur = list1;
            cur.next = Merge(list1.next,list2);
        }
        else{
            cur = list2;
            cur.next = Merge(list1,list2.next);
        }
        return cur;
    }
}

26.树的子结构（中等），本题考查代码的鲁棒性。含有大量的指针操作，程序容易崩溃，每次使用指针的时候，都要想如果为空该怎么处理。

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

树B是树A的子结构.png

思路：用递归去遍历

第一步：在树A中找到和树B的根节点的值一样的结点R
第二步：判断树A中以R为根节点的子树是不是包含和树B一样的结构

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
        if(root1!=null&&root2!=null){
            if(root1.val==root2.val)
                result = judgeSubTree(root1,root2);
            if(!result)
                result = HasSubtree(root1.left,root2);
            if(!result)
                result = HasSubtree(root1.right,root2);
        }
        return result;
    }
    public boolean judgeSubTree(TreeNode root1, TreeNode root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return judgeSubTree(root1.left, root2.left) && judgeSubTree(root1.right, root2.right);
    }
}

递归调用HasSubtree遍历二叉树A。如果发现某一节点的值和树B的头节点的值相同，则调用judgeSubTree，进行第二步判断。

27.二叉树的镜像（简单），本题考查面试思路， 可以通过画图让抽象形象化

操作给定的二叉树，将其变换为源二叉树的镜像。

两颗互为镜像的二叉树.png

思路：

先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左右子节点之后，就得到了树的镜像。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return ;
        if(root.left==null&&root.right==null)
            return ;
        //交换根节点的左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //递归
        if(root.left!=null)
            Mirror(root.left);
        if(root.right!=null)
            Mirror(root.right);
    }
}

28.对称的二叉树—二叉树的镜像变形（简单），本题考查画图让抽象形象化

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：递归

一个二叉树同此二叉树的镜像相同，则是对称的。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        return isSymmetrical(pRoot,pRoot);
    }
    boolean isSymmetrical(TreeNode pRoot1,TreeNode pRoot2){
        if(pRoot1==null&&pRoot2==null)
            return true;
        if(pRoot1==null||pRoot2==null)
            return false;
        if(pRoot1.val!=pRoot2.val)
            return false;
        return isSymmetrical(pRoot1.left,pRoot2.right)&&isSymmetrical(pRoot1.right,pRoot2.left);
    }
}

29.顺时针打印矩阵（简单），本题考查画图让抽象形象化

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路一：设置上下左右四个界限法

定义四个变量代表范围，up、down、left、right
1.向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
2.向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
3.向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
4.向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错

//定义四个变量，不断地收缩矩阵的边界
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return list;
        }
        int up = 0;//上边界
        int down = matrix.length - 1;//下边界，行数-1
        int left = 0;//左边界
        int right = matrix[0].length - 1;//右边界，列数-1
        while(true){
            //最上边一行，向右走存入整行的值
            for(int col=left;col<=right;col++){
                list.add(matrix[up][col]);
            }
            up++;//向下逼近
            if(up>down){
                break;
            }
            //最右边一列，向下走存入整列的值
            for(int row=up;row<=down;row++){
                list.add(matrix[row][right]);
            }
            right--;//向左逼近
            if(right<left){
                break;
            }
            //最下边一行，向左走存入整行的值
            for(int col=right;col>=left;col--){
                list.add(matrix[down][col]);
            }
            down--;//向上逼近
            if(down<up){
                break;
            }
             //最左边一列，向上走存入整列的值
            for(int row=down;row>=up;row--){
                list.add(matrix[row][left]);
            }
            left++;//向右逼近
            if(left>right){
                break;
            }
        }
     return list;
    }
}

思路二：把矩阵看成若干个顺时针方向的圈组成***

见Offer第2版Page163

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix.length <=0 || matrix == null)
           return list;
        int start = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        while(rows > start * 2 && cols > start * 2){
            print(matrix,rows,cols,start);
            start ++;
        }
        return list;
    }
    //打印一圈
    public void print(int [][] matrix, int rows, int cols, int start){
        int endX = cols - start - 1;
        int endY = rows - start - 1;
        //从左到右打印一行
        for(int i=start; i<=endX; i++){
            list.add(matrix[start][i]);
        }
        //从上到下打印一列
        if(start<endY){
            for(int i=start+1; i<=endY; i++){
                list.add(matrix[i][endX]);
            }
        }

        //从右到左打印一行
        if(start<endX && start<endY){
            for(int i=endX-1; i>=start; i--){
                list.add(matrix[endY][i]);
            }
        }
        //从下到上打印一列
        if(start<endX && start<endY-1){
            for(int i=endY-1; i>=start+1; i--){
                list.add(matrix[i][start]);
            }
        }
    }
}

30.包含min函数的栈（简单），本题考查举例让抽象形象化

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

整理一下JAVA中栈的常用方法

Stack()定义一个空栈
empty()栈空返回真，否则返回假
push()入栈
pop()栈顶值出栈
peek()获取栈顶值，不出栈
search(Object o)返回对象O在栈中的位置（以1开始）

思路：

使用两个栈，一个数据栈用来存所有元素，一个辅助栈用来存加入新元素之后每次的最小元素
举例：栈内压入4,3,2,1之后接连两次弹出栈顶数字再压入0时，数据栈，辅助栈，最小值的状态

举例.png

import java.util.Stack;

public class Solution {
    Stack<Integer> stack_data = new Stack<>();//数据栈
    Stack<Integer> stack_min = new Stack<>();//辅助栈
    
    public void push(int node) {
        stack_data.push(node);
        if(stack_min.empty()){
            stack_min.push(node);
        }
        else{
            if(node<stack_min.peek()){
                stack_min.push(node);
            }
            else{
                stack_min.push(stack_min.peek());
            }
        }
    }
    
    public void pop() {
        stack_data.pop();
        stack_min.pop();
    }
    
    public int top() {
        return stack_data.peek();
    }
    
    public int min() {
        return stack_min.peek();
    }
}