發表於   |   分類於   |   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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 // recursive ver.
class Solution {
    vector<vector<int>> res;
public:
    void traverse(TreeNode* r, int level) {
        if (level > res.size()) res.push_back(vector<int>());
        res[level - 1].push_back(r -> val);
        if (r -> left != nullptr) traverse(r -> left, level+1);
        if (r -> right != nullptr) traverse(r -> right, level+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root != nullptr) traverse(root, 1);
        return res;
    }
};

發表於   |   分類於   |   0 comments

recursively

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
/**
 * 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 {
private:
    vector<vector<int>> res;
public:
    int findLevel(TreeNode* r) {
        if (r == nullptr) return 0;
        int level = 1+max(findLevel(r->left), findLevel(r->right));
        if (level > res.size()) res.push_back(vector<int>());
        if (r) res[level - 1].push_back(r->val);
        return level;
    }
    vector<vector<int>> findLeaves(TreeNode* root) {
        findLevel(root);
        return res;
    }
};

queue

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 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q1, q2;
        vector<vector<int>> res;
        if(root) q1.push(root);
        while (!q1.empty()) {
            vector<int> tmp_res;
            while (!q1.empty()) {
                TreeNode* t = q1.front();
                q1.pop();
                if (t->left) q2.push(t->left);
                if (t->right) q2.push(t->right);
                tmp_res.push_back(t->val);
            }
            swap(q1, q2);
            res.push_back(tmp_res);
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    vector<int> head;
public:
    bool Union(int node1, int node2) {
        int h1 = node1, h2 = node2;
        while (head[h1] != -1) h1 = head[h1];
        while (head[h2] != -1) h2 = head[h2];
        if (h1 != h2) {
            head[h2] = h1;
            return true;
        }
        else return false;
    }
    bool validTree(int n, vector<pair<int, int>>& edges) {
        for (int i = 0; i < n; i++)  head.push_back(-1);
        for (auto e:edges) {
            if (!Union(e.first, e.second)) return false;
        }
        return (edges.size() == n-1);
    }
};

發表於   |   分類於   |   0 comments

遞歸地在子樹里找p/q，如果在不同子樹那麼LCA是parent，否則返回在子樹遞歸的結果。

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

發表於   |   分類於   |   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<string> findRepeatedDnaSequences(string s) {
        unordered_map<string,int> mp;
        vector<string> result;
        if(s.length()<10) return result;
        
        
        for(int i=0;i<=s.length()-10;i++){
            string temp=s.substr(i,10);
            if(mp.find(temp)==mp.end()) {
                mp[temp]=1;
            }
            else mp[temp]++;
        }
        for(auto k:mp){
            if(k.second>1) result.push_back(k.first);
        }
        return result;
    }
};
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{
public:
vector<string> findRepeatedDnaSequences(string s) {
    int l = s.length();
    // vector<int> set;
    unordered_map<int, int> set;
    unordered_map<int, int> res;
    vector<string> ress_v;
    int k = 0;
    map<int,int> m;
    m['C'-'A'] = 1;
    m['G'-'A'] = 2;
    m['T'-'A'] = 3;
    for (int i = 0; i < l; i+=1) {
        k = k << 2;
        k = k & 0xFFFFF;
        k |= m[s[i]-'A'];
        if (i > 8) {
            if (set[k]>=1 && find(ress_v.begin(), ress_v.end(), s.substr(i-9,10))==ress_v.end())
                ress_v.push_back(s.substr(i-9,10));
            // }
            set[k]+=1;
        }
    }
    // for (auto i:set) {
        // if(set.second > 1)
            // ress_v.pushback{}
    // }
    return ress_v;
}
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> rem;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (rem.find(nums[i])!=rem.end()) {
                res.push_back(rem[nums[i]]);
                res.push_back(i);
            }
            else {
                rem[target-nums[i]] = i;
            }
        }
        return res;
    }
};

version of 08/30/2015

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
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        map<int, int>test;
        for(int i=0;i<nums.size();i++){
            int t=nums[i];
            map<int,int>::iterator it = test.find(t);
            if(it!=test.end()){
                
//                if(test[j]==t){
                res.push_back(it->second+1);
                    res.push_back(i+1);
  //              }
            }
            test[target-nums[i]]=i;
        }
        return res;
    }
    
};

發表於   |   分類於   |   0 comments

1 L3ND 7H15 660 BuCK5 FR0M 7H3 Fu7uR3 M3 F0R 3N73R741N1N6 R3450N 0NLy, w17H C0MM17M3N7 7H47 1 w0N’7 C4u53 700 M4Ny BuRD3N5 70 Fu7uR3 M3. 70 D15P3L My CuRR3N7 C0NC3RN5, 4ND 70 B3 F41R w17H Fu7uR3 M3, 1 46R33 7H47 1N 7H3 C0M1N6 y34R 1 w0uLD:

  1. R357R1C7 My 5P3ND1N6(1NCLuD1N6 1N73RN37, R3N71N6, PH0N3) 70 uND3R 950$. (54v1N6 50$ P3R M0N7H 70 M4K3 uP)
  2. 50Lv3 47 L3457 3 L337C0D3 PR0BL3M5 3v3RyD4y F0R 7H3 F1R57 F3w M0N7H5
  3. 3x7R4 PR0BL3M5 50Lv3D C0uN75 F0R 5$ P3R PR0BL3M R3L4x1N6 7H3 R357R1C710N 61v3N By (1)
  4. L1v3 R34L. L0v3 y0uR L1F3. B3 BR4v3. L4u6H. B3 vuLN3R4BL3. R35P3C7 y0uR 71M3.
  5. uPD473 R3C0RD5 H3R3.

7H15 C0N7R4C7 C0M3 1N70 3FF3C7 1MM3D1473Ly FR0M 0C7.15/2016 70 D3C.25/2017. 1 H0P3 y0u’v3 607 4 J0B 4ND L1v3D w3LL 47 7H47 71M3. 7H15 C0N7R4C7 C4N B3 M0D1F13D 1F 17’5 F0R 600D R3450N.

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int l = nums.size();
        for (int i = 0; i < l; i++) {
            int t = nums[i];
            if (t > 0 && t - 1 < l && nums[t - 1] != t && t != (i + 1)) {
                nums[i] = nums[t - 1];
                nums[t - 1] = t;
                i--;
            }
        }
        for (int i = 0; i < l; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return l + 1;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int l = nums.size();
        vector<int> dp(l, 0);
        dp[0] = nums[0];
        for (int i = 1; i < l; i++) {
            if (dp[i - 1] < 0)
                dp[i] = nums[i];
            else 
                dp[i] = nums[i] + dp[i - 1];
        }
        int max = INT_MIN;
        for (int i = 0; i < l; i++) {
            if (dp[i] > max)
                max = dp[i];
        }
        return max;
    }
};

updated Dec 23, 2016:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int l = nums.size();
        int mx[l];
        int mx_v = INT_MIN;
        for (int i = 0; i < l; i++) {
            int tmp;
            if(i)  tmp = (mx[i-1]>0?mx[i-1]:0)+nums[i];
            else tmp = nums[i];
            mx[i] = tmp;
            if (tmp > mx_v) mx_v = tmp;
        }
        return mx_v;
    }
};

發表於   |   分類於   |   0 comments 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    vector<vector<int>> dp;
    int bound;
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        bound = triangle.size();
        for (int i = 0; i < bound; i++) {
            vector<int> tmp(i+1,INT_MIN);
            dp.push_back(tmp);
        }
        return solve(triangle, 0, 0);
    }
    int solve(vector<vector<int>> &triangle, int i, int j) {
        if (dp[i][j] !=INT_MIN) return dp[i][j];
        else if (i >= bound-1)
            dp[i][j] = triangle[i][j];
        else
            dp[i][j] = triangle[i][j]+min(solve(triangle, i+1, j), solve(triangle, i+1, j+1));
        return dp[i][j];
    }
};