[LeetCode] Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

class Solution {
public:
    int numSquares(int n) {
        vector<int> DP(n+1,INT_MAX);
        DP[0] = 0;
        for(int i =1;i<=n;i++)
        {
            for(int j=1;j*j<=i;j++)
            {
                DP[i] = min(DP[i], DP[i-j*j]+1);
            }
        }
        return DP[n];
    }
};

[LeetCode] Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

DP: If matrix[i][j] == 1, D[i][j] = min(D[i][j-1], D[i-1][j], D[i-1][j-1]) + 1;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(0 == m) return 0;
        int n = matrix[0].size();
        
        vector<vector<int>> D(m, vector<int>(n, 0));
        int res = 0;
        
        for(int i=0;i<m;i++)
        {
            D[i][0] = matrix[i][0] - '0';
            if(D[i][0] == 1) res = 1;
        }
        
        for(int i=0;i<n;i++)
        {
            D[0][i] = matrix[0][i] - '0';
            if(D[0][i] == 1) res = 1;
        }
        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]-'0' == 1)
                {
                    D[i][j] = min(D[i-1][j-1], 
                        min(D[i-1][j], D[i][j-1])) + 1;
                    res = max(D[i][j], res);
                }
            }
        }
        return res*res;
    }
};

[LintCode] Continuous Subarray Sum

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

Example

Give [-3, 1, 3, -3, 4], return [1,4].

class Solution {
public:
    vector<int> continuousSubarraySum(vector<int>& A) {
        int len = A.size();
        vector<int> res(2, 0);
        if(0 == len) return res;
        int start = 0,end = 0, lastMax = A[0];
        int maxV = lastMax;
        for(int i=1;i<len;i++)
        {
            if(lastMax < 0)
            {
                start = i;
                lastMax = A[i];
            }
            else lastMax = lastMax+A[i];
            end = i;
            if(lastMax > maxV)
            {
                maxV = lastMax;
                res[0] = start;
                res[1] = end;
            }
        }
        return res;
    }
};

[LintCode] Coins in a Line III

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

Example

Given array A = [3,2,2], return true.

Given array A = [1,2,4], return true.

Given array A = [1,20,4], return false.

Challenge

Follow Up Question:

If n is even. Is there any hacky algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?

This is similar to Coins in a Line II. The only difference is that it's in a 2-d scope.

Recursive: Complexity is power(2,n).

    int firstWillWin(vector<int> &values, int s, int e) {
        if(s == e) return values[s];
        return max( values[s] - firstWillWin(values, s+1, e),
                   values[e] - firstWillWin(values, s, e-1) );
        
    }
    bool firstWillWin(vector<int> &values) {
        int len = values.size();
        if(len<=2) return true;
        return firstWillWin(values, 0, len-1) > 0;
    }

DP:

    bool firstWillWin(vector<int> &values) {
        int len = values.size();
        if(len<=2) return true;
        vector<vector<int>> f(len, vector<int>(len,0));        
        for(int i=0;i<len;i++) f[i][i] = values[i];
        for(int i=len-2;i>=0;i--)
        {
            for(int j=i+1;j<len;j++)
            {
                f[i][j] = max(values[i] - f[i+1][j], values[j] - f[i][j-1]);
            }
        }
        return f[0][len-1] > 0;
    }

[LintCode] Coins in a Line II

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

Analysis:
From any index of the array, we should know:

1) the maximum value the first player will get if moving from it.
2) whether it should cover the next index in the move.

With the info, we can construct a DP solution.

class Solution {
public:
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int len = values.size();
        if(len<=2) return true;
        vector<int> maxAGets(len+2, 0),alsoGetNext(len, true);

        maxAGets[len-1] = values[len-1];
        maxAGets[len-2] = values[len-1] + values[len-2];
        
