120. Triangle

Difficulty: Medium

Frequency: N/A

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> minLen(triangle.back());
        for (int layer = n - 2; layer >= 0; layer--) {
            for (int i = 0; i <= layer; i++) {
                minLen[i] = min(minLen[i], minLen[i + 1]) + triangle[layer][i];
            }
        }
        return minLen[0];
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:


Things to learn:

 
 
 
 
Advertisements

121. Best Time to Buy and Sell Stock

Difficulty: Medium

Frequency: N/A

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxPro = 0;
        int minPrice = INT_MAX;
        for (int i = 0; i < prices.size(); i++) {
            minPrice = min(minPrice, prices[i]);
            maxPro = max(maxPro, prices[i] - minPrice);
        }
        return maxPro;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:


Things to learn:

 
 
 
 

095. Unique Binary Search Trees II

Difficulty: Medium

Frequency: N/A

 

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
/**
 * 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<TreeNode*> generateTrees(int n) {
        if (!n) return vector<TreeNode*>();
        return genBST(1, n);
    }
    vector<TreeNode*> genBST(int min, int max) {
        vector<TreeNode*> results;
        if (min > max) {
            results.push_back(NULL);
            return results;
        }
        for (int i = min; i <= max; i++) {
            vector<TreeNode*> left = genBST(min, i - 1);
            vector<TreeNode*> right = genBST(i + 1, max);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode *root = new TreeNode(i);
                    root->left = left[j];
                    root->right = right[k];
                    results.push_back(root);
                }
            }
        }
        return results;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:


Things to learn:

 
 
 
 

096. Unique Binary Search Trees

Difficulty: Medium

Frequency: N/A

 

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Test Cases:


Solution 1:

Data structure:
BST
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int numTrees(int n) {
        vector<int> types(n + 1, 0);
        types[0] = types[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                types[i] += types[j - 1] * types[i - j];
            }
        }
        return types[n];
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:


Things to learn: