三天刷完《剑指OFFER编程题》--Java版本实现（第一天）

最新推荐文章于 2022-09-08 16:31:50 发布

蜘蛛侠不会飞

最新推荐文章于 2022-09-08 16:31:50 发布

阅读量2.4k

点赞数 3

分类专栏：剑指offer 文章标签： java 算法面试刷题剑指offer

本文链接：https://blog.csdn.net/qq_40587575/article/details/106996017

版权

剑指offer 专栏收录该内容

17 篇文章

订阅专栏

正在更新中。。。。。。。。。

剑指offer --Python版本的实现：

剑指offer（1/3）第一大部分

剑指offer（2/3）第二大部分

剑指offer（3/3）第三大部分

----------------------------------------------------

《剑指offer》Java版本实现：

《剑指offer》Java版本-第一天

《剑指offer》Java版本-第二天

《剑指offer》Java版本-第三天

1.二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

从左下角开始搜索，如果该数大于目标数，则行数减去 1，向上搜索小的数值；

如果小于目标数，则列数 + 1 ，向左边搜索，搜索更大的数值

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length-1;
        int col = 0;  // 从左下角开始搜索,array.length 表示行的大小，array[0].length表示列的大小
        
        while (row >= 0 && col <= array[0].length-1){
            if (array[row][col] == target){
                return true;
            }else if(array[row][col] > target){
                row--;
            }else{
                col++;
            }
            
        }
        return false;

    }
}

2.替换空格

请实现一个函数，将一个字符串中的空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

第一种方法：新开一个内存空间

public class Solution {
    public String replaceSpace(StringBuffer str) {
        //创建一个新的空间
        StringBuffer out = new StringBuffer();
        for (int i = 0; i < str.length(); i++){
            char a = str.charAt(i);
            if (a == ' '){
                out.append("%20");
            }else{
                out.append(a);
            }
        }
        return out.toString();
    	
    }
}

第二种方法：不开辟新的空间，从后面往前面移动

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	// 计算空格的数量
        int spaceNum = 0;
        for (int i = 0; i < str.length(); i++){
            char a = str.charAt(i);
            if (a == ' '){
                spaceNum ++;
            }
        }
        
        // 开辟空间
        int oldIndex = str.length()-1; // 原字符串的下标
        int newLength = str.length() + spaceNum * 2;
        int newIndex = newLength -1;
        str.setLength(newLength); // 重新设置字符串的长度
        
        while(newIndex >= 0){
            if (str.charAt(oldIndex) != ' '){
                str.setCharAt(newIndex, str.charAt(oldIndex));
                oldIndex --;
                newIndex --;
            }else{
                str.setCharAt(newIndex--, '0');
                str.setCharAt(newIndex--, '2');
                str.setCharAt(newIndex--, '%');
                oldIndex--; // 只进行一次减 1
            }
        }
        
        return str.toString();
        
        
    }
}

3.从尾到头打印单链表值

第一种：使用数组

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList();
        if (listNode == null){
            return res;
        }
        
        while(listNode != null){
            res.add(listNode.val);
            listNode = listNode.next;
            
        }
        ArrayList<Integer> ress = new ArrayList();
        for(int i = res.size()-1; i >= 0; i--){
            ress.add(res.get(i));
        }
        return ress;
        
    }
}

第二种方法：使用栈

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 使用栈结构实现
        ArrayList<Integer> res = new ArrayList();
        if (listNode == null){
            return res;
        }
        Stack<Integer> stack = new Stack();
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        
        while (!stack.isEmpty()){
            res.add(stack.pop());
            
        }
        return res;
        
        
    }
}

4.根据前序，中序构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中，左，右
中序遍历 inorder = [9,3,15,20,7] 左，中，右
返回如下的二叉树：

3
/ \
9 20
/ \
15 7
思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边

利用二叉树前序遍历和中序遍历的特性。前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时可以利用递归，分别取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树继续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树继续上一个过程，最终得以重建二叉树。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

import java.util.Arrays;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] tin) {
        if (pre.length == 0 || tin.length == 0){
            return null;
        }
        
        TreeNode root = new TreeNode(pre[0]);
        // 找到 第一个元素在 tin 中的位置
        int i = getIndex(tin, pre[0]);
        
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(tin, 0, i));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(tin, i+1, tin.length));
        
        return root;
        
        
    }
    
    private int getIndex(int[] array, int value){
        int index = 0;
        for (int i = 0; i < array.length; i++){
            if (array[i] == value){
                index = i;
                break;
            }
        }
        return index;
    }
}