        for(int i=len-3;i>=0;i--)
        {
            //only take i
            int notTakeNext;
            if(alsoGetNext[i+1]) notTakeNext=values[i]+maxAGets[i+3];
            else notTakeNext=values[i]+maxAGets[i+2];
            
            //take i and i+1
            int takeNext, t=values[i]+values[i+1];
            if(alsoGetNext[i+2]) takeNext= t+maxAGets[i+4];
            else takeNext= t+maxAGets[i+3];
            
            maxAGets[i] = max(takeNext, notTakeNext);
            if(takeNext<notTakeNext) alsoGetNext[i] = false;
        }
        if(alsoGetNext[0]) return maxAGets[0] > maxAGets[2];
        return maxAGets[0] > maxAGets[1];
    }
};

Or, a more decent solution:

For any index i, we can know the gap between the two players if the first player moves from it. Suppose the first player moves from i and it wins f[i](the gap). If the second player moves from it, we should consider f[i] as a loss of the first player.

class Solution {
public:
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int size = values.size();
        if(2 >= size) return true;
        vector<int> f(size, 0);
        f[size-1] = values[size-1];
        f[size-2] = values[size-2]+values[size-1];
        
        for(int i = size-3; i >=0; --i)
        {
            f[i] = max(values[i]-f[i+1], values[i]+values[i+1]-f[i+2]);
        }
        return f[0] > 0;
    }
};

[LeetCode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Analysis:

Use DP to indicate whether some part of the string is composed by the words in the dictionary.

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) 
    {
        int len = s.length();
        bool D[len+1] = {false};

        D[len] = true;
        for(int i=len-1;i>=0;--i)
        {
            for(int k=i+1;k<=len;k++)
            {
                D[i] = D[k] && dict.find(s.substr(i, k-i)) != dict.end();
                if(D[i]) break;
            }
        }
        
        return D[0];
    }
};

[LeetCode] Best Time to Buy and Sell Stock IV

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

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

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

This solution is from here, with a small bug fix

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
    
        int len = prices.size();
        if (len < 2) return 0;
    
        int maxProfit = 0;
    
        //simple case where we just need to find the maximum climb in prices among all the pairs
        if (k >= len / 2)
        {
            for (int i = 1; i < len; i++)
            {
                maxProfit += max(0, prices[i] - prices[i-1]);
            }
            return maxProfit;
        }
        //Dynamic Programming case where we need to maximize our profit
    
        //keeps track of maximum profit so far at each index. On any index 'i' the value is max profit that we gained
        //by dealing stock that came before 'i'. After any 'm' iterations, this array holds max profit on index 'i' if we had
        //only 'i' stock values and 'm' possible deals.
        vector<int> maxProfitSoFar(len+1, 0); 
    
        //calculates the difference between the very current and previous stock price
        int currentProfit = 0;
    
        //keeps track of our current balance.
        int runningProfit = 0;
    
        //it backs up the value of max profit after doing 'm-1' deals until index 'i' before updating it to 
        //the value of doing 'm' deals until index i.
        int prevMaxProfit = 0;
    
        //k iterations for k deals - after each round mapxProfitSoFar holds the max profit for 'j' possible deals
        for (int j = 0; j < k; j++)
        {
            //resetting our balance for new iteration
            runningProfit = maxProfitSoFar[j];
    
            //initializing with the last max profit we are going to start the next iteration with indexes after this.
            prevMaxProfit = maxProfitSoFar[j]; 
    
            //we don't need to start from the beginning eveytime since we would face "the simple case" (above) and the profit 
            //is already calculated. It means that number of deals is greater than the 'len'
            for (int i = j+1; i < len; i++)
            {
                //what is the immediate different of the current two prices.
                currentProfit = prices[i] - prices[i-1];
    
                //is it better to do this deal? or should we stick to what we did with one less deal and see what future holds!
                runningProfit = max(runningProfit + currentProfit, prevMaxProfit); 
    
                //backing up max value with one less deal to compare in the next round
                prevMaxProfit = maxProfitSoFar[i]; 
    
                //updating max profit so far by asking if we gained more profit with last deal or we didn't gain anything more
                maxProfitSoFar[i] = max(runningProfit, maxProfitSoFar[i-1]); 
            }
        }
    
        //well the last item in the MaxProfitSoFar after k iterations holds max profit of 'k' deals of 'len' items.
        return maxProfitSoFar[len-1];
    }
};

