ARTS 第2周 GC引用计数算法

通过二维数组定义了9x9的数独库，这个数独库的某些位置会被数字填充，其他地方填充'.'，现在需要你来验证这个数独库是否合法的。有效数独的规则如下:

1. 每一行都是1-9不重复的数字
2. 每一列都是1-9不重复的数字
3. 每一个3x3的小方格中也是1-9不重复的数字

class Solution {
    public boolean isValidSudoku(char[][] board) {

        //实现的比较挫，这里定了9个数组用来代表9个 3x3的小方格
        char[] rect0 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect1 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect2 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect3 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect4 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect5 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect6 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect7 = {'.','.','.','.','.','.','.','.','.'};
        char[] rect8 = {'.','.','.','.','.','.','.','.','.'};

        Map<String, char[]> maps = new HashMap<>();
        maps.put("0_0", rect0);
        maps.put("0_1", rect1);
        maps.put("0_2", rect2);
        maps.put("1_0", rect3);
        maps.put("1_1", rect4);
        maps.put("1_2", rect5);
        maps.put("2_0", rect6);
        maps.put("2_1", rect7);
        maps.put("2_2", rect8);

        for (int i = 0; i < 9; i++) {
            char[] hor_array = {'.','.','.','.','.','.','.','.','.'};
            char[] ver_array = {'.','.','.','.','.','.','.','.','.'};
            for (int j = 0; j < 9; j++) {
                //行
                char hor_char = board[i][j];
                //列
                char ver_char = board[j][i];

                //如果第一次出现，则把对应的位置替换为对应的内容
                //如果第二次出现，那么内容就不是初始值了，可以认定是invalid
                if(hor_char != '.'){
                    if(hor_array[hor_char - '0'] == '.'){
                        hor_array[hor_char - '0'] = hor_char;
                    }else {
                        return false;
                    }

                    //计算当前位置所属的小方格
                    String key = (i / 3) + "_" + (j / 3);
                    //int index = (i % 3) * 3 + j % 3;
                    char[] rect = maps.get(key);
                    if (rect[hor_char - '0'] == '.') {
                        rect[hor_char - '0'] = hor_char;
                    }else {
                        return false;
                    }
                }

                if(ver_char != '.'){
                    if(ver_array[ver_char - 49] == '.'){
                        ver_array[ver_char - 49] = ver_char;
                    }else {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

/**
 * 最快的版本。 10ms  beats 100%。
 * 对于每个横、竖和3x3 进行 `|` 操作，这样通过 `&`操作就能知道这个数字是否重复过。
 * @param board
 * @return
 */
public boolean isValidSudokuFastest(char[][] board) {

    int [] vset = new int [9];
    int [] hset = new int [9];
    int [] bckt = new int [9];
    int idx = 0;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                idx = 1 << (board[i][j] - '0') ;
                if ((hset[i] & idx) > 0 ||
                        (vset[j] & idx) > 0 ||
                        (bckt[(i / 3) * 3 + j / 3] & idx) > 0) return false;
                hset[i] |= idx;
                vset[j] |= idx;
                bckt[(i / 3) * 3 + j / 3] |= idx;
            }
        }
    }
    return true;

}

select col1, col2, process(col4, map('{1,2,3,4,5}')) from table_a