Java实现剑指offer

短命女 2024-04-17 06:07 78阅读 0赞

### 文章目录 ###

*  03\_01\_DuplicationInArray
 *   *  找出数组中重复的数字
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二
             *  解法三
         *  测试用例
 *  03\_02\_DuplicationInArrayNoEdit
 *   *  不修改数组找出重复的数字
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二
         *  测试用例
 *  04\_FindInPartiallySortedMatrix
 *   *  二维数组中的查找
     *   *  题目描述
         *  解法
         *  测试用例
 *  05\_ReplaceSpaces
 *   *  替换空格
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二【推荐】
         *  测试用例
 *  06\_PrintListInReversedOrder
 *   *  从尾到头打印链表
     *   *  题目描述
         *  解法
         *   *  解法一【推荐】
             *  解法二【不推荐】
         *  测试用例
 *  07\_ConstructBinaryTree
 *   *  重建二叉树
     *   *  题目描述
         *  解法
         *  测试用例
 *  08\_NextNodeInBinaryTrees
 *   *  二叉树的下一个结点
     *   *  题目描述
         *  解法
         *  测试用例
 *  09\_01\_QueueWithTwoStacks
 *   *  用两个栈实现队列
     *   *  题目描述
         *  解法
         *  测试用例
 *  09\_02\_StackWithTwoQueues
 *   *  用两个队列实现栈
     *   *  题目描述
         *  解法
         *  测试用例
 *  10\_01\_Fibonacci
 *   *  斐波那契数列
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二
         *  测试用例
 *  10\_02\_JumpFloor
 *   *  跳台阶
     *   *  题目描述
         *  解法
         *  测试用例
 *  10\_03\_JumpFloorII
 *   *  变态跳台阶
     *   *  题目描述
         *  解法
         *  测试用例
 *  10\_04\_RectCover
 *   *  矩形覆盖
     *   *  题目描述
         *  解法
         *   *  解法一：利用数组存放结果
             *  解法二：直接用变量存储结果
         *  测试用例
 *  11\_MinNumberInRotatedArray
 *   *  旋转数组的最小数字
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二
         *  测试用例
 *  12\_StringPathInMatrix
 *   *  矩阵中的路径
     *   *  题目描述
         *  解法
         *  测试用例
 *  13\_RobotMove
 *   *  机器人的移动范围
     *   *  题目描述
         *  解法
         *  测试用例
 *  14\_CuttingRope
 *   *  剪绳子
     *   *  题目描述
         *  解法
         *   *  解法一：动态规划法
             *  贪心算法
         *  测试用例
 *  15\_NumberOf1InBinary
 *   *  二进制中 1 的个数
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二（推荐）
         *  测试用例
 *  16\_Power
 *   *  数值的整数次方
     *   *  题目描述
         *  解法
         *  测试用例
 *  17\_Print1ToMaxOfNDigits
 *   *  打印从 1 到最大的 n 位数
     *   *  题目描述
         *  解法
         *  测试用例
 *  18\_01\_DeleteNodeInList
 *   *  在O(1)时间内删除链表节点
     *   *  题目描述
         *  解法
         *  \`\`\`进行n次操作，平均时间复杂度为：( (n-1) \* O(1) + O(n) ) / n = O(1)，所以符合题目上说的O(1)\`\`\`
         *  测试用例
 *  18\_02\_DeleteDuplicatedNode
 *   *  删除链表中重复的节点
     *   *  题目描述
         *  解法
         *   *  解法一：递归
             *  解法二
         *  测试用例
 *  19\_RegularExpressionsMatching
 *   *  正则表达式匹配
     *   *  题目描述
         *  解法
         *  测试用例
 *  20\_NumericStrings
 *   *  表示数值的字符串
     *   *  题目描述
         *  解法
         *   *  解法一
             *  解法二【剑指offer解法】
         *  测试用例

# 03\_01\_DuplicationInArray #

## 找出数组中重复的数字 ##

### 题目描述 ###

在一个长度为 `n` 的数组里的所有数字都在 `0` 到 `n-1` 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 `7` 的数组 `{2, 3, 1, 0, 2, 5, 3}`，那么对应的输出是重复的数字 `2` 或者 `3`。

### 解法 ###

#### 解法一 ####

排序后，顺序扫描，判断是否有重复，时间复杂度为 `O(n²)`。

#### 解法二 ####

利用哈希表，遍历数组，如果哈希表中没有该元素，则存入哈希表中，否则返回重复的元素。时间复杂度为 `O(n)`，空间复杂度为 `O(n)`。

#### 解法三 ####

长度为 `n`，元素的数值范围也为 `n`，如果没有重复元素，那么数组每个下标对应的值与下标相等。

从头到尾遍历数组，当扫描到下标 `i` 的数字 `nums[i]`：

*  如果等于 `i`，继续向下扫描；
 *  如果不等于 `i`，拿它与第 `nums[i]` 个数进行比较，如果相等，说明有重复值，返回 `nums[i]`。如果不相等，就把第 `i` 个数 和第 `nums[i]` 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 `O(n)`，因为每个元素最多只要两次交换，就能确定位置。空间复杂度为 `O(1)`。

/**
     * @author bingo
     * @since 2018/10/27
     */
    
    public class Solution {
        
        /**
         * 查找数组中的重复元素
         * @param numbers 数组
         * @param length 数组长度
         * @param duplication duplication[0]存储重复元素
         * @return boolean
         */
        public boolean duplicate(int[] numbers, int length, int[] duplication) {
        
            if (numbers == null || length < 1) {
        
                return false;
            }
            for (int e : numbers) {
        
                if (e >= length) {
        
                    return false;
                }
            }
    
            for (int i = 0; i < length; ++i) {
        
                while (numbers[i] != i) {
        
                    if (numbers[i] == numbers[numbers[i]]) {
        
                        duplication[0] = numbers[i];
                        return true;
                    }
                    swap(numbers, i, numbers[i]);
                }
            }
    
            return false;
        }
    
        private void swap(int[] numbers, int i, int j) {
        
            int t = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = t;
        }
    }

### 测试用例 ###

1.  长度为 n 的数组中包含一个或多个重复的数字；
2.  数组中不包含重复的数字；
3.  无效测试输入用例（输入空指针；长度为 n 的数组中包含 0~n-1 之外的数字）。

# 03\_02\_DuplicationInArrayNoEdit #

## 不修改数组找出重复的数字 ##

### 题目描述 ###

在一个长度为 `n+1` 的数组里的所有数字都在 `1` 到 `n` 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 `8` 的数组 `{2, 3, 5, 4, 3, 2, 6, 7}`，那么对应的输出是重复的数字 `2` 或者 `3`。

### 解法 ###

#### 解法一 ####

创建长度为 `n+1` 的辅助数组，把原数组的元素复制到辅助数组中。如果原数组被复制的数是 `m`，则放到辅助数组第 `m` 个位置。这样很容易找出重复元素。空间复杂度为 `O(n)`。

#### 解法二 ####

数组元素的取值范围是 `[1, n]`，对该范围对半划分，分成 `[1, middle]`, `[middle+1, n]`。计算数组中有多少个(count)元素落在 `[1, middle]` 区间内，如果 count 大于 middle-1+1，那么说明这个范围内有重复元素，否则在另一个范围内。继续对这个范围对半划分，继续统计区间内元素数量。

时间复杂度 `O(n * log n)`，空间复杂度 `O(1)`。

注意，此方法无法找出所有重复的元素。

/**
     * @author bingo
     * @since 2018/10/27
     */
    
    public class Solution {
        
        /**
         * 不修改数组查找重复的元素，没有则返回-1
         * @param numbers 数组
         * @return 重复的元素
         */
        public int getDuplication(int[] numbers) {
        
            if (numbers == null || numbers.length < 1) {
        
                return -1;
            }
    
            int start = 1;
            int end = numbers.length - 1;
            while (end >= start) {
        
                int middle = start + ((end - start) >> 1);
    
                // 调用 log n 次
                int count = countRange(numbers, start, middle);
                if (start == end) {
        
                    if (count > 1) {
        
                        return start;
                    }
                    break;
                } else {
        
                    // 无法找出所有重复的数
                    if (count > (middle - start) + 1) {
        
                        end = middle;
                    } else {
        
                        start = middle + 1;
                    }
                }
            }
            return -1;
        }
    
    
        /**
         * 计算整个数组中有多少个数的取值在[start, end] 之间
         * 时间复杂度 O(n)
         * @param numbers 数组
         * @param start 左边界
         * @param end 右边界
         * @return 数量
         */
        private int countRange(int[] numbers, int start, int end) {
        
            if (numbers == null) {
        
                return 0;
            }
            int count = 0;
            for(int e : numbers) {
        
                if (e >= start && e <= end) {
        
                    ++count;
                }
            }
            return count;
        }
    }

### 测试用例 ###

1.  长度为 n 的数组中包含一个或多个重复的数字；
2.  数组中不包含重复的数字；
3.  无效测试输入用例（输入空指针）。

# 04\_FindInPartiallySortedMatrix #

## 二维数组中的查找 ##

### 题目描述 ###

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

### 解法 ###

从二维数组的右上方开始查找：

*  若元素值等于 `target`，返回 `true`；
 *  若元素值大于 `target`，砍掉这一列，即 `--j`；
 *  若元素值小于 `target`，砍掉这一行，即 `++i`。

也可以从二维数组的左下方开始查找，以下代码使用左下方作为查找的起点。

注意，不能选择左上方或者右下方的数字，因为这样无法缩小查找的范围。

/**
     * @author bingo
     * @since 2018/10/27
     */
    
    public class Solution {
        
        /**
         * 二维数组中的查找
         * @param target 目标值
         * @param array 二维数组
         * @return boolean
         */
        public boolean find(int target, int[][] array) {
        
            if (array == null) {
        
                return false;
            }
            int rows = array.length;
            int columns = array[0].length;
            
            int i = rows - 1;
            int j = 0;
            while (i >= 0 && j < columns) {
        
                if (array[i][j] == target) {
        
                    return true;
                }
                if (array[i][j] < target) {
        
                    ++j;
                } else {
        
                    --i;
                }
            }
            return false;
        }
    }

### 测试用例 ###

1.  二维数组中包含查找的数字（查找的数字是数组中的最大值和最小值；查找的数字介于数组中的最大值和最小值之间）；
2.  二维数组中没有查找的数字（查找的数字大于/小于数组中的最大值；查找的数字在数组的最大值和最小值之间但数组中没有这个数字）；
3.  特殊输入测试（输入空指针）。

# 05\_ReplaceSpaces #

## 替换空格 ##

### 题目描述 ###

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

### 解法 ###

#### 解法一 ####

创建 `StringBuilder`，遍历原字符串，遇到非空格，直接 append 到 `StringBuilder` 中，遇到空格则将 `%20` append 到 `StringBuilder` 中。

/**
     * @author bingo
     * @since 2018/10/27
     */
    
    public class Solution {
        
        /**
         * 将字符串中的所有空格替换为%20
         * @param str 字符串
         * @return 替换后的字符串
         */
        public String replaceSpace(StringBuffer str) {
        
            if (str == null || str.length() == 0) {
        
                return str.toString();
            }
            StringBuilder sb = new StringBuilder();
            int len = str.length();
            for (int i = 0; i < len; ++i) {
        
                char ch = str.charAt(i);
                sb.append(ch == ' ' ? "%20" : ch);
            }
    
            return sb.toString();
        }
    }

#### 解法二【推荐】 ####

先遍历原字符串，遇到空格，则在原字符串末尾 `append` 任意两个字符，如两个空格。

用指针 `p` 指向原字符串末尾，`q` 指向现字符串末尾，`p`, `q` 从后往前遍历，当 `p` 遇到空格，`q` 位置依次要 `append` ‘02%’，若不是空格，直接 `append` `p` 指向的字符。

> ?思路扩展：  
> 在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。

/**
     * @author bingo
     * @since 2018/10/27
     */
    
    public class Solution {
        
        /**
         * 将字符串中的所有空格替换为%20
         * @param str 字符串
         * @return 替换后的字符串
         */
        public String replaceSpace(StringBuffer str) {
        
            if (str == null || str.length() == 0) {
        
                return str.toString();
            }
            
            int len = str.length();
            for (int i = 0; i < len; ++i) {
        
                if (str.charAt(i) == ' ') {
        
                    // append 两个空格
                    str.append("  ");
                }
            }
    
            // p 指向原字符串末尾
            int p = len - 1;
    
            // q 指向现字符串末尾
            int q = str.length() - 1;
    
            while (p >= 0) {
        
                char ch = str.charAt(p--);
                if (ch == ' ') {
        
                    str.setCharAt(q--, '0');
                    str.setCharAt(q--, '2');
                    str.setCharAt(q--, '%');
                } else {
        
                    str.setCharAt(q--, ch);
                }
            }
    
            return str.toString();
    
        }
    }

### 测试用例 ###

1.  输入的字符串包含空格（空格位于字符串的最前面/最后面/中间；字符串有多个连续的空格）；
2.  输入的字符串中没有空格；
3.  特殊输入测试（字符串是一个空指针；字符串是一个空字符串；字符串只有一个空格字符；字符串中有多个连续空格）。

# 06\_PrintListInReversedOrder #

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

### 题目描述 ###

输入一个链表，按链表值从尾到头的顺序返回一个 `ArrayList`。

### 解法 ###

#### 解法一【推荐】 ####

遍历链表，每个链表结点值 `push` 进栈，最后将栈中元素依次 `pop` 到 `list` 中。

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    import java.util.Stack;
    
    /**
     * @author bingo
     * @since 2018/10/28
     */
    public class Solution {
        
        /**
         * 从尾到头打印链表
         * @param listNode 链表头节点
         * @return list
         */
        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;
        }
    }

#### 解法二【不推荐】 ####

利用递归方式：

*  若不是链表尾结点，继续递归；
 *  若是，添加到 `list` 中。

这种方式不推荐，当递归层数过多时，容易发生 `Stack Overflow`。

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    import java.util.Stack;
    
    /**
     * @author bingo
     * @since 2018/10/28
     */
    public class Solution {
        
        /**
         * 从尾到头打印链表
         * @param listNode 链表头结点
         * @return list
         */
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
            ArrayList<Integer> res = new ArrayList<>();
            if (listNode == null) {
        
                return res;
            }
            
            addElement(listNode, res);
            return res;
            
        }
        
        private void addElement(ListNode listNode, ArrayList<Integer> res) {
        
            if (listNode.next != null) {
        
                // 递归调用
                addElement(listNode.next, res);
            }
            res.add(listNode.val);
        }
    }

### 测试用例 ###

1.  功能测试（输入的链表有多个结点；输入的链表只有一个结点）；
2.  特殊输入测试（输入的链表结点指针为空）。

# 07\_ConstructBinaryTree #

## 重建二叉树 ##

### 题目描述 ###

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

### 解法 ###

在二叉树的前序遍历序列中，第一个数字总是根结点的值。在中序遍历序列中，根结点的值在序列的中间，左子树的结点位于根结点左侧，而右子树的结点位于根结点值的右侧。

遍历中序序列，找到根结点，递归构建左子树与右子树。

注意添加特殊情况的 `if` 判断。

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    /**
     * @author bingo
     * @since 2018/10/28
     */
    
    public class Solution {
        
        /**
         * 重建二叉树
         * 
         * @param pre 先序序列
         * @param in  中序序列
         * @return 二叉树根结点
         */
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        
            if (pre == null || in == null || pre.length != in.length) {
        
                return null;
            }
            int n = pre.length;
            return constructBinaryTree(pre, 0, n - 1, in, 0, n - 1);
        }
    
        private TreeNode constructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        
            TreeNode node = new TreeNode(pre[startPre]);
            if (startPre == endPre) {
        
                if (startIn == endIn) {
        
                    return node;
                }
                throw new IllegalArgumentException("Invalid input!");
            }
    
            int inOrder = startIn;
            while (in[inOrder] != pre[startPre]) {
        
                ++inOrder;
                if (inOrder > endIn) {
        
                    new IllegalArgumentException("Invalid input!");
                }
            }
            int len = inOrder - startIn;
            if (len > 0) {
        
                // 递归构建左子树
                node.left = constructBinaryTree(pre, startPre + 1, startPre + len, in, startIn, inOrder - 1);
            }
    
            if (inOrder < endIn) {
        
                // 递归构建右子树
                node.right = constructBinaryTree(pre, startPre + len + 1, endPre, in, inOrder + 1, endIn);
            }
            return node;
    
        }
    }

### 测试用例 ###

1.  普通二叉树（完全二叉树；不完全二叉树）；
2.  特殊二叉树（所有结点都没有左/右子结点；只有一个结点的二叉树）；
3.  特殊输入测试（二叉树根结点为空；输入的前序序列和中序序列不匹配）。

# 08\_NextNodeInBinaryTrees #

## 二叉树的下一个结点 ##

### 题目描述 ###

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

### 解法 ###

对于结点 `pNode`：

*  如果它有右子树，则**右子树的最左结点**就是它的下一个结点；
 *  如果它没有右子树，判断它与父结点 `pNode.next` 的位置情况：
    
     *  如果它是父结点的左孩子，那么父结点 `pNode.next` 就是它的下一个结点；
     *  如果它是父结点的右孩子，一直向上寻找，直到找到某个结点，它是它父结点的左孩子，那么该父结点就是 `pNode` 的下一个结点。

/*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    
    /**
     * @author bingo
     * @since 2018/10/28
     */
    
    public class Solution {
        
        /**
         * 获取中序遍历结点的下一个结点
         * @param pNode 某个结点
         * @return pNode的下一个结点
         */
        public TreeLinkNode GetNext(TreeLinkNode pNode) {
        
            if (pNode == null) {
        
                return null;
            }
            
            if (pNode.right != null) {
        
                TreeLinkNode t = pNode.right;
                while (t.left != null) {
        
                    t = t.left;
                }
                return t;
            }
            
            // 须保证 pNode.next 不为空，否则会出现 NPE
            if (pNode.next != null && pNode.next.left == pNode) {
        
                return pNode.next;
            }
            
            while (pNode.next != null) {
        
                if (pNode.next.left == pNode) {
        
                    return pNode.next;
                }
                pNode = pNode.next;
            }
            
            return null;
            
        }
    }

### 测试用例 ###

1.  普通二叉树（完全二叉树；不完全二叉树）；
2.  特殊二叉树（所有结点都没有左/右子结点；只有一个结点的二叉树；二叉树的根结点为空）；
3.  不同位置的结点的下一个结点（下一个结点为当前结点的右子结点、右子树的最左子结点、父结点、跨层的父结点等；当前结点没有下一个结点）。

# 09\_01\_QueueWithTwoStacks #

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

### 题目描述 ###

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

### 解法 ###

`Push` 操作，每次都存入 `stack1`；  
`Pop` 操作，每次从 `stack2` 取：

*  `stack2` 栈不为空时，不能将 `stack1` 元素倒入；
 *  `stack2` 栈为空时，需要一次将 `stack1` 元素全部倒入。

import java.util.Stack;
    
    /**
     * @author bingo
     * @since 2018/10/28
     */
    
    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 (stack2.isEmpty()) {
        
                if (stack1.isEmpty()) {
        
                    return -1;
                }
                while (!stack1.isEmpty()) {
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

### 测试用例 ###

1.  往空的队列里添加、删除元素；
2.  往非空的队列添加、删除元素；
3.  连续删除元素直至队列为空。

# 09\_02\_StackWithTwoQueues #

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

### 题目描述 ###

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

### 解法 ###

`Push` 操作，每次都存入 `queue1`；  
`Pop` 操作，每次从 `queue1` 取：

*  将 `queue1` 中的元素依次倒入 `queue2`，直到 `queue1` 剩下一个元素，这个元素就是要 `pop` 出去的；
 *  将 `queue1` 与 `queue2` 进行交换，这样保证每次都从 `queue1` 中存取元素，`queue2` 只起到辅助暂存的作用。

import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * @author bingo
     * @since 2018/10/29
     */
    
    public class Solution {
        
    
        private Queue<Integer> queue1 = new LinkedList<>();
        private Queue<Integer> queue2 = new LinkedList<>();
    
        public void push(int node) {
        
            queue1.offer(node);
        }
    
        public int pop() {
        
            if (queue1.isEmpty()) {
        
                throw new RuntimeException("Empty stack!");
            }
    
            while (queue1.size() > 1) {
        
                queue2.offer(queue1.poll());
            }
    
            int val = queue1.poll();
    
            Queue<Integer> t = queue1;
            queue1 = queue2;
            queue2 = t;
            return val;
    
        }
    }

### 测试用例 ###

1.  往空的栈里添加、删除元素；
2.  往非空的栈添加、删除元素；
3.  连续删除元素直至栈为空。

# 10\_01\_Fibonacci #

## 斐波那契数列 ##

### 题目描述 ###

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

### 解法 ###

#### 解法一 ####

采用递归方式，简洁明了，但效率很低，存在大量的重复计算。

f(10)
                   /        \
                f(9)         f(8)
              /     \       /    \
           f(8)     f(7)  f(7)   f(6)
          /   \     /   \ 
       f(7)  f(6)  f(6) f(5)

/**
     * @author bingo
     * @since 2018/10/29
     */
    
    public class Solution {
        
        /**
         * 求斐波那契数列的第n项，n从0开始
         * @param n 第n项
         * @return 第n项的值
         */
        public int Fibonacci(int n) {
        
            if (n < 2) {
        
                return n;
            }
            // 递归调用
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

#### 解法二 ####

从下往上计算，递推，时间复杂度 `O(n)`。

/**
     * @author bingo
     * @since 2018/10/29
     */
    
    public class Solution {
        
        /**
         * 求斐波那契数列的第n项，n从0开始
         * @param n 第n项
         * @return 第n项的值
         */
        public int Fibonacci(int n) {
        
            if (n < 2) {
        
                return n;
            }
            int[] res = new int[n + 1];
            res[0] = 0;
            res[1] = 1;
            for (int i = 2; i <= n; ++i) {
        
                res[i] = res[i - 1] + res[i - 2];
            }
            return res[n];
    
        }
    }

### 测试用例 ###

1.  功能测试（如输入 3、5、10 等）；
2.  边界值测试（如输入 0、1、2）；
3.  性能测试（输入较大的数字，如 40、50、100 等）。

# 10\_02\_JumpFloor #

## 跳台阶 ##

### 题目描述 ###

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

### 解法 ###

跳上 `n` 级台阶，可以从 `n-1` 级跳 `1` 级上去，也可以从 `n-2` 级跳 `2` 级上去。所以

f(n) = f(n-1) + f(n-2)

/**
     * @author bingo
     * @since 2018/11/23
     */
    
    public class Solution {
        
        /**
         * 青蛙跳台阶
         * @param target 跳上的那一级台阶
         * @return 多少种跳法
         */
        public int JumpFloor(int target) {
        
            if (target < 3) {
        
                return target;
            }
            int[] res = new int[target + 1];
            res[1] = 1;
            res[2] = 2;
            for (int i = 3; i <= target; ++i) {
        
                res[i] = res[i - 1] + res[i - 2];
            }
            return res[target];
        }
    }

### 测试用例 ###

1.  功能测试（如输入 3、5、10 等）；
2.  边界值测试（如输入 0、1、2）；
3.  性能测试（输入较大的数字，如 40、50、100 等）。

# 10\_03\_JumpFloorII #

## 变态跳台阶 ##

### 题目描述 ###

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

### 解法 ###

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

f(n-1) = f(0) + f(1) + ... + f(n-2) ①

跳上 `n` 级台阶，可以从 `n-1` 级跳 `1` 级上去，也可以从 `n-2` 级跳 `2` 级上去…也可以从 `0` 级跳上去。那么

f(n) = f(0) + f(1) + ... + f(n-2) + f(n-1)  ②
    
    ②-①：
    f(n) - f(n-1) = f(n-1)
    f(n) = 2f(n-1)

所以 f(n) 是一个等比数列：

f(n) = 2^(n-1)

/**
     * @author bingo
     * @since 2018/11/23
     */
    
    public class Solution {
        
        /**
         * 青蛙跳台阶II
         * @param target 跳上的那一级台阶
         * @return 多少种跳法
         */
        public int JumpFloorII(int target) {
        
            return (int) Math.pow(2, target - 1);
        }
    }

### 测试用例 ###

1.  功能测试（如输入 3、5、10 等）；
2.  边界值测试（如输入 0、1、2）；
3.  性能测试（输入较大的数字，如 40、50、100 等）。

# 10\_04\_RectCover #

## 矩形覆盖 ##

### 题目描述 ###

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

### 解法 ###

覆盖 `2*n` 的矩形：

*  可以先覆盖 `2*n-1` 的矩形，再覆盖一个 `2*1` 的矩形；
 *  也可以先覆盖 `2*(n-2)` 的矩形，再覆盖两个 `1*2` 的矩形。

#### 解法一：利用数组存放结果 ####

/**
     * @author bingo
     * @since 2018/11/23
     */
    
    public class Solution {
        
        /**
         * 矩形覆盖
         * @param target 2*target大小的矩形
         * @return 多少种覆盖方法
         */
        public int RectCover(int target) {
        
            if (target < 3) {
        
                return target;
            }
            int[] res = new int[target + 1];
            res[1] = 1;
            res[2] = 2;
            for (int i = 3; i <= target; ++i) {
        
                res[i] = res[i - 1] + res[i - 2];
            }
            return res[target];
        }
    }

#### 解法二：直接用变量存储结果 ####

/**
     * @author bingo
     * @since 2018/11/23
     */
    
    public class Solution {
        
        /**
         * 矩形覆盖
         * @param target 2*target大小的矩形
         * @return 多少种覆盖方法
         */
        public int RectCover(int target) {
        
            if (target < 3) {
        
                return target;
            }
            int res1 = 1;
            int res2 = 2;
            int res = 0;
            for (int i = 3; i <= target; ++i) {
        
                res = res1 + res2;
                res1 = res2;
                res2 = res;
            }
            return res;
        }
    }

### 测试用例 ###

1.  功能测试（如输入 3、5、10 等）；
2.  边界值测试（如输入 0、1、2）；
3.  性能测试（输入较大的数字，如 40、50、100 等）。

# 11\_MinNumberInRotatedArray #

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

### 题目描述 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组 `{3,4,5,1,2}` 为 `{1,2,3,4,5}` 的一个旋转，该数组的最小值为 `1`。

\*\*NOTE：\*\*给出的所有元素都大于 `0`，若数组大小为 `0`，请返回 `0`。

### 解法 ###

#### 解法一 ####

直接遍历数组找最小值，时间复杂度 `O(n)`，不推荐。

/**
     * @author bingo
     * @since 2018/10/30
     */
    
    public class Solution {
        
        /**
         * 获取旋转数组的最小元素
         * @param array 旋转数组
         * @return 数组中的最小值
         */
        public int minNumberInRotateArray(int[] array) {
        
            if (array == null || array.length == 0) {
        
                return 0;
            }
    
            int n = array.length;
            if (n == 1 || array[0] < array[n - 1]) {
        
                return array[0];
            }
    
            int min = array[0];
            for (int i = 1; i < n; ++i) {
        
                min = array[i] < min ? array[i] : min;
            }
    
            return min;
        }
    
    }

#### 解法二 ####

利用指针 `p`,`q` 指向数组的首尾，如果 `array[p] < array[q]`，说明数组是递增数组，直接返回 `array[p]`。否则进行如下讨论。

计算中间指针 `mid`：

*  如果此时 `array[p]`, `array[q]`, `array[mid]` 两两相等，此时无法采用二分方式，只能通过遍历区间 `[p,q]` 获取最小值；
 *  如果此时 `p`,`q` 相邻，说明此时 `q` 指向的元素是最小值，返回 `array[q]`；
 *  如果此时 `array[mid] >= array[p]`，说明 `mid` 位于左边的递增数组中，最小值在右边，因此，把 `p` 指向 `mid`，此时保持了 `p` 指向左边递增子数组；
 *  如果此时 `array[mid] <= array[q]`，说明 `mid` 位于右边的递增数组中，最小值在左边，因此，把 `q` 指向 `mid`，此时保持了 `q` 指向右边递增子数组。

/**
     * @author bingo
     * @since 2018/10/30
     */
    
    public class Solution {
        
        /**
         * 获取旋转数组的最小元素
         * @param array 旋转数组
         * @return 数组中的最小值
         */
        public int minNumberInRotateArray(int[] array) {
        
            if (array == null || array.length == 0) {
        
                return 0;
            }
    
            int p = 0;
            // mid初始为p，为了兼容当数组是递增数组(即不满足 array[p] >= array[q])时，返回 array[p]
            int mid = p;
            int q = array.length - 1;
            while (array[p] >= array[q]) {
        
                if (q - p == 1) {
        
                    // 当p,q相邻时(距离为1)，那么q指向的元素就是最小值
                    mid = q;
                    break;
                }
                mid = p + ((q - p) >> 1);
    
                // 当p,q,mid指向的值相等时，此时只能通过遍历查找最小值
                if (array[p] == array[q] && array[mid] == array[p]) {
        
                    mid = getMinIndex(array, p, q);
                    break;
                }
    
                if (array[mid] >= array[p]) {
        
                    p = mid;
                } else if (array[mid] <= array[q]) {
        
                    q = mid;
                }
            }
    
            return array[mid];
    
    
        }
    
        private int getMinIndex(int[] array, int p, int q) {
        
            int minIndex = p;
            for (int i = p + 1; i <= q; ++i) {
        
                minIndex = array[i] < array[minIndex] ? i : minIndex;
            }
            return minIndex;
        }
    }

### 测试用例 ###

1.  功能测试（输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字）；
2.  边界值测试（输入的数组是一个升序排序的数组，只包含一个数字的数组）；
3.  特殊输入测试（输入空指针）。

# 12\_StringPathInMatrix #

## 矩阵中的路径 ##

### 题目描述 ###

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 `a b c e s f c s a d e e` 这样的 `3 X 4` 矩阵中包含一条字符串`"bcced"`的路径，但是矩阵中不包含`"abcb"`路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

### 解法 ###

回溯法。首先，任选一个格子作为路径起点。假设格子对应的字符为 ch，并且对应路径上的第 i 个字符。若相等，到相邻格子寻找路径上的第 i+1 个字符。重复这一过程。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
        /**
         * 判断矩阵中是否包含某条路径
         * @param matrix 矩阵
         * @param rows 行数
         * @param cols 列数
         * @param str 路径
         * @return bool
         */
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        
            if (matrix == null || rows < 1 || cols < 1 || str == null) {
        
                return false;
            }
            boolean[] visited = new boolean[matrix.length];
            int pathLength = 0;
            for (int i = 0; i < rows; ++i) {
        
                for (int j = 0; j < cols; ++j) {
        
                    if (hasPath(matrix, rows, cols, str, i, j, pathLength, visited)) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean hasPath(char[] matrix, int rows, int cols, char[] str, int i, int j, int pathLength, boolean[] visited) {
        
            if (pathLength == str.length) {
        
                return true;
            }
            boolean hasPath = false;
            if (i >= 0 && i < rows && j >= 0 && j < cols && matrix[i * cols + j] == str[pathLength] && !visited[i * cols + j]) {
        
                ++pathLength;
                visited[i * cols + j] = true;
                hasPath = hasPath(matrix, rows, cols, str, i - 1, j, pathLength, visited)
                        || hasPath(matrix, rows, cols, str, i + 1, j, pathLength, visited)
                        || hasPath(matrix, rows, cols, str, i, j - 1, pathLength, visited)
                        || hasPath(matrix, rows, cols, str, i, j + 1, pathLength, visited);
                if (!hasPath) {
        
                    --pathLength;
                    visited[i * cols + j] = false;
                }
            }
            return hasPath;
        }
    }

### 测试用例 ###

1.  功能测试（在多行多列的矩阵中存在或者不存在路径）；
2.  边界值测试（矩阵只有一行或者一列；矩阵和路径中的所有字母都是相同的）；
3.  特殊输入测试（输入空指针）。

# 13\_RobotMove #

## 机器人的移动范围 ##

### 题目描述 ###

地上有一个`m`行和`n`列的方格。一个机器人从坐标`0,0`的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于`k`的格子。 例如，当`k`为`18`时，机器人能够进入方格`（35,37）`，因为`3+5+3+7 = 18`。但是，它不能进入方格`（35,38）`，因为`3+5+3+8 = 19`。请问该机器人能够达到多少个格子？

### 解法 ###

从坐标(0, 0) 开始移动，当它准备进入坐标(i, j)，判断是否能进入，如果能，再判断它能否进入 4 个相邻的格子 (i-1, j), (i+1, j), (i, j-1), (i, j+1)。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
        /**
         * 计算能到达的格子数
         * @param threshold 限定的数字
         * @param rows 行数
         * @param cols 列数
         * @return 格子数
         */
        public int movingCount(int threshold, int rows, int cols) {
        
            if (threshold < 0 || rows < 1 || cols < 1) {
        
                return 0;
            }
            boolean[] visited = new boolean[rows * cols];
            return getCount(threshold, 0, 0, rows, cols, visited);
        }
    
        private int getCount(int threshold, int i, int j, int rows, int cols, boolean[] visited) {
        
            if (check(threshold, i, j, rows, cols, visited)) {
        
                visited[i * cols + j] = true;
                return 1
                        + getCount(threshold, i - 1, j, rows, cols, visited)
                        + getCount(threshold, i + 1, j, rows, cols, visited)
                        + getCount(threshold, i, j - 1, rows, cols, visited)
                        + getCount(threshold, i, j + 1, rows, cols, visited);
            }
            return 0;
        }
    
        private boolean check(int threshold, int i, int j, int rows, int cols, boolean[] visited) {
        
            return i >= 0
                    && i < rows
                    && j >= 0
                    && j < cols
                    && !visited[i * cols + j]
                    && getDigitSum(i) + getDigitSum(j) <= threshold;
        }
    
        private int getDigitSum(int i) {
        
            int res = 0;
            while (i > 0) {
        
                res += i % 10;
                i /= 10;
            }
            return res;
        }
    }

### 测试用例 ###

1.  功能测试（方格为多行多列；k 为正数）；
2.  边界值测试（方格只有一行或者一列；k = 0）；
3.  特殊输入测试（k < 0）。

# 14\_CuttingRope #

## 剪绳子 ##

### 题目描述 ###

给你一根长度为`n`绳子，请把绳子剪成`m`段（`m`、`n`都是整数，`n>1`并且`m≥1`）。每段的绳子的长度记为k\[0\]、k\[1\]、……、k\[m\]。k\[0\]*k\[1\]*…\*k\[m\]可能的最大乘积是多少？例如当绳子的长度是 8 时，我们把它剪成长度分别为 `2、3、3` 的三段，此时得到最大的乘积`18`。

### 解法 ###

#### 解法一：动态规划法 ####

时间复杂度`O(n²)`，空间复杂度`O(n)`。

*  长度为 2，只可能剪成长度为 1 的两段，因此 f(2)=1
 *  长度为 3，剪成长度分别为 1 和 2 的两段，乘积比较大，因此 f(3) = 2
 *  长度为 n，在剪第一刀的时候，有 n-1 种可能的选择，剪出来的绳子又可以继续剪，可以看出，原问题可以划分为子问题，子问题又有重复子问题。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
    
        /**
         * 剪绳子求最大乘积
         * @param length 绳子长度
         * @return 乘积最大值
         */
        public int maxProductAfterCutting(int length) {
        
            if (length < 2) {
        
                return 0;
            }
            if (length < 4) {
        
                return length - 1;
            }
    
            // res[i] 表示当长度为i时的最大乘积
            int[] res = new int[length + 1];
            res[1] = 1;
            res[2] = 2;
            res[3] = 3;
            // 从长度为4开始计算
            for (int i = 4; i <= length; ++i) {
        
                int max = 0;
                for (int j = 1; j <= i / 2; ++j) {
        
                    max = Math.max(max, res[j] * res[i - j]);
                }
                res[i] = max;
            }
    
            return res[length];
    
        }
    }

#### 贪心算法 ####

时间复杂度`O(1)`，空间复杂度`O(1)`。

贪心策略：

*  当 n>=5 时，尽可能多地剪长度为 3 的绳子
 *  当剩下的绳子长度为 4 时，就把绳子剪成两段长度为 2 的绳子。

**证明：**

*  当 n>=5 时，可以证明 2(n-2)>n，并且 3(n-3)>n。也就是说，当绳子剩下长度大于或者等于 5 的时候，可以把它剪成长度为 3 或者 2 的绳子段。
 *  当 n>=5 时，3(n-3)>=2(n-2)，因此，应该尽可能多地剪长度为 3 的绳子段。
 *  当 n=4 时，剪成两根长度为 2 的绳子，其实没必要剪，只是题目的要求是至少要剪一刀。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
    
        /**
         * 剪绳子求最大乘积
         * @param length 绳子长度
         * @return 乘积最大值
         */
        public int maxProductAfterCutting(int length) {
        
            if (length < 2) {
        
                return 0;
            }
            if (length < 4) {
        
                return length - 1;
            }
    
            int timesOf3 = length / 3;
            if (length % 3 == 1) {
        
                --timesOf3;
            }
            int timesOf2 = (length - timesOf3 * 3) >> 1;
            return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
        }
    }

### 测试用例 ###

1.  功能测试（绳子的初始长度大于 5）；
2.  边界值测试（绳子的初始长度分别为 0、1、2、3、4）。

# 15\_NumberOf1InBinary #

## 二进制中 1 的个数 ##

### 题目描述 ###

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

### 解法 ###

#### 解法一 ####

利用整数 1，依次左移每次与 n 进行与运算，若结果不为0，说明这一位上数字为 1，++cnt。

此解法 i 需要左移 32 次。

不要用 n 去右移并与 1 进行与运算，因为n 可能为负数，右移时会陷入死循环。

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

#### 解法二（推荐） ####

*  运算 (n - 1) & n，直至 n 为 0。运算的次数即为 n 的二进制中 1 的个数。

因为 n-1 会将 n 的最右边一位 1 改为 0，如果右边还有 0，则所有 0 都会变成 1。结果与 n 进行与运算，会去除掉最右边的一个1。

举个栗子：

若 n = 1100，
    n - 1 = 1011
    n & (n - 1) = 1000
    
    即：把最右边的 1 变成了 0。

> 把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
        /**
         * 计算整数的二进制表示里1的个数
         * @param n 整数
         * @return 1的个数
         */
        public int NumberOf1(int n) {
        
            int cnt = 0;
            while (n != 0) {
        
                n = (n - 1 ) & n;
                ++cnt;
            }
            return cnt;
        }
    }

### 测试用例 ###

1.  正数（包括边界值 1、0x7FFFFFFF）；
2.  负数（包括边界值 0x80000000、0xFFFFFFFF）；
3.  0。

# 16\_Power #

## 数值的整数次方 ##

### 题目描述 ###

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

### 解法 ###

注意判断值数是否小于 0。另外 0 的 0 次方没有意义，也需要考虑一下，看具体题目要求。

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
        /**
         * 计算数值的整数次方
         * @param base 底数
         * @param exponent 指数
         * @return 数值的整数次方
         */
        public double Power(double base, int exponent) {
        
            double result = 1.0;
            int n = Math.abs(exponent);
            for (int i = 0; i < n; ++i) {
        
                result *= base;
            }
    
            return exponent < 0 ? 1.0 / result : result;
        }
    }

### 测试用例 ###

1.  把底数和指数分别设为正数、负数和零。

# 17\_Print1ToMaxOfNDigits #

## 打印从 1 到最大的 n 位数 ##

### 题目描述 ###

输入数字 `n`，按顺序打印出从 `1` 最大的 `n` 位十进制数。比如输入 `3`，则打印出 `1、2、3` 一直到最大的 3 位数即 999。

### 解法 ###

此题需要注意 n 位数构成的数字可能超出最大的 int 或者 long long 能表示的范围。因此，采用字符数组来存储数字。

关键是：

*  对字符数组表示的数进行递增操作
 *  输出数字（0开头的需要把0去除）

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
    
        /**
         * 打印从1到最大的n位数
         * @param n n位
         */
        public void print1ToMaxOfNDigits(int n) {
        
            if (n < 1) {
        
                return;
            }
    
            char[] chars = new char[n];
            for (int i = 0; i < n; ++i) {
        
                chars[i] = '0';
            }
    
            while (!increment(chars)) {
        
                printNumber(chars);
            }
        }
    
        /**
         * 打印数字（去除前面的0）
         * @param chars 数字数组
         */
        private void printNumber(char[] chars) {
        
            int index = 0;
            int n = chars.length;
            for (char ch : chars) {
        
                if (ch != '0') {
        
                    break;
                }
                ++index;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = index; i < n; ++i) {
        
                sb.append(chars[i]);
            }
            System.out.println(sb.toString());
        }
    
        /**
         * 数字加1
         * @param chars 数字数组
         * @return 是否溢出
         */
        private boolean increment(char[] chars) {
        
            boolean flag = false;
            int n = chars.length;
            int carry = 1;
            for (int i = n - 1; i >= 0; --i) {
        
    
                int num = chars[i] - '0' + carry;
                if (num > 9) {
        
                    if (i == 0) {
        
                        flag = true;
                        break;
                    }
                    chars[i] = '0';
                } else {
        
                    ++chars[i];
                    break;
                }
            }
            return flag;
        }
    }

### 测试用例 ###

1.  功能测试（输入 1、2、3…）；
2.  特殊输入测试（输入 -1、0）。

# 18\_01\_DeleteNodeInList #

## 在O(1)时间内删除链表节点 ##

### 题目描述 ###

给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间内删除该节点。

### 解法 ###

判断要删除的节点是否是尾节点，若是，直接删除；若不是，把要删除节点的下一个节点赋给要删除的节点即可。

### `进行n次操作，平均时间复杂度为：( (n-1) * O(1) + O(n) ) / n = O(1)，所以符合题目上说的O(1)` ###

/**
     * @author bingo
     * @since 2018/11/20
     */
    
    public class Solution {
        
    
        class ListNode {
        
            int val;
            ListNode next;
        }
    
        /**
         * 删除链表的节点
         * @param head 链表头节点
         * @param tobeDelete 要删除的节点
         */
        public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
        
            if (head == null || tobeDelete == null) {
        
                return head;
            }
    
            // 删除的不是尾节点
            if (tobeDelete.next != null) {
        
                tobeDelete.val = tobeDelete.next.val;
                tobeDelete.next = tobeDelete.next.next;
            }
            // 链表中仅有一个节点
            else if (head == tobeDelete) {
        
                head = null;
            }
            // 删除的是尾节点
            else {
        
                ListNode ptr = head;
                while (ptr.next != tobeDelete) {
        
                    ptr = ptr.next;	
              	}
                ptr.next = null;
            }
    
            return head;
        }
    }

### 测试用例 ###

1.  功能测试（从有多个节点的链表的中间/头部/尾部删除一个节点；从只有一个节点的链表中删除唯一的节点）；
2.  特殊输入测试（指向链表头节点的为空指针；指向要删除节点的为空指针）。

# 18\_02\_DeleteDuplicatedNode #

## 删除链表中重复的节点 ##

### 题目描述 ###

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表`1->2->3->3->4->4->5` 处理后为 `1->2->5`。

### 解法 ###

#### 解法一：递归 ####

/**
     * @author bingo
     * @since 2018/11/21
     */
    
    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        
        /**
         * 删除链表重复的节点
         * @param pHead 链表头节点
         * @return 删除节点后的链表
         */
        public ListNode deleteDuplication(ListNode pHead) {
        
            if (pHead == null || pHead.next == null) {
        
                return pHead;
            }
    
            if (pHead.val == pHead.next.val) {
        
                if (pHead.next.next == null) {
        
                    return null;
                }
                if (pHead.next.next.val == pHead.val) {
        
                    return deleteDuplication(pHead.next);
                }
                return deleteDuplication(pHead.next.next);
            }
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        }
    }

#### 解法二 ####

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        
        public ListNode deleteDuplication(ListNode pHead) {
        
            if (pHead == null || pHead.next == null) {
        
                return pHead;
            }
            
            ListNode pre = null;
            ListNode cur = pHead;
            while (cur != null) {
        
                if (cur.next != null && cur.next.val == cur.val) {
        
                    int val = cur.val;
                    while (cur.next != null && cur.next.val == val) {
        
                        cur = cur.next;
                    }
                    if (pre == null) {
        
                        pHead = cur.next;
                    } else {
        
                        pre.next = cur.next;
                    }
                } else {
        
                    pre = cur;
                }
                cur = cur.next;
            }
            return pHead;
        }
    }

### 测试用例 ###

1.  功能测试（重复的节点位于链表的头部/中间/尾部；链表中没有重复的节点）；
2.  特殊输入测试（指向链表头节点的为空指针；链表中所有节点都是重复的）。

# 19\_RegularExpressionsMatching #

## 正则表达式匹配 ##

### 题目描述 ###

请实现一个函数用来匹配包括`.`和`*`的正则表达式。模式中的字符`.`表示任意一个字符，而`*`表示它前面的字符可以出现任意次（包含`0`次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串`aaa`与模式`a.a`和`ab*ac*a`匹配，但是与`aa.a`和`ab*a`均不匹配。

### 解法 ###

判断模式中第二个字符是否是 `*`：

*  若是，看如果模式串第一个字符与字符串第一个字符是否匹配：
    
     *  1.  若不匹配，在模式串上向右移动两个字符`j+2`，相当于 a\* 被忽略
     *  1.  若匹配，字符串后移`i+1`。此时模式串可以移动两个字符`j+2`，也可以不移动`j`。
 *  若不是，看当前字符与模式串的当前字符是否匹配，即 str\[i\] == pattern\[j\] || pattern\[j\] == ‘.’：
    
     *  1.  若匹配，则字符串与模式串都向右移动一位，`i+1`，`j+1`。
     *  1.  若不匹配，返回 fasle。

/**
     * @author bingo
     * @since 2018/11/21
     */
    
    public class Solution {
        
        /**
         * 判断字符串是否与模式串匹配
         * @param str 字符串
         * @param pattern 模式串
         * @return 是否匹配
         */
        public boolean match(char[] str, char[] pattern) {
        
            if (str == null || pattern == null) {
        
                return false;
            }
            return match(str, 0, str.length, pattern, 0, pattern.length);
        }
    
        private boolean match(char[] str, int i, int len1,
                              char[] pattern, int j, int len2) {
        
            if (i == len1 && j == len2) {
        
                return true;
            }
    
            // "",".*"
            if (i != len1 && j == len2) {
        
                return false;
            }
    
            if (j + 1 < len2 && pattern[j + 1] == '*') {
        
                if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) {
        
                    return match(str, i, len1, pattern, j + 2, len2)
                            || match(str, i + 1, len1, pattern, j, len2)
                            || match(str, i + 1, len1, pattern,j + 2, len2);
                }
    
                // "",".*"
                return match(str, i, len1, pattern, j + 2, len2);
    
            }
            if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) {
        
                return match(str, i + 1, len1, pattern, j + 1, len2);
            }
            return false;
    
        }
    }

### 测试用例 ###

1.  功能测试（模式字符串里包含普通字符、`.`、`*`；模式字符串和输入字符串匹配/不匹配）；
2.  特殊输入测试（输入字符串和模式字符串是空指针、空字符串）。

# 20\_NumericStrings #

## 表示数值的字符串 ##

### 题目描述 ###

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

### 解法 ###

#### 解法一 ####

利用正则表达式匹配即可。

[]  ： 字符集合
    ()  ： 分组
    ?   ： 重复 0 ~ 1
    +   ： 重复 1 ~ n
    *   ： 重复 0 ~ n
    .   ： 任意字符
    \\. ： 转义后的 .
    \\d ： 数字

/**
     * @author bingo
     * @since 2018/11/21
     */
    
    public class Solution {
        
        /**
         * 判断是否是数字
         * @param str
         * @return
         */
        public boolean isNumeric(char[] str) {
        
            return str != null 
                    && str.length != 0 
                    && new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
        }
    }

#### 解法二【剑指offer解法】 ####

表示数值的字符串遵循模式`A[.[B]][e|EC]`或者`.B[e|EC]`，其中A为数值的整数部分，B紧跟小数点为数值的小数部分，C紧跟着e或者E为数值的指数部分。上述A和C都有可能以 `+` 或者 `-` 开头的09的数位串，B也是09的数位串，但前面不能有正负号。

/**
     * @author mcrwayfun
     * @version v1.0
     * @date Created in 2018/12/29
     * @description
     */
    public class Solution {
        
    
        private int index = 0;
    
        /**
         * 判断是否是数值
         * @param  str 
         * @return 
         */
        public boolean isNumeric(char[] str) {
        
            if (str == null || str.length < 1) {
        
                return false;
            }
    
            // 判断是否存在整数
            boolean flag = scanInteger(str);
    
            // 小数部分
            if (index < str.length && str[index] == '.') {
        
                index++;
                // 小数部分可以有整数或者没有整数
                // 所以使用 ||
                flag = scanUnsignedInteger(str) || flag;
            }
    
            if (index < str.length && (str[index] == 'e' || str[index] == 'E')) {
        
                index++;
                // e或E前面必须有数字
                // e或者E后面必须有整数
                // 所以使用 &&
                flag = scanInteger(str) && flag;
            }
    
            return flag && index == str.length;
    
        }
    
        private boolean scanInteger(char[] str) {
        
            // 去除符号
            while (index < str.length && (str[index] == '+' || str[index] == '-')) {
        
                index++;
            }
    
            return scanUnsignedInteger(str);
        }
    
        private boolean scanUnsignedInteger(char[] str) {
        
            int start = index;
            while (index < str.length && str[index] >= '0' && str[index] <= '9') {
        
                index++;
            }
            // 判断是否存在整数
            return index > start;
        }
    }

### 测试用例 ###

1.  功能测试（正数或者负数；包含或者不包含整数部分的数值；包含或者不包含效数部分的值；包含或者不包含指数部分的值；各种不能表达有效数值的字符串）；
2.  特殊输入测试（输入字符串和模式字符串是空指针、空字符串）。