2018-06-29 36. Valid Sudoku

题意：给你一个9 * 9的二维vector，里面可能包含数字或‘.’字符，判断该二维vector是否为shudu，或者当前满足可能成为shudu的条件。
解题思路：
方法一：常规做法，分为三次遍历：按行遍历，按列遍历，按3 * 3方格遍历。每次遍历均满足1-9数组不重复。该方法略麻烦。
方法二：定义三个二维bool类型的vector数组，仅使用一次遍历，将当前shudu二维vector通过不同的规则映射到三个bool类型的vector数组中，并判断这三个bool类型vector中元素是否都只被至多出现一次。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> a(9, vector<bool>(9, false));
        vector<vector<bool>> b(9, vector<bool>(9, false));
        vector<vector<bool>> c(9, vector<bool>(9, false));
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.')
                    continue;
                int k = board[i][j] - 1;
                int p = i / 3 * 3 + j / 3;
                if(a[i][k] || b[j][k] || c[p][k])
                    return false;
                else
                    a[i][k] = b[j][k] = c[p][k] = true;
            }
        }
        return true;
    }
};

有两点值得学习
第一：仅仅是常规顺序遍历一次所给二维vector，就能通过不同的规则映射完成题目要求的三种条件，思路新颖。由于shudu中可能出现的数字是1——9，当声明大小为9的vector时，角标正好为0——8，所以可以完成一对一映射。
第二：映射的规则十分巧妙。
1、二维vector a和for遍历规则相同，所给vector的行映射到a的行，第一个内层for loop结束后，对应着a的第一行，如果所给vector的第一行符合条件，则a的第一行也符合条件。
2、二维vector b的转置对应于所给vector，第一个内层for loop结束后，b的每一行都至多有一个元素被访问。开始第二个内层for loop时，j又从0开始，此时又访问b vector的第一行元素，与第一次内层for loop第一次访问时对应的b的行一样，都是对应下标为0的行，所以将原始二维vector的每一列元素对应到了b vector的同一行，如果原始vector的某一列不满足规则，则b vector的相应某行会不满足规则。
3、二维vector c每一行对应于所给vector的一个3 * 3的矩阵元素，由于p = i / 3 * 3 + j / 3，所以vector c 从从第一行到第九行分别对应所给二维vector的从左到右从上至下1——9个3 * 3的矩阵。

微信图片_20180629211706.jpg