6.剑指 Offer 11. 旋转数组的最小数字

二分查找

class Solution {
     public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            //只要右边比中间大，那右边一定是有序数组
            if (numbers[r] > numbers[mid]) {
                r = mid;
            } else if (numbers[r] < numbers[mid]) {
                l = mid + 1;
             //去重
            } else r--;
        }
        return numbers[l];
    }
}

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

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length ==0 || board[0].length == 0){
            return false;
        }
        char[] chars = word.toCharArray();
        boolean[][] visited = 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(dfs(board,chars,visited,i,j,0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board,char[] chars,boolean[][] visited,int i,int j,int start){
        if(i<0 || i>= board.length || j<0 || j>= board[0].length || chars[start] != board[i][j] || visited[i][j]){
            return false;
        }
        //递归终止条件
        if(start == chars.length - 1) return true;
        //设置为使用过
        visited[i][j] = true;
        boolean ans = false;
        //以board[i][j]为中心，上下左右递归
        ans = dfs(board,chars,visited,i+1,j,start + 1)
        || dfs(board,chars,visited,i-1,j,start + 1)
        || dfs(board,chars,visited,i,j+1,start + 1)
        || dfs(board,chars,visited,i,j-1,start + 1);

        //释放
        visited[i][j] = false;
        return ans;
    }
}

3.剑指 Offer 05. 替换空格

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}

class Solution {

    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0,0,m,n,k,visited);
    }

    private int dfs(int i,int j,int m,int n,int k,boolean visited[][]){
        if(i<0 || i>=m || j<0 || j>= n || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j]){
            return 0;
        }
        visited[i][j] = true;
        //递归下边的和右边的
        return dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited) + 1;
    }

}

4.剑指 Offer 06. 从尾到头打印链表

class Solution {
    public static int[] reversePrint(ListNode head){
        ListNode node = head;
        int count = 0;
        while(node != null){
            ++count;
            node  = node.next;
        }
        int[] nums = new int[count];
        node = head;
        for(int i = count-1;i>=0;--i){
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}