剑指Offer刷题记录1-10

一时失言乱红尘 2021-09-10 08:22 341阅读 0赞

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

#### 1.二维数组中查找 ####

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

方法一，从左下开始遍历，大就往右，小就往上

public static boolean Find(int target, int [][] array) {
            int len=array.length-1;
            int i=0;
            while((len>=0)&&(i<array[0].length)){
                if(array[len][i]==target)
                    return true;
                else if(array[len][i]>target)
                    len--;
                else if(array[len][i]<target)
                    i++;        
            }
            return false;
         }

方法二 二分法 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案。

public static boolean Find(int target, int [][] array) {
            for(int i=0;i<array.length;i++){
                int low=0;
                int high=array[i].length-1;
                while(low<=high){
                    int mid=(low+high)/2;
                    if(target>array[i][mid])
                        low=mid+1;
                    else if(target<array[i][mid])
                        high=mid-1;
                    else 
                        return true;
                }
            }
            return false;
    
      @Test
        public void test(){
            int arrays[][]={{1,4,7,9},{2,7,8,11},{4,8,12,19}}; 
            if(Find(12,arrays)) 
                System.out.println("数据含有这样的整数");
            else
                System.out.println("没有这样的整数");
        }

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

输入一个链表，从尾到头打印链表每个节点的值。  
利用栈存储，后进先出特性

public class ListNode {
            int val;
            ListNode next = null;
            ListNode(int val) {
                this.val = val;
            }
         }
        
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList list=new ArrayList<Integer>();
            Stack<Integer> stack=new Stack<>();
            while(listNode!=null){
                stack.push(listNode.val);
                listNode=listNode.next;
            }
            while(!stack.isEmpty()){
                list.add(stack.pop());
            }
            return list;
        }

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

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。  
2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。  
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

public class TreeNode {
              int val;
              TreeNode left;
              TreeNode right;
              TreeNode(int x) { val = x; }
         }
    
     public TreeNode reConstructBinaryTree(int[] pre,int[] in){
            if(pre.length==0||in.length==0)
                return null;
            TreeNode node=new TreeNode(pre[0]);
            for(int i=0;i<in.length;i++){
                if(pre[0]==in[i]){
                    node.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
                    node.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                }
            }
            return node;
        }

方便理解再举个例子：  
前序遍历: GDAFEMHZ  
中序遍历: ADEFGHMZ

![5057999-9815cf5ae6e6af09.png][]

第一步，根据前序遍历的特点，我们知道根结点为G  
第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。  
第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。  
第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。  
第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1 确定根,确定左子树，确定右子树。  
2 在左子树中递归。  
3 在右子树中递归。  
4 打印当前根。

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

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

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.empty()&&stack2.empty())
                    throw new RuntimeException("queue is empty");
                if(stack2.empty()){
                    while(!stack1.empty()){
                        stack2.push(stack1.pop());
                    }
                }
                return stack2.pop();
            }

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

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

采用二分法解答这个问题，  
mid = low + (high - low)/2  
需要考虑三种情况：  
(1)array\[mid\] > array\[high\]:  
出现这种情况的array类似\[3,4,5,6,0,1,2\]，此时最小数字一定在mid的右边。  
low = mid + 1  
(2)array\[mid\] == array\[high\]:  
出现这种情况的array类似 \[1,0,1,1,1\] 或者\[1,1,1,0,1\]，此时最小数字不好判断在mid左边  
还是右边,这时只好一个一个试 ，  
high = high - 1  
(3)array\[mid\] < array\[high\]:  
出现这种情况的array类似\[2,2,3,4,5,6,6\],此时最小数字一定就是array\[mid\]或者在mid的左  
边。因为右边必然都是递增的。  
high = mid  
**注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid** **一定会指向下标靠前的数字**  
比如 array = \[4,6\]  
array\[low\] = 4 ;array\[mid\] = 4 ; array\[high\] = 6 ;  
如果high = mid - 1，就会产生错误， 因此high = mid  
但情形(1)中low = mid + 1就不会错误

