CTRL+A, CTRL+C, CTRL+V

Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

I do believe there should be an O(n) solution, but sort of tricky. The O(n^2) solution is quite straightforward in DP problems.

public static int maxChar(int n) {
 int[] dp = new int[n];
 for (int i = 0; i < n; ++i) {
  dp[i] = i + 1;    // type A
 }
 for (int i = 0; i < n; ++i) {
  for (int j = i + 4; j < n; ++j) {
   dp[j] = Math.max(dp[j], dp[i] * (j - i - 3));    // using Ctrl + V
  }
 }
 return dp[n - 1];
}

Interleaving String

Interleaving StringAug 31 '12

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

dp[i][j] == true means the substring of s3 from start to 'i + j'th char is the interleaved string of s2 till 'i'th char and s1 till 'j'th char

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if (s1.empty()) return s2 == s3;
        else if (s2.empty()) return s1 == s3;
        else if (s3.empty()) return s1.empty() && s2.empty();
        else if (s1.size() + s2.size() != s3.size()) return false;
        
        int lengthS1 = s1.size() + 1, lengthS2 = s2.size() + 1;
        vector<vector<bool>> dp(lengthS2, vector<bool>(lengthS1, false));
        dp[0][0] = true;
        
        for (int i = 1; i < lengthS2; ++i) {
            dp[i][0] = s2[i - 1] == s3[i - 1] ? dp[i - 1][0] : false;
        }
        
        for (int j = 1; j < lengthS1; ++j) {
            dp[0][j] = s1[j - 1] == s3[j - 1] ? dp[0][j - 1] : false;
        }
        
        for (int i = 1; i < lengthS2; ++i) {
            for (int j = 1; j < lengthS1; ++j) {
                if (s1[j - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
                if (s2[i - 1] == s3[i + j - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
        
        return dp[lengthS2 - 1][lengthS1 - 1];
    }
};

Triangle

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.

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = triangle.size();
        if (!n) return 0;
        
        int *sum = new int[n];
        sum[0] = triangle[0][0];
        
        for (int i = 1; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (j != 0 && j != i) {
                    sum[j] = min(sum[j - 1], sum[j]) + triangle[i][j];
                }
                else if (j == i) {
                    sum[j] = sum[j - 1] + triangle[i][j];
                }
                else {
                    sum[j] = sum[j] + triangle[i][j];
                }
            }
        }
        
        int m = sum[0];
        for (int i = 1; i < n; ++i) if (sum[i] < m) m = sum[i];
        delete[] sum;
        return m;
    }
};

Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

Idea: use a hashmap to store the previous computed results

public class Solution {
    public String countAndSay(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (n == 0) return "";
        String str = "1";
        HashMap map = new HashMap();
        for (int i = 1; i < n; ++i) {
            int start = 0;
            StringBuffer newstr = new StringBuffer();
            for (int j = 0; j < str.length(); ++j) {
                if (j != str.length() - 1 && str.charAt(j) == str.charAt(j+1)) {
                    continue;
                }
                String stored = map.get(str.substring(start, j+1));
                if (stored == null) {
                    String strappend = String.valueOf(j - start + 1) + str.substring(start, start + 1);
                    map.put(str.substring(start, j+1), strappend);
                    newstr.append(strappend);
                }
                else {
                    newstr.append(stored);
                }
                start = j + 1;
            }
            str = newstr.toString();
        }
        return str;
    }
}

Edit Distance

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

class Solution {
public:
    int minDistance(string word1, string word2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n1 = word1.size();
        int n2 = word2.size();
        
        if (n1 == 0) {
            return n2;
        }
        else if (n2 == 0) {
            return n1;
        }
        
        vector >dp;
        dp.resize(n1 + 1);
        for (int i = 0; i <= n1; ++i) {
            dp[i].resize(n2 + 1);
        }
        
        for (int i = 0; i <= n1; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n2; ++j) {
            dp[0][j] = j;
        }
        
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i-1][j-1];
                }
                else {
                    dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1,
                        dp[i-1][j-1] + 1);
                }
            }
        }
        
        return dp[n1][n2];
    }
};

Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

This could be solved using DP. For each node, the max sum path for its parent could be from its left (1) or right subtree (2) through itself or only itself (3) to its parent node (_maxSubPathSum). For the global max sum, it could be the sum of a node's left subtree through the node itself to its right subtree(4), plus the above 3 cases.
Time Complexity: O(n)

/**
 * 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 maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root) return 0;
        
        int m = root->val;
        int localMax = _max(root, m);
        return localMax > m ? localMax : m;
    }
    
    int _max(TreeNode *root, int &m) {
        if (!root) return 0;
        int leftMax = _max(root->left, m);
        int rightMax = _max(root->right, m);
        
        int maxSum = max(root->val, max(root->val + leftMax, root->val + rightMax));
        m = max(max(m, maxSum), root->val + leftMax + rightMax);
        
        return maxSum; 
            
    }
};

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

» Solve this problem

Idea: The best choice could be the max of: do nothing / one more transaction based on the previous result on day j where j < i and at most one transaction was made before day j

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = prices.size();
        if (n <= 1) return 0;
        
        int minp = prices[0];
        int *dp = new int[n];
        int *dp1 = new int[n]; //max profit with one or less transaction
        
        memset(dp, 0, n*sizeof(int));
        memset(dp1, 0, n*sizeof(int));
        
        for (int i = 1; i < n; i++) {
            if (prices[i] < minp) minp = prices[i];
            dp1[i] = max(dp1[i-1], prices[i] - minp);
            if (prices[i] <= prices[i-1]) {
                dp[i] = dp[i-1];
                continue;
            }
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], dp1[j] + prices[i] - prices[j]);
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        return dp[n-1];
    }
};

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II

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

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

» Solve this problem

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = prices.size();
        if (n <= 1) return 0;
        int *dp = new int[n];
        memset(dp, 0, n*sizeof(int));
        
        for (int i = 1; i < n; ++i) {
            if (prices[i] <= prices[i-1]) {
                dp[i] = dp[i - 1];
                continue;
            }
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], dp[j] + prices[i] - prices[j]);
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        
        return dp[n - 1];
    }
};