Coins in a Line

http://leetcode.com/2011/02/coins-in-line.html

Fraction to Recurring Decimal

Q:

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

T:
Keep a remainder. Multiply it by 10 each time we append a new digit to the result, and append the quotient as the new digit, and assign remainder as the mod of the remainder to the denominator. We need a hashmap to store the positions of each remainder. When we see a remainder again, we know the digits will cycle.

A:

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        int sign = 0;
        if((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            sign = 1;
        }
        int64_t n = numerator;
        int64_t d = denominator;
        n = abs(n);
        d = abs(d);
        string ret = "";
        if(sign) {
            ret += "-";
        }
        ret += to_string(n/d);
        if(n%d == 0) {
            return ret;
        }
        ret += ".";
        unordered_map< int, int > mark;
        int64_t r = n%d;
        while(r > 0) {
            if(mark[r] > 0) {
                ret.insert(mark[r], 1, '(');
                ret += ")";
                return ret;
            }
            mark[r] = ret.size();
            r *= 10;
            ret += to_string(r/d);
            r %= d;
        }
        return ret;
    }
};

Search for a Range

Q:
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

T:
First do binary search to find the left most position of the target, then do binary search to find the right most position.

A:

class Solution {
public:
    vector< int > searchRange(int A[], int n, int target) {
        vector< int > ret;
        ret.push_back(-1);
        ret.push_back(-1);
        int l=0;
        int r=n-1;
        while(l < r) {
            int m=(l+r)/2;
            if(A[m] < target) {
                l=m+1;
            } else {
                r=m;
            }
        }
        if(A[l] != target) {
            return ret;
        }
        int low = l;
        r=n-1;
        while(l < r) {
            int m=(l+r+1)/2;
            if(A[m] > target) {
                r=m-1;
            } else {
                l=m;
            }
        }
        if(A[r] != target) {
            return ret;
        }
        int hi = r;
        ret[0] = low;
        ret[1] = hi;
        return ret;
    }
};

Palindrome Partitioning II

Q:
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

T:
DP. Define cutnum[i] is the number of minimum cuts of s.substr(0, i), then
   cutnum[i] = min(cutnum[j] + 1), for 0<j<i and s.substr(j, i-j) is a palindrome.
We also need to consider when j==0, if s.substr(0, i) is apalindrome, then cutnum[i] is 0. Also, cutnum[i] is initialized as i-1.
We need a 2D array pair[i][j] to remember whether s.substr(i, j-i+1) is a palindrome.

A:

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        if(len == 0) {
            return 0;
        }
        vector< int > cutnum(len+1);
        bool pair[len][len];
        for(int i=1; i <= len; i++) {
            cutnum[i] = i-1;
        }
        cutnum[0] = 0;
        for(int i=0; i < len; i++) {
            for(int j=0; j < len; j++) {
                pair[i][j] = false;
            }
        }
        for(int i=0; i < len; i++) {
            for(int j=0; j <= i; j++) {
                if(s[i] == s[j] && (i-j < 2 || pair[j+1][i-1])) {
                    pair[j][i] = true;
                    cutnum[i+1] = min(cutnum[i+1], cutnum[j] + ((j==0)?0:1));
                }
            }
        }
        return cutnum[len];
    }
};

Unique Paths

Q:
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.

T:
DP.

A:

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

Decode Ways

Q:
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

T:
DP. The number of ways of the sub string that ends at i depends on the ways of the sub string ending at i-1 and i-2.

A:

class Solution {
public:
    bool check(char a) {
        if(a == '0') {
            return false;
        } else {
            return true;
        }
    }
    bool check(char a, char b) {
        if(a == '1' || (a == '2' && b <= '6')) {
            return true;
        }
        return false;
    }
    int numDecodings(string s) {
        int n = s.size();
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            if(check(s[0])) {
                return 1;
            }
            return 0;
        }
        int c = 0;
        int c2 = check(s[0]);
        int c1 = 0;
        if(check(s[0]) && check(s[1])) {
            c1++;
        }
        if(check(s[0], s[1])) {
            c1++;
        }
        for(int i=2; i < n; i++) {
            if(check(s[i])) {
                c += c1;
            }
            if(check(s[i-1], s[i])) {
                c += c2;
            }
            if (c == 0) {
                return 0;
            }
            c2 = c1;
            c1 = c;
            c = 0;
        }
        return c1;
    }
};

