Hashmap使用

hashmap初始化

// init data HashMap<Integer, Integer> [] rows = new HashMap[9]; HashMap<Integer, Integer> [] columns = new HashMap[9]; HashMap<Integer, Integer> [] boxes = new HashMap[9]; for (int i = 0; i < 9; i++) { rows[i] = new HashMap<>(); columns[i] = new HashMap<>(); boxes[i] = new HashMap<>(); }

Hashmap用于判断数组内是否重复，所以要会找隐藏的数组 比如对于数独问题，我们就可以每一行，每一列，每一个小数独都建造一个hsahmap数组。 当然，对于一次迭代来说： 每一个子数独应该用 (i/3)*3+(j/3); 这个子数独就是隐藏的数组

hashmap代码

class Solution { public boolean isValidSudoku(char[][] board) { // init data HashMap<Integer, Integer> [] rows = new HashMap[9]; HashMap<Integer, Integer> [] columns = new HashMap[9]; HashMap<Integer, Integer> [] boxes = new HashMap[9]; for (int i = 0; i < 9; i++) { rows[i] = new HashMap<Integer, Integer>(); columns[i] = new HashMap<Integer, Integer>(); boxes[i] = new HashMap<Integer, Integer>(); } // validate a board for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char num = board[i][j]; if (num != '.') { int n = (int)num; int box_index = (i / 3 ) * 3 + j / 3; // keep the current cell value rows[i].put(n, rows[i].getOrDefault(n, 0) + 1); columns[j].put(n, columns[j].getOrDefault(n, 0) + 1); boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1); // check if this value has been already seen before if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1) return false; } } } return true; } } int i = 0; i = i | 1<<5; System.out.println(i); //32 i = i | 1<<4; System.out.println(i); //48

位运算代码

class Solution { private final int N = 9; public boolean isValidSudoku(char[][] board) { int[] rows = new int[N]; //行的位运算数组 int[] cols = new int[N]; //列的位运算数组 int[] boxes = new int[N]; //方格的位运算数组 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i][j] == '.') continue; int tmp = board[i][j] - '0'; int boxIndex = i / 3 * 3 + j / 3; if ((rows[i] >> tmp & 1) == 1 //rows[i] >> tmp & 1取出第i行的tmp数字，看是否已填，如果等于1，代表已填 || (cols[j] >> tmp & 1) == 1 //cols[j] >> tmp & 1取出第j列的tmp数字，看是否已填，如果等于1，代表已填 || (boxes[boxIndex] >> tmp & 1) == 1) //boxes[boxIndex] >> tmp & 1取出第boxIndex个方格的tmp数字，看是否已填，如果等于1，代表已填 return false; rows[i] = rows[i] | (1 << tmp); //将tmp数字加入到第i行的位运算数组 cols[j] = cols[j] | (1 << tmp); //将tmp数字加入到第j列的位运算数组 boxes[boxIndex] = boxes[boxIndex] | (1 << tmp); //将tmp数字加入到第boxIndex个方格的位运算数组 } } return true; } } 转载： 作者：sharonou 链接：https://leetcode-cn.com/problems/valid-sudoku/solution/javawei-yun-suan-1ms-100-li-jie-fang-ge-suo-yin-by/