17 Letter Combinations of a Phone Number

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"].

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> dict = vector<string>({"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"});
        string comb;
        vector<string> res;
        if (digits.size()<=0)
            return res;
        help(digits,0,comb,res,dict);
        return res;
    }
    void help(string s, int i, string &comb, vector<string> &res, vector<string> &dict){
        if (i>=s.size()){
            res.push_back(comb);
            return;
        }
        string temp = dict[s[i]-'0'];
        if (temp.size()==0)
            help(s,i+1,comb,res,dict);
        else{
            for (int j=0;j<temp.size();j++){
                comb.push_back(temp[j]);
                help(s,i+1,comb,res,dict);
                comb.pop_back();
            }
        }
    }
};

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

class Solution {
public:
    int jump(vector<int>& nums) {
        int fartherest = 0;
        int lastFartherest = 0;
        int i=0;
        int count=0;
        while(i<=fartherest && i<nums.size())
        {
            if (i>lastFartherest){
                ++count;
                lastFartherest = fartherest;
            }
            fartherest = max(fartherest, i+nums[i]);
            ++i;
        }
        return count;
    }
};

35 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) {
        int left=0,right = n-1;
        int res = 0;
        while(left<=right)
        {
            int mid = left+(right-left)/2;
            if (target == A[mid]){
                return mid;
            }
            else if (A[mid]<target){
                left = mid+1;
                res = left;
            }
            else{
                right = mid-1;
                res = mid;
            }
        }
        return res;
    }
};

112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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

129 Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int res = 0;
        int sum=0;
        help(root, res, sum);
        return sum;
    }
    void help(TreeNode *root, int res, int &sum)
    {
        if (!root)
            return;
        res = res*10 + root->val;
        if (!root->left && !root->right)
        {
            sum+= res;
            return;
        }
        if (root->left)
        {
            help(root->left, res, sum);
        }
        if (root->right)
        {
            help(root->right,res,sum);
        }
    }
};

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum=0;
        if (!root)
            return 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode * tmp = q.front();
            q.pop();
            if (!tmp->left && !tmp->right)
            {
                sum+= tmp->val;
            }
            else
            {
                if (tmp->left)
                {
                    tmp->left->val += tmp->val*10;
                    q.push(tmp->left);
                }
                if (tmp->right)
                {
                    tmp->right->val += tmp->val*10;
                    q.push(tmp->right);
                }
            }
        }
        return sum;
    }
    
};

93 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<int> ip;
        vector<string> res;
        help(s,ip,res,0);
        return res;
    }
    void help(string s, vector<int> & ip, vector<string> &res, int pos)
    {
        if (ip.size()==4 && pos == s.size())
        {
            string tmp;
            for (int i=0;i<ip.size();i++)
            {
                tmp+= to_string(ip[i])+".";
            }
            tmp.pop_back();
            res.push_back(tmp);
            return;
        }
        if (ip.size()==4 || pos>=s.size())
            return;
        for (int i=1;i<=3;i++)
        {
            string tmp = s.substr(pos,i);
            int val = stoi(tmp);
            if (isValid(tmp))
            {
                ip.push_back(val);
                help(s,ip,res,pos+i);
                ip.pop_back();
            }
        }
    }
    bool isValid(string s)
    {
        int i=0;
        if (s[0]=='0' && s.size()>1)
            return false;
        int val = stoi(s);
        if (val>=0 && val<=255)
            return true;
        return false;
    }

};

89 Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n==0)
        {
            vector<int> res = vector<int>(1,0);
            return res;
        }
        vector<int> res = grayCode(n-1);
        int i = res.size()-1;
        for (;i>=0;i--)
        {
            int temp = res[i];
            temp = temp | (1<<(n-1));
            res.push_back(temp);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res = vector<int>(1,0);
        for (int i=1;i<=n;i++)
        {
            for (int j = res.size()-1;j>=0;j--)
            {
                int temp = res[j];
                temp = temp|(1<<(i-1));
                res.push_back(temp);
            }
        }
        return res;
    }
};

220 Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution {
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size();
        if (m==0)
            return 0;
        int n = grid[0].size();
        if (n==0)
            return 0;
        int count = 0;
        for (int i=0;i<m;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (grid[i][j]=='1')
                {
                    ++count;
                    dfs(grid,i,j,m,n);
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>> &grid,int i, int j, int m, int n)
    {
        grid[i][j]='X';
        if (i-1>=0 && grid[i-1][j]=='1')
        {
            dfs(grid,i-1,j,m,n);
        }
        if (i+1<m && grid[i+1][j]=='1' )
        {
            dfs(grid,i+1,j,m,n);
        }
        if (j-1>=0 && grid[i][j-1]=='1')
        {
            dfs(grid,i,j-1,m,n);
        }
        if (j+1<n && grid[i][j+1]=='1')
        {
            dfs(grid,i,j+1,m,n);
        }
    }
};

161 One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size()<t.size())
            return isOneEditDistance(t,s);
        if (s.size()-t.size()>=2)
            return false;
        if (s.size()==t.size())
            return sameSize(s,t);
        else
            return oneSizeDif(s,t);
    }
    bool sameSize(const string &s,const string &t)
    {
        for (int i=0;i<s.size();i++)
        {
            if (s[i]!=t[i])
                return s.substr(i+1)==t.substr(i+1);
        }
        return false;
    }
    bool oneSizeDif(const string &s, const string &t)
    {
        for (int i=0;i<t.size();i++)
        {
            if (s[i]!=t[i])
            {
                return s.substr(i+1)==t.substr(i);
            }
        }
        return true;
    }
};

97 Interleaving String

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.

Solution 1: 2 dimensional matrix:

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

Solution 2: 1 dimensional vector

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

132 Palindrome Partitioning II

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.

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

164 Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

class Solution {
public:
    int maximumGap(vector<int> &num) {
        int n = num.size();
        if (n<=1)
            return 0;
        int maxVal = num[0],minVal = num[0];
        for (int i=1;i<n;i++)
        {
            maxVal = max(maxVal,num[i]);
            minVal = min(minVal,num[i]);
        }
        
        int step = (maxVal-minVal)/(n)+1;
        int numberBucket = (maxVal-minVal)/step+1;
        vector<int> minVec = vector<int>(numberBucket,INT_MAX);
        vector<int> maxVec = vector<int>(numberBucket,INT_MIN);
        for (int i=0;i<n;i++)
        {
            int index = (num[i]-minVal)/step;
            minVec[index] = min(minVec[index],num[i]);
            maxVec[index] = max(maxVec[index],num[i]);
        }
        int res = 0;
        int last = 0;
        for (int i=0;i<numberBucket;i++)
        {
            if (minVec[i]==INT_MAX && maxVec[i]==INT_MIN)
                continue;
            res = max(maxVec[i]-minVec[i],res);
            if (i>0)
                res = max(res,minVec[i]-maxVec[last]);
            last = i;
        }
        return res;
            
    }
};

190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res;
        for (int i=0;i<32;i++)
        {
            res = res<<1 | (n&1);
            n = n>>1;
        }
        return res;
    }
};

44 Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char * star=NULL;
        const char * star_s = s;
        while(*s)
        {
            if (*s==*p || *p=='?')
            {
                s++;
                p++;
                continue;
            }
            else if (*p=='*')
            {
                star = p;
                star_s = s;
                p++;
                continue;
            }
            else if (star)
            {
                s=++star_s;
                p=star+1;
            }
            else
                return false;
        }
        while(*p=='*')
            p++;
        return !*p;
        
    }
};

157 Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int res=0;
        while(res<n)
        {
            int readNumber = read4(buf+res);
            res+= readNumber;
            if (readNumber<4)
                break;
        }
        if (res>n)
        {
            buf[n]='\0';
            res = n;
        }
        return res;
    }
};

158 Read N Characters Given Read4 II - Call multiple times

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function may be called multiple times.

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
     Solution(){
         start=0;end=0;
     }
     bool isEmpty(){
         return start==end;
     }
    int read(char *buf, int n) {
        int res=0;
        while(res<n && !isEmpty()){
            buf[res]=buffer[start];
            start++;
            start %=5;
            res++;
        }
        while(res<n){
            int count = read4(buf+res);
            res += count;
            if (count<4)
                break;
        }
        if (res>n){
            for (int i=n;i<res;i++){
                buffer[end]=buf[i];
                end = (end+1)%5;
            }
            res = n;
        }
        return res;
    }
