剑指offer之3-10题解

àì夳堔傛蜴生んèń 2021-12-13 18:27 228阅读 0赞

# 剑指offer之3-10题解 #

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

#### 前言： ####

最近开始刷牛客的剑指offer，把刷过的题，代码总结一下。有参考网上的代码，一起加油。

## 目录 ##

1.  从尾到头打印链表
2.  重建二叉树
3.  用两个栈实现队列
4.  旋转数组的最小数字
5.  斐波那契数列
6.  跳台阶
7.  变态跳台阶
8.  矩阵覆盖

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

### 3. 从尾到头打印链表 ###

（一）题目描述  
![在这里插入图片描述][20190707095632911.png]  
（二） 思路

1.  使用栈：栈具有先进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。

（三）代码实现

/**
    *    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) {
        
            Stack<Integer> stack = new Stack<>();
            while (listNode!=null){
        
                stack.add(listNode.val);
                listNode = listNode.next;
            }
            ArrayList<Integer> list = new ArrayList<>();
            while (!stack.isEmpty()){
        
                list.add(stack.pop());
            }
            return list;
        }
    }

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

### 4. 重建二叉树 ###

（一）题目描述  
![在这里插入图片描述][20190707100331434.png]  
（二） 思路

1.  前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结构，右部分为右子树中序遍历结果。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

（三）代码实现（报错，先跳过）

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    import java.util.HashMap;
    import java.util.Map;
    public class Solution {
        
        public class Solution {
        
        private Map<Integer,Integer> indexForInOrders = new HashMap<>();
    
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        
            for (int i = 0; i < in.length; i++) {
        
                indexForInOrders.put(in[i],i);
            }
            return reConstructBinaryTree(pre,0,pre.length-1,0);
        }
    
        public TreeNode reConstructBinaryTree(int[] pre, int preL,int preR,int inL) {
        
            if (preL>preR)
                return null;
            TreeNode root = new TreeNode(pre[preL]);
            int inIndex = indexForInOrders.get(root.val);
            int leftTreeSize = inIndex-inL;
            root.left = reConstructBinaryTree(pre,preL+1,preL+leftTreeSize,inL);
            root.right = reConstructBinaryTree(pre,preL+leftTreeSize+1,preR,inL+leftTreeSize+1);
            return root;
        }
    }

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

### 5. 用两个栈实现队列 ###

（一）题目描述  
![在这里插入图片描述][20190707105126828.png]

（二） 思路

1.  push操作：直接push。
2.  pop操作：将stack1的数据全部push进stack2，返回stack2栈顶元素即可。

（三）代码实现

import java.util.Stack;
    
    public class Solution {
        
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
    
        public void push(int node) {
        
            stack1.push(node);
        }
    
        public int pop() {
        
            if (stack1.isEmpty() && stack2.isEmpty()) {
        
                throw new RuntimeException("队列为null");
            } else if (stack2.isEmpty()) {
        
                while (!stack1.isEmpty()) {
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

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

### 6. 旋转数组的最小数字 ###

（一）题目描述  
![在这里插入图片描述][20190707105113448.png]

（二） 思路

1.  我的思路是直接找到最小值返回即可。代码通过。
2.  大佬的思路是通过二分查找算法进行求解（l代表low，m代表mid，h代码high）：
3.  当nums\[m\]<=nums\[h\]时，表示\[m,h\]区间内的数组是非递减数组，\[l,m\]区间内是旋转数组，此时令h = m；
4.  否则\[m+1,h\]区间内是旋转数组，令 l =m + 1

（三）代码实现  
大佬代码：

public class Solution {
        
       public int minNumberInRotateArray(int[] nums){
        
            if (nums.length==0){
        
                return 0;
            }
            int l = 0;
            int h = nums.length-1;
            while (l<h){
        
                int m = l+(h-l)/2;
                if (nums[m]<=nums[h]){
        
                    h = m;
                }else {
        
                    l = m+1;
                }
            }
            return nums[l];
        }
    }

小白代码：

public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
        if (array.length==0){
        
                return 0;
            }
            int minIndex = 0;
            for (int i = 1; i < array.length; i++) {
        
                if (array[minIndex]>array[i]){
        
                    minIndex = i;
                }
            }
            return array[minIndex];
        }
    }

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

### 7. 斐波那契数列 ###

（一）题目描述  
![在这里插入图片描述][20190707111307914.png]  
斐波那契数列公式：  
![在这里插入图片描述][20190707111447897.png]

（二）思路

1.  使用递归求解，但是会重复计算一些子问题。例如，计算f(4)需要计算f(3)和f(2)，计算f(3)需要计算f(2)和f(1)，可以看到f(2)被重复计算了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
2.  动态规划：考虑到第i项只与第i-1和第i-2项有关，因此只需要存储前两项就能求解第i项，从而将空间复杂度由O(N)降为O(1);

（三）代码实现

1.  递归版一

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

1.  递归版二

public class Solution {
        
       public int Fibonacci(int n) {
        
            if (n <= 1) {
        
                return n;
            }
            int[] fib = new int[n + 1];
            fib[1] = 1;
            for (int i = 2; i <= n; i++) {
        
                fib[i] = fib[i - 1] + fib[i - 2];
            }
            return fib[n];
        }
    }

1.  动态规划版

public class Solution {
        
       public static int Fibonacci(int n) {
        
            if (n <= 1) {
        
                return n;
            }
            int pre2 = 0;
            int pre1 = 1;
            int fib = 0;
            for (int i = 2; i <= n; i++) {
        
                fib = pre2 + pre1;
                pre2 = pre1;
                pre1 = fib;
            }
            return fib;
        }
    }

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

### 8. 跳台阶 ###

（一）题目描述  
![在这里插入图片描述][20190707113358164.png]  
（二）思路

1.  当n=1时，有一种跳法
2.  当n=2时，有两种跳法
3.  跳n阶台阶，可以先跳1阶台阶，再跳n-1阶台阶；或者先跳2阶台阶，再跳n-2阶台阶。而n-1和n-2阶台阶的跳法可以看成子问题，该问题的递推公式为：  
    ![在这里插入图片描述][2019070711371190.png]

（三）代码实现

1.  递归版

public class Solution {
        
            public int JumpFloor(int target) {
        
                if (target <= 2) {
        
                    return target;
                } else {
        
                    return JumpFloor(target - 1) + JumpFloor(target - 2);
                }
            }
        }

1.  动态规划版

public class Solution {
        
            public int JumpFloor(int target) {
        
                if (target <= 2) {
        
                    return target;
                }
                int pre1 = 2;
                int pre2 = 1;
                int result = 0;
                for (int i = 3; i <= target; i++) {
        
                    result = pre1 + pre2;
                    pre2 = pre1;
                    pre1 = result;
                }
                return result;
            }
        }

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

### 9. 变态跳台阶 ###

（一）题目描述  
![在这里插入图片描述][20190707142911310.png]  
（二）思路

1.  跳上n-1级台阶，可以从n-2级跳1级上去，也可以从n-3级跳2级上去…那么

> f(n-1) = f(n-2) + f(n-3) + … + f(0)

1.  同样，跳上n级台阶，可以用n-1级跳1级上去，也可以从n-2级跳2级上去…那么

> f(n) = f(n-1) + f(n-2) + … + f(0)

1.  综上可得

> f(n) = 2 \* f(n-1)

（三）代码实现

public class Solution {
        
            public int JumpFloorII(int target) {
        
                if (target <= 2) {
        
                    return target;
                }
                return 2 * JumpFloorII(target - 1);
            }
        }

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

### 10. 矩阵覆盖 ###

（一）题目描述

![在这里插入图片描述][20190707143024501.png]  
（二）思路

1.  当n为1时，只有一种覆盖方法：  
    ![在这里插入图片描述][2019070714283973.png]
2.  当n为2时，有两种覆盖方法：  
    ![在这里插入图片描述][2019070714283040.png]
3.  要覆盖2*n的大矩阵，可以先覆盖2*1的矩形，再覆盖2\*(n-1)的矩形；或者先覆盖2*2的矩形，再覆盖2*(n-2)的矩形。而覆盖2\*(n-1)和2\*(n-2)的矩形可以看成子问题。该问题的递归公式如下：  
    ![在这里插入图片描述][20190707142820760.png]

（三）代码实现

1.  递归版

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

1.  动态规划版

public class Solution {
        
     public int RectCover(int target) {
        
            if (target <= 2) {
        
                return target;
            }
            int pre2 = 1;
            int pre1 = 2;
            int result = 0;
            for (int i = 3; i <= target; i++) {
        
                result = pre1 + pre2;
                pre2 = pre1;
                pre1 = result;
            }
            return result;
        }
    }

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

[20190707095632911.png]: /images/20211213/d8cda28801a94ec394cbaca554c2d249.png
[20190707100331434.png]: /images/20211213/b3995bcb1dfe4c01b7e845952301b446.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211213/1d8188886bc94bdaabe800482ea74ea0.png
[20190707105126828.png]: /images/20211213/5824ebb5cff448738962afd7839f10a3.png
[20190707105113448.png]: /images/20211213/d39d1a5f5ee14d5ea2bff6ea9761e9ac.png
[20190707111307914.png]: /images/20211213/bad45810ecab40539ba5c1546fedea05.png
[20190707111447897.png]: /images/20211213/3bb6862dfed54c5f80d11b80902ec197.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211213/d25cc2a785824db78b78bcf315a128ae.png
[20190707113358164.png]: /images/20211213/7acbb80c93ca4680a31d29a6903f3688.png
[2019070711371190.png]: /images/20211213/e52ff40eee6f4b118735b09aabd5ffe5.png
[20190707142911310.png]: /images/20211213/a06b1d61bab6488687b0a924cb5361e9.png
[20190707143024501.png]: /images/20211213/33ab66450cc548e6ab01b26999877af7.png
[2019070714283973.png]: /images/20211213/8c481066a658400db61d717bef9b7e95.png
[2019070714283040.png]: /images/20211213/df93799fd5d94b30aae59c51b4f3f55f.png
[20190707142820760.png]: /images/20211213/9399a29d2aea4348af96d80c68ac722f.png