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 nth sequence.

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

class Solution {
public:

    string int2string(int c)
    {
        string cstr;
        while (c)
        {
            cstr += (char)(c % 10 + '0');
            c = c / 10;
        }
        reverse(cstr.begin(), cstr.end());
        return cstr;
    }
    
    string countAndSay(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        string ret = "1";
        
        if (n <= 1) return ret;
        
        int i = 2;
        
        while (i <= n)
        {
            string tmp;
            int j = 0, count = 0;
            while (j < ret.size())
            {
                char cur = ret[j]; int c = 1;
                ++j;
                while (j < ret.size() && ret[j] == ret[j - 1])
                {
                    ++j; ++c;
                }
                string&& cstr = int2string(c);
                tmp += cstr + cur;
            }
            ret = tmp;
            ++i;
        }
    }
};

Search Insert Position

/*
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
*/

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int i = 0;
        while (i < n)
        {
            if (A[i] == target) return i;
            if (i + 1 < n && A[i] < target && A[i + 1] > target) return i + 1;
            if (A[0] > target) return 0;
            if (A[n - 1] < target) return n;
            ++i;
        }
        return -1;
    }
};

Search for a Range

/*
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].
*/

class Solution {
public:
    int binarySearch(int A[], int n, int target)
    {
        int i = 0, j = n - 1;
        
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target) return m;
            
            if (A[m] > target) j = m - 1;
            
            if (A[m] < target) i = m + 1;
        }
        return -1;
    }
    
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int pos_target = -1;
        
        int left = 0, right = n - 1;
        
        while (left <= right)
        {
            int m = left + (right - left) / 2;
            
            if (A[m] == target) {pos_target = m; break;}
            
            if (A[m] > target) right = m - 1;
            
            if (A[m] < target) left = m + 1;
        }
        
        if (pos_target == -1) return vector<int>{-1, -1};
        
        int start = pos_target, i = left, j = pos_target - 1;
    	while (i <= j)
		{
			int m = i + (j - i) / 2;
			
			if (A[m] == target)
			{
				j = m;
				if (i == j)
				{
					start = i;
					break;
				}
			}
			else
			{
				i = m + 1;
			}
		}
		
		int end = pos_target; i = pos_target + 1, j = right;
		while (i <= j)
		{
			int m = i + (j - i) / 2;
			
			if (A[m] == target)
			{
				i = m;
				if (i == j)
				{
					end = i;
					break;
				}
			}
			else
			{
				j = m - 1;
			}
		}
		
        return vector<int>{start, end};
    }
};

/*
A better approach 
*/

class Solution {
public:
    
    vector<int> searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int lower = -1, upper = -1, i = 0, j = n - 1;
        
        //find lowerbound
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target)
            {
                lower = m;
                j = m - 1;
            }
            else if (A[m] > target)
            {
                j = m - 1;
            }
            else
            {
                i = m + 1;
            }
        }
        
        if (lower == -1) return vector<int>{-1, -1};
        
        i = lower, j = n - 1;
        while (i <= j)
        {
            int m = i + (j - i) / 2;
            
            if (A[m] == target)
            {
                i = m + 1;
                upper = m;
            }
            else
            {
                j = m - 1;
            }
        }
        
        return vector<int>{lower, upper};
    }
};

Longest Valid Parentheses

class Solution {
public:
    int longestValidParentheses(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	int res = 0, cur = 0, persistent = 0;
		
		vector<int> stack;
		
		for (int i = 0; i < s.size(); ++i)
		{
			if (s[i] == '(')
			{
				stack.push_back(cur);
			}
			else
			{
				if (stack.empty())
				{
					if (cur > persistent) persistent = cur;
					cur = 0;
				}
				else
				{
					stack.pop_back();
					cur ++;
					if (cur > res) res = cur;
				}
			}
		}
        //cout << stack.size() << endl;
        
        if (stack.empty()) return 2 * res;
        
        int rval = stack[0], prev = res;
		for (int i = 1; i < stack.size(); ++i)
		{
			rval = max(stack[i] - stack[i - 1], rval);
            //cout << rval << endl;
		}
        rval = max(res - stack.back(), rval);
        rval = max(rval , persistent);
		return 2 * rval;
	}
};