5.使用2个栈实现队列

需要两个栈Stack1和Stack2，push的时候直接push进Stack1。pop需要判断Stack1和Stack2中元素的情况，Stack1空的话，直接从Stack2 pop，Stack1不空的话，把Stack1的元素push进入Stack2，然后pop Stack2的值。

1.push: 直接push进stack1。需要pop全部stack2，才开始将stack1元素放进stack2中

2.pop：if stack2 不为空，直接pop stack2； if stack2 为空，需要将stack1元素全部放入stack2中，然后pop

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
        
    }
    
    public int pop() {
        if (stack1.isEmpty() && stack2.isEmpty()){
            return -1;
        }
        
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    
    }
}

6.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

    输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
    例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
    NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。

1. 如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。

2. 当一次循环中首元素小于尾元素，说明最小值就是首元素。

3. 但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。如：【1,2,2,3,4】 --> 【2,3,4,1,2】

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
        if (len == 0){
            return 0;
        }
        
        // 如果第一个数字 都比最后一个数字小，则代表没有旋转
        int left = 0;
        int right = len - 1;
        if (array[left] < array[right]){
            return array[left];
        }
        
        int mid;
        int minVal = array[left];
        while ((right - left) > 1){
            mid = (right + left) / 2;
            if (array[left] <= array[mid]){
                left = mid;
            }else if (array[right] >= array[mid]){
                right = mid;
            }else if ((array[left] == array[mid]) && array[mid] == array[right]){
                // 只能遍历找到最小的值
                for (int i = 0; i < len; i++){
                    if (minVal > array[i]){
                        minVal = array[i];
                        right = i;
                    }
                    
                }
            }
        }

        return array[right];
        
    
    }
}

2. 直接使用遍历的方法，但是时间复杂度为 O(N)

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        // 直接使用遍历的方法
        if (array.length == 0){
            return 0;
        }
        
        int minVal = array[0];
        for (int i = 0; i < array.length; i++){
            if (minVal > array[i]){
                minVal = array[i];
            }
        }
        return minVal;
    
    }
}

7.斐波那契数列

1. 使用递归的形式

public class Solution {
    public int Fibonacci(int n) {
        
        if (n <= 0) return 0;
        if (n == 1) return 1;
        
        return (Fibonacci(n-2) + Fibonacci(n-1));

    }
}

2. 使用递归的方法：

不同与python，【a, b = b, a+b】, java需要使用一个中间变量

public class Solution {
    public int Fibonacci(int n) {
        
        int a = 0, b = 1;
        int temp;
        for (int i = 0; i < n; i++){
            temp = a;
            a = b;
            b = temp + b;
        }
        
        return a;

    }
}

8.跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。

求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

public class Solution {
    public int JumpFloor(int target) {
        // 斐波那契数列的一种变体
        if (target <= 1) return 1;
        if (target == 2) return 2;
        
        return (JumpFloor(target -1) + JumpFloor(target -2));

    }
}

9. 变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

相当于找规律：跳法 target = 2 的 (n-1)次方

public class Solution {
    public int JumpFloorII(int target) {
        if (target == 1) return 1;
        int res = 1 ;
        for (int i = 1; i < target; i++){
            res *= 2;
        }
        return res;
    }
}

10. 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：

还是找规律的一道题，归根结底还是斐波那契数列

public class Solution {
    public int RectCover(int target) {
        if (target <= 0) return 0;
        if (target == 1) return 1;
        if (target == 2) return 2;
        
        return (RectCover(target - 1) + RectCover(target - 2));

    }
}

11.二进制中 1 的个数

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

负数的二进制：

