發表於   |   0 comments

C++ review

Modern object-oriented (OO) languages provide 3 capabilities:

  • encapsulation (combining the data and its functions into one single name)
  • inheritance
  • polymorphism
閱讀全文 »

發表於   |   分類於   |   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
class Solution {
private:
    vector<vector<int>> ans;
    vector<int> marked;
    vector<int> sol;
public:
    vector<vector<int>> permute(vector<int>& nums) {
       for (int i = 0; i < nums.size(); i++) 
            marked.push_back(0);
        permute_(nums);
        return ans;
    }
    
    
    void permute_(vector<int>& nums) {
        bool flag = false;
        int i;
        for (i = 0; i < nums.size(); i++) {
            if(!marked[i]) {
                sol.push_back(nums[i]);
                marked[i] = 1;
                flag = true;
            }
            else 
                continue;
            permute_(nums);
           
            sol.pop_back();
            marked[i] = 0;
        }
        if (!flag) {
             ans.push_back(sol);
            return;
        }
    }
};

發表於   |   分類於   |   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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> sets;
        vector<vector<int> > ans;
        sort(nums.begin(), nums.end());
        ans.push_back(sets);
        backtracking(nums, 0, sets, ans);
        return ans;
    }
    void backtracking(vector<int>& nums, int start, vector<int> &sets, vector<vector <int>> &ans) {
        unsigned long len = nums.size();
        if (start >= len)
            return void();
        for (int i = start; i < len; i++) {
            if (i > start && nums[i] == nums[i-1])
                continue;
            sets.push_back(nums[i]);
            ans.push_back(sets);
            backtracking(nums, i + 1, sets, ans);
            sets.pop_back();
        }
    }
};

發表於   |   分類於   |   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 {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> sets;
        vector<vector<int> > ans;
        ans.push_back(sets);
        backtracking(nums, 0, sets, ans);
        return ans;
    }
    void backtracking(vector<int>& nums, int start, vector<int> &sets, vector<vector <int>> &ans) {
        int len = nums.size();
        if (start >= len)
            return void();
        for (int i = start; i < len; i++) {
            sets.push_back(nums[i]);
            ans.push_back(sets);
            backtracking(nums, i + 1, sets, ans);
            sets.pop_back();
        }
    }
};

發表於   |   分類於   |   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
class Solution {
private:
    vector<int> sol;
    vector<vector<int>> ans;
    
    
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> marked(nums.size(), 0);
        sort(nums.begin(), nums.end());
        permuteUnique_(nums, marked, 0);
        return ans;
    }
    void permuteUnique_(vector<int>& nums, vector<int>& marked, int level) {
        int prev_num;
        //printf("level=%d ", level);
        if (level >= nums.size()) {
            ans.push_back(sol);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (marked[i])
                continue;
            if (i > 0 && (nums[i] == prev_num))
                continue;
            prev_num = nums[i];
            sol.push_back(nums[i]);
            //cout<<sol.size();
            marked[i] = 1;
            permuteUnique_(nums, marked, level + 1);
            sol.pop_back();
            marked[i] = 0;
        }
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int min = INT_MAX;
        int second_min = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > second_min) return true;
            else if (nums[i] <= min) min = nums[i];
            else second_min = nums[i];
        }
        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
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
/**
 * 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<vector<TreeNode*>> forests;
    int max = -1;
    TreeNode* traversalAdd(int n, TreeNode* tree) {
        if (tree == NULL) return NULL;
        TreeNode* root = new TreeNode(tree->val + n);
        root -> left = traversalAdd(n, tree -> left);
        root -> right = traversalAdd(n, tree -> right);
        return root;
    }
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> resultTrees;
        if (n > max) {
            vector<TreeNode*> trees;
            for (int i = 0; i < n + 1; i++)
                forests.push_back(trees);
            max = n;
        }
        if (forests[n].size() == 0 && n != 0){
            if (n == 1) {
                TreeNode *root = new TreeNode(1);
                forests[1].push_back(root);
                return forests[1];
            }
            if (n == 0) {
                //forests[0].push_back(NULL);
                return forests[0];
            }
            
            // vector<TreeNode*> left;
            // left.push_back(NULL);
            vector<TreeNode *> right = generateTrees(n - 1);
            for (int k = 0; k < right.size(); k++) {
                TreeNode *root = new TreeNode(1);
                root -> left = NULL;
                root -> right = traversalAdd(1, right[k]);
                resultTrees.push_back(root);
            }
                
            for (int i = 1; i < n - 1; i++) {
                vector<TreeNode *> left = generateTrees(i);
                vector<TreeNode *> right = generateTrees(n - 1 - i);
                for (int j = 0; j < left.size(); j++) {
                    for (int k = 0; k < right.size(); k++) {
                        TreeNode *root = new TreeNode(i + 1);
                        root -> left = left[j];
                        root -> right = traversalAdd(i + 1, right[k]);
                        resultTrees.push_back(root);
                    }
                }
            }
            
            // right.clear();
            // right.push_back(NULL);
            vector<TreeNode*> left = generateTrees(n - 1);
            for (int k = 0; k < left.size(); k++) {
                TreeNode *root = new TreeNode(n);
                root -> left = left[k];
                root -> right = NULL;//right;
                resultTrees.push_back(root);
            }
            
            return resultTrees;
        }
        else return forests[n];
    }
};

發表於   |   分類於   |   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
class MinStack {
public:
    vector<int> a;
    int min;
    int len;
    bool flag;
    int min_index;
    /** initialize your data structure here. */
    MinStack() {
        len = 0;
        min = -1;
        flag = false;
    }
    
    void push(int x) {
        a.push_back(x);
        len++;
        if(!flag) {
            min = x;
            flag = true;
        }
        else {
            if (x < min) {
                min = x;
               min_index = len-1;
        }
        }
        
    }
    
    void pop() {
        a.pop_back();
        if(min_index == len - 1)
            get_min();
        len--;
        if(len == 0)
            flag = false;
    }
    
    int top() {
        return a[a.size()-1];
    }
    
    int getMin() {
        if(flag == false) {
            get_min();
        }
        return min;
    }
    
    void get_min() {
        min = a[0];
            for(int i = 0; i < a.size(); i++) {
                if(a[i] < min) {
                    min = a[i];
                    min_index = i;
                }
            }
    }
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