Letter Combinations of a Phone Number

Q:
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

T:
Use a vector to store previously generated combinations. For a new digit, append each of its characters to each of the previous combination.

A:

class Solution {
public:
    vector< string > letterCombinations(string digits) {
        string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector< string > ret;
        ret.push_back("");
        for(int i=0; i < digits.size(); i++) {
            string str = charmap[digits[i] - '0'];
            vector< string > tmp;
            for(int j=0; j < str.size(); j++) {
                for(int k=0; k < ret.size(); k++) {
                    tmp.push_back(ret[k]+str[j]);
                }
            }
            ret = tmp;
        }
        return ret;
    }
};

Max Points on a Line

Q:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

T:
For each point, look at its following points one by one. Use a hashmap to count the number of points that has the same slope. The slope with max number of count should be the answer for current point. If there is a point that overlaps the current point, we need to add it to the count for each slope we see.

A:

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector< Point > &points) {
        if(points.size() < 3) {
            return points.size();
        }
        int max = 0;
        for(int i=0; i < points.size(); i++) {
            map< double, int > count;
            int plus = 0;
            int nx = 1;
            for(int j=i+1; j < points.size(); j++) {
                double dx = points[i].x - points[j].x;
                double dy = points[i].y - points[j].y;
                if (dx == 0 && dy == 0) {
                    plus++;
                } else if (dx == 0) {
                    nx++;
                } else {
                    double slop = dy/dx;
                    count[slop]++;
                }
            }
            int tmp = nx;
            for(auto m : count) {
                if (m.second + 1 > tmp) {
                    tmp = m.second + 1;
                }
            }
            tmp += plus;
            if(tmp > max) {
                max = tmp;
            }
        }
        return max;
    }
};

Remove duplicated lines in a file

http://blog.csdn.net/v_july_v/article/details/7382693

Largest Independent Set

http://www.geeksforgeeks.org/largest-independent-set-problem/

Swap Nodes in Pairs

Q:
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

T:
Simple linked list operation.

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        ListNode * p = head;
        head = head->next;
        p->next = head->next;
        head->next = p;
        ListNode * q = p->next;
        while(q && q->next) {
            p->next = q->next;
            q->next = q->next->next;
            p->next->next = q;
            p = q;
            q = q->next;
        }
        return head;
    }
};

Maximal Rectangle

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

T:
We can treat each row and its above elements as a histogram. The height of the histogram for each row is the number of continues '1's in its above elements. Then we can use the Largest Rectangle in Histogram method to calculate the area of each row.


A:

class Solution {
public:
    int maximalRectangle(vector< vector< char > > &matrix) {
        if(matrix.size() == 0) {
            return 0;
        }
        if(matrix[0].size() == 0) {
            return 0;
        }
        vector< vector< int > > height(matrix.size(), vector< int >(matrix[0].size(), 0));
        for(int j=0; j < matrix[0].size(); j++) {
            for(int i=0; i < matrix.size(); i++) {
                if(matrix[i][j] == '0') {
                    height[i][j] = 0;
                } else if(i==0) {
                    height[i][j] = 1;
                } else {
                    height[i][j] = height[i-1][j] + 1;
                }
            }
        }
        int maxarea = 0;
        for(int i=0; i < height.size(); i++) {
            stack st;
            for(int j=0; j < height[i].size(); j++) {
                if(st.empty() || height[i][st.top()] < height[i][j]) {
                    st.push(j);
                } else {
                    int tmp = st.top();
                    st.pop();
                    maxarea = max(maxarea, (int)(height[i][tmp]*(st.empty()?j:(j-st.top()-1))));
                    j--;
                }
            }
            while(!st.empty()) {
                int tmp = st.top();
                st.pop();
                maxarea = max(maxarea, (int)(height[i][tmp]*(st.empty()?height[i].size():(height[i].size()-st.top()-1))));
            }
        }
        return maxarea;
    }
};

Largest Rectangle in Histogram

Q:

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

T:
To do this in O(n) time, we need to maintain a stack with increasing heights. Traverse through the heights, push its index to the stack if its height is larger than the stack top. Once we see a height lower than the stack top, we can keep popping from the stack and meanwhile calculating the area whose height is determined by the currently popped height, until the stack top's height is higher than the currently traversed height. Since we can make sure the heights between the currently popped height and the stack top are higher than the current height (when pushing each height into the stack, we keep popping the stack as long as the top is higher than the currently traversed height), and the heights between the currently popped height and the currently traversed height are higher than the currently popped height (the heights in the stack is increasing), we can use the index of the stack top and the currently traversed height to determine the width of the area. If the area is larger than seen, we record it as a new record.

A:

class Solution {
public:
    int largestRectangleArea(vector< int > &height) {
        height.push_back(0);
        int area = 0;
        stack st;
        for(int i=0; i < height.size(); i++) {
            if(st.empty() || height[st.top()] < height[i] ) {
                st.push(i);
            } else {
                int tmp = st.top();
                st.pop();
                area = max(area, height[tmp]*(st.empty()?i:(i-st.top()-1)));
                i--;
            }
        }
        return area;
    }
};

Edit Distance

Q:
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
T:
Suppose word1[i] == word2[j], then the distance equals the distance of word1.substr(0, i) and word2.substr(0, j). Otherwise, the distance is one plus the distance of three combinations: word1.substr(0, i) and word2.substr(0, j) by replacing word1[i] with word2[j], word1.substr(0, i+1) and word2.substr(0, j) by adding word2[j] at the end, word1.substr(0, i) and word2.substr(0, j+1) by deleting word1[i] at the end. Let c[i][j] notes the distance between word1.substr(0, i) and word2.substr(0, j), it is:
c[0][j] = j;
c[i][0] = i;
c[i][j] = c[i-1][j-1], if word1[i-1] == word2[j-1]
             1 + min(c[i-1][j-1], c[i-1][j], c[i][j-1]), else

A:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int * cur = new int[word2.size()+1];
        for(int i=0; i<=word2.size(); i++) {
            cur[i] = i;
        }
        for(int i=1; i<=word1.size(); i++) {
            int tmp = i-1;
            cur[0] = i;
            for(int j=1; j<=word2.size(); j++) {
                int tmp2 = cur[j];
                if(word1[i-1] == word2[j-1]) {
                    cur[j] = tmp;
                    tmp = tmp2;
                } else {
                    cur[j] = min(min(cur[j], cur[j-1]), tmp) + 1;
                    tmp = tmp2;
                }
            }
        }
        int ret = cur[word2.size()];
        delete[] cur;
        return ret;
    }
};

Longest Consecutive Sequence

Q:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

T:
First store all numbers in a hashmap. Then traverse the array, for each number in the map, see if its previous numbers or next numbers also in the map.

A:

class Solution {
public:
    int longestConsecutive(vector &num) {
        unordered_map< int, bool > mark;
        for(int i=0; i< num.size(); i++) {
            mark[num[i]] = true;
        }
        int maxlen = 0;
        for(int i=0; i< num.size(); i++) {
            mark[num[i]] = false;
            int mx = 1;
            int v = num[i] + 1;
            while(mark[v]) {
                mark[v] = false;
                mx++;
                v++;
            }
            v = num[i] - 1;
            while(mark[v]) {
                mark[v] = false;
                mx++;
                v--;
            }
            if(mx > maxlen) {
                maxlen = mx;
            }
        }
        return maxlen;
    }
};

Merge k Sorted Lists

Q:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