private:
    int buffer[5];
    int start;
    int end;
};

159 Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int len=0;
        unordered_map<char,int> mp;
        int count=0;
        int start=0,end=0;
        while(end<s.size())
        {
            if (mp.find(s[end])==mp.end())
            {
                if (count<2)
                {
                    mp[s[end]]=end;
                    count++;
                }
                else
                {
                    count++;
                    while(count>2)
                    {
                        if (mp.find(s[start])!=mp.end())
                        {
                            if (mp[s[start]]==start)
                            {
                                mp.erase(s[start]);
                                count--;
                            }
                        }
                        start++;
                    }
                    mp[s[end]]=end;
                }
            }
            else
            {
                mp[s[end]]=end;
            }
            len = max(len,end-start+1);
            end++;
        }
        return len;
    }
};

3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = 0;
        unordered_map<char,int> mp;
        int start=0;
        int end = start;
        while(end<s.size())
        {
            if (mp.find(s[end])!=mp.end())
            {
                start = max(start,mp[s[end]]+1);
                mp[s[end]]=end;
            }
            else
            {
                mp[s[end]]=end;
            }
            len = max(len,end-start+1);
            end++;
        }
        return len;
    }
};

82 Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummy =new ListNode(0);
        dummy->next = head;
        int val = INT_MIN;
        ListNode *cur = head;
        ListNode* pre = dummy;
        while(cur)
        {
            if (cur->val == val || cur->next && cur->val == cur->next->val)
            {
                pre->next = cur->next;
                val = cur->val;
                delete cur;
                cur=pre->next;
            }
            else
            {
                val = cur->val;
                pre = cur;
                cur = cur->next;
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

9 Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Solution 1: Use String
class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0)
            return false;
        if (x==0)
            return true;
        string original = to_string(x);
        string reverse;
        while(x>0)
        {
            reverse.push_back(x%10 + '0');
            x /= 10;
        }
        return reverse == original;
    }
};

Solution 2: Use integer
class Solution {
public:
    bool isPalindrome(int x) {
        if (x==0)
            return true;
        if (x<0|| x%10==0)
            return false;
        
        int y = 0;
        while(x>y)
        {
            y = y*10 + x%10;
            if (x==y)
                return true;
            x /= 10;
        }
        return x==y;
    }
};

2 Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (!l1)
            return l2;
        if (!l2)
            return l1;
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        int carry = 0;
        while(l1 || l2 || carry>0)
        {
            int num1 = l1? l1->val:0;
            int num2 = l2? l2->val:0;
            int sum = (num1+num2+carry)%10;
            carry = (num1+num2+carry)/10;
            tmp->next = new ListNode(sum);
            tmp = tmp->next;
            l1 = l1? l1->next:l1;
            l2 = l2? l2->next:l2;
        }
        tmp = dummy->next;
        delete dummy;
        return tmp;
        
    }
};

69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

class Solution {
public:
    int sqrt(int x) {
        if (x<=1)
            return x;
         return help(x,1,x/2);
    }
    int help(int x, int low,int high)
    {
        if (low>high)
            return high + (low-high)/2;
        double mid = (double) low + (high-low)/2;
        if (mid==x/mid)
            return mid;
        if (mid>x/mid)
            return help(x,low,mid-1);
        return help(x,mid+1,high);
    }
};

159 Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char,int> mp;
        int start=0;
        int end = 0;
        int max_len=0;
        int count=0;
        while(end<s.size())
        {
            if (count<2)
            {
                if (mp.find(s[end])==mp.end() || mp[s[end]]<start)
                {
                    count++;
                }
                mp[s[end]]=end;
            }
            else
            {
                if (mp.find(s[end])==mp.end()|| mp[s[end]]<start)
                {
                    count++;
                    while(count>2)
                    {
                        if (mp[s[start]]<=start)
                        {
                            mp.erase(s[start]);
                            count--;
                        }
                        start++;
                    }
                }
                mp[s[end]]=end;
            }
            end++;
            if (count<=2)
            {
                max_len = max(max_len,end-start);
            }
        }
        return max_len;
    }
};