计算机中，负数以其正值的补码形式表达
什么叫补码呢？这得从原码，反码说起。
原码：一个整数，按照绝对值大小转换成的二进制数，称为原码。
比如 00000000 00000000 00000000 00000101 是 5的原码。
反码：将二进制数按位取反，所得的新二进制数称为原二进制数的反码。
取反操作指：原为1，得0；原为0，得1。（1变0; 0变1）
比如：将00000000 00000000 00000000 00000101每一位取反，得11111111 11111111 11111111 11111010。
称：11111111 11111111 11111111 11111010是 00000000 00000000 00000000 00000101 的反码。
反码是相互的，所以也可称：
11111111 11111111 11111111 11111010 和00000000 00000000 00000000 00000101 互为反码。
补码：反码加1称为补码。
也就是说，要得到一个数的补码，先得到反码，然后将反码加上1，所得数称为补码。
比如：00000000 00000000 00000000 00000101的反码是：11111111 11111111 11111111 11111010。
那么，补码为：
11111111 11111111 11111111 11111010 + 1 = 11111111 11111111 11111111 11111011
所以，-5 在计算机中表达为：11111111 11111111 11111111 11111011。
转换为十六进制：0xFFFFFFFB。

public class Solution {
    public int NumberOf1(int n) {
        
        int res = 0;
        while (n != 0){
            n = (n-1) & n;
            res ++;
        }
        return res;

    }
}

第二种方法：通过 flag = 1 依次左移 ,与原数相与，来计算所有的二进制中1 的数量

对于32位的整数这样移动32次就记录了这个数二进制中1的个数了

public class Solution {
    public int NumberOf1(int n) {
        int res = 0;
        int flag = 1;
        
        while (flag != 0){
            if ((n & flag) != 0){
                res ++;
            }
            flag = flag << 1;
        }
        return res;

    }
}

12. 数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

首先，判断exponent 是否为负数,如果是则标记，并转为正整数
循环相乘
判断 exponent 的标记，如果是负数，则取倒数

public class Solution {
    public double Power(double base, int exponent) {
        
        double res = 1.0;
        if(base == 0) return 0;
        if(exponent == 0) return res;
        
        boolean flag = true;
        
        if(exponent < 0){
            flag = false;
            exponent = -exponent;
        }
        
        for(int i = 0; i< exponent; i++){
            res *= base;
        }
        
        return flag ? res : 1/ res;
            
        
  }
}

13.调整数组顺序使奇数位于偶数前面

题目描述

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

public class Solution {
    public void reOrderArray(int [] array) {
        int index = 0; // 用于保存奇数位置
        int size = array.length;
        
        for (int i =0; i< size; i++){
            if (array[i] % 2 == 1){ // 如果是奇数的话
                int j = i;
                while (j > index){ // 循环交换奇数和偶数位置，偶数位置相对不变
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    j--;
                }
            index++; // 更新奇数位置
                
            }
        }
        
    }
}

14.链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

思路：

如果在只希望一次遍历的情况下, 寻找倒数第k个结点, 可以设置两个指针
第一个指针先往前走k-1步, 然后从第k步开始第二个指针指向头结点
然后两个指针一起遍历
当地一个指针指向尾节点的时候, 第二个指针正好指向倒数第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) {
        // 快指针先走 k-1 步，慢指针指向头节点，两个节点一起走
        // 当快指针走到尾，则慢指针找到 倒数 第 k 个节点
        if (k <= 0 || head == null){
            return null;
        }
        ListNode fastNode = head;
        ListNode slow = head;
        for (int i=0; i<k-1; i++){
            if (fastNode.next == null){ // 判断是否会越界
                return null;
            }
            fastNode = fastNode.next;
        }
        
        while(fastNode.next != null){
            slow = slow.next;
            fastNode = fastNode.next;
        }
        return slow;
        
    }
}

15.反转单链表

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

输入的链表头指针为None或者整个链表只有一个结点时，反转后的链表出现断裂，返回的翻转之后的头节点不是原始链表的尾结点。因此需要引入一个翻转后的头结点，以及一个指向当前结点的指针，一个指向当前结点前一个结点的指针，一个指向当前结点后一个结点的指针，防止出现断裂。

推广：递归实现反转链表

比较简单的非递归的实现方法：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 如果是head为空，或者只有一个节点，则直接返回
        if (head == null || head.next == null){
            return head;
        }
        ListNode p = head;
        ListNode newHead = null; // 新的头节点
        
        while(p != null){
            ListNode temp = p.next; // 保存p指向下一个节点的指针
            p.next = newHead;
            newHead = p; // 更新头节点
            p = temp;  // 即 p = p.next ，更新p节点
        }
        return newHead;
        
    }
}

