LeetCode36判断数独是否有效

hashset || hashmap

class Solution { private final int N = 9; public boolean isValidSudoku(char[][] board) { HashSet<Integer> [] rows = new HashSet[N]; HashSet<Integer> [] cols = new HashSet[N]; HashSet<Integer> [] boxes = new HashSet[N]; for (int i = 0; i < N; i++) { rows[i] = new HashSet<>(); cols[i] = new HashSet<>(); boxes[i] = new HashSet<>(); } 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'; if (rows[i].contains(tmp) //本行中已有数字 || cols[j].contains(tmp) //本列中已有数字 || boxes[(i / 3) * 3 + j / 3].contains(tmp)) //本方格中已有数字 return false; rows[i].add(tmp); //添加到本行 cols[j].add(tmp); //添加到本列 boxes[(i / 3) * 3 + j / 3].add(tmp); //添加到本方格 } } return true; } } 转载： 作者：sharonou 链接：https://leetcode-cn.com/problems/valid-sudoku/solution/javawei-yun-suan-1ms-100-li-jie-fang-ge-suo-yin-by/

位运算

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/

补充：关于异或运算的其他应用：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

将所有元素做异或运算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的结果就是那个只出现一次的数字，时间复杂度为O(n)。

进阶版：有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。 然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。

根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。 再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。