Leetcode

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int run(TreeNode root) {
        
        if (root == null){
            return 0;
        } else if (root.left == null){
            return run(root.right) + 1;
        } else if (root.right == null){
            return run(root.left) + 1;
        } else {
            return Math.min(run(root.left), run(root.right))+1;
        }
    }
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int run(TreeNode *root) {
        
        if(root == nullptr) {
            return 0;
        } else if (root->left == nullptr ){
            
            return run(root ->right) + 1;
            
        } else if (root-> right == nullptr){
            return run(root ->left) +1;
        } else{
            return 1 + min(run(root->left),run(root->right));
        }
    }
};

Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:

1
2
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

max-points-on-a-line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

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
#include <vector>
#include <iostream>
 
 
using namespace std;
 
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
     
    int maxPoints(vector<Point> &points) {
         
        int size = points.size();
         
        if( size == 0){
            return 0;
        } else if (size == 1){
            return 1;
        } else {
             
            int result = 0;
             
             
            for (int i = 0; i < size; ++i){
                int curmax = 1;
                int same = 0;
                int verticle = 1;
                 
                map < double, int > m;
                 
                for (int j = 0; j < size; ++j){
                     
                    if(i == j) continue;
                     
                    int dx = points[i].x - points[j].x;
                    int dy = points[i].y - points[j].y;
                     
                
                    if(dx == 0){
                       if (dy == 0) {same ++;}
                       else{
                           verticle ++;
                           curmax = max( curmax, verticle);
                       }
                        
                          
                    }else{
                        double k = (1.0*dy)/dx;
                        if(m[k] == 0){
                            m[k] = 2;
                        }else{
                            ++m[k];
                        }
                        curmax = max(m[k],curmax);
                         
                    }
                     
                }
                result = max(result, curmax + same);
                 
            }
            return result;
        }
                 
         
         
    }
};

sort-list

Sort a linked list in O(n log n) time using constant space complexity.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    ListNode *merge(ListNode * left, ListNode * right){
        ListNode tmp(0);
        ListNode *p = &tmp;
        
        while (left && right){
            if (left -> val < right -> val){
                p -> next = left;
                left = left -> next;
            } else{
                p -> next = right;
                right = right -> next;
            }
            
            p = p ->next;
        }
        
        if(left){
            p -> next = left;
        }
        
        if(right){
            p -> next = right;
        }
        
        
        
        return tmp.next;
        
        
        
    }
    
    ListNode *sortList(ListNode *head) {
        if(!head || !head->next){
            return head;
        }
        
        ListNode *p = head, *q = head->next;
        
        while(q && q->next){
            p = p->next;
            q = q->next->next;
        }
        
        ListNode * right = sortList( p ->next);
        p ->next = NULL;
        ListNode * left = sortList(head);
        
        return merge(left, right);
        
    }
};

two-sum

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

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<int> twoSum(vector<int> &numbers, int target) {
        vector <int> ans;
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < numbers.size() - 1; ++i){
            int tmp = target - numbers[i];
            for(int j = i+1; j <numbers.size(); ++j ){
                if (tmp == numbers[j]){
                    ans.push_back(i+1);
                    ans.push_back(j+1);
                    
                    
                }
            }
        }
        
        return ans;
    }
};

using hash unordered_map

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
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        
        unordered_map <int, int> hash;
        vector <int> res;
        
        for (int i = 0; i < numbers.size(); ++i){
            hash[numbers[i]] = i;
        }
        
        for (int i = 0; i < numbers.size(); ++i){
            int tmp = target - numbers[i];
            if(hash.find(tmp)!= hash.end() && hash[tmp] > i){
                res.push_back(i+1);
                res.push_back(hash[tmp] + 1);
                
            }
        }
        return res;
        /*
        vector <int> ans;
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < numbers.size() - 1; ++i){
            int tmp = target - numbers[i];
            for(int j = i+1; j <numbers.size(); ++j ){
                if (tmp == numbers[j]){
                    ans.push_back(i+1);
                    ans.push_back(j+1);
                    
                    
                }
            }
        }
        
        return ans;*/
    }
};

balanced-binary-tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 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
29
30
31
32
33
34
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    int getDepth(TreeNode * root){
        if (root == NULL) return 0;
        if (root -> left == NULL) return 1 + getDepth(root ->right);
        if (root -> right == NULL) return 1 + getDepth(root ->left);
        return 1 + max(getDepth(root-> left), getDepth(root-> right));
        
    }
    bool isBalanced(TreeNode *root) {
        
        if (root == NULL) return true;
        
        
        int left = getDepth(root -> left);
        int right = getDepth(root -> right);
        
        if (abs(left - right) > 1 ) return false;
        
        return (isBalanced(root -> left) && isBalanced(root -> right));
        
    }
};

binary-preorder-traversal

Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},

1
2
3
4
5
1
 \
  2
 /
3

return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

###Recursive

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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector <int> result;
        
        if (root == NULL) return result;
        
        helper(root,result);
        
        return result;
    }
    
private:
    void helper(TreeNode * root, vector <int> &vec){
        if (root == NULL) return;
        vec.push_back(root -> val);
        helper(root -> left, vec);
        helper(root -> right, vec);
    }
};

iterative

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 binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector <int> result;
        stack <TreeNode *> st;
        
        if (root == NULL) return result;
        
        st.push(root);
        
        while(!st.empty()){
            TreeNode * current = st.top();
            st.pop();
            
            if (current -> right != NULL) st.push(current->right);
            if (current -> left != NULL) st.push(current->left);
            result.push_back(current -> val);
            
            
        }
        
        
        
        
        //helper(root,result);
        
        return result;
    }
    
private:
    
    
    
    void helper(TreeNode * root, vector <int> &vec){
        if (root == NULL) return;
        vec.push_back(root -> val);
        helper(root -> left, vec);
        helper(root -> right, vec);
    }
};

string to integer atoi

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
spoilers alert… click to show requirements for atoi.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

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
class Solution {
public:
    int atoi(const char *str) {
        long long res = 0;
        if (str == NULL){
            return res;
        }
        
        int len = strlen(str);
        int i = 0;
        bool neg = false;
        
        while (str[i] == ' '|| str[i] == '0'){
            ++i;
        }
        
        if (str[i] == '-'){
            
            neg = true;
            ++i;
        } else if (str[i] == '+'){
            neg = false;
            ++i;
        }
        
        for (;i < len;++i){
            char ch = str[i];
            if (ch >='0' && ch <='9'){
                res = res*10 + ch - '0';
                
                if (res > INT_MAX){
                    return neg? INT_MIN:INT_MAX;
                }
                
            }else{
                if (neg) return -res;
        		return res;   
            }
            
        }
        
        if (neg) return -res;
        return res;
        
    }
};

merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        
        ListNode * dummy = new ListNode(0);
        ListNode * p = dummy;
        
        while(l1!=NULL && l2!=NULL){
            if (l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
            }else {
                p -> next = l2;
                l2 = l2 -> next;
            }
            
            p = p ->next;
        }
        
        if(l1!= NULL){
            p -> next = l1;
        }
        if(l2!= NULL){
            p -> next = l2;
        }
        
        return dummy -> next;
    }
};

##

1
2
赏

谢谢你请我吃糖果

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    2、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: true
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

<br>上海交通大学研究生在读<br>对新鲜事物感兴趣<br>云计算<br>深度学习<br>数据分析