[C++] Data structures and their common operators

	vector	stack	queue	Deque (Double ended queue)	Priority_queue
Access	x=v.front() x=v.back()	x=s.top()	x=q.front()	x=dq.front() x=dq.back()	x=pq.top()
Add	v.insert(itr, x) v.push_back(x) v.emplace(itr, x) v.emplace_back(x)	s.emplace(x) s.push(x)	q.emplace(x) q.push(x)	dq.emplace(itr, x) dq.emplace_back(x) dq.emplace_front(x) dq.push_back(x) dq.push_front(x) dq.insert(itr,x)	pq.emplace(x) pq.push(x)
Remove	v.clear() v.erase(itr) v.pop_back()	s.pop()	q.pop()	dq.clear() dq.erase(itr) dq.pop_back() dq.pop_front()	pq.pop()
Check empty	v.empty()	s.empty()	q.empty()	dq.empty()	pq.empty()
Check size	x=v.size()	x=s.size()	x=q.size()	dq.size()	pq.size()

Vector vs. Deque:

Both vector and deque provide a very similar interface, but internally they work in quite different ways: vector uses a single array that needs occasionally re-allocation for growth; deque has its elements scattered in different chunk of storage, with the container keeping the necessary information for direct accesses to any element in constant time - through iterators.

[LeetCode] Maximum Subarray

Problem Statement (link):

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:
Suppose we scan from left to right, each element could either be counted in the max-sum subarray, or not. If we use an array to store this information, we probably could solve the problem in O(n) time.

Thus, the idea is to use DP to solve the problem. Specifically, the DP array stores the maximum sum we have so far if we count the current element in. In addition, we use an integer to store the maximum sum we have so far.

Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n==0) return 0;
        int maxSum=INT_MIN; // max sum so far
        vector<int> dp(n+1);  // dp[i+1]: the maxSum of subarray which ends with A[i];
        dp[0]=0;
        for (int i=0; i<n; i++) {
            if (dp[i]<0) dp[i+1]=A[i];
            else dp[i+1]=dp[i]+A[i];
            maxSum=max(maxSum, dp[i+1]);
        }
        return maxSum;
    }
};

[LeetCode] Generate Parentheses

Problem Statement (link):

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
The problem asks for all combinations, this usually indicates it's a DFS problem.

In the recursion function, if we've used up all left and right parentheses, we push the formed string into result vector. Otherwise, we can add either left parentheses or right parentheses. The code for this problem is shown in Sol 1 below.

The extended version of this problem is that instead of only having parentheses, we are given n1 parentheses pairs, n2 bracket pairs, and n3 curly parentheses, and we are asked for the same thing - all combinations.

The idea is pretty similar to the simple version. The only difference is that we can do one of the following:
1) add left parentheses '(';
2) add left bracket '[';
3) add left curly parentheses '{';
4) add the right part, depending on the left situation, we choose either ')', ']', or '}'.

The code is shown in Sol 2 below.

Code:
Sol 1:

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n<1) return res;
        dfs(res, "", "", n);
        return res;
    }
    void dfs(vector<string> &res, string left, string tmp, int n) {
        if (left.size()==0 && n==0) {
            res.push_back(tmp);
            return;
        }
        if (n>0) {
            dfs(res, "("+left, tmp+"(", n-1);
        }
        if (left.size()>0) {
            dfs(res, left.substr(1), tmp+")", n);
        }
    }
};

Sol 2:

string rightPart(string left) {
    if (left=="(") return ")";
    else if (left=="[") return "]";
    else return "}";
}

void dfsParen(vector<string> &res, string leftStack, string str, int n1, int n2, int n3) {
    if (leftStack.empty() && n1==0 && n2==0 && n3==0) {
        res.push_back(str);
        return;
    }

    // add left parentheses
    if (n1>0) {
        dfsParen(res, "("+leftStack, str+"(", n1-1, n2, n3);
    }
    if (n2>0) {
        dfsParen(res, "["+leftStack, str+"[", n1, n2-1, n3);
    }
    if (n3>0) {
        dfsParen(res, "{"+leftStack, str+"{", n1, n2, n3-1);
    }

    // add right parentheses
    if (!leftStack.empty()) {
        dfsParen(res, leftStack.substr(1), str+rightPart(leftStack.substr(0,1)), n1, n2, n3);
    }
}

vector<string> getParen(int n1, int n2, int n3) {
    vector<string> res;
    if (n1==0 && n2==0 && n3==0) return res;
    string leftStack;
    string str="";
    dfsParen(res, leftStack, str, n1, n2, n3);
    return res;
}