使用递归的实现方法：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 使用递归的方法
        if (head == null || head.next == null){
            return head;
        }
        ListNode headNext = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return headNext;

    }
}

16.合并两个有序的链表

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

使用非递归方法1：

较复杂，最好使用一个辅助的头部节点： ListNode root = new ListNode(-1);

/*
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){  // 如果链表1 为空，则返回链表2
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        
        ListNode start = null; // 用于保存头部节点
        ListNode p = null;
        
        while(list1 != null && list2 != null){
            if (list1.val < list2.val){
                // 用于判断头部节点在 那个链表上
                if (start == null){
                    start = list1;
                    p = list1;
                }else{
                    p.next = list1;
                    p = p.next;
                }
                list1 = list1.next; // 更新节点，指向下一个节点
            }else{
                if (start == null){
                    start = list2;
                    p = list2;
                }else{
                    p.next = list2;
                    p = p.next;
                }
                list2 = list2.next;
            }
        }
        
        // 可能某个链表还剩余值,下列例子就链表2 会剩余
        // 比如链表1： 1->2->4
        // 链表2：    3->5->6
        if(list1 == null){
            p.next = list2;
        }
        
        if (list2 == null){
            p.next = list1;
        }
        
        return start;
        
    }
}

使用非递归方法2：使用辅助节点

/*
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;
        }
        if (list2 == null){
            return list1;
        }
        
        ListNode node = new ListNode(-1); // 用于保存头部节点
        ListNode root = node;
        
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                node.next = list1;
                node = node.next; // 更新node节点，指向下一个
                list1 = list1.next;
            }else{
                node.next = list2;
                node = node.next;
                list2 = list2.next;
            }
        }
                // 可能某个链表还剩余值,下列例子就链表2 会剩余
        // 比如链表1： 1->2->4
        // 链表2：    3->5->6
        if(list1 == null){
            node.next = list2;
        }
        
        if (list2 == null){
            node.next = list1;
        }
        return root.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;
        }
        if (list2 == null){
            return list1;
        }
        ListNode ret = null;
        if (list1.val < list2.val){
            ret = list1;
            ret.next = Merge(list1.next, list2);
        }else{
            ret = list2;
            ret.next = Merge(list1, list2.next);
        }
        
        return ret;
    }
}

17.树的子结构

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

涉及树结构的题目，一般都使用递归方法

1. 如果两棵二叉树节点值不相同：

1-1：递归遍历 A树左子树

1-2：递归遍历 A 树右子树

2.如果两棵二叉树节点值相同：

1.1：B树为空，则B是A的子树

1.2：递归判断AB树节点值是否相同

/**
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 res = false;
        
        if (root1 != null && root2 != null){
            if (root1.val == root2.val){
                res = doseSubtree(root1, root2);
        }
        if (res == false){
            res = HasSubtree(root1.left, root2);
        }
        if (res == false){
            res = HasSubtree(root1.right, root2);
        }
    }
        return res;
    }
    private boolean doseSubtree(TreeNode root1,TreeNode root2){
        if (root2 == null){
            return true;
        }
        if (root1 == null){
            return false;
        }
        if (root1.val != root2.val){
            return false;
        }
        return doseSubtree(root1.left, root2.left) && doseSubtree(root1.right, root2.right);
        
    }


}

18.二叉树的镜像

题目描述

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

输入描述:

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

递归实现：

/**
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; // 交换左右子树
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        Mirror(root.left); // 递归对左子树交换
        Mirror(root.right);
    }
}

方法二：非递归实现，使用队列实现，类似于树的层次遍历

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

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

    }

}
*/
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null)
        {
            return;
        }        // 使用队列
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            // 交换元素
            TreeNode temp;
            if (node.left != null || node.right != null){
                temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            
            if (node.left != null){
                q.offer(node.left);
            }
            if (node.right != null){
                q.offer(node.right);
            }
        }
           
    }
    
}

19.顺时针打印矩阵

题目描述

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

