2020-02-08 刷题 2（数组）

36 有效的数独

由于二维数组一共只有81个数，所以基本都可以保证常数时间复杂度和常数空间复杂度。官方题解里，每行，每列，每个3x3分别一个哈希，一次循环就能判断完；我的做法是一个哈希表，对应了每个元素及其出现的位置，然后遍历这个哈希表。
另外，判断是否在一个patch（也就是3x3）内，只要用两个坐标除以三的商是否相等就可以。
标签：哈希表
代码：

time: 68.81%, memory: 38.65%
class Solution {
public:
struct point{
    point(int i_x, int i_y): x(i_x), y(i_y){}
    int x, y;
};
bool isValidSudoku(vector<vector<char>>& board) {
    map<char, vector<point>> pos_map;
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            if (board[i][j] != '.'){
                pos_map[board[i][j]].push_back(point(i, j));
            }
        }
    }

    map<char, vector<point>>::iterator iter;
    for(iter = pos_map.begin(); iter != pos_map.end(); iter++){
        vector<point> tmp_vec = iter -> second;
        int vec_len = tmp_vec.size();
        if(vec_len <= 1)
            continue;
        else if(vec_len > 9){
            return false;
        }
        else{
            for(int i = 0; i < vec_len - 1; i++){
                for(int j = i + 1; j < vec_len; j++) {
                    if (tmp_vec[j].x == tmp_vec[i].x || tmp_vec[j].y == tmp_vec[i].y) 
                        return false;
                    if ((tmp_vec[i].x / 3 == tmp_vec[j].x / 3) && (tmp_vec[i].y / 3 == tmp_vec[j].y / 3))
                        return false;
                }
            }
        }
    }
    return true;
}
};

48 旋转图像

标签：原地旋转，数组，矩阵
官方题解的一个想法很巧妙，就是顺时针旋转90度，等效于先转置再翻转。学习到了。
本题采用的做法跟旋转数组很像，只是扩展到了二维数组。
基本的变换公式为：(x', y') = (y, n-1-x).
观察到旋转操作其实只发生在每一层内，可以在每一层分别旋转。具体操作还是很麻烦，但是认真一点是可以写对的。
代码：

time:100%, memory:5.05%
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
    int N = matrix.size();
    int round = N / 2;
    int cnt = 0;
    int start_x = 0, start_y = 0;
    int prev_x = 0, prev_y = 0;
    int next_x, next_y;
    int last_val = matrix[0][0], tmp_val;
    int cur_round = 0;
    while(cur_round < round){
        // move prev val to next val
        next_x = prev_y;
        next_y = N - 1 - prev_x;
        tmp_val = matrix[next_x][next_y];
        matrix[next_x][next_y] = last_val;
        last_val = tmp_val;
        cnt++;

        // update coord
        if(next_x == start_x && next_y == start_y){
            // not new round
            start_y++;
            if(cnt == (N - cur_round * 2) * 4 - 4){
                // new round
                start_x++;
                start_y = start_x;
                cur_round++;
                cnt = 0;
            }
            prev_x = start_x;
            prev_y = start_y;
            last_val = matrix[prev_x][prev_y];
        }
        else{
            prev_x = next_x;
            prev_y = next_y;
        }

    }
}
};