T:
Use a min-heap.

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct compare {
        bool operator () (ListNode * & p1, ListNode * & p2) {
            return p1->val > p2->val;
        }
    };
    ListNode *mergeKLists(vector< ListNode * > &lists) {
        ListNode dummy(0);
        priority_queue< ListNode*, vector< ListNode* >, compare > qu;
        for(int i=0; i < lists.size(); i++) {
            if(lists[i] != NULL) {
                qu.push(lists[i]);
            }
        }
        ListNode * p = &dummy;
        while(!qu.empty()) {
            p->next = qu.top();
            qu.pop();
            p = p->next;
            if(p->next) {
                qu.push(p->next);
            }
        }
        return dummy.next;
    }
};

Minimum Window Substring

Q:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

T:
We need two hashmap. One hashmap stores the number of each character in T. The other hashmap stores the number of character seen in S currently. We use to pointers to calculate the window. The end pointer traverse S and keeps updating the hashmap. If a character occurs less than it's in T, increase the number of characters that is valid for matching T. Once the number equals to T's size, we move the start pointer forward as long as there are more number of characters in current window than in T. By this, we can get the valid windows. Once we get a window, we record it if its length is smaller than previous window.

A:

class Solution {
public:
    string minWindow(string S, string T) {
        unordered_map< char, int > snum;
        unordered_map< char, int > tnum;
        for(int i=0; i < T.size(); i++) {
            tnum[T[i]]++;
        }
        string ret = "";
        int match = 0;
        int start = 0;
        int end = 0;
        for(end=0; end < S.size(); end++) {
            snum[S[end]]++;
            if(snum[S[end]] <= tnum[S[end]]) {
                match++;
            }
            if(match == T.size()) {
                while(snum[S[start]] > tnum[S[start]]) {
                    snum[S[start]]--;
                    start++;
                }
                if(ret.size()==0 || ret.size() > end-start+1) {
                    ret = S.substr(start, end-start+1);
                }
                snum[S[start]]--;
                start++;
                match--;
            }
        }
        return ret;
    }
};

Regular Expression Matching

Q:
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

T:
Typical recursive program.

A:

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(!s || !p) {
            return false;
        }
        if(*p == 0) return *s == 0;
        if(*(p+1)!='*') {
            return (*p == *s || (*p == '.' && *s != 0)) && isMatch(s+1, p+1);
        }
        while(*p == *s || (*p == '.' && *s != 0)) {
            if(isMatch(s, p+2)) return true;
            s++;
        }
        return isMatch(s, p+2);
    }
};

Sqrt(x)

Q:
mplement int sqrt(int x).
Compute and return the square root of x.

T:
Binary search. Note that we use x/m for comparing.

A:

class Solution {
public:
    int sqrt(int x) {
        if (x < 2) {
            return x;
        }
        int l=0; 
        int r = x;
        int res = l;
        while(l<=r) {
            int m = (l+r) / 2;
            if (m == x/m) {
                return m;
            } else if(m < x/m) {
                l = m+1;
                res = m;
            } else {
                r = m-1;
            }
        }
        return res;
    }
};

Spiral Matrix

Q:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

T:
Index manipulating.

A:

class Solution {
public:
    vector< in t> spiralOrder(vector< vector< int > > &matrix) {
        vector< in t> ret;
        int m=matrix.size();
        if(m == 0) {
            return ret;
        }
        int n=matrix[0].size();
        int i=0;
        int j=0;
        while(m > 0 && n > 0) {
            for(int k=0; k < n; k++) {
                ret.push_back(matrix[i][j]);
                j++;
            }
            if(m == 1) {
                break;
            }
            i++;
            j--;
            for(int k=1; k < m; k++) {
                ret.push_back(matrix[i][j]);
                i++;
            }
            if(n==1) {
                break;
            }
            j--;
            i--;
            for(int k=1; k < n; k++) {
                ret.push_back(matrix[i][j]);
                j--;
            }
            if(m <= 2) {
                break;
            }
            i--;
            j++;
            for(int k=2; k < m; k++) {
                ret.push_back(matrix[i][j]);
                i--;
            }
            j++;
            i++;
            m-=2;
            n-=2;
        }
        return ret;
    }
};

Trapping Rain Water

Q:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. 

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

T:
For each element, it can trap the water whose height is determined by the highest bar from its left and the highest bar from its right. So we can traverse the array by two passes, from left to right to find the left highest bar height and from right to left to find the right highest bar height.

