剑指 Offer（第 2 版）7/6 9-13

1.剑指 Offer 11. 旋转数组的最小数字 简单

只需遍历一遍即可
当出现numbers[i] < numbers[i - 1]时找打答案

 class Solution {
    
        public int minArray(int[] numbers) {
    
            int n = numbers.length;
            for (int i = 1; i < n; i++) {
    
                if (numbers[i] < numbers[i - 1])return numbers[i];
            }
            //未反转返回第一个最小元素
            return numbers[0];
        }
    }

2.剑指 Offer 12. 矩阵中的路径 中等

回溯
记得要细心

 class Solution {
    
        public boolean exist(char[][] board, String word) {
    
            boolean[][] isVisited = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
    
                for (int j = 0; j < board[0].length; j++) {
    
                    if (exist(board,word,0,i,j,isVisited))return true;
                }
            }
            return false;
        }

        /** * * @param board * @param word * @param i 为待寻找第i个字母 * @param x 起始的x坐标 * @param y 起始的y坐标 * @return */
        public boolean exist(char[][] board, String word, int i, int x,int y, boolean[][] isVisited ){
    
            if (i == word.length())return true;
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length)return false;
            if (isVisited[x][y])return false;
            if (board[x][y] != word.charAt(i))return false;
            isVisited[x][y] = true;
            //寻找顺序为 右 下 左 上
            //右
            if (exist(board,word,i + 1,x,y + 1,isVisited))return true;
            //下
            if (exist(board,word,i + 1,x + 1,y,isVisited))return true;
            //左
            if (exist(board,word,i + 1,x,y - 1,isVisited))return true;
            //上
            if (exist(board,word,i + 1,x - 1,y,isVisited))return true;
            isVisited[x][y] = false;
            return false;
        }
    }

3.剑指 Offer 13. 机器人的运动范围 中等

递归

class Solution {
    
        int ans;
        public int movingCount(int m, int n, int k) {
    
            boolean[][] dp = new boolean[m][n];//记录格子是否被访问过
            move(m,n,k,0,0,dp);
            return ans;
        }
        public void move(int m, int n, int k,int x,int y,boolean[][] dp){
    
            if (x < 0 || x >= m || y < 0 || y >= n)return;
            if (dp[x][y])return;
            //判断该格子是否可以访问
            String xstr = x + "";
            String ystr = y + "";
            int count = 0;
            for (int i = 0; i < xstr.length(); i++) {
    
                count += Integer.parseInt(xstr.charAt(i) + "");
            }
            for (int i = 0; i < ystr.length(); i++) {
    
                count += Integer.parseInt(ystr.charAt(i) + "");
            }
            if (count > k)return;
            dp[x][y] = true;//可以访问本节点
            ans++;
            //左 右 上 下
            move(m,n,k,x,y - 1,dp);
            move(m,n,k,x,y + 1,dp);
            move(m,n,k,x - 1,y,dp);
            move(m,n,k,x + 1,y,dp);
        }
    }

4.剑指 Offer 14- I. 剪绳子 中等

此题数据范围较小可以使用动态规划

class Solution {
    
        /* 动态规划，枚举最后一段绳子的长度 dp[i] = Math.max(j * dp[i - j],j * (i - j)) */
        public int cuttingRope(int n) {
    
            //dp[i] = 长度为i的绳子，切割成多份绳子乘积的最大值
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
    
                //枚举最后一段绳子的长度
                int max = Integer.MIN_VALUE;
                for (int j = 1; j < i; j++) {
    
                    //绳子的切割方式有两种
                    max = Math.max(max,j * dp[i - j]);//切割成 > 2段
                    max = Math.max(max,j * (i - j));//切割成 = 2段
                }
                dp[i] = max;
            }
            return dp[n];
        }
    }

5.剑指 Offer 14- II. 剪绳子 II 中等

此题和力扣中的整数拆分问题几乎一模一样,可以去参考整数拆分的思想,本题额外解决了如何
处理大数取余的问题.

数学知识解决,暂时不要求掌握
方法一:数学思想 + 循环大数取余

 //数学相关，了解即可 不要求掌握此解
    class Solution {
    
        /* 大数求余公式：(xy)⊙p=[(x⊙p)(y⊙p)]⊙p ⊙p : 对p取余 可以采用循环求余的方式 */
        public int cuttingRope(int n) {
    
            //当 n < 4时单独考虑
            if (n < 4) return n - 1;
            //当 n >= 4时
            int x = n / 3;
            int y = n % 3;
            int p = 1000000007;
            long ret = 1;
            //这里只计算到 3 的 (x - 1)次方
            //保证每轮结束后都不超过int的最大值，但是不保证ret * 3小于int最大值
            //所以这里ret的类型为long
            for (int i = 1; i < x; i++) {
    
                ret = ret * 3 % p;
            }
            if (y == 0) return (int) (ret * 3 % p);
                //余数为1则拆出两个2，其余为3
            else if (y == 1) return (int) (ret * (2 * 2) % p);
                //余数为1则拆出一个2，其余为3
            else if (y == 2) return (int) (ret * 3 * 2 % p);
            return -1;
        }
    }