發表於   |   分類於   |   0 comments

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int hash[128] = {0};
        int j = 0;
        int l = s.length();
        int cur_nchar=0, max_len=0;
        for (int i=0; i<l; i++) {
            if(!hash[s[i]]++) cur_nchar++;
            if (cur_nchar <= k) max_len = max(max_len, i-j+1);
            while(cur_nchar > k) {
                if (!--hash[s[j++]]) cur_nchar--;
            }
            
        }
        return max_len;
    }
};

Dec 8 update:
mistakes made: thought there are only letters but all ASCII characters are possible input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int end = 0;
        int start = 0;
        int len = s.length();
        int cnt = 0;
        vector<int> v(256, 0);
        int max = 0;
        while(end<len) {
            if (!(v[(256+int(s[end++]))%256]++)) cnt++;
            while (cnt > k) {
                // move start
                if (!--v[(256+int(s[start++]))%256]) cnt--;
            }
            if (end-start > max)
                max = end-start;
        }
        return max;
    }
};

發表於   |   分類於   |   0 comments

因為是BST直接搜索p,q直到分叉或者碰到p/q，第一個開始分叉的節點，或先碰到的p/q是LCA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int m = min(p -> val, q -> val);
        int n = max(p -> val, q -> val);
        if (!root || (root->val > m && root->val < n) || root->val == m || root->val == n) return root;
        else if (root->val < m) return lowestCommonAncestor(root->right, p, q);
        else return lowestCommonAncestor(root->left, p, q);
    }
   
};

發表於   |   分類於   |   0 comments

