一刷的入口

10-1. 斐波那契数列

见一刷

10-2.青蛙跳台阶问题

见一刷

11. 旋转数组的最小数字

见一刷，本题最佳写法是二分法。
本题要注意的是，Leetcode上有[1,3,5]这样的测试用例，导致一刷的写法1不能通过。因此此处提出修改。因为牛客博客还没有解决再次编辑的时候出现的转义，只能在这里修改了。
在Leetcode上ac的：

class Solution {
    public int minArray(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < numbers[i - 1]) {
                return numbers[i];
            }
        }
        return numbers[0];
    }
}

最优二分写法：
如果你和最右边的j比较，那么你应该让j--，如果你和最左边的i比较，则最后一个else应该是i++。

public class Solution2 {

    public int minArray(int[] numbers) {
        int i = 0;
        int j = numbers.length-1;
        while(i<j){
            int m = (i+j)/2;
            if(numbers[m]>numbers[j]){//说明m在左边增长数组中,此时旋转点在(m,j]
                i = m+1;
            }else if(numbers[m]<numbers[j]){//说明在右边增长数组中,此时旋转点在[i,m]
                j = m;
            }else {//相等了，因此需要缩减范围重新比较
                j--;
            }
        }
        return numbers[i];
    }
}

12 矩阵中的路径

一刷学习别人的题解中，使用了压缩空间的技巧，这里记录最直观的回溯法，二维的写法。
首先要理解回溯，到了某个节点，就标记到了，如果要回退，则将标记改回去。
这题可以理解成一个标准的回溯模板题。

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")) {
            return false;
        }
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        char[] chs = word.toCharArray();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == chs[0]) {
                    if (bfs(board, i, j, isVisited, chs, 0)) return true;
                }
            }
        }
        return false;
    }

    private boolean bfs(char[][] board, int i, int j, boolean[][] isVisited, char[] chs, int index) {

        if (index == chs.length) {
            return true;
        }
        if (i < 0 || j < 0 || i == board.length || j == board[0].length || isVisited[i][j] || board[i][j] != chs[index]) {
            return false;
        }
        isVisited[i][j] = true;
        boolean res = bfs(board, i + 1, j, isVisited, chs, index + 1)
                || bfs(board, i - 1, j, isVisited, chs, index + 1)
                || bfs(board, i, j + 1, isVisited, chs, index + 1)
                || bfs(board, i, j - 1, isVisited, chs, index + 1);
        isVisited[i][j] = false;
        return res;
    }
}

13. 机器人的运动范围

可以好好理解本题的深度遍历和上题的回溯法的区别。深度遍历一般是你进入某个位置后，这个位置就定死了，或者说，不用再回到这个地方了，因为我已经遍历了。而回溯不同，回溯是我前面的路走不通后，要回来再尝试其他路。回溯的目的性更强，找到某个序列，而遍历只要到了即可。因此，回溯需要反复改标记，而遍历只需要改动一次标记。

public class Solution {
    public int movingCount(int m, int n, int k) {
        if (n <= 0 || k < 0 || m <= 0)
            return 0;
        if(k==0)
            return 1;
        boolean[][] isVisited = new boolean[m][n];//标记
        int count = movingCountCore(k, m, n, 0, 0, isVisited);
        return count;
    }

    private int movingCountCore(int threshold,int rows,int cols,
                                int row,int col, boolean[][] isVisited) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row][col]
                || cal(row) + cal(col) > threshold)
            return 0;
        isVisited[row][col] = true;
        return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row + 1, col, isVisited)
                + movingCountCore(threshold, rows, cols, row, col - 1, isVisited)
                + movingCountCore(threshold, rows, cols, row, col + 1, isVisited);
    }

    private int cal(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

14.1 减绳子

同样，可以直接参考一刷的题解。一刷记录了两个思路，建议看一刷
记录Leetcode上的ac：

class Solution {
    public int cuttingRope(int n) {
        if (n <= 1)//绳长1或者0执行剪操作
            return 0;
        if (n == 2)//绳长2执行剪操作
            return 1;
        if (n == 3)//绳长3执行剪操作
            return 2;
        int[] product = new int[n + 1]; // 用于存放最大乘积值

        product[2] = 2;//剩余绳长为2可形成的最大乘积（可剪可不剪，不减就是直接拿2最大）
        product[3] = 3;//剩余绳长为3可形成的最大乘积（可剪可不剪，不减就是直接拿3最大）

        // 开始从下到上计算长度为i绳子的最大乘积值product[i]
        for (int i = 4; i <= n; i++) {

            for (int j = 2; j <= i / 2; j++) {//j到i/2即可，从i/2到i并不会更新最大值
                product[i]=Math.max(product[i],product[j] * product[i - j]);
            }
        }
        return product[n];
    }
}

14.2 减绳子

思路和一刷的思路2相似，只是多了一个取余

public class Solution {
    public int cuttingRope(int n) {
        if(n == 2)
            return 1;
        if(n == 3)
            return 2;
        long res = 1;
        while(n > 4){
            res *= 3;
            res = res % 1000000007;
            n -= 3;
        }
        return (int)(res * n % 1000000007);
    }
}

15.二进制中1的个数

一刷中记录的解法比较全。
这里记录一个ac的方法
这里需要说明。java中的>>>是无符号数的右移，如果用>>则会出错。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                count++;
            }
            n = n >>> 1;//把n的2进制形式往右推一位
        }
        return count;
    }

}

解法2：（一刷上的思路3）

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
         }
        return count;
    }
}