發表於   |   分類於   |   0 comments

這題其實超簡單，但我一開始沒看清題，以為invalid的輸入也是會出現的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int m;
    int n;
    
public:
    int countBattleships(vector<vector<char>>& board) {
        n = board.size();
        if (!n) return 0;
        m = board[0].size();
        int count = 0;
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') {
                    if ((i == 0 || board[i-1][j] == '.') && (j == 0 || board[i][j-1] == '.'))
                        count++;
                }
            }
        }
        return count;
    }
};

所以我最開始的版本用到了并查集，type用來標記不同union的類別（horizontal/vertical/invalid或者undefined）。在union的時候檢查和更新類別。其實和輸入只有valid的情況類似：輸入有invalid時，cnt++僅在左邊和上面的鄰居都是undefined；後者則需要都是’.’。差別是為了排除invalid，要union后記錄type。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class UF {
private:
    vector<int> head;
    vector<int> rk;
    vector<int> type; // 1 h 2 v 0 invalid -1 undefined
    int cnt = 0;
public:
    UF(int N):rk(N,-1),type(N,-1),head(N,-1) {}
    int getCnt() {return cnt;}
    void MakeSet(int i) {
        rk[i] = 1;
        head[i] = i;
        cnt++;
    }
    
    int Find(int x) {
        int i = x;
        while(head[i] != i) {
            i = head[i];
        }
        int j = x;
        while(j != i) {
            head[j] = i;
            j = head[j];
        }
        return i;
    }
    void Union(int x, int y, int t) {
        int rx = Find(x);
        int ry = Find(y);
        if (rk[rx] == rk[ry]) {
            head[ry] = rx;
            rk[rx]+=rk[ry];
        }
        else if (rk[rx] > rk[ry]) {head[ry] = rx; rk[ry]+=rk[rx];}
        else {head[rx] = ry; rk[rx]+=rk[ry];}
        
        if (type[rx] == -1 || type[rx] == t) {type[rx] = t; type[ry] = t; cnt-=1;}
        else if (type[rx] != t) {type[rx] = 0; type[ry] = 0; cnt-=1;}
    }
};
class Solution {
    int m;
    int n;
    
public:
    int countBattleships(vector<vector<char>>& board) {
        n = board.size();
        if (!n) return 0;
        m = board[0].size();
        UF u = UF(m*n);
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'X') {
                    u.MakeSet(i*m+j);
                    if (i > 0 && board[i-1][j] == 'X') {
                        u.Union((i-1)*m+j, i*m+j, 2);
                    }
                    if (j > 0 && board[i][j-1] == 'X') {
                        u.Union(i*m+j-1, i*m+j, 1);
                    }
                }
            }
        }
        return u.getCnt();
        
    }
};

發表於   |   分類於   |   0 comments

link: https://leetcode.com/problems/surrounded-regions/

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

偷看了一下discussion仿照寫的，練習了并查集，基本思路是把所有的’O’連接起來，然後在boundary上的跟一個dummy node union，最後遍歷一遍找和dummy node不相連的所有的’O’；另外一開始我是用map來實現head/rk兩個數組，因為想讓index儲存坐標pair，但這樣讓運行時間直接翻了上百倍…
my solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
    int* head;
    int* rk;
    int m;
public:
    void MakeSet(int i) {
        head[i] = i;
        rk[i] = 1;
    }
    int place_t(int r, int c) {
        return r * m + c;
    }
    int Find(int i) {
        int tmp = i;
        while (head[tmp] != tmp) { //find root
            tmp = head[tmp];
        }
        int t = i;
        while (t != tmp) {
            head[t] = tmp;
            t = head[t];
        }
        return tmp;
    }
    void Union(int x, int y) {
        int rk_x, rk_y;
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x != root_y) {
            rk_x = rk[root_x];
            rk_y = rk[root_y];
            if (rk_x == rk_y) {
                head[root_y] = root_x;
                rk[root_x] += 1;
            }
            else if (rk_x > rk_y)   head[root_y] = root_x;
            else head[root_x] = root_y; 
        }
    }
    void solve(vector<vector<char>>& board) {
        int row_l;
        if (!board.empty()) row_l = board[0].size();
        else return;
        m = row_l;
        int col_l = board.size();
        head = new int[row_l*col_l+1];
        rk = new int[row_l*col_l+1];
        MakeSet(place_t(col_l-1, row_l));
        for (int i = 0; i < col_l; i++) {
            for (int j = 0; j < row_l; j++) {
                int cur = place_t(i,j);
                MakeSet(cur);
                if ((i == 0 || j == 0 || i == col_l-1 || j == row_l-1) && board[i][j] == 'O') {
                    Union(cur, place_t(col_l-1, row_l));
                }
                if (i > 0 && board[i][j] == 'O' && board[i-1][j] == 'O') Union(cur, place_t(i - 1, j));
                if (j > 0 && board[i][j] == 'O'&& board[i][j-1] == 'O') Union(cur, place_t(i, j - 1));
            }
        }
        int dum_place = Find(place_t(col_l-1, row_l));
        for (int i = 0; i < col_l; i++) {
            for (int j = 0; j < row_l; j++) {
                if (board[i][j] == 'O') {
                    int cur = Find(place_t(i,j));
                    if (cur != dum_place) board[i][j] = 'X';
                }
            }
        }
        
        delete[] head;
        delete[] rk;
    }
};

