發表於   |   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 {
    vector<int> visited;
    int m;
    int n;
public:
    int flatten(int i, int j) {
        return i*n+j;
    }
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        int cnt = 0;
        if (m) {
            n = grid[0].size();
            for (int i = 0; i < m*n; i++) {
                visited.push_back(0);
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visited[flatten(i,j)]) {
                        dfs(i,j,grid);
                        cnt++;
                    }
                    
                }
            }
        }
        return cnt;
    }
    void dfs(int i, int j, vector<vector<char>>& grid) {
        visited[flatten(i,j)] = 1;
//        cout << "dfs at "<<i<<" "<<j<<endl;
        if (i > 0 && grid[i-1][j] == '1' && !visited[flatten(i-1,j)])  dfs(i-1,j, grid);
        if (i < m-1 && grid[i+1][j] == '1' && !visited[flatten(i+1,j)])  dfs(i+1,j, grid);
        if (j > 0 && grid[i][j-1] == '1' && !visited[flatten(i,j-1)])  dfs(i,j-1, grid);
        if (j < n-1 && grid[i][j+1] == '1' && !visited[flatten(i,j+1)])  dfs(i,j+1, grid);
    }
};

發表於   |   分類於   |   0 comments

You are given a m x n 2D grid initialized with these three possible values.

  • -1 - A wall or an obstacle.
  • 0 - A gate.
  • INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

1
2
3
4
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

1
2
3
4
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4
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
class Solution {
    int m;
    int n;
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        m = rooms.size();
        if (!m) return;
        n = rooms[0].size();
        deque<pair<int,int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!rooms[i][j]) q.push_back(make_pair(i,j));
            }
        }
        bfs(q, rooms);
    }
    void bfs(deque<pair<int,int>>& q, vector<vector<int>>& rooms) {
        while(!q.empty()) {
            pair<int,int>p = q.front();
            q.pop_front();
            int i = p.first;
            int j = p.second;
            if (i > 0 && rooms[i-1][j]>rooms[i][j]+1) {
                rooms[i-1][j]=rooms[i][j]+1;
                q.push_back(make_pair(i-1,j));
            }
            if (i < m-1 && rooms[i+1][j]>rooms[i][j]+1) {
                rooms[i+1][j]=rooms[i][j]+1;
                q.push_back(make_pair(i+1,j));
            }
            if (j > 0 && rooms[i][j-1]>rooms[i][j]+1) {
                rooms[i][j-1]=rooms[i][j]+1;
                q.push_back(make_pair(i,j-1));
            }
            if (j < n-1 && rooms[i][j+1]>rooms[i][j]+1) {
                rooms[i][j+1]=rooms[i][j]+1;
                q.push_back(make_pair(i,j+1));
            }
        }
    }
};

發表於   |   分類於   |   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
class graph {
    vector<unordered_set<int>> adj;
    int n;
    vector<int> temp_visited;
    vector<int> perm_visited;
public:
    void add_edge(int u, int v) {
        adj[u].insert(v);
    }
    graph(int V, vector<pair<int, int>>& prerequisites):perm_visited(V, 0), temp_visited(V, 0), adj(V, unordered_set<int>()) {
        n = V;
        for (auto p:prerequisites) {
            add_edge(p.second, p.first);
        }
    }
    bool containsCycle() {
        for (int i = 0; i < n; i++)
            if (!perm_visited[i])
                if (dfs(i)) return true;
        return false;
    }
    bool dfs(int cur) {
        if (perm_visited[cur]) return false;
        temp_visited[cur] = 1;
        for (int next:adj[cur]) {
            if (temp_visited[next]) return true;
            if (dfs(next)) return true;
        }
        temp_visited[cur] = 0;
        perm_visited[cur] = 1;
        return false;
    }
};
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses, prerequisites);
        return !(g.containsCycle());
    }
};

發表於   |   0 comments