A:

class Solution {
public:
    int trap(int A[], int n) {
        int maxleft[n];
        int maxright[n];
        int maxheight = 0;
        maxleft[0] = 0;
        for(int i=1; i < n; i++) {
            if(maxheight < A[i-1]) {
                maxheight = A[i-1];
            }
            maxleft[i] = maxheight;
        }
        maxheight = 0;
        maxright[n-1] = 0;
        for(int j=n-2; j>=0; j--) {
            if(maxheight < A[j+1]) {
                maxheight = A[j+1];
            }
            maxright[j] = maxheight;
        }
        int vol = 0;
        for(int i=0; i < n; i++) {
            vol += max(0, min(maxleft[i], maxright[i]) - A[i]);
        }
        return vol;
    }
};

Valid Parentheses

Q:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

T:
When seeing a left parenthesis, push it to the stack. When seeing a right parenthesis, pop the stack to see whether there is a match.

A:

class Solution {
public:
    bool isValid(string s) {
        stack< char > left;
        for(int i=0; i < s.size(); i++) {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                left.push(s[i]);
            } else {
                if(left.empty()) {
                    return false;
                }
                char p = left.top();
                left.pop();
                switch(p) {
                    case '(': {
                        if (s[i] != ')') {
                            return false;
                        }
                        break;
                    }
                    case '[': {
                        if (s[i] != ']') {
                            return false;
                        }
                        break;
                    }
                    case '{': {
                        if (s[i] != '}') {
                            return false;
                        }
                        break;
                    }
                }
            }
        }
        return left.empty();
    }
};

Maximum Subarray

Q:

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.

T:
Traverse the array. Continue adding new elements to the sum. Record the max sum once seeing a larger one. When seeing a negative number, we also add it to the sum, as long as the sum is positive. Once the sum becomes negative, we reset the sum to zero since the max sum should not include the elements before whose sum is negative.

A:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int sum = 0;
        int max = INT_MIN;
        for(int i=0; i < n; i++) {
            sum+=A[i];
            if(sum > max) {
                max = sum;
            }
            if(sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
};

Reverse Words in a String

Q:
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

T:
To do this in place, we can first reverse the string, then reverse each words.

A:

class Solution {
public:
    void reverseWords(string &s) {
        int l=0;
        int r=s.size()-1;
        while(l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
        l = 0;
        while(l < s.size()) {
            while(s[l] == ' ' && l < s.size()) {
                l++;
            }
            int ll=l;
            while(s[l] != ' ' && l < s.size()) {
                l++;
            }
            int rr=l-1;
            while(ll < rr) {
                char tmp = s[ll];
                s[ll] = s[rr];
                s[rr] = tmp;
                ll++;
                rr--;
            }
            l++;
        }
        l = 0;
        int b = 0;
        while(l< s.size()) {
            while(s[l] == ' ' && l < s.size()) {
                l++;
            }
            while(s[l] != ' ' && l < s.size()) {
                s[b] = s[l];
                b++;
                l++;
            }
            if(l < s.size()-1 && s[l] == ' ') {
                s[b] = ' ';
                b++;
            }
            if(l == s.size()) {
                while(s[b-1]==' ' && b > 0) {
                    b--;
                }
                s = s.substr(0, b);
                return;
            }
        }
    }
};

Interleaving String

Q:
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.

T:
Let m=s1.size()-1, n=s2.size()-1. If s3[m+n+1] == s1[m], then the problem is equivalent to examine whether s1.substr(0, m), s2 can interleave to make s3. So we can solve this by DP. let match[i][j] be whether s1.substr(0, i) and s2.substr(0, j) can interleave to make s3.substr(0, i+j). We have:
match[i][j] = match[i-1][j], if s1[i-1] == s3[i+j-1]
                  or match[i][j-1], if s2[j-1] == s3[i+j-1]
                  or false.
match[0][0] = true.
match[0][j] =  match[0][j-1], if s2[j-1] == s3[j-1]
                  or false.


A:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size()+s2.size()) {
            return false;
        }
        if(s1.size() == 0) {
            return s2 == s3;
        }
        if(s2.size() == 0) {
            return s1 == s3;
        }
        bool match[s2.size()+1];
        match[0] = true;
        for(int i=1; i<=s2.size(); i++) {
            if(s2[i-1] == s3[i-1]) {
                match[i] = match[i-1];
            } else {
                match[i] = false;
            }
        }
        for(int i=0; i< s1.size(); i++) {
            if(s1[i] != s3[i]) {
                match[0] = false;
            }
            for(int j=1; j<=s2.size(); j++) {
                match[j] = (s1[i]==s3[i+j]&&match[j]) || (s2[j-1]==s3[i+j]&&match[j-1]);
            }
        }
        return match[s2.size()];
    }
};

