Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/palindrome-permutation-ii/

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
class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> ret;
        unordered_map<char, int> counter;
        for (int i = 0; i < s.size(); ++i) {
            counter[s[i]] += 1;
        }
        int singularCount = 0;
        char singularChar;
        bool singularFlag = false;
        for (auto& item : counter) {
            if (item.second % 2) {
                singularCount += 1;
                singularChar = item.first;
                singularFlag = true;
            }
        }
        if (singularCount > 1) return ret;
        string cur;
        if (singularFlag) {
            cur += singularChar;
            --counter[singularChar];
        }
        
        
        helper(ret, counter, cur, '\n', s.size());
        
        return ret;
    }
    
    void helper(vector<string>& ret, unordered_map<char, int>& counter, string cur, char pre, int lens){
        bool flag = false; // mark the end
        string originStr = cur;
        for (auto& item : counter) {
            if (item.second == 0 || item.first == pre) continue;
            flag = true;
            int originCount = item.second;
            // string newStr = item.first + cur + item.first;
            while(item.second > 0) {
                cur = item.first + cur + item.first;
                item.second -= 2;
                helper(ret, counter, cur, item.first, lens);
            }
            item.second = originCount;
            cur = originStr;
        }
        if (cur.size() == lens) ret.push_back(cur); 
    }
};

Posted on

Description

Direction Solution (MLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int sizeS = s.size();
        int sizeT = t.size();
        
        vector<vector<int>> dp(sizeS + 1, vector<int>(sizeT + 1, 0));
        for (int i = 1; i <= sizeS; ++i) dp[i][0] = i;
        for (int j = 1; j <= sizeT; ++j) dp[0][j] = j;
        
        
        for (int i = 1; i <= sizeS; ++i){
            for (int j = 1; j <= sizeT; ++j) {
                int bias = (s[i - 1] == t[j - 1]) ? 0 : 1; 
                dp[i][j] = dp[i - 1][j - 1] + bias;
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            }
        }
        
        
        return dp[sizeS][sizeT] == 1;
    }
};

Unfortunately, this implementation can result in the memory excess in the last test case. So why don’t be naive, or let’s say, back to the origin.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) swap(s, t);
        int m = s.size(), n = t.size(), diff = m - n;
        if (diff >= 2) return false;
        else if (diff == 1) {
            for (int i = 0; i < n; ++i) {
                if (s[i] != t[i]) {
                    return s.substr(i + 1) == t.substr(i);
                }
            }
            return true;
        } else {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if (s[i] != t[i]) ++cnt;
            }
            return cnt == 1;
        }
    }
};

Posted on

Description

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let’s take the following BST as an example, it may help you understand the problem better:

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The “head” symbol means the node it points to is the smallest element of the linked list.

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (root == NULL) return NULL;
        
        pair<Node*, Node*> ret = makeList(root); 
        ret.second->right = ret.first;
        ret.first->left = ret.second;
        
        return ret.first;
    }
    
    pair<Node*, Node*> makeList(Node* root) {
        
        pair<Node*, Node*> pairLeft = root->left ? 
                    makeList(root->left) : make_pair(root, root);
        pair<Node*, Node*> pairRight = root->right ? 
                    makeList(root->right) : make_pair(root, root);
        
        if (root->left) {
            pairLeft.second->right = root;
            root->left = pairLeft.second;
        }
        if (root->right) {
            pairRight.first->left = root;
            root->right = pairRight.first;
        }
        
        return make_pair(pairLeft.first, pairRight.second);
    }
    
};

Posted on

Description