[[ 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.

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> res = new ArrayList();
        int rows = matrix.length;  // 行的大小
        int cols = matrix[0].length; // 列的大小
        
        if (rows == 0 || cols == 0){
            return res;
        }
        
        // 从左到右开始遍历，right最右边【列】，从上到下，bottom最底部【行】
        int left = 0, right = cols-1, top = 0, bottom = rows -1;
        
        while(left <= right && top <= bottom){
            // 从左到右开始遍历
            for(int i = left; i <= right; i++){
                res.add(matrix[top][i]);
            }
            // 从上到下开始遍历
            for (int i = top+1; i <= bottom; i++){
                res.add(matrix[i][right]);
            }
            // 从下往上开始遍历
            if (top != bottom){
                for (int i = right-1; i>= left; i--){
                    res.add(matrix[bottom][i]);
                }
            }
            //从 右往左开始遍历
            if (left != right){
                for (int i = bottom-1; i > top; i--){
                    res.add(matrix[i][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
      return res;
    }
    
}

20.包含min函数的栈

题目描述

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

思路：利用一个辅助栈来存放最小值

栈 3，4，2，5，1

辅助栈 3，3，2，2，1

每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈顶

当出栈时，辅助栈也要出栈

这种做法可以保证辅助栈顶一定都当前栈的最小值

import java.util.Stack;

public class Solution {

    private Stack<Integer> dataStack = new Stack();
    private Stack<Integer> minStack = new Stack();
    
    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty() || min() > node){ // 如果为空，则之间push进去，如果最小栈的最小值都比node大，也把node值push
            minStack.push(node); 
        }else{
            minStack.push(min());
        }
    }
    
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

21. 栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

1. 建立一个辅助栈，把push序列的数字依次压入辅助栈，

2. 每次压入后，比较辅助栈的栈顶元素和pop序列的首元素是否相等，相等的话就推出pop序列的首元素和辅助栈的栈顶元素，

3.若最后辅助栈为空，则push序列可以对应于pop序列。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      if (pushA.length==0 || popA.length == 0){
          return false;
      }
        // 使用一个辅助栈
        Stack<Integer> stack = new Stack();
        int index = 0;
        for (int i=0; i< pushA.length; i++){
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek()==popA[index]){
                stack.pop();
                index++;  // 用于数组后一位继续判断
            }
        }
        return stack.isEmpty();
    }
}

22.从上往下打印二叉树

相当于时树的层次遍历

从上往下打印出二叉树的每个节点，同层节点从左至右打印。（依次打印出每层的结点值）

需要一个队列和一个存储数据的数组

import java.util.ArrayList;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        // 使用队列的方法
        ArrayList<Integer> res = new ArrayList();
        if (root == null){
            return res;
        }
        
        LinkedList<TreeNode> queue = new LinkedList();
        queue.offer(root);
        
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            res.add(node.val);
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return res;

    }
}

23.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。（二叉搜索树的中序遍历是有序的）

条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。

1、确定root；

2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；

3、遍历右子树，若发现有小于root的值，则直接返回false；

4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int size = sequence.length;
        if (size == 0) return false;
        if (size == 1) return true;
        return verifySquenceOfBST(sequence, 0, size-1);
    }
    
    private boolean verifySquenceOfBST(int[] sequence, int start, int end){
        if (start >= end) return true;
        int i = start;
        int rootValue = sequence[end];
        while (sequence[i] < rootValue){  // 找到 大于 root值的第一个索引
            i++;
        }
        int j  = i; // 保存索引值
        while (j < end){  // 右子树值比 根值大
            if (sequence[j] < rootValue) return false;
            j++;
        }
        boolean left = verifySquenceOfBST(sequence, start, i-1); // 递归判断左子树
        boolean right = verifySquenceOfBST(sequence, i, end-1); //递归判断右子树
        return left && right;
    }
}

24.二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

输入一棵二叉树和一个值，求从根结点到叶结点的和等于该值的路径

递归回溯方法：

递归先序遍历树，把结点加入路径。
若该结点是叶子结点则比较当前路径和是否等于期待和。
弹出结点，每一轮递归返回到父结点时，当前路径也应该回退一个结点

import java.util.ArrayList;
import java.util.Collections;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList();
    ArrayList<Integer> path = new ArrayList();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) return res;
        find(root, target);
        return res;
    }
    
    public void find(TreeNode root, int sum){
        if (root == null) return;
        int value = root.val;
        path.add(value); // 先将根节点放进去
        if (root.left == null && root.right == null && sum==value){
            res.add(new ArrayList(path));
        }else{
            find(root.left, sum-value); // 递归查找左子树
            find(root.right, sum-value); // 递归查找右子树
        }
        path.remove(path.size()-1); // 使用回溯方法
        
    }
}

