[webdriver]

LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.

To be successful in a technical interview, we believe it is mainly repeating these three important steps:

Code. Read. Discuss.

We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.

1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.

We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !

This is part 2

第一部分： www.westca.com/Forums/...inese.html

[webdriver]

Problem Name: Minimum Depth of Binary Tree
Description:
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.

[webdriver]

Now comes the solution (in C++) ...

1. Recursion. Pay attention to cases when the non-leaf node has only one child.
2. Iteration + Queue. Contributed by SUN Mian(瀛欏啎).

代碼:

/**  * 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 minDepth(TreeNode *root) {         return minDepth_1(root);     }         int minDepth_1(TreeNode *root) {         if (!root)             return 0;                 if (!root->left && !root->right)             return 1;         else if (!root->left)             return 1 + minDepth_1(root->right);         else if (!root->right)             return 1 + minDepth_1(root->left);         else             return 1 + min(minDepth_1(root->left), minDepth_1(root->right));     }         int minDepth_2(TreeNode *root) {         if (!root) return 0;         queue<TreeNode *> q;         q.push(root);         q.push(NULL);         int depth = 1;         while (true)         {             TreeNode *node = q.front();             q.pop();             if (!node) {                 depth++;                 q.push(NULL);             } else {                 if (!node->left && !node->right) return depth;                 if (node->left) q.push(node->left);                 if (node->right) q.push(node->right);             }         }     } };

[webdriver]

Problem Name: Minimum Path Sum
Description:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right
which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

[webdriver]

Now comes the solution (in C++) ...

Dynamic Programming. Space O(N).

代碼:

class Solution { public:     int minPathSum(vector<vector<int> > &grid) {         if (grid.empty()) return INT_MIN;         int M = grid.size(), N = grid[0].size();         int dp[N];         dp[0] = grid[0][0];         for (int i = 1; i < N; ++i)             dp[i] = grid[0][i] + dp[i-1];                 for (int i = 1; i < M; ++i)         {             dp[0] += grid[i][0];             for (int j = 1; j < N; ++j)                 dp[j] = min(dp[j-1], dp[j]) + grid[i][j];         }                 return dp[N-1];     } };

[webdriver]

Problem Name: Max Points On a Line
Description:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

[webdriver]

Now comes the solution (in C++) ...

...

代碼:

class Solution { public:     int maxPoints(vector<Point> &points) {         int N = points.size(), res(0);         unordered_map<double, int> m;         for(int i = 0;i < N; ++i){             m.clear();             int ss(1), sp(0);                        // ss:points with same slope,starts with 1, sp:same points, starts with 0             for(int j = i+1;j < N; ++j){                 double slope = std::numeric_limits<double>::infinity();                 if(points[i].x != points[j].x)                     slope = 1.0*(points[i].y - points[j].y)/(points[i].x - points[j].x);                 else if(points[i].y == points[j].y){                     sp++; continue;                 }                 int tmp = 0;                 if(m.find(slope) != m.end())                     tmp = ++m[slope];                 else                     tmp = m[slope] = 2;                 ss = max(ss,tmp);             }             res = max(res,ss+sp );         }         return res;     } };

[webdriver]

Problem Name: Median of Two Sorted Arrays
Description:
There are two sorted arrays A and B of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

[webdriver]

Now comes the solution (in C++) ...

1. O(m+n)
2. O(log(m+n))
3. O(logm + logn)

代碼:

class Solution { public:     double findMedianSortedArrays(int A[], int m, int B[], int n) {         return findMedianSortedArrays_1(A, m, B, n);     }     double findMedianSortedArrays_1(int A[], int m, int B[], int n) {         int i = 0, j = 0;         int m1 = 0, m2 = 0;         int total = m + n;         for (int k = 0; k <= total / 2; ++k)         {             int a = (i == m) ? INT_MAX : A[i];             int b = (j == n) ? INT_MAX : B[j];             m1 = m2;             m2 = min(a, b);             if (a < b) i++;             else j++;         }         if (total & 0x1) return m2;         else return (m1 + m2) / 2.0;     }     double findMedianSortedArrays_2(int A[], int m, int B[], int n) {         int total = m + n;         if (total & 0x1)             return findKthSortedArrays(A, m, B, n, total / 2 + 1);         else             return (findKthSortedArrays(A, m, B, n, total / 2) + findKthSortedArrays(A, m, B, n, total / 2 + 1)) / 2;     }     double findKthSortedArrays(int A[], int m, int B[], int n, int k) {         if (m > n)             return findKthSortedArrays(B, n, A, m, k);         if (m == 0) return B[k-1];         if (k == 1) return min(A[0], B[0]);         int i = min(k / 2, m);         int j = k - i;         int a = A[i-1];         int b = B[j-1];         if (a < b) return findKthSortedArrays(A + i, m - i, B, n, k - i);         else if (a > b) return findKthSortedArrays(A, m, B + j, n - j, k - j);         else return a;     }     double findMedianSortedArrays_3(int A[], int m, int B[], int n) {         return findMedian(A, m, B, n, max(0, (m + n) / 2 - n), min(m - 1, (m + n) / 2));     }     double findMedian(int A[], int m, int B[], int n, int l, int r) {         if (l > r)             return findMedian(B, n, A, m, max(0, (m + n) / 2 - m), min(n, (m + n) / 2));         int i = (l + r) / 2;         int j = (m + n) / 2 - i;         int Ai_1 = (i == 0) ? INT_MIN : A[i-1];         int Bj_1 = (j == 0) ? INT_MIN : B[j-1];         int Ai = (i == m) ? INT_MAX : A[i];         int Bj = (j == n) ? INT_MAX : B[j];         if (Ai < Bj_1) return findMedian(A, m, B, n, i+1, r);         if (Ai > Bj) return findMedian(A, m, B, n, l, i-1);         if ((m + n) % 2 == 1) return Ai;         else return (Ai + max(Ai_1, Bj_1)) / 2.0;     } };

[webdriver]

Problem Name: Merge Intervals
Description:
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].