沒看清題直接寫，一開始忽略了top to bottom的順序。有了這個條件於是用queue來level-wise地訪問。

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
/**
 * 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 {
    map<int, vector<int>> mp;
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<pair<TreeNode*,int>> q;
        q.push(pair<TreeNode*,int>(root,0));
        while (!q.empty()) {
            pair<TreeNode*,int> cur = q.front();
            q.pop();
            mp[cur.second].push_back(cur.first->val);
            if (cur.first->left) q.push(pair<TreeNode*,int>(cur.first->left,cur.second-1));
            if (cur.first->right) q.push(pair<TreeNode*,int>(cur.first->right,cur.second+1));
        }
        for (auto i:mp) 
            res.push_back(i.second);
        return res;
    }
    
};

改進：保持hashmap按照key排序比較耗時，可以直接把節點放進結果的vector。因為二叉樹的從左到右的column編號是連續的，可以事先遍歷一遍找到最左和最右的節點的column編號，然後就可以把當前level放進vector的第level-left_most_column_number位置上。

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 Solution {
    int miin = 0, maax = 0;
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        traversal(root, 0);
        
        queue<pair<TreeNode*,int>> q;
        q.push({root,0});
        for (int i = miin; i <= maax; i++)
            res.push_back({});
        while (!q.empty()) {
            pair<TreeNode*,int> cur = q.front();
            q.pop();
            res[cur.second-miin].push_back(cur.first->val);
            if (cur.first->left) q.push({cur.first->left,cur.second-1});
            if (cur.first->right) q.push({cur.first->right,cur.second+1});
        }
        return res;
    }
    void traversal(TreeNode* r, int level) {
        if (level < miin) miin = level;
        if (level > maax) maax = level;
        if (r->left) traversal(r->left, level-1);
        if (r->right) traversal(r->right, level+1);
        
    }
};

發表於   |   分類於   |   0 comments

和deep copy linked list一樣的遞歸辦法(DFS)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
    map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return nullptr;
        if (mp[node] != nullptr) return mp[node];
        mp[node] = new UndirectedGraphNode(node->label);
        for (auto n:node->neighbors) {
            mp[node]->neighbors.push_back(cloneGraph(n));
        }
        return mp[node];
    }
};

Iterative version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    map<int, UndirectedGraphNode*> mp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return nullptr;
        stack<UndirectedGraphNode*> stk;
        stk.push(node);
        UndirectedGraphNode* newHead = new UndirectedGraphNode(node->label);
        mp[node->label] = newHead;
        while (!stk.empty()) {
            UndirectedGraphNode* cur = stk.top();
            stk.pop();
            for (auto i:cur->neighbors) {
                if (mp.find(i->label) == mp.end()) {
                    mp[i->label] = new UndirectedGraphNode(i->label);
                    stk.push(i);
                }
                mp[cur->label]->neighbors.push_back(mp[i->label]);
            }
        }
        return newHead;
    }
};

BFS寫的時候一開始TLE，沒有注意到圖裡面有self-cycle，這種node不能push到queue里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    unordered_map<int, UndirectedGraphNode*> mp;
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == nullptr) return nullptr;
        queue<UndirectedGraphNode*> q;
        q.push(node);
        UndirectedGraphNode *newHead = new UndirectedGraphNode(node->label);
        mp[node->label] = newHead;
        while (!q.empty()) {
            UndirectedGraphNode* tmp = q.front();
            q.pop();
            for (auto i:tmp->neighbors) {
                if (mp.find(i->label) == mp.end()) {
                    mp[i->label] = new UndirectedGraphNode(i->label);
                    q.push(i);
                }
                mp[tmp->label]->neighbors.push_back(mp[i->label]);
            }
        }
        return newHead;
    }
};

發表於   |   分類於   |   0 comments

最開始用的Naive版本效率很低，想法是用vector記錄pointer地址，然後對每個原list里的random指針，在vector里找到對應index，於是知道了新duplicate的鏈錶中對應的地址，assign給新鏈錶節點的random指針。每次都要find，時間複雜度O(N^2)。

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 Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == nullptr) return nullptr;
        RandomListNode *p = head, *prev = nullptr;
        vector<RandomListNode *> v1, v2;
        while (p != NULL) {
            v1.push_back(p);
            RandomListNode *tmp;
            tmp = new RandomListNode(p -> label);
            v2.push_back(tmp);
            if (prev!= nullptr) prev -> next = tmp;
            prev = tmp;
            p = p -> next;
        }
        p = head;
        RandomListNode *cur = v2[0];
        while (p != NULL) {
            if (p->random != nullptr) {
                auto pos = find(v1.begin(), v1.end(), p->random);
                cur -> random = v2[pos-v1.begin()];
            }
            else cur -> random = nullptr;
            p = p -> next;
            cur = cur -> next;
        }
        return v2[0];
    }
};

Discussion有兩種有趣的做法，都是修改原來的鏈錶，一種是將原鏈錶和新複製的用next串起來，這樣可以根據next找到原來節點對應的複製節點，從而assign random；另外一種我更喜歡的做法是修改原來鏈錶的random指向複製節點，複製節點的random先暫時指向原來random指針指向的節點，再循環一遍更新為原來節點的新random指針指向的複製節點。最後再做恢復。時間都是O(N)，除複製節點外空間前者O(1)，後者O(N)。前者通過複製鏈錶的next指向原來的next節點節省了空間，但後者的空間無法節省下來因為更新完複製節點的random以後原來節點的random無法不依靠外界信息restore了。本質其實類似。實現了一下：

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:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == nullptr) return nullptr;
        RandomListNode *p = head, *prev = nullptr, *newHead = nullptr;
        vector<RandomListNode *> v;
        int cnt = 0;
        while (p != NULL) {
            RandomListNode *tmp = new RandomListNode(p -> label);
            v.push_back(p -> random);
            tmp -> random = p -> random;
            if (!cnt++) newHead = tmp;
            p -> random = tmp;
            if (prev!= nullptr) prev -> next = tmp;
            prev = tmp;
            p = p -> next;
        }
        p = newHead;
        while (p != NULL) {
            if (p -> random) p -> random = p -> random -> random;
            p = p -> next;
        }
        p = head;
        int i = 0;
        while (p != NULL) {
            p -> random = v[i++];
            p = p -> next;
        }
        return newHead;
    }
};

用遞歸來完成：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    map<RandomListNode*, RandomListNode*> mp;
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (head == nullptr) return nullptr;
        if (mp[head]!=nullptr) return mp[head];
        mp[head] = new RandomListNode(head->label);
        mp[head] -> next = copyRandomList(head->next);
        mp[head] -> random = copyRandomList(head->random);
        return mp[head];
    }
};

發表於   |   分類於   |   0 comments

沒什麼好說的..

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int titleToNumber(string s) {
        int res = 0;
        int l = s.length();
        for (int i = 0; i < l; i++) {
            res *= 26;
            res += s[i]-'A'+1;
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments

這道題竟然是hard..
邏輯很簡單，但是edge case和各種容易犯錯的小細節非常多。

  • thousand/million/billion在0後面不加
  • 空格的問題
  • ten和eleven~nineteen的區分
  • zero在不同chunk
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 {
    vector<string> lessThan20 = {"", "One ", "Two ", "Three ", "Four ", "Five ", "Six ", "Seven ", "Eight ", "Nine ", "Ten ", "Eleven ", "Twelve ", "Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ", "Eighteen ", "Nineteen "};
    vector<string> tens = {"", "", "Twenty ", "Thirty ", "Forty ", "Fifty ", "Sixty ", "Seventy ", "Eighty ", "Ninety "};
    vector<string> thousands = {"", "Thousand ","Million ","Billion "};
public:
    string convertChunk(int num) {
        int n = num;
        string s="";
        if (num/100) s+= lessThan20[num/100] + "Hundred ";
        n%=100;
        if (n < 20) s+=lessThan20[n];
        else s+=tens[n/10] +lessThan20[n%10];
        return s;
    }
    string numberToWords(int num) {
        if (!num) return "Zero";
        string s = "";
        int cnt = 0;
        while (num) {
            string tmp = convertChunk(num%1000);
            if (tmp != "") s= tmp+thousands[cnt]+s;
            else s= tmp+s;
            cnt++;
            num/=1000;
        }
        return s.substr(0,s.length()-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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        vector<int> res;
        if (!m) return res;
        int n = matrix[0].size();
        
        int r = n, c = m-1;
        int i = 0, j = -1;
        while (r>0 || c>0) {
            int t = r--;
            if (t == 0) break;
            while(t-->0) {res.push_back(matrix[i][++j]);}
            t = c--;
            if (t == 0) break;
            while(t-->0) {res.push_back(matrix[++i][j]);}
            t = r--;
            if (t == 0) break;
            while(t-->0) {res.push_back(matrix[i][--j]);}
            t = c--;
            if (t == 0) break;
            while(t-->0) {res.push_back(matrix[--i][j]);}
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments

O(1) time for each move, O(n) space.

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 TicTacToe {
private:
    int n;
    vector<vector<int>> state;
    vector<vector<int>> cnt;
    
public:
    /** Initialize your data structure here. */
    TicTacToe(int n):state({vector<int>(n, 0), vector<int>(n, 0), vector<int>(2, 0)}), cnt({vector<int>(n, 0), vector<int>(n, 0), vector<int>(2, 0)}) {
        this->n = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    int move(int row, int col, int player) {
        if (state[0][row] < 6) {
            if (++cnt[0][row] == n) {state[0][row] |= 1;}
            state[0][row] |= 1 << player;
            if (state[0][row] == 3 || state[0][row] == 5) return player;
        }
        if (state[1][col] < 6) {
            if (++cnt[1][col] == n) {state[1][col] |= 1;}
            state[1][col] |= 1 << player;
            if (state[1][col] == 3 || state[1][col] == 5) return player;
        }
        
        if (row == col && state[2][0] < 6) {
            if (++cnt[2][0] == n) state[2][0] |= 1; 
            state[2][0] |= 1 << player; 
            if (state[2][0] == 3 || state[2][0] == 5) return player;
        }
        if (n-1-row == col && state[2][1] < 6) {
            if (++cnt[2][1] == n) state[2][1] |= 1; 
            state[2][1] |= 1 << player; 
            if (state[2][1] == 3 || state[2][1] == 5) return player;
        }
        return 0;
    }
};
/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