還可以直接floodfill搜索（相當於DFS），注意遞歸版本會爆棧，手動寫個stack就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    int m;
    int n;
public:
    void solve(vector<vector<char>>& board) {
        m = board.size();
        if (!m) return;
        n = board[0].size();
        vector<vector<int>> mark(m, vector<int>(n,-1)); //-1 unvisited 0 visited 1 marked
        
        for (int j = 0; j < n; j++) {
            search(0,j,board,mark);
        }
        for (int j = 0; j < n; j++) {
            search(m-1,j,board,mark);
        }
        for (int j = 0; j < m; j++) {
            search(j,0,board,mark);
        }
        for (int j = 0; j < m; j++) {
            search(j,n-1,board,mark);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mark[i][j] != 1 && board[i][j] == 'O')  board[i][j] = 'X';
            }
        }
    }
    
    void search(int i, int j,  vector<vector<char>>&board,  vector<vector<int>>&mark) {
        stack<pair<int,int>> stk;
        stk.push(pair<int,int>(i,j));
        while (!stk.empty()) {
            pair<int,int> cur = stk.top();
            int x = cur.first;
            int y = cur.second;
            stk.pop();
            if (board[x][y] == 'O') mark[x][y] = 1;
            else {mark[x][y] = 0; continue;}
            
            if (x > 0 && board[x-1][y]=='O' && mark[x-1][y]==-1) stk.push(pair<int,int>(x-1,y));
            if (x < m-1 && board[x+1][y]=='O' && mark[x+1][y]==-1) stk.push(pair<int,int>(x+1, y));
            if (y > 0 && board[x][y-1]=='O' && mark[x][y-1]==-1) stk.push(pair<int,int>(x,y-1));
            if (y < n-1 && board[x][y+1]=='O' && mark[x][y+1]==-1) stk.push(pair<int,int>(x,y+1));
        }
        return;
    }
};

updated Dec 13:

BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    int m;
    int n;
public:
    void solve(vector<vector<char>>& board) {
        queue<pair<int, int>> q;
        m = board.size();
        if (!m) return;
        n = board[0].size();
        vector<vector<int>> marked(m, vector<int>(n,0));
        for (int i = 1; i < m-1; i++) {
            if (board[i][0] == 'O')
                q.push(make_pair(i,0));
            if (board[i][n-1] == 'O')
                q.push(make_pair(i,n-1));
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O')
                q.push(make_pair(0,j));
            if (board[m-1][j] == 'O')
                q.push(make_pair(m-1,j));
        }
        
        while (!q.empty()) {
            pair<int,int> p = q.front();
            q.pop();
            int i = p.first;
            int j = p.second;
            marked[i][j] = 1;
            if (i > 0 && board[i-1][j] == 'O' && !marked[i-1][j]) { q.push(make_pair(i-1,j));}
            if (i < m-1 && board[i+1][j] == 'O' && !marked[i+1][j]) { q.push(make_pair(i+1,j));}
            if (j > 0 && board[i][j-1] == 'O' && !marked[i][j-1]) { q.push(make_pair(i,j-1));}
            if (j < n-1 && board[i][j+1] == 'O' && !marked[i][j+1]) { q.push(make_pair(i,j+1));}
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'O' && !marked[i][j])    board[i][j] = 'X';
        }
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int l = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < l; i++) {
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int a = nums[i];
            int j = i+1;
            int k = l-1;
            while (j < k) {
                // cout << nums[j] << ' ' << nums[k] << ' '<< -a << endl;
                int sum = nums[j]+nums[k];
                if (sum < 0-a) {
                    j++;
                    while (j > 0 && nums[j] == nums[j-1]) j++;
                }
                else if(sum > 0-a) {
                    k--;
                    while (k < l-1 && nums[k] == nums[k+1]) k--;
                }
                else {
                    vector<int> res;
                    res.push_back(nums[i]);
                    res.push_back(nums[j]);
                    res.push_back(nums[k]);
                    result.push_back(res);
                    j++;
                    while (j > 0 && nums[j] == nums[j-1]) j++;
                    k--;
                    while (k < l-1 && nums[k] == nums[k+1]) k--;
                }
            }
        }
        sort(result.begin(), result.end());
        result.erase( unique( result.begin(), result.end() ), result.end() );
        
        return result;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int max_l = INT_MIN;