https://leetcode.com/problems/maximum-binary-tree/description/

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
/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* ret = NULL;
        helper(nums, ret, 0, nums.size() - 1);
        return ret;
    }
    
    void helper(vector<int>& nums, TreeNode*& ret, int start, int end) {
        if (start > end) return;
        int maxium = INT_MIN;
        int target = -1;
        for (int i = start; i <= end; ++i) {
            if (nums[i] > maxium) {
                maxium = max(nums[i], maxium);
                target = i;   
            }
        }
        
        ret = new TreeNode(maxium);
        helper(nums, ret->left, start, target - 1);
        helper(nums, ret->right, target + 1, end);
    }
};

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct SegNode{
    int leftBound;
    int rightBound;
    pair<int, int> maxium;
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* ret = NULL;
        if (nums.size() == 0) return ret;
        vector<SegNode> seg(nums.size() * 4);
        build(seg, nums, 0, nums.size() - 1, 0);
        
        helper(nums, ret, 0, nums.size() - 1, seg);
        return ret;
    }
    
    pair<int, int> build(vector<SegNode>& seg, vector<int>& nums, int start, int end, int index) {
        if (start > end) return make_pair(INT_MIN, -1);
        seg[index].leftBound = start;
        seg[index].rightBound = end;
        
        if (start == end) {
            seg[index].maxium = make_pair(nums[start], start);
            return seg[index].maxium;
        }
        int mid = (start + end) >> 1;
        
        auto l = build(seg, nums, start, mid, index * 2 + 1);
        auto r = build(seg, nums, mid + 1, end, index * 2 + 2);
        seg[index].maxium = l.first > r.first ? l : r;
        return seg[index].maxium;
    }
    
    pair<int, int> query(int left, int right, vector<SegNode>& seg, int index) {
        if (left > right) return make_pair(INT_MIN, -1);
        int leftBound = seg[index].leftBound;
        int rightBound = seg[index].rightBound;
        int mid = (leftBound + rightBound) >> 1;
        if (left == leftBound && right == rightBound) return seg[index].maxium;
        if (left > mid) return query(left, right, seg, index * 2 + 2);
        if (right <= mid) return query(left, right, seg, index * 2 + 1);
        
        auto l = query(left, mid, seg, index * 2 + 1);
        auto r = query(mid + 1, right, seg, index * 2 + 2);
        return l.first > r.first ? l : r;
    }
    
    void helper(vector<int>& nums, TreeNode*& ret, int start, int end, vector<SegNode>& seg) {
        if (start > end) return;
        auto target = query(start, end, seg, 0);
        
        ret = new TreeNode(target.first);
        ret->left = NULL;
        ret->right = NULL;
        helper(nums, ret->left, start, target.second - 1, seg);
        helper(nums, ret->right, target.second + 1, end, seg);
    }
};

Posted on

Description

https://leetcode.com/problems/remove-k-digits/

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
class Solution {
public:
    struct cmp {
        bool operator() (pair<int, char>& left, pair<int, char>& right) {
            return left.second > right.second;
        }
    };
    string removeKdigits(string num, int k) {
        if (num.size() <= k) return string("0");
        
        //Check Zero
        int preNoZero = 0;
        int count = 0;
        int index = -1;
        for (int i = 0; i < num.size(); ++i) {
            if (num[i] == '0' && count <= k) {
                preNoZero = count;
                index = i;
            }else {
                count += 1;
            }
        }
        num.erase(0, index + 1);
        k -= preNoZero;
        
        
        int pick = num.size() - k;
        string ret;
        int last = 0;
        while (pick > 0) {
            char minum = '9' + 1;
            int targetIndex = -1;
            for (int i = last; i < num.size(); ++i) {
                if (num[i] < minum && num.size() - i >= pick) {
                    minum = num[i];
                    targetIndex = i;
                }
            }
            --pick;
            ret += minum;
            num.erase(targetIndex, 1);
            last = targetIndex;
        }
        if (ret.size() == 0) return string("0");
        return ret;
    }
};

Posted on

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negativeintegers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

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
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
enum Type {
    NUM,
    MUL,
    DIV,
    SUB,
    ADD,
    LEFT,
    RIGHT
};

