前言:
一直对位运算只是初步的了解。这次看到一个题利用位运算换取存储空间。写个题解,加深印象。
位运算
1.移位
直接上例子(左移<<)
public class Test {
public static void main(String[] args) {
System.out.println(5<<2);//运行结果是20
}
}
在实际的运算中则是将5转化为二进制再左移两位。(java int 32位为例)
0000 0000 0000 0000 0000 0000 0000 0
101
然后左移2位后,低位补0:
0000 0000 0000 0000 0000 0000 000
1 01
00 换算成10进制为20
同理
public class Test {
public static void main(String[] args) {
System.out.println(1<<3);//运行结果是8
}
}
0000 0000 0000 0000 0000 0000 0000 000
1
0000 0000 0000 0000 0000 0000 0000
1
000
(右移同理)
2.位与(&)
位与:第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n为也为1,否则为0
public class Test {
public static void main(String[] args) {
System.out.println(5 & 3);//结果为1
}
}
程序中:
将5化成二进制: 0000 0000 0000 0000 0000 0000 0000 0
101
将3化成二进制: 0000 0000 0000 0000 0000 0000 0000 00
11
将1化成二进制: 0000 0000 0000 0000 0000 0000 0000 000
1
(因为5的第3位为1,3的第三位为0,则结果的第三位就为0,第二位同理。第一位3和5都是1,则就为1。)
3.位或( | )
位或操作:第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1,那么结果的第n为也为1,否则为0
public class Test {
public static void main(String[] args) {
System.out.println(5 | 3);//结果为7
}
}
5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0
101
3转换为二进制:0000 0000 0000 0000 0000 0000 0000 00
11
7转换为二进制:0000 0000 0000 0000 0000 0000 0000 0
111
由位运算操作符衍生而来的有:
&= 按位与赋值 、|= 按位或赋值 、^= 按位非赋值、 >>= 右移赋值、 <<= 赋值左移。
举个栗子:
@Test
public void testBitOperation(){
int a = 8; //1000
a |= 3; //3:11
System.out.println(a); //应该是1011(二进制) 及 11
}
现在来看看具体应用:
题目:
解題思路:
先说下正常的题目思路
:题目的提示说是哈希表但是大小才为9✖9并且每个格子数字不超过9。所以不必用哈希表而是用
数组写题
。题目要求的是每行每列每个3✖3的小方格不能出现相同的数字。所以我们可以先准备
3个二维数组来分别储存行列及小方格值。再利用两次for循环遍历数独
。每次遍历的值,一次性储存在3个值的对应
下标的位置
,并标记。如果下次遍历的数在已有标记则直接返回结果。
直接判断的代码如下:
class Solution {
public boolean isValidSudoku(char board[][]) {
int length = board.length;
//二维数组line表示的是对应的行中是否有对应的数字,比如line[0][3]
//表示的是第0行(实际上是第1行,因为数组的下标是从0开始的)是否有数字3
int line[][] = new int[length][length];
int column[][] = new int[length][length];
int cell[][] = new int[length][length];
for (int i = 0; i < length; ++i)
for (int j = 0; j < length; ++j) {
//如果还没有填数字,直接跳过
if (board[i][j] == '.')
continue;
//num是当前格子的数字
int num = board[i][j] - '0' - 1;
//k是第几个单元格,9宫格数独横着和竖着都是3个单元格
int k = i / 3 * 3 + j / 3;
//如果当前数字对应的行和列以及单元格,只要一个由数字,说明冲突了,直接返回false。
//举个例子,如果line[i][num]不等于0,说明第i(i从0开始)行有num这个数字。
if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
return false;
//表示第i行有num这个数字,第j列有num这个数字,对应的单元格内也有num这个数字
line[i][num] = column[j][num] = cell[k][num] = 1;
}
return true;
}
}
运算结果:
位运算解法:
因为这题只需要9位而java
Int类型是4个字节占的是32位远远大于9位
,所以我们完全可以不用二维数组,而是用一维数组,再转化为二进制,利用位运算进行标记。
比如示例1中的第二位数是3
,在直接判断的方法存储是(下标-1):
line[0][2] = column[1][2] = cell[0][2] = 1;
换成二进制则写法则是:
(因为二级制利用1来标记,所以1左移3位为1000则为8)
column[1] |= 8;
line[0] |= 8;
cell[0] |= 8
此时后续判断3这个值是否存在只要判断这个位上是否有1。代码如下:
if ((column[i] & 8) > 0 || (line[0=j] & 8) > 0 || (cell[k] & 8) > 0)
return false;
所以相当于本来需要用二维数组,现在用一维数组就可以搞定。多出的步骤只是把十进制转二进制储存。
真正储存的形式变为从十进制变成二级制储存与判断。
代碼:
附上完整代码(参考):
public boolean isValidSudoku(char[][] board) {
int[] line = new int[9];
int[] column = new int[9];
int[] cell = new int[9];
int shift = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
//如果还没有填数字,直接跳过
if (board[i][j] == '.')
continue;
shift = 1 << (board[i][j] - '0');
int k = (i / 3) * 3 + j / 3;
//如果对应的位置只要有一个大于0,说明有冲突,直接返回false
if ((column[i] & shift) > 0 || (line[j] & shift) > 0 || (cell[k] & shift) > 0)
return false;
column[i] |= shift;
line[j] |= shift;
cell[k] |= shift;
}
}
return true;
}
运行结果:
如有不足,敬请指正~