6.8 permutationSequence & validSudoku & trappingRain!!

• to do
  
  
  八点多一点在宝座上坐下。。
  1] Permutation Sequence

    int factorial(int n) {
        return (n == 1 || n == 0)? 1:factorial(n-1)*n;
    }

    void helper(string& str, string& ret, int k) {
        if ( str.size()==1 ) {
            ret.push_back(str[0]);
            return;
        } else {
            int gct = str.size();
            int gsize = factorial(gct-1);
            int gindex = ceil((float)k/gsize); //!!!note
            ret.push_back(str.at(gindex-1));
            str.erase(str.begin()+gindex-1);
            helper(str, ret, k-(gindex-1)*gsize);
        }
    }

    string getPermutation(int n, int k) {
        if (n<1 || k<1 || k>factorial(n) ) return "";
        string str, ret;
        for (int i=1; i<=n; ++i) {
            str.push_back('0'+i);
        }
        helper(str, ret, k);
        return ret;
    }

比较顺，不过int gindex = ceil((float)k/gsize);开始又忘记int的自动rounding了, 恩应该叫integer division只保存int部分。
3-4-5, 有种周五了的错觉。。
骑车路过被加拿大雁群拦截要过路费还是咋的。
不知道怎么对大大们表示臣服无害，装作淡定企图慢慢飘过。孰知一只大大伸长脖子，危险的侧脸静静观察我，越来越近
突然 威严的一动翅膀摇摇摆摆要对峙我的样子。妈呀好久没这么吓过了，刹车惊叫下车 同时间发生 推着车逃之夭夭~ 哈哈我都被自己吓着了心跳猛然加速，然后被自己逗逼笑了lol
'#'觉得birds接近了都好creepy

2] Valid Sudoku
method 1: naive

    bool validLine(vector<char>& line, vector<bool> occurred) {
        if (line.size()!=9) return false;
        for (int i=0; i<line.size(); ++i) {
            if ('1'<=line[i] && line[i]<='9') {
                if (occurred[line[i]-'1']) {
                    return false;
                } else {
                   occurred[line[i]-'1'] = true;
                }
            } else if (line[i]!='.') {
                return false;
            }
        }
        return true;
    }

    bool isValidSudoku(vector<vector<char>>& board) {
        if (board.size()!=9) return false;
        vector<bool> occurred(9, false);
        //each line
        for (int i=0; i<9; ++i) {
            if ( !validLine(board[i], occurred) ) return false;
        }
        //each col
        for (int col=0; col<9; ++col) {
            vector<char> line{};
            for (int row=0; row<9; ++row) {
                line.push_back(board[row][col]);
            }
            if ( !validLine(line, occurred) ) return false;
        }
        //each 3*3
        for (int col=0; col<7; col+=3) {
            for (int row=0; row<7; row+=3) {
                vector<char> line{};
                for (int j=row; j<row+3; ++j) {
                    line.insert( line.end(), (board[j]).begin()+col, (board[j]).begin()+col+3);//notice pos, head, non-inclusive tail
                }
                if ( !validLine(line, occurred) ) return false;
            }

        }
        return true;
    }```

method 2: 38%
```c++
    bool validChar(char target, vector<bool>& occurred) {
        if (target=='.') return true;
        else if ('0'<target && target<'10') {
            if (occurred[target-'1']) return false;
            else occurred[target-'1'] = true;
        } else {
            return false;
        }
        return true;
    }

    bool isValidSudoku(vector<vector<char>>& board) {
        if (board.size()!=9) return false;
        vector<bool> occurred(9, false);
        //each line/col
        for (int i=0; i<9; ++i) {
            fill(occurred.begin(), occurred.end(), false);
            for (int col=0; col<9; ++col) {
                if ( !validChar(board[i][col], occurred) ) return false;
            }
            fill(occurred.begin(), occurred.end(), false);
            for (int row=0; row<9; ++row) {
                if ( !validChar(board[row][i], occurred) ) return false;
            }
        }
        //each 3*3
        for (int col=0; col<7; col+=3) {
            for (int row=0; row<7; row+=3) {

                fill(occurred.begin(), occurred.end(), false);
                for (int i=row; i<row+3; ++i) {
                    for (int j=col; j<col+3; ++j) {
                        if ( !validChar(board[i][j], occurred) ) return false;
                    }
                }
            }

        }
        return true;