注意负号的corner case，以及INT_MIN

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    double myPow(double x, int n) {
        // if (n<0)    return 1/x*myPow(1/x, -(n+1));
        if (n==1)   return x;
        if (!n) return 1;
        double m = myPow(x, n/2);
        double t = (n<0)?1/x:x;
        if (n%2) return m*m*t;
        else return m*m;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    double myPow(double x, int n) {
        if (n<0)    return 1/x*myPow(1/x, -(n+1));
        if (n==1)   return x;
        if (!n) return 1;
        double m = myPow(x, n/2);
        if (n%2) return m*m*x;
        else return m*m;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int h = nums.size()-1;
        int l = 0;
        while(l<h-1) {
            int mid = (h+l)/2;
            if (nums[mid-1] < nums[mid]) {
                if (nums[mid] > nums[mid+1]) return mid;
                l = mid+1;
            }
            else h = mid-1;
        }
        return (nums[l]>nums[h])?l:h;
    }
};

發表於   |   分類於   |   0 comments

要注意的是rely on INT_MIN的问题。

in-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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 {
    TreeNode *prev = NULL;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (root->left) if (!isValidBST(root->left)) return false;;
        if (prev && root->val <= prev->val)
            return false;
        prev = root;
        if (root->right) if (!isValidBST(root->right)) return false;
        return true;
    }
};

pre-order:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    bool isValidBST(TreeNode* root) {
        return helper(root, nullptr, nullptr);
    }
    
    bool helper(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if (!root) return true;
        if ((minNode && root->val <= minNode->val) || (maxNode && root->val >= maxNode->val))
            return false;
        return helper(root->left, minNode, root) && helper(root->right, root, maxNode);
    }
};

發表於   |   分類於   |   0 comments

Write a function to generate the generalized abbreviations of a word.

Example:

1
2
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3",

backtracking

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
class Solution {
    unordered_map<string, vector<string>> mp;
public:
    vector<string> generateAbbreviations(string word) {
        string s = "";
        mp[""].push_back("");
        helper(word);
        return mp[word];
    }
    vector<string> helper(string s) {
        string res = "";
        if (mp.find(s) != mp.end())
            return mp[s];
        int len = s.length();
        res += s[0];
        vector<string> rem = helper(s.substr(1));
        for (auto rest: rem) {
            mp[s].push_back(res+rest);
        }
        for (int i = 0; i < len; i++) {
            res = to_string(i+1);
            if (i < len-1) {
                res += s[i+1];
                vector<string> rem = helper(s.substr(i+2));
                for (auto rest: rem) 
                    mp[s].push_back(res+rest);
            }
            else mp[s].push_back(res);
        }
        return mp[s];
    }
};

發表於   |   分類於   |   0 comments

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Logger logger = new Logger();
// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 
// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;
// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;
// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;
// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;
// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;
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
class Logger {
    unordered_map<string, int> mp;
public:
    /** Initialize your data structure here. */
    Logger() {
        
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        if (mp.find(message) == mp.end()) {
            mp[message] = timestamp;
            return true;
        }
        if (mp[message]+10 <= timestamp) {
            mp[message] = timestamp;
            return true;
        }
        return false;
    }
};
/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * bool param_1 = obj.shouldPrintMessage(timestamp,message);
 */

發表於   |   分類於   |   0 comments

Given a sequence of words, check whether it forms a valid word square.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

Note:
The number of words given is at least 1 and does not exceed 500.
Word length will be at least 1 and does not exceed 500.
Each word contains only lowercase English alphabet a-z.

我有不审题和自动脑补题意的坏习惯，一开始以为输入就是一个square..= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        int m = words.size();
        for (int i = 0; i < m; i++) {
            int len = words[i].length();
            if (len > m) return false;
            for (int j = 0; j < len; j++) {
                if (words[j].length() < i+1 || words[j][i] != words[i][j])
                    return false;
            }
        }
        return true;
    }
};

發表於   |   分類於   |   0 comments