Pow(x, n)

Q:
Implement pow(x, n).

T:
To save computing time, we can calculate pow(x, n/2) and reuse it.

A:

class Solution {
public:
    double pow(double x, int n) {
        if(x == 1.0) {
            return 1.0;
        }
        if(x == -1.0) {
            if(n%2 == 0) {
                return 1.0;
            }
            return -1.0;
        }
        if(n < 0) {
            return 1.0 / pow(x, -n);
        }
        if (n == 0) {
            return 1;
        }
        double v = pow(x, n/2);
        if(n%2 == 0) {
            return v*v;
        } else {
            return v*v*x;
        }
    }
};

Merge Sorted Array

Q:
Given two sorted integer arrays A and B, merge B into A as one sorted array.

T:
We can insert elements in B one by one. Keep an index pointing to the position where the current element in B should be inserted, and move the following elements in A one position afterwards.

A:

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int j=0;
        for(int i=0; i< n; i++) {
            while(j< m+i && A[j] < B[i]) {
                j++;
            }
            for(int k=m+i-1; k>=j; k--) {
                A[k+1] = A[k];
            }
            A[j] = B[i];
        }
    }
};

Word Ladder II

Q:

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

T:
Do level by level BFS. Do not add a word in a new level if it already appears in previous levels. To do this, we can simple erase the words in the current level from the dictionary before processing next level. We also need a set for each word to remember its previous words to generate the paths when finally reaching the end.

A:

class Solution {
public:
    vector< vector< string> > findLadders(string start, string end, unordered_set &dict) {
        vector< vector< string > > ret;
        if(start.size() != end.size()) {
            return ret;
        }
        unordered_set< string > qu;
        qu.insert(start);
        dict.erase(start);
        vector< string > v;
        v.push_back(start);
        if(start == end) {
            ret.push_back(v);
            return ret;
        }
        unordered_map< string, unordered_set< string > > previous;
        while(!qu.empty()) {
            unordered_set< string > oldqu(qu);
            qu.clear();
            if(oldqu.find(end) != qu.end()) {
                bool stop = false;
                vector< string > vec;
                vec.push_back(end);
                ret.push_back(vec);
                while(!stop) {
                    stop = true;
                    int sz = ret.size();
                    for(int i=0; i< sz; i++) {
                        string cur = ret[i][0];
                        vector< string > tmp = ret[i];
                        tmp.insert(tmp.begin(), "");
                        unordered_set< string > & pres = previous[cur];
                        for( auto pre : pres) {
                            if(stop && pre != start) {
                                stop = false;
                            }
                            tmp[0] = pre;
                            ret.push_back(tmp);
                        }
                    }
                    for(int i=0; i< sz; i++) {
                        ret.erase(ret.begin());
                    }
                }
                break;
            }
            for(auto str : oldqu) {
                for(int i=0; i< str.size(); i++) {
                    for(char c='a'; c<= 'z'; c++) {
                        if(c != str[i]) {
                            string newstr = str;
                            newstr[i] = c;
                            if(dict.find(newstr) != dict.end() || newstr == end) {
                                previous[newstr].insert(str);
                                qu.insert(newstr);
                            }
                        }
                    }
                }
            }
            for( auto visited : qu) {
                dict.erase(visited);
            }
        }
        return ret;
    }
};

Permutations

Q:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

T:
Typical recursive application. For each permutation including the elements after the nth element, we can insert the nth element in each position to generate a permutation including the nth element.