偷看discussion有人用+-1來表示state，絕對值==size的時候代表row/column/diagonal全是player 1/2。這樣代碼簡短很多，時間複雜度一樣。

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
 class TicTacToe {
private:
    int n;
    vector<vector<int>> cnt;
    
public:
    /** Initialize your data structure here. */
    TicTacToe(int n):cnt({vector<int>(n, 0), vector<int>(n, 0), vector<int>(2, 0)}) {
        this->n = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    int move(int row, int col, int player) { 
        cnt[0][row] += (player == 1? 1 : -1);
        cnt[1][col] += (player == 1? 1 : -1);
        if (row == col) cnt[2][0] += (player == 1? 1 : -1);
        if (n-1-row == col) cnt[2][1] += (player == 1? 1 : -1);
        if (abs(cnt[0][row]) == n || abs(cnt[1][col]) == n || abs(cnt[2][0]) == n || abs(cnt[2][1]) == n) return player;
        return 0;
    }
};
/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

發表於   |   分類於   |   0 comments

in place:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void reverseWords(string &s) {
        auto p1 = s.begin();
        for (auto p2 = s.begin(); p2 != s.end()+1; p2++) {
            if (*p2 == ' ' || p2 == s.end()) {
                reverse(p1, p2);
                p1 = p2+1;
            }
        }
        reverse(s.begin(), s.end());
    }
};

not in place:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void reverseWords(string &s) {
        int l = s.length();
        // split string s;
        vector<string> v;
        int p1 = 0;
        int p2 = s.find(" ");
        while (p2 != string::npos) {
            v.push_back(s.substr(p1, p2-p1));
            p1 = p2+1;
            p2 = s.find(" ", p1);
        }
        if (p1 < l) v.push_back(s.substr(p1));
        stringstream ss;
        for (int i = v.size()-1; i>=0; i--) {
            ss << v[i] ;
            if (i > 0) ss<< " ";
        }
        s = ss.str();
        
    }
};