發表於   |   分類於   |   0 comments

DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    vector<vector<int>> sum;
    int m;
    int n;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        m = matrix.size();
        if (m) {
            n = matrix[0].size();
            for (int i = 0; i<m; i++)
                sum.push_back(vector<int>(n, 0));
        }
        for (int i = 0; i<m; i++) {
            for (int j = 0; j<n; j++) {
                sum[i][j] = ((j>0)?sum[i][j-1]:0) + ((i>0)?sum[i-1][j]:0) - ((i>0&&j>0)?sum[i-1][j-1]:0) + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2][col2]-((row1>0)?sum[row1-1][col2]:0)-((col1>0)?sum[row2][col1-1]:0)+((row1>0&&col1>0)?sum[row1-1][col1-1]:0);
    }
};

没人会想用二维segtree写吧我全当练手了：

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
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;
    }
    
    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;
    }
    
    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) {
        this->row_num = matrix.size();
        if (this->row_num) {
            this->col_num = matrix[0].size();
            if (this->col_num)
                this->root = buildBigTree(0, row_num-1, 0, col_num-1);
        }
    }
    
    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.sumRegion(1, 2, 3, 4);

發表於   |   分類於   |   0 comments

standard segment tree

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
struct node {
    node * left = nullptr;
    node * right = nullptr;
    int down, up;
    int val = 0;
    node(int l, int u):up(u),down(l) {}
};
class NumArray {
    int size;
    node* root;
public:
    node* buildTree(int l, int u, vector<int> &nums) {
        node* r = new node(l, u);
        if (l == u) {
            r->val = nums[l];
            return r;
        }
        if ((l+u)/2 >= l)
            r->left = buildTree(l, (l+u)/2, nums);
        if ((l+u)/2+1 <= u)
            r->right = buildTree((l+u)/2+1, u, nums);
        r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        return r;
    }
    
    void updateTree(int i, int val, node* r) {
        if (r->down == r->up) {
            r->val = val;
            return;
        }
        int mid = (r->down + r->up)/2;
        if (mid >= i) {
            updateTree(i, val, r->left);
            r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        }
        else {
            updateTree(i, val, r->right);
            r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        }
    }
    
    int sumRangeFromTree(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)?sumRangeFromTree(r->left, l, m, i, min(j,m)):0;
            int s2 = (j>m)?sumRangeFromTree(r->right, m+1, u, max(i,m+1), j):0;
            return s1+s2;
        }
    }
    
    NumArray(vector<int> &nums) {
        this->size = nums.size();
        if (this->size)
            this->root = buildTree(0, this->size-1, nums);
    }
    
    void update(int i, int val) {
        updateTree(i, val, this->root);
    }
    
    int sumRange(int i, int j) {
        return sumRangeFromTree(this->root, 0, size-1, i, j);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

發表於   |   分類於   |   0 comments

class Solution {
unordered_map res;
public:
bool wordBreak(string s, unordered_set& wordDict) {
map> mp;
for (auto word: wordDict) {
mp[word[0]].push_back(word);
}
res[“”] = true;
return helper(s, mp);
}
bool helper(string s, map>& wordDict) {
if (res.find(s) != res.end()) {
return res[s];
}
for (auto word:wordDict[s[0]]) {
if (s.substr(0, word.length()) == word) {
if (helper(s.substr(word.length()), wordDict)) {
res[s] = true;
return true;
}
}
}
res[s] = false;
return false;
}
};

發表於   |   分類於   |   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
class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> p;
        helper(p, target, candidates, 0);
        return res;
    }
    void helper(vector<int> &partial, int target, vector<int>& candidates, int start) {
        int l = candidates.size();
        if (!target) res.push_back(partial);
        int w;
        for (int i = start; i < l; i++) {
            if (w == candidates[i]) continue;
            w = candidates[i];
            if (w<=target)  {
                partial.push_back(w);
                helper(partial, target-w, candidates, i+1);
            }
            else break;
            partial.pop_back();
        }
    }
};

發表於   |   分類於   |   0 comments