Implement strStr()

/*
Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
*/

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (not haystack || not needle) return NULL;
        
        if (not *needle) return haystack; //corner
        
        char *p1 = needle, *p2 = haystack;;
        while (*p1)
        {
            p1++;
            p2++;
        }
        p2--;
        
        int i = 0;
        
        while (*(haystack + i) && *p2)
        {
            if (*(haystack + i) == *(needle))
            {
                int p = i, q = 0;
                while (*(haystack + p) && *(haystack + p) == *(needle + q))
                {
                    ++p; ++q;
                    if (not *(needle + q))
                    {
                        return haystack + i;
                    }
                }
            }
            ++i;
            p2++;
        }
        return NULL;
    }
};

Remove Element

/*
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
*/

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int res = n;
        int i = 0, j = 0, length = 0;
        
        while (j < n) //loop invariant
        {
            i = j; //state restore
            
            while (j < n && A[j] != elem) ++j; //find range : two cases : 1. find elem, or reach end
                
            
            for (int p = i; i != 0 && p < j; ++p) //two cases : 1. first time find elem, i == 0; 2. otherwise
                A[p - length] = A[p];
            
            if (j == n) return res;
            
            //state set
            j ++; //to next starting position
            length ++; //next move length
            res --; //aivailable length
        }
        return res;
    }
};

Remove Duplicates from Sorted Array

/*
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].
*/

class Solution {
public:
    void swap(int A[], int i, int j)
    {
        if (i == j) return;
        A[i] = A[i] ^ A[j];
        A[j] = A[i] ^ A[j];
        A[i] = A[i] ^ A[j];
    }
    
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (not A || n < 1) return 0;
        
        int i = 0, j = 1;
        
        while (j < n)
        {
            if (A[j] == A[i])
            {
                ;
            }
            else
            {
                swap(A, ++i, j);
            }
            
            ++j;
        }
        return i + 1;
    }
};

Reverse Nodes in k-Group

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (k <= 1) return head;
        
        ListNode Dummy(0);
        Dummy.next = head;
        
        ListNode *begin = head, *tail = head, *prev = &Dummy, *next = NULL;
        
        while (begin){
            
            //find range
            int i = 0;
            while (tail && i < k - 1)
            {
                tail = tail->next;
                ++i;
            }
            if (not tail)
            { 
                return Dummy.next;
            }
            next = tail->next;
            
            //reverse between begin and tail
            ListNode *pv = begin, *cur = begin->next;
            while (pv != tail)
            {
                ListNode *tmp = cur->next;
                cur->next = pv;
                pv = cur;
                cur = tmp;
            }
            
            //restore
            prev->next = tail;
            begin->next = next;
            
            //new state for next group
            prev = begin;
            begin = next;
            tail = begin;//I missed this state
        }
        
        return Dummy.next;
    }
};

Generate Parentheses

/*
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:

"((()))", "(()())", "(())()", "()(())", "()()()"
*/



class Solution {
public:

    void helper(int l, int r, string pair, int n, vector<string>& res)
    {
        if (l == r && l == n)
        {
            res.push_back(pair);
            return;
        }
        
        if (l < n)
            helper(l + 1, r, pair+'(', n, res);
        if (r < l)
            helper(l, r + 1, pair+')', n, res);
    }
    
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<string> res;
        
        if (n <= 0) return res;
        
        helper(0, 0, "", n, res);
        
        return res;
    }
};

Valid Parentheses

/*
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.
*/

class Solution {
public:
    bool isValid(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<char> stack;
        
        int i = 0;
        while (i < s.size())
        {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                stack.push_back(s[i]);
            }
            else if (stack.empty() || (s[i] == ')' && stack.back() != '(') || (s[i] == ']' && stack.back() != '[') || (s[i] == '}' && stack.back() != '{'))
            {
                return false;
            }
            else
            {
                stack.pop_back();
            }
            ++i;
        }
        if (not stack.empty()) return false; //tricky part
        return true;
    }
};