LIKE CODING

Tuesday, September 15, 2015

LeetCode [282] Expression Add Operators

282. Expression Add Operators

Hard

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

Constraints:

0 <= num.length <= 10
num only contain digits.

typedef long long ll;
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> ret;
        dfs(num, "", 0, 0, 0, ret, target);
        return ret;
    }

    void dfs(string num, string exp, int pos, ll curVal, ll preVal, vector<string>& ret, ll target)
    {
        if(pos == num.size() && curVal==target)
        {
            ret.push_back(exp);
        }
        else if(pos<num.size())
        {
            for(int i=pos; i<num.size(); ++i)
            {
                string v = num.substr(pos, i-pos+1);
                if(v.size()>1 && v[0]=='0') break;
                if(pos==0)
                {
                    dfs(num, v, i+1, stoll(v), stoll(v), ret, target);
                }
                else
                {
                    dfs(num, exp+"+"+v, i+1, curVal+stoll(v), stoll(v), ret, target);
                    dfs(num, exp+"-"+v, i+1, curVal-stoll(v), -stoll(v), ret, target);
                    dfs(num, exp+"*"+v, i+1, curVal-preVal+preVal*stoll(v), preVal*stoll(v), ret, target);
                }
                
            }
        }
    }
};

Sunday, September 13, 2015

LeetCode [281] Zigzag Iterator

Ref
[1] https://leetcode.com/problems/zigzag-iterator/
[2] http://www.fgdsb.com/2015/01/30/zigzag-iterator/

Monday, September 7, 2015

LeetCode [278] First Bad Version

278. First Bad Version

Easy

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l<=r){
            int mid = l+(r-l)/2;
            boolean bad = isBadVersion(mid);
            if(bad==true && mid==l) return mid;
            else if(bad==true) r = mid;
            else if(bad==false && mid==r) return -1;
            else l = mid+1;
        }
        return -1;
    }
}

Saturday, September 5, 2015

LeetCode [277] Find the Celebrity

=============

Line 8-13 computes c, which is the only possible celebrity
Proof:

if c=0, c does not know any one in [1...n-1]. [c+1...n-1] are not celebrities.
if c=1, 0 knows 1. Thus 0 is not celebrity and [c+1...n-1] are not celebrities.
if c=2, there are 2 cases. In both cases 0 and 1 are not celebrities. Also, [c+1...n-1] are not celebrities.

0 knows 1 and 1 knows 2.
0 does not know 1 but 0 knows 2.

if c=i, [0, i-1] and [i+1, n-1] are not celebrities.

Ref
[1] https://leetcode.com/problems/find-the-celebrity/
[2] http://www.geeksforgeeks.org/the-celebrity-problem/

Friday, September 4, 2015

LeetCode [276] Paint Fence

Note

dp[i]: number of ways to paint i+1 fences
dp[i] = dp[i-1]*k - dup
dup denotes the number of ways to paint i fences while the (i-2)-th and (i-1)-th fences have the same color.
Thus, dup is also the number of ways to paint i+1 fences while the (i-2)-th, (i-1)-th and i-th fences have the same color.
Therefore, dup should be deducted from dp[i-1]*k when computing dp[i]
When computing dp[i], dup = dp[i-2] - dp[i-3] + dp[i-4] -,...., +/- dp[0].

For 5 fences with 2 colors,

there are two ways to paint the first fence dp[0] = 2

0 1 2 3 4 5

there are four ways to paint the first two fences dp[1] = 4

0 1 2 3 4 5

1 1

1 2

2 1

2 2

computing dp[2] = dp[1]*2-dup = 8 - dup. In this case, dup = dp[2-2] = dp[0] = 2. Thus, dp[2] = 6.

0 1 2 3 4 5

~~1 1 1~~

1 1 2

1 2 1

1 2 2

2 1 1

2 1 2

2 2 1

~~2 2 2~~

dp[3] = dp[2]*2-dup. dup = dp[1] - dp[0] = 4-2 =2. Thus, dp[3] = 12-2 = 10;
*when computing dp[2], dp[0] illegal paintings have already been deducted. Thus, dp[0] should be deducted from dp[1] when computing the illegal paintings for dp[3].
0 1 2 3 4 5

1 1 2 1
1 1 2 2

1 2 1 1
1 2 1 2

1 2 2 1
~~1 2 2 2~~

~~2 1 1 1~~
2 1 1 2

2 1 2 1
2 1 2 2

2 2 1 1
2 2 1 2

dp[4] = dp[3]*k - dp[2] + dp[1] - dp[0] = 20 - 6 + 4 - 2 = 16

0 1 2 3 4 5

1 1 2 1 1
1 1 2 1 2
1 1 2 2 1
~~1 1 2 2 2~~

~~1 2 1 1 1~~
1 2 1 1 2
1 2 1 2 1
1 2 1 2 2

1 2 2 1 1
1 2 2 1 2

2 1 1 2 1
2 1 1 2 2

2 1 2 1 1
2 1 2 1 2
2 1 2 2 1
~~2 1 2 2 2~~

~~2 2 1 1 1~~
2 2 1 1 2
2 2 1 2 1
2 2 1 2 2

Ref
[1] https://leetcode.com/problems/paint-fence/
OJ

LeetCode [275] H-Index II

Ref
[1] https://leetcode.com/submissions/detail/38811322/
OJ

Thursday, September 3, 2015

LeetCode [274] H-Index

274. H-Index

Medium

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

//C++: 4ms
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>());
        int n = citations.size();
        int i = 0;
        for(; i<n; ++i){
            if(citations[i]<i+1) break;
        }
        return i;
    }
};

class Solution {
public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n+1];
    for(int c : citations) {
        if(c >= n) {
            buckets[n]++;
        } else {
            buckets[c]++;
        }
    }
    int count = 0;
    for(int i = n; i >= 0; i--) {
        count += buckets[i];
        if(count >= i) {
            return i;
        }
    }
    return 0;
}
}