public int minNumberInRotateArray(int [] array) {
            if(array.length==0)
                return 0;
            int low=0;int high=array.length-1;
            while(low<high){
                int mid=low+(high-low)/2;
                if(array[mid]>array[high]){
                    low=mid+1;
                }else if(array[mid]==array[high]){
                    high=high-1;
                }else{
                    high=mid;
                }
            }
            return array[low];
        }

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

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。  
n<=39

public int Fibonacci(int n) {
            if(n==1) 
                return 1;
            if(n==2)
                return 1;
            if(n>2)
                return Fibonacci(n-1)+Fibonacci(n-2);
            
            return 0;
        }

#### 8.跳台阶 ####

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。  
两种跳法，1阶或者2阶，那么  
假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);  
假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2).  
可以得出总跳法为: f(n) = f(n-1) + f(n-2) 。通过实际的情况可以得出：一阶f(1) = 1 ,两阶f(2) = 2。得出的是一个斐波那契数列：

| 1, (n=1)
    f(n) =    | 2, (n=2)
              | f(n-1)+f(n-2) ,(n>2,n为整数)

// 2 --->  11,2   2
            // 3 ---> 12,21,111  3
            // 4 ---> 112,121,211,1111,22  
            // 5 ---> 1112,1121,1211,2111,221,122,212,11111 8
            if(target<=0)
                return -1;
            if(target==1)
                return 1;
            if(target==2)
                return 2;
            return JumpFloor(target-1)+JumpFloor(target-2);

public int JumpFloor2(int target) {
            if(target==1)
                return 1;
            if(target==2)
                return 2;
            int first=1,second=2,third=0;
            for(int i=3;i<=target;i++){
                third=first+second;
                first=second;
                second=third;
            }
            return third;
        }

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

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

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
    f(1) = 1
    f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。
    f(3) = f(3-1) + f(3-2) + f(3-3) 
    ...
    f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 
    1.这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
    2.n = 1时，只有1种跳法，f(1) = 1
    3. n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2) = f(2-1) + f(2-2) 
    4.n = 3时，会有三种跳得方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
        因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
    5. n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：
        f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)    
    6. 由以上已经是一种结论，但是为了简单，我们可以继续简化：
        f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
        f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
        可以得出：
        f(n) = 2*f(n-1)    
    7. 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
                  | 1       ,(n=0 ) 
    f(n) =     | 1       ,(n=1 )
                  | 2*f(n-1),(n>=2)

public int JumpFloorII(int target) {
          /*      
           * 1 -- >1          1
           * 2 --> 11,2      2
           * 3 -->12,21,111,3           4
           * 4 -->1111,121,112,211,22,13,31,4    8
           */
              if(target<=0){
                  return -1;
              }else if(target==1){
                  return 1;
              }else {
                  return 2*JumpFloorII(target-1);
              }
          }

#### 10.矩形覆盖 ####

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

斐波那契数列  
2\*n的大矩形，和n个2\*1的小矩形  
其中target\*2为大矩阵的大小  
有以下几种情形：  
1.target <= 0 大矩形为<= 2\*0,直接return 1；  
2.target = 1大矩形为2\*1，只有一种摆放方法，return1；  
3.target = 2 大矩形为2\*2，有两种摆放方法，return2；  
4.target = n 分为两步考虑：  
第一次摆放一块 2 \*1 的小矩阵，则摆放方法总共为f(target - 1)

![5057999-820fe85e19fbee2c.png][]

第一次摆放一块1 *2的小矩阵，则摆放方法总共为f(target-2)  
因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1\*2（用××表示）摆放方法就确定了，所以为f(targte-2)

![5057999-df0bd0bd6c2d9a5f.png][]

public int RectCover(int target){
            if(target<1)
                return 0;
            if(target*2==2)
                return 1;
            if(target*2==4)
                return 2;
            return RectCover(target-1)+RectCover(target-2);
        }

[5057999-9815cf5ae6e6af09.png]: /images/20210811/3e7483d379a34190bce316d944e551da.png
[5057999-820fe85e19fbee2c.png]: /images/20210811/1bf2d5427a544c90ae7175ccf4d87674.png
[5057999-df0bd0bd6c2d9a5f.png]: /images/20210811/e517c3fc5a044ba38d41b761387cbd2b.png