剑指offer Heap & HashTable & 图

复习一下ArrayList，LinkedList，List的自带方法

剑指offer 40 最小的k个数
传统解法

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr == null || k == 0) return new int[0];
        if(arr.length <= k ) return arr;
        Arrays.sort(arr);
        // new int[length]
        int[] ans = new int[k];
        for(int i=0; i<k; i++){
            ans[i] = arr[i];
        }
        return ans;
    }
}

HashTable的性质和用法
HashMap是HashTable 的一种java实现
HashMap的进一步讨论

剑指offer 50 第一个只出现一次的字符

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> map = new HashMap<>();
        char[] charArray = s.toCharArray();
        for(char c: charArray){
            map.put(c,!map.containsKey(c));
        }
        //仍要根据charArray的顺序来查找
        for(char c: charArray){
            if(map.get(c)) return c;
        }
        //必须是‘ ’，如果是“ ”，则输出的是string类型
        return ' ';
    }
}

剑指offer 12 矩阵中的路径

class Solution {
    public boolean exist(char[][] board, String word) {
        // String -> char[] toCharArray()
        char[] words = word.toCharArray();
        //两个for循环是遍历起始点
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }

    /*dfs不是根据 board[i][j] == word[k] 来判断true的，而是根据 board[i][j] ！= word[k] 来判断false的
    只要不是不相等，就往下判断，直到遍历完word，才返回true，然后再开始回溯true
    */
    public boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i < 0 || j < 0 || i > (board.length-1) || j > (board[0].length-1) || 
           board[i][j] != word[k]) return false;
        if(word.length-1 == k) return true;
        // 遍历过后的标识，避免重复遍历
        board[i][j] = '#';
        /* int[m][n]
        m表示这个二维数组有多少个数组
        n表示每一个一维数组的元素个数
        [1,2,3,4,
         5,6,7,8] int[2][4]
        */
        // 下 上 右 左的顺序来查看
        boolean res = dfs(board,word,i+1,j,k+1) || dfs(board,word,i-1,j,k+1) ||
                      dfs(board,word,i,j+1,k+1) ||dfs(board,word,i,j-1,k+1);
        //找完归为，因为如果不是这个起始点，得归为留给下一个起始点继续探索
        board[i][j] = word[k];
        return res;
    }
}

剑指offer 13 机器人的运动范围

class Solution {
    int m;
    int n;
    int[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        visited = new int[m][n];
        //探索所有坐标和大于k的点，并设为1，所以当dfs是，直接返回0
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                // example: 13/10=1 + 13%10=3 ==> 1+3=4
                if((i/10 + i%10 + j/10 + j%10) > k){
                    visited[i][j] = 1;
                }
            }
        }
        return dfs(0,0);
    }
    public int dfs(int x, int y){
        //当超过边界 或 已经访问/和大于k
        if(x<0 || y<0 || x>(m-1) || y>(n-1) || visited[x][y] == 1) return 0;
        //已经访问过的设为1
        visited[x][y] = 1;
        //通过递归求和
        return 1+ dfs(x+1,y) + dfs(x,y+1);
    }

}