一开始是Trie+backtracking，会TLE。

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
class TrieNode {
    public:
    vector<TrieNode*> children;
    bool leaf = false;
    TrieNode():children(26, nullptr) {}
};
class Solution {
    vector<string> res;
    unordered_set<string> wordDict;
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        TrieNode* root = buildTrie(wordDict);
        this->wordDict = wordDict;
        string str = "";
        backtracking(str, s, root);
        return res;
    }
    
    TrieNode* buildTrie(unordered_set<string> words) {
        TrieNode* root = new TrieNode();
        TrieNode* t = root;
        for (auto word : words) {
            int l = word.length();
            for (int i = 0; i < l; i++) {
                if (!t -> children[word[i]-'a'])
                    t -> children[word[i]-'a'] = new TrieNode();
                t = t -> children[word[i]-'a'];
            }
            t -> leaf = true;
            t = root;
        }
        return root;
    }
    
    void backtracking(string partial, string s, TrieNode* r) {
        if (!s.length()) {
            res.push_back(partial); 
            return;
        }
        TrieNode* node = r;
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (node->children[s[i]-'a'])   node = node->children[s[i]-'a'];
            else return;
            if (node->leaf) {
                string tmp = partial+(partial.length()?" ":"")+s.substr(0, i+1);
                backtracking(tmp, s.substr(i+1), r);
            }
        }
    }
};

于是加上memorization，把临时的结果储存起来。不过这里backtracking也得修改成有返回值的函数，res也变成局部变量，不等到搜索到字符串结尾再push_back，而是返回局部解。这算是DP了吧。beats 71.48%, 还没想到哪里可以优化。

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
class TrieNode {
    public:
    vector<TrieNode*> children;
    bool leaf = false;
    TrieNode():children(26, nullptr) {}
};
class Solution {
    unordered_map<string, vector<string>> mp;
    unordered_set<string> wordDict;
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        TrieNode* root = buildTrie(wordDict);
        this->wordDict = wordDict;
        vector<string> res = backtracking(s, root);
        return res;
    }
    
    TrieNode* buildTrie(unordered_set<string> words) {
        TrieNode* root = new TrieNode();
        TrieNode* t = root;
        for (auto word : words) {
            int l = word.length();
            for (int i = 0; i < l; i++) {
                if (!t -> children[word[i]-'a'])
                    t -> children[word[i]-'a'] = new TrieNode();
                t = t -> children[word[i]-'a'];
            }
            t -> leaf = true;
            t = root;
        }
        return root;
    }
    
    vector<string> backtracking(string s, TrieNode* r) {
        if (mp.find(s)!=mp.end())   return mp[s];
        vector<string> res;
        if (!s.length()) {
            res.push_back(""); 
            mp[s] = res;
            return res;
        }
        TrieNode* node = r;
        int l = s.length();
        for (int i = 0; i < l; i++) {
            if (node->children[s[i]-'a'])   node = node->children[s[i]-'a'];
            else {mp[s]=res; return res;}
            if (node->leaf) {
                vector<string> ret = backtracking(s.substr(i+1), r);
                for (auto ret_str: ret) {
                    string tmp = s.substr(0, i+1)+(ret_str.length()?" ":"")+ret_str;
                    res.push_back(tmp);
                }
            }
        }
        mp[s] = res;
        return res;
    }
};

發表於   |   分類於   |   0 comments

学习一个如何split string。

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
class Solution {
    unordered_map<char, string> mp;
    set<string> words;
public:
    bool wordPattern(string pattern, string str) {
        int l = pattern.length();
        stringstream ss;
        ss.str(str);
        string item;
        vector<string> v;
        while (getline(ss, item, ' ')) {
            v.push_back(item);
        }
        if (l!=v.size()) return false;
        for (int i = 0; i < l; i++) {
            if (!mp.count(pattern[i]))  {
                if (words.find(v[i])!=words.end()) return false;
                words.insert(v[i]);
                mp[pattern[i]] = v[i];
                
            }
            else if (v[i]!=mp[pattern[i]]) return false;
        }
        return true;
    }
};

或者：

1
2
3
4
5
6
stringstream ss(str);
string item;
vector<string> v;
while (ss>>item) {
    v.push_back(item);
}

