HashTable

几种用法

1. 给定一堆二维点 int[][] obstacles，需要判断是否存在一个点。这时，可以将二维点以 String的形式存在 Set 里，比如 obstacles[i][0] + "," + obstalces[i][1]，这样将来可以将点转换成该形式进行判断。

经典题目

874 Walking Robot Simulation

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, angle = 0;
        Set<String> set = new HashSet<>();
        for (int[] o : obstacles) {
            set.add(o[0] + "," + o[1]);
        }
        int max = 0;
        for (int command: commands) {
            if (command == -1) {
                angle += 1;
                angle = angle == 4 ? 0 : angle;
            } else if (command == -2) {
                angle -= 1;
                angle = angle == -1 ? 3 : angle;
            } else {
                while (command-- > 0 && (!set.contains((x + dirs[angle][0]) + "," + (y + dirs[angle][1])))) {
                    x += dirs[angle][0];
                    y += dirs[angle][1];
                }
            }
            max = Math.max(max, x * x + y * y);
        }
        return max;
    }
}

711 Number of Distinct Islands II

// 二维矩阵 hash 计算方法。

class Solution {
    public int numDistinctIslands2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length;
        int m = grid[0].length;
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> points = new ArrayList<>();     // store [row, col] pair
                    dfs(i, j, n, m, grid, points);              // dfs to find all connected points
                    
                    String hash = getHash(points, n + m);
                    set.add(hash);
                }
            }
        }
        return set.size();
    }
    
    // Hash Function:
    // For a point (x, y), there are 8 different ways which have the same shape
    // (x, y), (x, -y), (-x, y), (-x, -y)
    // (y, x), (y, -x), (-y, x), (-y, -x)
    // Thus, for a particular point list, we would have 8 potential different point lists with the same shape.
    
    // The process would be : we iterate through different point list,
    // for each point list, we first find min_x and min_y within it,
    // and then make all the points align to the top left corner, which means (x, y) -> (x - min_x, y - min_y)
    // during this process, we use another array to help us record the relative hash for each point based on x, y and seed.
    
    // After get the hash array, we then sort it in ascending order, and make it a string.
    // Then we store the min string among all 8 hash strings to be the final result hash.
    
    private String getHash(List<int[]> points, int seed) {
        String hash = "";
        int[] xm = new int[points.size()];
        int[] ym = new int[points.size()];
        int[] out = new int[points.size()];
        
        for (int c = 0; c < 8; c++) {
            for (int i = 0; i < points.size(); i++) {
                int y = points.get(i)[0];
                int x = points.get(i)[1];
                update(xm, ym, i, c, x, y);
            }
            int mx = xm[0], my = ym[0];
            for (int i = 1; i < xm.length; i++) {
                mx = Math.min(mx, xm[i]);
                my = Math.min(my, ym[i]);
            }
            for (int i = 0; i < points.size(); i++) {
                out[i] = (xm[i] - mx) * seed + (ym[i] - my);
            }
            Arrays.sort(out);
            String candidate = Arrays.toString(out);
            if (hash.compareTo(candidate) < 0) hash = candidate;
        }
        return hash;
    }
    
    private void update(int[] xm, int[] ym, int index, int c, int x, int y) {
        if (c == 0) {
            xm[index] = x;
            ym[index] = y;
        } else if (c == 1) {
            xm[index] = x;
            ym[index] = -y; 
        } else if (c == 2) {
            xm[index] = -x;
            ym[index] = y;
        } else if (c == 3) {
            xm[index] = -x;
            ym[index] = -y;
        } else if (c == 4) {
            xm[index] = y;
            ym[index] = x;
        } else if (c == 5) {
            xm[index] = y;
            ym[index] = -x;
        } else if (c == 6) {
            xm[index] = -y;
            ym[index] = x;
        } else {
            xm[index] = -y;
            ym[index] = -x;
        }
    }
    
    private void dfs(int row, int col, int n, int m, int[][] grid, List<int[]> points) {
        if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] == 0) return;
        points.add(new int[] {row, col});
        grid[row][col] = 0;         // set 0 to avoid infinite loop
        dfs(row + 1, col, n, m, grid, points);
        dfs(row - 1, col, n, m, grid, points);
        dfs(row, col + 1, n, m, grid, points);
        dfs(row, col - 1, n, m, grid, points);
    }
}