[LeetCode] Container with Most Water

Problem Statement (link):

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Analysis:
The naive O(n^2) brute force is apparently not optimal.

An O(n) algorithm goes like this:
- Start from the very beginning and end of the vector, we calculate the volume hold by these two boards;
- Compare the height of current boards, advance the shorter board;

To justify this algorithm, think about the following case:
Suppose we are currently at left index i, right index j. If height i is smaller height j, then with any other height jj (i<jj<j), the area(i, jj) < area(i, j). The reason is that the container area is determined by the shorter height of the two boards, i.e., board i. In other words, the maximum area that determined by board i is already found.

Code:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int left=0, right=height.size()-1;
        int vol=min(height[left], height[right]) * (right-left);
        while (left<right) {
            if (height[left]<height[right]) left++;
            else right--;
            vol=max(vol, min(height[left], height[right]) * (right-left));
        }
        return vol;
    }
};

[LeetCode] String to Integer (atoi)

Problem Statement (link):

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:
The logic/algorithm is pretty simple, the tricky part is about all the corner cases..:
1) "+-2" --> "0", multiple sign appeared;
2) Once you met a char, you should return the current integer by discarding all the rest of the string. i.e., "-23a56" --> "-23" rather than "-2356";
3) Overflow.

O(n) time complexity is required as we need to scan all the chars.

Code:

class Solution {
public:
    int atoi(const char *str) {
        while(*str==' ') str++;
        int sign=1;
        if (*str=='-' || *str=='+') {
            if ((*str=='+'&&*(str+1)=='-')||(*str=='-'&&*(str+1)=='+'))
                return 0;
            sign=*str=='-'?-1:1; str++;
        }

        int res=0;
        while(*str) {
            if (!isDigit(*str)) break;
            res=10*res+(*str-'0');
            str++;
            // overflow
            if ((res>=214748364 && *str>='8' && *str<='9') || res>=999999999 && isDigit(*str))
                return sign==1?INT_MAX:INT_MIN;
        }
        return res*sign;
    }
    bool isDigit(const char c) {
        int d=c-'0';
        if (d>=0 && d<=9)
            return true;
        return false;
    }
};

[LeetCode] Reverse Integer

Problem Statement (link):

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Analysis:
There are several ways to approach this problem, we could convert the integer to string, inverse the string, then convert the string to int. Or, we could read each digit into a stack, pop out each digit in sequence and form a new integer.

Here, I simple extract each digit from the end of int x by taking the reminder. The time complexity is O(n) where n is the length of the integer.

Code:

class Solution {
public:
    int reverse(int x) {
        int sign=x<0?-1:1;
        x=abs(x);
        int rev=0;
        while (x>0) {
            rev=rev*10+x%10;
            x/=10;
            if (rev<0) return 0; // overflow
        }
        return rev*sign;
    }
};

[LeetCode] Interleaving String

Problem Statement (link):

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.

Analysis:
It reminds me of the Edit Distance problem. As we could break this problem down to some smaller problems, i.e., consider if s1[:i-1] and s2[:j-1] could build s[:i+j-1], we could use DP.

We could construct a matrix dp[s1.length()+1][s2.length()+1], remember in DP we usually leave one more extra space for initial condition, which is both s1 and s2 are blank string in this problem. Each entry dp[i][j] indicates whether s1[i-1] and s2[j-1] could build  s[:i+j-1].

Now consider the transfer function. dp[i][j] is true if either of the following cases is true:
1) current char in s1 is same as current char in s3, and previous dp entry in the same row is true
i.e., s1[i-1]==s3[i+j-1] && dp[i-1][j]) == true
2) current char in s2 is same as current char in s3, and previous dp entry in the same col is true
i.e., s2[j-1]==s3[i+j-1] && dp[i][j-1] == true

Our final answer is in the last entry of the DP matrix.

The time complexity of the algorithm is O(len1 * len2), where the two lengths are the lengths of s1 and s2, respectively.

Code:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1=s1.length(), len2=s2.length();
        if (len1+len2!=s3.length()) return false;
        vector<vector<bool>> dp(len1+1, vector<bool> (len2+1, false));

        // initial
        dp[0][0]=true;
        for (int i=1; i<=len1; i++)
            if (s1[i-1]==s3[i-1] && dp[i-1][0]) dp[i][0]=true;
        for (int j=1; j<=len2; j++)
            if (s2[j-1]==s3[j-1] && dp[0][j-1]) dp[0][j]=true;

        // update dp
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                dp[i][j]=(s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};