A:

class Solution {
public:
    vector< vector< int > > ret;
    void generate(int n, vector& num) {
        if(n == num.size()-1) {
            vector< int > vec;
            vec.push_back(num[n]);
            ret.push_back(vec);
            return;
        }
        generate(n+1, num);
        int sz = ret.size();
        for(int i=0; i< sz; i++) {
            vector< int > vec = ret[i];
            ret[i].insert(ret[i].begin(), num[n]);
            for(int j=1; j<=vec.size(); j++) {
                vector< int > vec2 = vec;
                vec2.insert(vec2.begin() + j, num[n]);
                ret.push_back(vec2);
            }
        }
    }
    vector< vector< int > > permute(vector< int > &num) {
        generate(0, num);
        return ret;
    }
};

Random number generator with a blacklist

http://www.careercup.com/question?id=12336561

Median of Two Sorted Arrays

Q:

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

T:

For 0<=i<=m and 0<=j<=n, we split A and B into two parts. The lower part is A[0:i-1] and B[0:j-1], the upper part is A[i:m-1] and B[j:n-1]. If i and j split the two part equally, i.e. i+j = m-i + n-j, and all the elements in lower part is smaller than the upper part, then the median can be calculated from A[i-1], A[i], B[j-1], B[j]. Note in the code below j is calculated as (m+n+1)/2 - i, so that when m+n is odd, i+j == (m+n)/2 +1.

A:

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if(m < n) {
            return findMedianSortedArrays(B, n, A, m);
        }
        if(m==0) {
            return 0;
        }
        if(n==0) {
            if(m%2==1) {
                return A[(m-1)/2];
            } else {
                return (A[(m-1)/2] + A[(m-1)/2+1])/2.0;
            }
        }
        int l=0;
        int r=m;
        while(l<=r) {
            int i=(l+r)/2;
            int j=(m+n+1)/2-i;
            if(i < m && j>0 && A[i] < B[j-1]) {
                l = i+1;
            } else if(i>0 && j < n && A[i-1] > B[j]) {
                r = i-1;
            } else {
                int num1 = 0;
                if(i==0 && j>0) {
                    num1 = B[j-1];
                } else if(j==0 && i>0) {
                    num1 = A[i-1];
                } else if(i>0 && j>0) {
                    num1 = max(A[i-1], B[j-1]);
                }
                if ((m+n)%2 == 1) {
                    return num1;
                }
                int num2 = 0;
                if (i==m && j < n) {
                    num2 = B[j];
                } else if(j==n && i < m) {
                    num2 = A[i];
                } else if(i < m && j < n) {
                    num2 = min(A[i], B[j]);
                }
                return ((double)num1 + (double)num2) / 2.0;
            }
        }
        return 0;
    }
};

Implement strStr()

Q:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

T:

KMP is hard to think out. Just use two layers of loop can also work. O(m*n).

A:

class Solution {
public:
    int strStr(char *haystack, char *needle) {
        if(haystack == NULL || needle == NULL) {
            return -1;
        }
        char * h=haystack;
        char * n=needle;
        if(!*n && *h) {
            return 0;
        }
        if(!*h && *n) {
            return -1;
        }
        if(!*n && !*h) {
            return 0;
        }
        do {
            while(*h && *h != *n) {
                h++;
            }
            if(!*h) {
                return -1;
            }
            char * a=h+1;
            char * b=n+1;
            while(*a && *b && *b==*a) {
                a++;
                b++;
            }
            if(!*a && *b) {
                return -1;
            }
            if(*b) {
                h++;
            } else {
                return h-haystack;
            }
        } while (*h);
        return -1;
    }
};

Lowest Common Ancestor of a Binary Tree

leetcode article

Construct Binary Tree from Preorder and Inorder Traversal

Q:
Given preorder and inorder traversal of a tree, construct the binary tree.

T:
We know the root node of current tree is the first element of the preorder traversal. We can iterate through the ignored traversal to find that root node. Then we know the length of the left subtree and right subtree.

A:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *build(vector< int > & preorder, int ps, int pe, vector< int > & inorder, int is, int ie) {
        if(ps > pe) {
            return NULL;
        }
        TreeNode * node = new TreeNode(preorder[ps]);
        int in = -1;
        for(int i=is; i<=ie; i++) {
            if(inorder[i] == preorder[ps]) {
                in = i;
                break;
            }
        }
        if(in == -1) {
            return node;
        }
        node->left = build(preorder, ps+1, ps+in-is, inorder, is, in-1);
        node->right = build(preorder, ps+in-is+1, pe, inorder, in+1, ie);
        return node;
    }
    TreeNode *buildTree(vector< int > &preorder, vector< int > &inorder) {
        return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

Two Sum

Q:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

T:

Traverse the array. For each element, put it in the hashmap. Also check whether there is already an number in the hashmap that together sum to the target.

A:

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        map m;
        vector ret;
        for(int i=0; i 0) {
                ret.push_back(m[numbers[i]]);
                ret.push_back(i+1);
                return ret;
            }
            m[target - numbers[i]] = i+1;
        }
        return ret;
    }
};

Validate Binary Search Tree

Q:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

T:

We can do in-order traverse of the tree. All we need is to add an additional checking to see that whether the currently visited node is greater than its previously visited node. We can use a global variable to store previously visited node.

A:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * prev = NULL;
    bool isValidBST(TreeNode *root) {
        if(root == NULL) {
            return true;
        }
        if(!isValidBST(root->left)) {
            return false;
        }
        if(prev != NULL && prev->val >= root->val) {
            return false;
        }
        prev = root;
        return isValidBST(root->right);
    }
};

Sudoku Solver

Q:


Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

T:
Typical branch and back-trace problem. We check each of the 81 positions recursively.

A:

class Solution {
public:
    bool solve(int pos, vector< vector< char > > &board) {
        if(pos == 81) {
            return true;
        }
        int i = pos/9;
        int j = pos%9;
        if(board[i][j] != '.') {
            return solve(pos+1, board);;
        }
        for(char c='1'; c<='9'; c++) {
            int stop = 0;
            for(int k=0; k<9; k++) {
                if(board[k][j] == c) {
                    stop = 1;
                    break;
                }
            }
            if(stop) {
                continue;
            }
            for(int k=0; k<9; k++) {
                if(board[i][k] == c) {
                    stop = 1;
                    break;
                }
            }
            if(stop) {
                continue;
            }
            for(int k=3*(i/3); k<3*(i/3)+3; k++) {
                for(int l=3*(j/3); l<3*(j/3)+3; l++) {
                    if(board[k][l] == c) {
                        stop = 1;
                        break;
                    }
                }
                if(stop) {
                    break;
                }
            }
            if(stop) {
                continue;
            }
            board[i][j] = c;
            if(solve(pos+1, board)) {
                return true;
            }
            board[i][j] = '.';
        }
    }
    void solveSudoku(vector< vector< char > > &board) {
        solve(0, board);
    }
};

Min Stack

Q:
 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

    push(x) -- Push element x onto stack.
    pop() -- Removes the element on top of the stack.
    top() -- Get the top element.
    getMin() -- Retrieve the minimum element in the stack.

T:
We need another stack to store the current minimum element. We can push the current minimum element into that stack when pushing data to the stack. To improve this a little bit, we don't need to push the current minimum each time we push a new data. We only need to push a new minimum value if we see a new value, which is less or equal to current minimum. When poping, we only pop the current minimum element when we pop the same value from the data stack.

A:

class MinStack {
public:
    stack data;
    stack minstack;
    void push(int x) {
        data.push(x);
        if(minstack.empty() || minstack.top() >= x) {
            minstack.push(x);
        }
    }

    void pop() {
        if(data.empty()) {
            return;
        }
        int x = data.top();
        data.pop();
        if(x == minstack.top()) {
            minstack.pop();
        }
    }

    int top() {
        if(data.empty()) {
            return -1;
        }
        return data.top();
    }

    int getMin() {
        if (minstack.empty()) {
            return -1;
        }
        return minstack.top();
    }
};