發表於   |   分類於   |   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
class Solution {
public:
    int max = 0;
    vector<int> F;
    int numTrees(int n) {
        if (n > max) {
            for (int i = 0; i < n + 1 - max; i++)
                F.push_back(-1);
            max = n;
            
        }
        if (n == 0 || n == 1) {
            F[n] = 1;
            return 1;
        }
        else {
            if (F[n] != -1) return F[n];
            F[n] = 0;
            for (int i = 0; i < n; i++)
                F[n] += numTrees(i)*numTrees(n-1-i);
            return F[n];
        }
    }
};

發表於   |   分類於   |   0 comments

updated Dec 13:

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 graph {
    vector<unordered_set<int>> adj;
    int n;
    vector<int> temp_visited;
    vector<int> perm_visited;
    vector<int> sort_result;
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);
        }
    }
    vector<int> topologicalSort() {
        for (int i = 0; i < n; i++)
            if (!perm_visited[i]) {
                dfs(i);
                if (sort_result.empty()) return sort_result;
            }
        reverse(sort_result.begin(), sort_result.end());
        return sort_result;
    }
    void dfs(int cur) {
        if (perm_visited[cur]) return;
        temp_visited[cur] = 1;
        for (int next:adj[cur]) {
            if (temp_visited[next]) {
                sort_result = vector<int>();
                return;
            }
            dfs(next);
            if (sort_result.empty()) return;
        }
        temp_visited[cur] = 0;
        perm_visited[cur] = 1;
        sort_result.push_back(cur);
        return;
    }
};
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses, prerequisites);
        return g.topologicalSort();
    }
};
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 Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        def dfs(root):
            # print "root:",root
            marked = [0] * numCourses
            stack = []
            stack.append(root)
            while stack:
                s = stack[-1]
                if visited[s]:
                    stack.pop()
                    if marked[s]:
                        res.append(s)
                    marked[s] = 0
                else:  
                    visited[s] = 1
                    marked[s] = 1
                    if len(pre[s]) == 0:
                        stack.pop()
                        marked[s] = 0
                        res.append(s)
                        continue
                    for x in pre[s]:
                        if x in stack and marked[x] == 1:
                            return 0
                        stack.append(x)
            return 1
        roots = range(numCourses)
        pre = [[]]*numCourses
        for i in range(numCourses):
            pre[i] = []
        visited = [0]*numCourses
        res = []
        for i in range(len(prerequisites)):
            # print "iter",i
            after = prerequisites[i][0]
            prev = prerequisites[i][1]
            if prev in roots:
                roots.remove(prev)
            pre[after].append(prev)
        for root in roots:
            if not dfs(root):
                return []
        if 0 in visited:
            return []
        return res