157 Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function will only be called once for each test case.

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int res = 0;
        int read_char = 0;
        while (res<n)
        {
            read_char = read4(buf+res);
            res += read_char;
            if (read_char<4)
                break;
        }
        if (res>=n)
        {
            buf[n]='\0';
            res = n;
        }
        return res;
    }
};

163 Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

class Solution {
public:
    vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
        vector<string> res;
        for (int i=0;i<n;i++)
        {
            if (A[i]>upper)
                break;
            else if (A[i]==upper)
                upper--;
            else if (A[i]<lower)
                continue;
            else if (A[i]==lower)
                lower++;
            else
            {
                if (A[i]-lower==1)
                {
                    res.push_back(to_string(lower));
                    lower = A[i]+1;
                }
                else
                {
                    string range = to_string(lower)+"->"+to_string(A[i]-1);
                    res.push_back(range);
                    lower = A[i]+1;
                }
            }
        }
        if (lower<upper)
            res.push_back(to_string(lower)+"->"+to_string(upper));
        else if (lower == upper)
            res.push_back(to_string(lower));
        return res;
    }
};

31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size()<=1)
            return;
        int i=num.size()-1;
        while(i>0 && num[i]<=num[i-1])
            i--;
        if (i==0)
        {
            sort(num.begin(),num.end());
            return;
        }
        i--;
        int j=num.size()-1;
        while(j>i && num[j]<=num[i])
            j--;
        swap(num[i],num[j]);
        sort(num.begin()+i+1,num.end());
    }
};

99 Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        TreeNode *pre = NULL;
        TreeNode *first = NULL;
        TreeNode *second = NULL;
        inorderTraversal(root,pre,first,second);
        int tmp = first->val;
        first->val = second->val;
        second->val = tmp;
    }
    void inorderTraversal(TreeNode *root, TreeNode* & pre, TreeNode *&first, TreeNode* &second)
    {
        if (!root)
            return;
        inorderTraversal(root->left,pre,first,second);
        if (pre && pre->val>root->val)
        {
            if (!first)
                first = pre;
            second = root;
        }
        pre = root;
        inorderTraversal(root->right,pre,first,second);
    }
};

Leetcode 187 Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Solution: 
基本思路，每十个字符当成一个string扫描。map里面没有就存入map,map里有且之前没有存入result中就存入，如果已经存过就跳过。
难点：string存入map太占地方，每个字符一个byte，每个string要10个byte。解决方法用bit map：ACGT一共4种二进制编码：A:00,C:01,G:10,T:11,每个字符只需要2bit，每个string 20bit=3bytes就够了。

1.每十个字符当成一个string扫描，对每个字符转换成int。
转换方法：按字符扫描，原结果左移2位，然后最低两位按编码设定即可。
如：GTCA：
第一次扫描A： result=10b
第二次扫描T: result先左移2位：result=1000b，再设置最低2位为11：result=1011b
第三次赛秒C：result先左移2位(<<2)，再最低2位设置为二进制01 (和01b与)： result = result<<2 |01
注意：上面都是二进制数，但是c++没有直接二进制数的表达方法，所以要转换成10进制数进行与运算。

2. 如果map里面没有，就存入map，设置个数为1。
如果map里面已有，且个数为1，表示之前有且仅有一个，则记录在result里，改变个数为-1；如果map里面有，但是个数不为1，代表已经记录在result了，不操作。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        if (s.size()<10)
            return res;
        unordered_map<int,int> mp;
        for (int i=0;i<(int)s.size()-9;i++)
        {
            string tmp_str = s.substr(i,10);
            int str_val = strToInt(tmp_str);
            if (mp.find(str_val)==mp.end())
            {
                mp[str_val]=1;
            }
            else
            {
                if (mp[str_val]==1)
                {
                    mp[str_val]=-1;
                    res.push_back(tmp_str);
                }
            }
        }
        return res;
    }
    int strToInt(string s)
    {
        int res=0;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='A')
                res = res<<2;
            else if (s[i]=='C')
                res = res<<2|1;
            else if (s[i]=='G')
                res = res<<2 |2;//binary 10 = 2
            else
                res = res <<2 |3;//binary 11 = 3
        }
        return res;
    }
};

