# Sword-Offer

**Repository Path**: jackytallow/sword-offer

## Basic Information

- **Project Name**: Sword-Offer
- **Description**: 重新整理剑指Offer的题解
- **Primary Language**: Java
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-12-28
- **Last Updated**: 2021-01-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 剑指Offer题解（持续更新中）

## 目录
* [二维数组的查找](#二维数组的查找)
* [替换表格](#替换表格)
* [从尾到头打印链表](#从尾到头打印链表)
* [重建二叉树](#重建二叉树)
* [用两个栈实现一个队列](#用两个栈实现一个队列)
* [旋转数组的最小数字](#旋转数组的最小数字)
* [斐波那契数列](#斐波那契数列)
* [跳台阶](#跳台阶)
* [变态跳台阶](#变态跳台阶)
* [矩形覆盖](#矩形覆盖)
* [二进制中1的个数](#二进制中1的个数)


## 二维数组的查找
1. 题目：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2. 思路：
- 首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束。
如果该数字大于要查找的数字，剔除这个数字所在的列。
如果该数字小于要查找的数字，剔除这个数字所在的行。
也就是说如果要查找的数字不在数组的右上角，则每－次都在数组的查找范围中剔除行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
- 这个二维数组的行是按照从左到右依次递增，列是按照从上到下依次增大，所以下面的数一定大于上面的数，右边的数一定大于左边的数
- 可以定义到右上角，开始遍历，如果输入的整数小于它，则必定是在左边，如果大于它的话，必定是在下面
3. 解题代码：
```
public static boolean find(int[][] matrix, int number) {

        if (matrix.length < 0 && matrix[0].length - 1 < 0){
            return false;
        }

        int row = 0;
        int col = matrix[0].length - 1;


        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] > number) {
                //回到前一列
                col -= 1;
            } else if (matrix[row][col] < number) {
                //回到下一行
                row += 1;
            }
            else{
                return true;
            }
        }
        return false;
    }
```

## 替换表格
1. 题目：
请实现一个函数，把字符串中的每个空格替换成"%20"，例如“We are happy.”，则输出“We%20are%20happy.”。
2. 思路：
- 这道只用知道这个字符串中空格的数量，我是使用StringBuffer进行拼接，遍历，把有空格的都拼接成%20，最后再以字符串形式打印就可以
3. 解题代码：
```
 public String replaceSpace(StringBuffer str) {

        StringBuffer stringBuffer = new StringBuffer();
        int len = str.length() -1;
        for(int i = 0;i<len;i++){
            if (stringBuffer.charAt(i) == ' '){
                stringBuffer.append("%20");
            }else{
                stringBuffer.append(stringBuffer.charAt(i));
            }
        }
        return stringBuffer.toString();
    }
```

## 从尾到头打印链表
1. 题目：
- 输入个链表的头结点，从尾到头反过来打印出每个结点的值。
2. 思路：
- 可以利用栈的特性，后进先出，所以可以把这个链表从头到尾压入栈中，
- 然后再进行出栈，这个时候尾先出，头在最后,pop到一个list中
3. 解题代码：
```
  public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         ArrayList<Integer> arrayList = new ArrayList<>();
        ListNode p = listNode;
        
        Stack<Integer> stack = new Stack<>();
        while(p != null){
            stack.push(p.val);
            p = p.next;
        }
        
        int n = stack.size() - 1;
        for(int i = n;i>=0 ; i--){
            arrayList.add(stack.pop());
        }
        return arrayList;
    }
```

## 重建二叉树
1. 题目:
- 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
- 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
- 例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}，重建二叉树并输出它的头结点。
2. 思路：
- 由前序遍历的第一个节点可知根节点。
- 根据根节点，可以将中序遍历划分成左右子树。
- 在前序遍历中找出对应的左右子树，其第一个节点便是根节点的左右子节点。按照上述方式递归便可重建二叉树。
3. 解题代码：
```
  /**
         * 二叉树节点类 
         */
        public static class BinaryTreeNode {
            int value;
            BinaryTreeNode left;
            BinaryTreeNode right;
        }

        /**
         * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
         *
         * @param preorder 前序遍历 
         * @param inorder  中序遍历 
         * @return 树的根结点
         */
        public static BinaryTreeNode construct(int[] preorder, int[] inorder) {
            // 输入的合法性判断，两个数组都不能为空，并且都有数据，而且数据的数目相同  
            if (preorder == null || inorder == null || preorder.length != inorder.length || inorder.length < 1) {
                return null;
            }

            return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
        
        /**
         * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二节树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
         *
         * @param preorder 前序遍历 
         * @param ps       前序遍历的开始位置 
         * @param pe       前序遍历的结束位置 
         * @param inorder  中序遍历 
         * @param is       中序遍历的开始位置 
         * @param ie       中序遍历的结束位置 
         * @return 树的根结点
         */
        public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {

            // 开始位置大于结束位置说明已经没有需要处理的元素了  
            if (ps > pe) {
                return null;
            }
            // 取前序遍历的第一个数字，就是当前的根结点  
            int value = preorder[ps];
            int index = is;
            // 在中序遍历的数组中找根结点的位置  
            while (index <= ie && inorder[index] != value) {
                index++;
            }

            // 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常  
            if (index > ie) {
                throw new RuntimeException("Invalid input");
            }

            // 创建当前的根结点，并且为结点赋值  
            BinaryTreeNode node = new BinaryTreeNode();
            node.value = value;

            // 递归构建当前根结点的左子树，左子树的元素个数：index-is+1个  
            // 左子树对应的前序遍历的位置在[ps+1, ps+index-is]  
            // 左子树对应的中序遍历的位置在[is, index-1]  
            node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1);
            // 递归构建当前根结点的右子树，右子树的元素个数：ie-index个  
            // 右子树对应的前序遍历的位置在[ps+index-is+1, pe]  
            // 右子树对应的中序遍历的位置在[index+1, ie]  
            node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie);

            // 返回创建的根结点  
            return node;
        }
```

## 用两个栈实现一个队列
1. 题目：
 * 用两个栈实现一个队列。队列的声明如下，
 * 请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
2. 思路：
- 栈1用于存储元素，栈2用于弹出元素，负负得正。
- 说的通俗一点，现在把数据1、2、3分别入栈一，然后从栈一中出来（3、2、1），放到栈二中，那么，从栈二中出来的数据（1、2、3）就符合队列的规律了，即负负得正。
3. 解题代码：
```
 public static class MList<T> {
        // 插入栈，只用于插入的数据
        private Stack<T> stack1 = new Stack<>();
        // 弹出栈，只用于弹出数据
        private Stack<T> stack2 = new Stack<>();

        public MList() {
        }

        // 添加操作，成在队列尾部插入结点
        public void appendTail(T t) {
            stack1.add(t);
        }

        // 删除操作，在队列头部删除结点
        public T deleteHead() {

            // 先判断弹出栈是否为空，如果为空就将插入栈的所有数据弹出栈，
            // 并且将弹出的数据压入弹出栈中
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.add(stack1.pop());
                }
            }

            // 如果弹出栈中还没有数据就抛出异常
            if (stack2.isEmpty()) {
                throw new RuntimeException("No more element.");
            }

            // 返回弹出栈的栈顶元素，对应的就是队首元素。
            return stack2.pop();
        }
    }
```

## 旋转数组的最小数字
1. 题目：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。
2. 思路：
 - 个人觉得题目没有说的很清楚，在一个递增数组中做一次旋转，给出旋转后的数组找到最小元素，有个比较暴力的方法，如果前一个元素大于后一个元素，说明旋转了，则找到了最小的元素，如果前一个元素一直小于后一个元素，说明没有旋转，返回第一个元素就可以
- 另一种就是用二分查找法，如果中间元素位于递增，则中间>右边，这时候最小元素在后半部分，反之，最小元素在前半部分

3. 解题代码:
这里只提供暴力解法的代码
```
    public int minNumberInRotateArray(int [] array) {

        int length = array.length - 1;
        if (length == 0)
            return array[0];

        for(int i = 0;i<length;i++){
            if (array[i] > array[i+1])
                return array[i+1];
        }
        //返回第一个元素
        return array[0];
    }
```

## 斐波那契数列
1. 题目:
- 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
2. 思路：
- 这道题首先要知道斐波那契数列的公式为F(n-1) + F(n-2)
- 定义两个遍历，一个a，一个b，进行交互：temp = a , a = b, b = temp + b;

3. 解题代码：
```
public int Fibonacci(int n) {
       if(n <= 0)
           return 0;
       int a = 1 , b = 1;
       int temp;
       for(int i =2 ; i<n;i++){
           temp = a;
           a = b;
           b = temp + b;
       }
       return b;
    }
```

## 跳台阶
1. 题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。
求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
2. 思路：
- 这是一道典型的动态规划问题，对于第n级台阶来说，一种是爬一个台阶，到n-1阶，
另一种是爬两个台阶，到n-2阶
- 这样的话可以推导出公式F(n-1) + F(n-2) 这样算不同的方式
3. 解题代码：
```
  public int JumpFloor(int target) {
        if (target < 0)
            return 0;
        if (target == 1)
            return 1;
        int a = 1, b = 2;
        int temp;
        for (int i = 3; i <= target; i++) {
            temp = a;
            a = b;
            b = temp + b;
        }
        return b;
    }
```

## 变态跳台阶
1. 题目：
 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法。
2. 思路：
- n = 0的时候，f(n) =0
- n = 1的时候，f(n) =1
- n = 2的时候，f(n) 
- 假设到了n级台阶，我们可以n-1级一步跳上来，也可以不经过n-1级跳上来，所以f(n) = 2*f(n-1)
3. 解题代码：
```
 public int JumpFloorII(int target) {
        int res = 1;
        for (int i = 1; i <= target - 1; i++) {
            res = res * 2;
        }
        return res;
    }
```

## 矩形覆盖
1. 题目：
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
2. 思路：
- 不难看出，这也是一个斐波那契问题，这里假设到了n，上一步就有两种情况，在n-1的时候，竖放一个矩形
- 在n-2的时候，横放两个矩形，所以总数是f(n) = f(n-1) + f(n-2)
3. 解题代码：
```
 public int RectCover(int target) {
       if (target<= 0)
           return 0;
           if (target == 1)
           return 1;
       if (target == 2)
           return 2;
       int[] res = new int[target];
       res[0] = 1;
       res[1] = 2;
       for(int i =2;i<= target-1;i++){
           res[i] = res[i-1] + res[i-2];
       }
       return res[target-1];
    }
```

## 二进制中1的个数
1. 题目： 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

2. 思路：
- 如果整数不等于0,那么该整数的二进制至少有1位是1
(1)先假设这个数的最右边一位是1，那么该数字减去1之后，最右边变成了0，其他位不变
(2)假设最后一位不是1而是0，最右边的1在m位，m之前的位不变
上面两种情况总结，一个整数减去1，第m位变成0，m位右边的变为1
3. 解题代码
```java
    private int numberOfOne(int n) {
        int count = 0;
        while(n != 0) {
            count += 1;
            n = (n-1)&n;
        }
        return count;
    }
```