[LintCode] Backpack II

Given n items with size A[i] and value V[i], and a backpack with size m. What's the maximum value can you put into the backpack?

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

Note

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m

Update:

We can save the possible size, while the max value of an impossible size should be the max of values of possible sizes.

Analysis: just like Backpack 1, we just need record the weights for possible sizes.

class Solution {
public:
    int backPackII(int m, vector<int> A, vector<int> V) {
        int len = A.size();
        int maxV = 0;
        vector<int> weight(m+1,0);
        for (int i=0;i<len;i++)
        {
            for (int j=m;j>=A[i];j--)
            {
                weight[j] = max(V[i]+weight[j-A[i]], weight[j]);
                maxV = max(maxV, weight[j]);
            }
        }
        return weight[m];
    }
};

[LintCode] Longest Common Subsequence

Given two strings, find the longest comment subsequence (LCS).

Your code should return the length of LCS.

Example

For "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1

For "ABCD" and "EACB", the LCS is "AC", return 2

Clarification

What's the definition of Longest Common Subsequence?

    * The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.

    * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        // write your code here
        int m = A.length(), n = B.length();
        vector<vector<int>> D(m+1, vector<int>(n+1,0));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(A[i-1] == B[j-1])
                {
                    D[i][j] = D[i-1][j-1] + 1;
                }
                else
                {
                    D[i][j] = max(D[i][j-1], D[i-1][j]);
                }
            }
        }
        return D[m][n];
    }
};

[LintCode] k Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

This problem is similar with backpack, but it has a constraint of k elements.

class Solution {
public:
    int kSum(vector<int> A, int k, int target) 
    {
        vector<vector<int>> rec(target+1, vector<int>(k, 0));
        for(int i=0;i<A.size();i++)
        {
            for(int j=target; j>=A[i]; j--)
            {
                if(A[i] == j) rec[j][0]++;
                for(int v = 0; v < min(k-1,i); v++)
                {
                    rec[j][v+1] += rec[j-A[i]][v];
                }
            }
        }
        return rec[target][k-1];
    }
};

[LintCode] Product of Array Exclude Itself

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate BWITHOUT divide operation.

Example

For A=[1, 2, 3], return [6, 3, 2].

class Solution {
public:
    vector<long long> productExcludeItself(vector<int> &nums) 
    {
        int n = nums.size();
        vector<long long> output(n, 1);
        
        long long left =1, right = 1;
        for(int i = 0; i < n; i++) {
            output[i] *= left; 
            left *= nums[i];
            
            output[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        return output;
    }
};

[LintCode] Backpack

Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? 

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Analysis:
We can say all the possible sums that are smaller than m. The biggest one is the result.

class Solution {
public:
    int backPack(int m, vector<int> A) {
        // write your code here
        int len = A.size();
        vector<bool> size(m+1,false);
        size[0] = true;
        
        for (int i=0;i<len;i++)
        {
            for (int j=m;j>=A[i];j--)
            {
                if (size[j-A[i]])
                    size[j] = true;
            }
        }
        int i = m;
        while(!size[i]) i--;
        return i;
    }
};

[LintCode] Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station's index is 2.

Analysis: This problem can be transformed to maximum subarray. If there is a station from where we can go through all the stations, and given the solution is unique, it must be the starting of the maximum subarray.

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        if(0 == n) return -1;
        int lastMax = gas[0]-cost[0];
        int totalMax = lastMax;
        int start = 0, maxStart = 0;
        for(int i=1;i<2*n-1;i++)
        {
            int j = i % n;
            int suf = gas[j] - cost[j];
            if(lastMax < 0)
            {
                if(i>=n) break;
                lastMax = suf;
                start = i;
            }
            else lastMax += suf;
            if(lastMax > totalMax)
            {
                totalMax = lastMax;
                maxStart = start;
            }
        }
        int sum = 0;
        for(int i=maxStart;i<n+maxStart;i++)
        {
            int j = i%n;
            sum += gas[j]-cost[j];
            if(sum < 0) return -1;
        }
        return maxStart;
    }
};