public:
    void sol(TreeNode* r, int prev, int cur_l) {
        if (r == nullptr) {
            if (cur_l > max_l) max_l = cur_l;
            cur_l = 1;
            return;
        }
        // cout << "val "<<r->val << " prev" << prev << " cur "<< cur_l << endl;
        if ((r -> val) == prev + 1)
            cur_l++;
        else {
            if (cur_l > max_l) max_l = cur_l;
            cur_l = 1;
        }
        sol(r->left, r->val, cur_l);
        sol(r->right, r->val, cur_l);
    }
    int longestConsecutive(TreeNode* root) {
        if (root == nullptr) return 0;
        sol(root, INT_MIN, 1);
        return max_l;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    vector<int> head;
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        for (int i = 0; i < n; i++){
            head.push_back(-1);
        }
        for (auto e : edges) {
            int h1 = e.first, h2 = e.second;
            while (head[h1] != -1) h1 = head[h1];
            while (head[h2] != -1) h2 = head[h2];
            if (h1 != h2) head[h2] = h1;
        }
        int cnt = 0;
        for (auto i : head) {
            if (i == -1) cnt ++;
        }
        return cnt;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    string decodeString(string s) {
        stack<string> stk;
        int cur_num = 0;
        string cur_str;
        // string res_str="";
        for(int i = 0; i < s.length(); i++) {
            if (s[i] >= '0' && s[i] <= '9'){
                cur_num *= 10;
                cur_num += s[i]-'0';
            }
            else if (s[i] == '[') {
                stk.push(to_string(cur_num));
                cur_num = 0;
                stk.push("[");
            }
            else if (s[i] >= 'a' && s[i] <= 'z') {
                stk.push(string(1,s[i]));
            }
            else { //s[i] = ']'
                string tmp;
                while(stk.top() != "[") {tmp.insert(0,stk.top()); stk.pop();}
                stk.pop();
                int rep = stoi(stk.top());
                stk.pop();
                for (int i = 0; i < rep; i++)
                    cur_str = cur_str + tmp;
                stk.push(cur_str);
                cur_str = "";
            }
        }
        string res;
        while (!stk.empty()) {res.insert(0, stk.top()); stk.pop();}
        return res;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> res;
        int prev = INT_MAX;
        int lb = INT_MAX, ub;
        nums.insert(nums.begin(),lower-1);
        nums.push_back(upper+1);
        for (auto i : nums) {
            if (prev != INT_MAX) {
                if (i - prev == 2) res.push_back(to_string(prev+1));
                stringstream ss;
                ss<<prev+1<<"->"<<i-1;
                if (i - prev > 2 || i - prev < 0) res.push_back(ss.str());
            }
            prev = i;
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        if(root) stk.push(root);
        vector<int> res;
        while(!stk.empty()) {
            TreeNode *r = stk.top();
            res.push_back(r->val);
            stk.pop();
            if(r->right) stk.push(r->right);
            if(r->left) stk.push(r->left);
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments

空間是O(1)的Morris Inorder traversal解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 // O(1) space version, Morris Inorder traversal
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        TreeNode* prev = NULL;
        vector<int> res;
        while(cur) {
            if(cur->left == nullptr) {
                res.push_back(cur -> val);
                cur = cur -> right;
            }
            else {
                prev = cur -> left;
                while(prev -> right != nullptr && prev -> right != cur) {
                    prev = prev -> right;
                }
                if (prev -> right == nullptr) {
                    prev -> right = cur;
                    cur = cur -> left;
                }
                if (prev -> right == cur) {
                    prev -> right = nullptr;
                    res.push_back(cur -> val);
                    cur = cur -> right;
                }
            }
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        int prev_val = INT_MIN;
        TreeNode* prev_node = nullptr;
        int swapped_val = INT_MAX;
        TreeNode* swapped_node = nullptr;
        bool sf = false;
        while(cur) {
            if (cur -> left == nullptr) {
                if (!sf && swapped_val != INT_MAX && cur -> val > swapped_val) {
                    swapped_node -> val = prev_val;
                    prev_node -> val = swapped_val;
                    sf = true;
                }
                if (!sf && swapped_val == INT_MAX && cur -> val < prev_val) {
                    swapped_val = prev_val;
                    swapped_node = prev_node;
                    // cout << "swapped: " << prev_val<<" "<<swapped_val;
                }
                prev_node = cur;
                prev_val = cur -> val;
                cur = cur -> right;
            }
            else {
                // find the qianqu jiedian
                prev = cur -> left;
                while (prev -> right != nullptr && prev -> right != cur) {
                    prev = prev -> right;
                }
                if (prev -> right == nullptr) {
                    prev -> right = cur;
                    cur = cur -> left;
                }
                
                if (prev -> right == cur) {
                    prev -> right = nullptr;
                    if (!sf && swapped_val != INT_MAX && cur -> val > swapped_val) {
                        swapped_node -> val = prev_val;
                        prev_node -> val = swapped_val;
                        sf = true;
                    }
                    if (!sf && swapped_val == INT_MAX && cur -> val < prev_val) {
                        swapped_val = prev_val;
                        swapped_node = prev_node;
                    }
                    prev_node = cur;
                    prev_val = cur -> val;
                    cur = cur -> right;
                }
            }
        }
        if (!sf) {
            swapped_node -> val = prev_val;
            prev_node -> val = swapped_val;
            cout << "swapped: "<<prev_val<<" "<<swapped_val;
        }
    }
};