这个版本太慢了，改天优化。。
以及我第一次碰到了MLE的问题，原因是update调用了sumTrees，new之后没有free，之后直接update不新建node。以后还要注意。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
struct row_node{
    row_node * left = nullptr;
    row_node * right = nullptr;
    int down, up;
    int val = 0;
    row_node(int l, int u):up(u),down(l) {}
};
struct col_node {
    col_node * left = nullptr;
    col_node * right = nullptr;
    int down, up;
    row_node * root = nullptr;// row segtree
    col_node(int l, int u):up(u),down(l) {}
};
class NumMatrix {
    int col_num = 0;
    int row_num = 0;
    col_node* root;
    vector<vector<int>> &mat;
public:
    col_node* buildBigTree(int rl, int ru, int cl, int cu) {
        col_node* r = new col_node(rl, ru);
        if (rl == ru) {
            r->root = buildSmallTree(cl, cu, mat[ru]);
            return r;
        }
        if ((rl+ru)/2 >= rl)
            r->left = buildBigTree(rl, (rl+ru)/2, cl, cu);
        if ((rl+ru)/2+1 <= ru)
            r->right = buildBigTree((rl+ru)/2+1, ru, cl, cu);
        if (r->left && r->right)
            r -> root = sumTrees(r->left->root, r->right->root);
        return r;
    }
    row_node* sumTrees(row_node* l, row_node*r) {
        row_node* node = new row_node(l->down, l->up);
        node->val = l->val + r->val;
        if (l->left)
            node->left = sumTrees(l->left, r->left);
        if (l->right)
            node->right = sumTrees(l->right, r->right);
        return node;
    }
				
				void updateSumTrees(row_node* node, row_node* l, row_node*r) {
        node->val = l->val + r->val;
        if (l->left)
            updateSumTrees(node->left, l->left, r->left);
        if (l->right)
            updateSumTrees(node->right, l->right, r->right);
    }
    row_node* buildSmallTree(int l, int u, vector<int> &row) {
        row_node* r = new row_node(l, u);
        if (l == u) {
            r->val = row[l];
            return r;
        }
        if ((l+u)/2 >= l)
            r->left = buildSmallTree(l, (l+u)/2, row);
        if ((l+u)/2+1 <= u)
            r->right = buildSmallTree((l+u)/2+1, u, row);
        r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        return r;
    }
				
				void updateSmallTree(int j, int val, row_node* r) {
								if (r->down == r->up) {
												r->val = val;
												return;
								}
								int mid = (r->down+r->up)/2;
								if (mid>=j) {
												updateSmallTree(j, val, r->left);
												r->val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
								}
								else {
												updateSmallTree(j, val, r->right);
												r->val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
								}
				}
    void updateTree(int i, int j, int val, col_node* r) {
        if (r->down == r->up) {
            updateSmallTree(j, val, r->root);
            return;
        }
        int mid = (r->down + r->up)/2;
        if (mid >= i) {
            updateTree(i, j, val, r->left);
            updateSumTrees(r->root, r->left->root, r->right->root);
        }
        else {
            updateTree(i, j, val, r->right);
            updateSumTrees(r->root, r->left->root, r->right->root);
        }
    }
                        
    int sumRangeFromBigTree(col_node* r, int l, int u, int r1, int c1, int r2, int c2) {
        if (l == r1 && u == r2)
            return sumRangeFromSmallTree(r->root, 0, col_num-1, c1, c2);
        else {
            int m = (l+u)/2;
            int s1 = (r1<=m)?sumRangeFromBigTree(r->left, l, m, r1, c1, min(r2,m), c2):0;
            int s2 = (r2>m)?sumRangeFromBigTree(r->right, m+1, u, max(r1,m+1), c1, r2, c2):0;
            return s1+s2;
        }
    }
    int sumRangeFromSmallTree(row_node* r, int l, int u, int i, int j) {
        if (l == i && u == j)
            return r->val;
        else {
            int m = (l+u)/2;
            int s1 = (i<=m)?sumRangeFromSmallTree(r->left, l, m, i, min(j,m)):0;
            int s2 = (j>m)?sumRangeFromSmallTree(r->right, m+1, u, max(i,m+1), j):0;
            return s1+s2;
        }
    }
    NumMatrix(vector<vector<int>> &matrix):mat(matrix) {
        row_num = matrix.size();
        if (row_num) {
            col_num = matrix[0].size();
            if (col_num)
                root = buildBigTree(0, row_num-1, 0, col_num-1);
        }
    }
    void update(int i, int j, int val) {
        updateTree(i, j, val, root);
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sumRangeFromBigTree(this->root, 0, row_num-1, row1, col1, row2, col2);
    }
};
// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.update(1, 1, 10);
// numMatrix.sumRegion(1, 2, 3, 4);