發表於   |   分類於   |   0 comments

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    vector<string> dic = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
public:
    vector<string> letterCombinations(string digits) {
        string s = "";
        if (!digits.length()) return res;
        backtracking(digits, s);
        return res;
    }
    
    void backtracking(string digits, string s) {
        int len = digits.length();
        if (!len) {res.push_back(s); return;}
        string str = dic[digits[0]-'2'];
        for (int i = 0; i < str.length(); i++) {
            string tmp = s + str[i];
            backtracking(digits.substr(1), tmp);
        }
    }
};

發表於   |   分類於   |   0 comments

O(1) space solution: 一个很好的思路，int有四个字节，只用了一位，可以用第二位来表示下一个status。注意count neighbor的时候会否把自己算进去。

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        if (m) {
            int n = board[0].size();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int count = -board[i][j];
                    for (int ii = max(i-1, 0); ii <= min(i+1, m-1); ii++) {
                        for (int jj = max(j-1, 0); jj <= min(j+1, n-1); jj++) {
                            count += board[ii][jj] & 1;
                        }
                    }
                    if (count == 3 || count + board[i][j] == 3) board[i][j] |= 2;
                }
            }
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) 
                    board[i][j] >>= 1;
            }
        }
    }
};

發表於   |   分類於   |   0 comments

O(1) space解法很妙，把row/col有0的情况记录在第一排/第一列，但(0, 0)的点要注意，不能用来同时表示第一排和第一列，选择一个以后用另外的bool来单独表示另一个。再根据这m+n个0/1来更新全部的格子。

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
class Solution {
    int m;
public:
    void setZeroes(vector<vector<int>>& matrix) {
        m = matrix.size();
        if(m) {
            int n = matrix[0].size();
            bool zero;
            for (int i = 0; i < m; i++) {
                if (!matrix[i][0] ) zero = true;
                for (int j = 1; j < n; j++) {
                    if (!matrix[i][j]) {
                        cout << i << " " << j << " " << (!i || !j) << endl;
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            for (int i = m-1; i >= 0; i--) {
                for (int j = n-1; j >= 1; j--) {
                    if (!matrix[i][0] || !matrix[0][j]) {
                            matrix[i][j] = 0;
                    }
                }
                if (zero) matrix[i][0] = 0;
            }
        }
    }
};

發表於   |   分類於   |   0 comments

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

一开始写的算法是只要能赢就返回true，但题意是guarantee，即对手无论如何下都能保证赢。无奈刚过subscription时间，无法提交验证他们提供的test cases。

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
class Solution {
public:
    unordered_map<string, bool> mp;
    bool canWin(string s) {
        if (mp.count(s)) return mp[s];
        int l = s.length();
        
        for (int i = 0; i < l-1; i++) {
            if (s[i] == '+' && s[i+1] == '+') {
                s[i] = '-';
                s[i+1] = '-';
                bool not_found = true;
                for (int j = 0; j < l-1; j++) {
                    if (s[j] == '+' && s[j+1] == '+') {
                        s[j] = '-';
                        s[j+1] = '-';
                        if (!canWin(s)) not_found = false;
                        s[j] = '+';
                        s[j+1] = '+';
                    }
                }
                mp[s] = not_found;
                if (not_found) {return true;}
                s[i] = '+';
                s[i+1] = '+';
            }
        }
        mp[s] = false;
        return false;
    }
};

discussion里有更简洁的做法，在每次canWin里只考虑一方是否能赢，而不是先手下完再用一个循环考虑后手，两步之后再递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    unordered_map<string, bool> mp;
public:
    bool canWin(string s) {
        if(mp.count(s)) return mp[s];
        if(s.length() < 2) return false;
        for(int i=1; i<s.length(); i++){
            if(s[i-1] == '+' && s[i] == '+'){
                string t = s;
                t[i-1] = t[i] = '-';
                if(!canWin(t)){
                    mp[s] = true;
                    return true;
                }
                //s[i-1] = s[i] = '+';
            }
        }
        mp[s] = false;
        return false;
    }
};

(ref: https://discuss.leetcode.com/topic/63191/c-backtracking-with-memorization-26ms)