[LeetCode] Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Analysis:

Similar with Maximum subarray, we need to maintain an array for the maximum product that ends at index i. To achieve that, we need to know the minimum product that ends at i, because some elements might be negative.

If num[i+1] is negative, Max[i+1] = max(Min[i]*num[i+1], num[i+1]),

else Max[i+1] = max(Max[i]*num[i+1], num[i+1]);

class Solution {
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int lastMax = nums[0], lastMin = nums[0];
        int res = lastMax;
        for(int i=1;i<len;i++)
        {
            if(nums[i] >=0 )
            {
                lastMax = max(lastMax*nums[i], nums[i]);
                lastMin = min(lastMin*nums[i], nums[i]);
            }
            else
            {
                int t = max(lastMin*nums[i], nums[i]);
                lastMin = min(lastMax*nums[i], nums[i]);
                lastMax = t;
            }
            res = max(res, lastMax);
        }
        return res;
    }
};

[LeetCode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Analysis: This is typical DP problem. Let D[i] be the maximum subarray that ends at index i. Then, D[i+1] = max(D[i] + nums[i], nums[i]). Max(D[i]) will be the result.

    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;

        vector<int> rec(len,0);

        rec[0] = nums[0];
        for(int i=1;i<len;i++)
        {
            rec[i] = max(rec[i-1] + nums[i], nums[i]);
        }        
        return *max_element(rec.begin(), rec.end());
    }

Look at the code. Actually, the max subarray can be obtained from the adjacent elements

    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int maxSub = nums[0];
        int res = maxSub;
        for(int i=1;i<len;i++)
        {
            maxSub = max(nums[i] + maxSub, nums[i]);
            res = max(maxSub, res);
        }
        return res;
    }

[LeetCode] Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution {
public:
    int climbStairs(int n) {
        int n_1 = 1, n_2 = 1;
        int res = 1;
        for(int i=2;i<=n;i++)
        {
            res = n_1 + n_2;
            n_2 = n_1;
            n_1 = res;
        }
        return res;
    }
};

[LeetCode] Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        if(0 == m) return 0;
        int n = obstacleGrid[0].size();
        if(0 == n) return 0;
        int paths[m][n];
        paths[0][0] = obstacleGrid[0][0] == 1?0:1;
        for(int i=1;i<m;i++) 
        {
            if(obstacleGrid[i][0] == 1)paths[i][0] = 0;
            else paths[i][0] = paths[i-1][0];
        }
        for(int i=1;i<n;i++) 
        {
            if(obstacleGrid[0][i] == 1)paths[0][i] = 0;
            else paths[0][i] = paths[0][i-1];
        }        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(obstacleGrid[i][j] == 1) paths[i][j]=0;
                else paths[i][j] = 
                        paths[i-1][j] + paths[i][j-1];
            }
        }
        return paths[m-1][n-1];
    }
};

[LeetCode] Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        int paths[m][n];
        for(int i=0;i<m;i++) paths[i][0] = 1;
        for(int j=0;j<n;j++) paths[0][j] = 1; 
        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                paths[i][j] = 
                paths[i-1][j] + paths[i][j-1];
            }
        }
        return paths[m-1][n-1];
    }
}

[LeetCode] 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) {
        int len1 = word1.length();
        int len2 = word2.length();
        int dp[len1+1][len2+1];
        for(int i=0;i<=len1;i++)
        {
            dp[i][0] = i;
        }
        for(int i=1;i<=len2;i++)
        {
            dp[0][i] = i;
        }
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(word1[i-1] == word2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    int c = min(dp[i-1][j] + 1, dp[i][j-1]+1);
                    dp[i][j] = min(c, dp[i-1][j-1]+1);
                }
            }
        }
        return dp[len1][len2];
    }
};

[LeetCode] House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(0 == size) return 0;
        int next1Max = nums[size-1];
        int next2Max = 0;
        for(int i=size-2; i>=0; i--)
        {
            int cur = max(next1Max, nums[i] + next2Max);
            next2Max = next1Max;
            next1Max = cur;
        }
        return next1Max;
    }
};