179 Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> str;
        for (int i=0;i<num.size();i++)
            str.push_back(to_string(num[i]));
        sort(str.begin(),str.end(),compare);
        string res;
        int i=0;
        while(i<str.size()-1 && str[i]=="0")
            i++;
        for (;i<str.size();i++)
            res += str[i];
        return res;
    }
    static bool compare(string s1,string s2)
    {
        return (s1+s2)>(s2+s1);
    }
};

148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        int len=0;
        ListNode *tmp = head;
        while(tmp)
        {
            tmp=tmp->next;
            len++;
        }
        return mergeSort(head,len);
    }
    ListNode* mergeSort(ListNode *head,int n)
    {
        if (n<=1)
            return head;
        int len=n/2;
        ListNode *tmp = head;
        while(len>1)
        {
            tmp = tmp->next;
            len--;
        }
        ListNode *b = tmp->next;
        tmp->next = NULL;
        head = mergeSort(head,n/2);
        b = mergeSort(b,n-n/2);
        ListNode *newHead = merge(head,b);
        return newHead;
    }
    ListNode* merge(ListNode* a,ListNode*b)
    {
        if (!a && !b)
            return NULL;
        if (!a)
            return b;
        if (!b)
            return a;
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        while(a && b)
        {
            if (a->val<b->val)
            {
                tmp->next = a;
                a=a->next;
            }
            else
            {
                tmp->next = b;
                b=b->next;
            }
            tmp = tmp->next;
        }
        if (a)
            tmp->next = a;
        if (b)
            tmp->next = b;
        tmp = dummy->next;
        delete dummy;
        return tmp;
    }
};

146 LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

class doubleListNode
{
public:
    doubleListNode(int key_k, int value)
    {
        key = key_k;
        val = value;
        left = NULL;
        right = NULL;
    }
    doubleListNode *left;
    doubleListNode *right;
    int key;
    int val;
};
class LRUCache{
public:
    LRUCache(int capacity) {
        cache_capacity = capacity;
        size = 0;
        dummy = new doubleListNode(0,0);
        tail = dummy;
        
    }
    ~LRUCache()
    {
        delete dummy;
    }
    void insertNewNodeToHead(int key, int val);
    void removeToHead(doubleListNode * node);
    int get(int key) {
        if (mp.find(key)!=mp.end())
        {
            int res = mp[key]->val;
            removeToHead(mp[key]);
            return res;
        }
        else
            return -1;
    }
    void set(int key, int value) {
        if (mp.find(key)!=mp.end())
        {
            mp[key]->val = value;
            removeToHead(mp[key]);
        }
        else
        {
            if (size<cache_capacity)
            {
                insertNewNodeToHead(key,value);
                ++size;
            }
            else
            {
                if (tail!=dummy)
                {
                    mp.erase(tail->key);
                    tail = tail->left;
                    delete tail->right;
                }
                insertNewNodeToHead(key,value);
            }
        }
    }
    int cache_capacity;
    int size;
    unordered_map<int, doubleListNode*> mp;
    doubleListNode *dummy;
    doubleListNode *tail;
};
void LRUCache::insertNewNodeToHead(int key, int val)
{
    doubleListNode *newNode = new doubleListNode(key,val);
    newNode->right = dummy->right;
    if (dummy->right)
        dummy->right->left = newNode;
    dummy->right = newNode;
    newNode->left = dummy;
    if (tail == dummy)
        tail = dummy->right;
    mp[key]=newNode;
}
void LRUCache::removeToHead(doubleListNode * node)
{
    if (node)
    {
        if (node == tail)
        {
            tail = tail->left;
            tail->right = NULL;
        }
        else
        {
            node->left->right = node->right;
            node->right->left = node->left;
        }

        node->right = dummy->right;
        if (dummy->right)
            dummy->right->left = node;
        node->left = dummy;
        dummy->right = node;
        if (tail==dummy)
            tail = dummy->right;
    }
}

57 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i=0;
        while(i<intervals.size())
        {
            if (intervals[i].end<newInterval.start)
            {
                res.push_back(intervals[i]);
            }
            else if (intervals[i].start>newInterval.end)
            {
                break;
            }
            else 
            {
                newInterval.start = min(intervals[i].start,newInterval.start);
                newInterval.end = max(intervals[i].end,newInterval.end);
            }
            i++;
        }
        res.push_back(newInterval);
        while (i<intervals.size())
        {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};