class Solution {
public:
    int calculate(string s) {
        int index = 0;
        
        stack<string> operatorStack;
        queue<string> retQueue;
        
        while (index < s.size()) {
            while(index < s.size() && s[index] == ' ') ++index;
            if (index >= s.size()) break;
            string cur = string(1, s[index]);
            switch(judge(cur)) {
                case NUM:
                    cur = parse(index, s);
                    retQueue.push(cur);
                    break;
                case MUL:
                    while (!operatorStack.empty() && 
                        (operatorStack.top() == "*" || 
                            operatorStack.top() == "/")) {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case DIV:
                    while (!operatorStack.empty() && 
                        (operatorStack.top() == "*" || 
                            operatorStack.top() == "/")) {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case SUB:
                    while (!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case ADD:
                    while (!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.push(cur);
                    ++index;
                    break;
                case LEFT:
                    operatorStack.push(cur);
                    ++index;
                    break;
                case RIGHT:
                    while(!operatorStack.empty() && operatorStack.top() != "(") {
                        retQueue.push(operatorStack.top());
                        operatorStack.pop();
                    }
                    operatorStack.pop(); //pop the '('
                    ++index;
                    break;
            }
        }
        while (!operatorStack.empty()) {
            retQueue.push(operatorStack.top());
            operatorStack.pop();
        }
        
        stack<long> helper;
        while (!retQueue.empty()) {
            string& s = retQueue.front();
            retQueue.pop();
            if (judge(s) != NUM) {
                long r = helper.top();
                helper.pop();
                long l = helper.top();
                helper.pop();
                helper.push(function(s, l, r) );
            }else{
                helper.push(stol(s));
            }
        }
        
        return helper.top();
    }
    
    string parse(int& index, string& s) {
        string ret = "";
        while (index < s.size() && s[index] <= '9' && s[index] >= '0') {
            ret += s[index];
            ++index;
        }
        
        return ret;
    }
    
    long function(string& op, long leftNumber, long rightNumber) {
        switch (op[0]) {
            case '-':
                return leftNumber - rightNumber;
            case '+':
                return leftNumber + rightNumber;
            case '/':
                return leftNumber / rightNumber;
            case '*':
                return leftNumber * rightNumber;
        }
        return -1; //Wrong
    }
    
    Type judge(string& c) {
        if (c == "(") return LEFT;
        if (c == ")") return RIGHT;
        if (c == "+") return ADD;
        if (c == "-") return SUB;
        if (c == "*") return MUL;
        if (c == "/") return DIV;
        return NUM;
    }
};

Posted on

Description

https://leetcode.com/problems/validate-binary-search-tree/

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
/**
 * 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(LONG_MIN, LONG_MAX, root);
    }
    
    bool helper(long lowerBound, long upperBound, TreeNode* root) {
        if (root == NULL) return true;
        if (root->val <= lowerBound 
            || root->val >= upperBound) {
            return false;
        }
        
        return helper(lowerBound, root->val, root->left) 
                    && helper(root->val, upperBound, root->right);
    }
    
};

Posted on

Description

https://leetcode.com/problems/graph-valid-tree/

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

1
2
Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

1
2
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges

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
class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        if (n == 0 || n == 1) return true;
        vector<int> status(n, 0);
        unordered_map<int, vector<int>> edgeMap;
        
        for (auto& item : edges) {
            edgeMap[item.first].push_back(item.second);
            edgeMap[item.second].push_back(item.first);
        }
        
        if (edgeMap.count(0) == 0) return false;
        bool hasLoop = false;
        traverse(edgeMap, status, 0, hasLoop, -1);
        if (hasLoop == true) return false;
        
        //Check is directed graph
        for (int i = 1; i < n; ++i) {
            if (status[i] != 1) return false;
        }
        
        return true;
    }
    
    void traverse(unordered_map<int, vector<int>>& edgeMap, 
            vector<int>& status, int index, bool& hasLoop, int pre) {
        if (hasLoop == true || status[index] == 1) return;
        if (status[index] == - 1) {
            hasLoop = true;
            return;
        }
        
        auto& lis = edgeMap[index];
        status[index] = -1; //Mark as pending
        for (auto& item : lis) {
            if (item == pre) continue;
            traverse(edgeMap, status, item, hasLoop, index);
        }
        
        status[index] = 1; //Mark as visit
        return;
    }
};

Posted on

Description

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
class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<int> dp(n, -1);
        vector<bool> occupied(n);
        int ret = n;
        for (int i = 0; i < n; ++i) dp[i] = i;
        for (int i = 0; i < edges.size(); ++i) {
            int left = edges[i].first;
            int right =edges[i].second;
            int leftRoot = findRoot(dp, left);
            int rightRoot = findRoot(dp, right);
            if (leftRoot != rightRoot) {
                dp[leftRoot] = rightRoot;
                --ret;
            }
        }
        
        return ret;
    }
    

    int findRoot(vector<int>& dp, int index) {
        stack<int> st;
        while (dp[index] != index) {
            st.push(index);
            index = dp[index];
        }
        while(st.empty() == false) {
            int item = st.top();
            dp[item] = index;
            st.pop();
        }
        return index;
    }
};