25.复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

此题有点复杂呀，指针指来指去的（记住每个while循环都要更新结点）

解题思路：【从头到尾，依次遍历插入next、random节点，拆分原链表和复制链表】

1、遍历链表，复制每个next结点，相当于增加了节点，如复制结点A得到A1，将结点A1插到结点A后面；

2、重新遍历链表，复制每一个random，如A1.random = A.random.next;

3、拆分链表，将链表拆分为原链表和复制后的链表

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) return null;
        
        // 第一步骤：复制next 节点
        RandomListNode dummy = pHead;
        while (dummy != null){
            RandomListNode copyNode = new RandomListNode(dummy.label);// 复制一个节点
            RandomListNode dummyNext = dummy.next;  // 保存节点
            
            copyNode.next = dummyNext; // 插入节点
            dummy.next = copyNode;
            
            dummy = dummyNext; // 更新节点，往后循环
        }
        
        // 第二步骤，复制random节点
        dummy = pHead; // 从头开始遍历
        while(dummy != null){
            RandomListNode dummyRandom = dummy.random;
            RandomListNode copyNode = dummy.next; 
            if (dummyRandom != null){
                copyNode.random = dummyRandom.next; // 指向新的节点
            }
            dummy = copyNode.next; // 更新节点
        }
        
        // 第三步骤： 分离复制的链表
        dummy = pHead;
        RandomListNode cloneHead = pHead.next; // 复制链表的头节点
        
        while(dummy != null){
            RandomListNode copyNode = dummy.next;
            RandomListNode dummyNext = copyNode.next; //保存下一个节点
            
            dummy.next = dummyNext; // 取出原始节点
            if (dummyNext != null){
                copyNode.next = dummyNext.next; // 取出复制的节点
            }else{
                copyNode.next = null;
            }
            dummy = dummyNext; // 更新节点
        }
        
        return cloneHead;
        
        
    }
}

另外一种比较简单的方法：使用哈希表，直接复制一个相同的链表,时间、空间复杂度均为： o(n);

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        // 使用哈希表实现
        if (pHead == null) return null;
        
        HashMap<RandomListNode, RandomListNode> map = new HashMap();
        RandomListNode cur = pHead;
        
        while (cur != null){  // 直接复制节点，此时还没有连接
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        
        cur = pHead;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);  // 连接 next 节点
            cur = cur.next;
        }
        
        cur = pHead;
        while (cur != null){
            map.get(cur).random = map.get(cur.random);// 连接 random 节点
            cur = cur.next;
        }
        
        RandomListNode newHead = map.get(pHead);
        return newHead;
        
        
    }
}

26.二叉搜索树和双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

递归版本实现：

递归流程如图所示：

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

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

    }

}
*/
public class Solution {
    private TreeNode node = null;
    private TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 使用中序遍历的方法
        if (pRootOfTree == null) return null;
        if (pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
        ConvertSub(pRootOfTree);
        return head;
        
    }
    
    private void ConvertSub(TreeNode pRootOfTree){
        // 使用中序遍历的方法
        if (pRootOfTree == null) return;
        ConvertSub(pRootOfTree.left);
        
        if (node == null){
            node = pRootOfTree;
            head = pRootOfTree;
        }else{
            node.right = pRootOfTree;
            pRootOfTree.left = node;
            node = pRootOfTree; // 更新节点
        } 
        ConvertSub(pRootOfTree.right);

    }
}

非递归版本实现：

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

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

    }

}
*/
import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 非递归版本实现
        if (pRootOfTree == null) return null;
        
        Stack<TreeNode> stack = new Stack();
        TreeNode pre = null; //保存中序遍历上一节点
        TreeNode p = pRootOfTree;
        while (p != null || !stack.isEmpty()){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (pre == null){
                pRootOfTree = p;
                pre = pRootOfTree;
            }else{
                pre.right = p;
                p.left = pre;
                pre = p;
            }
            p = p.right;
        }
        return pRootOfTree;

    }
}