Leetcode: 3Sum Closest in C++

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution:
int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int len = num.size();
        int cloest = INT_MAX;
        int sum =0;
        int left =0;
        int right = len-1;
        int result = 0;
        for(int i=0;i<len-2;i++)
        {
            left = i+1;
            right = len-1;
            while(left<right)
            {
                sum = num[left]+num[i]+num[right];
                if(sum==target)
                   return sum;
                else if(sum>target)
                   right--;
                else
                   left++;
                if(abs(sum-target)<cloest)
                {
                   cloest = abs(sum - target);
                   result = sum;
                }
            }
            
        }
        return result;
    }

Leetcode: Rotate Image in C++

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:

Could you do this in-place?


Solution:
void rotate(vector<vector<int> > &matrix) {
         int n = matrix.size();
         for(int i =0; i<n; i++)
         {
             for(int j=0;j<n;j++)
             {
                 if(i+j<n)
                 swap(matrix[i][j], matrix[n-1-j][n-1-i]);
             }
         }
         for(int i =0; i<n/2; i++)
         {
             for(int j=0;j<n;j++)
             {
                 swap(matrix[i][j], matrix[n-1-i][j]);
             }
         }
    }

Leetcode: Longest Valid Parentheses in C++

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:
int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        int maxv = 0;
        for(int i = n-2; i>=0;i--)
        {
            if(s[i]=='(')
            {
                int j = i+ dp[i+1]+1;
                if(j<n&&s[j]==')')
                dp[i] = 2 + dp[i+1] + dp[j+1];
                maxv = max(dp[i], maxv);
            }
        }
        return maxv;
    }

Leetcode: Median of Two Sorted Arrays in C++

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)).
Either Drop the right side of Bigger one or left side of the small one. 
Solution:
int findMid(int A[], int m,  int B[], int n, int k)
{
        if(m<=0) return B[k-1];
        if(n<=0) return A[k-1];
        if(k<=1)
        return min(A[0], B[0]);
        if(A[m/2]>B[n/2])
        {
            if(m/2+n/2+1<k)
                 return findMid(A, m, B+n/2+1, n - n/2-1, k-n/2-1 );
            else
                return findMid(A, m/2, B, n, k);
        }
        else
        {
            if(m/2+n/2+1<k)
                return findMid(A+m/2+1, m- m/2-1, B, n, k-m/2-1 );
            else
                return findMid(A, m, B, n/2, k);
        }
    }
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if((m+n)%2==0)
        return (findMid(A,m,B,n,(m+n)/2)+findMid(A,m,B,n,(m+n)/2+1))/2.0;
        else
        return findMid(A,m,B,n,(m+n)/2+1);
    }

Leetcode: Remove Nth Node From End of List in C++

Given a linked list, remove the n^th node from the end of list and return its head.
Solution:
ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(!head)
        return NULL;
        ListNode* fast = head;
        for(int i=0;i<n;i++)
           fast = fast->next;
        ListNode* slow = head;
        ListNode* pre = slow;
        if(!fast)
        {
            head = head->next;
            delete slow;
            return head;
        }
        while(fast)
        {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
            pre->next = slow->next;
            delete slow;
            return head;
    }

Leetcode: Container With Most Water in C++

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Solution:
int maxArea(vector<int> &height) {
        int max = 0;
        int len =height.size();
        int start =0;
        int end =len-1;
        while(start<end)
        {
            int curL = height[start];
            int curR = height[end];
            int area = (end-start)*min(curL, curR);
            if(area>max)
            max = area;
            if(curL>curR)
            {
                while(end>start&&height[end]<=curR)
                end--;
            }
            else
            {
                while(end>start&&height[start]<=curL)
                 start++;
            }
        }
        return max;
    }

Leetcode: String to Integer (atoi) in C++

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution:
int atoi(const char *str) {
        double result = 0;
        int len = strlen(str);
        int i = 0;
        int flag = true;
        while(i<len&&str[i]==' ')
             i++;
        if(i<len&&(str[i]=='-'||str[i]=='+'))
        {
           flag = str[i]=='-'?false:true;
           i++;
        }
        for(;i<len;i++)
        {
            if(str[i]<'0'||str[i]>'9'||str[i]==' ')
               break;
            result = 10*result+(str[i]-'0');
            if(result>INT_MAX&&flag)
               return INT_MAX;
            if(result-1>INT_MAX&&!flag)
               return INT_MIN;
        }
        if(!flag)
        result = -result;
        return result;
    }

Leetcode: Longest Substring Without Repeating Characters in C++

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.
Solution:
int lengthOfLongestSubstring(string s) {
        vector<int> curmap(256,-1);
        int n = s.size();
        int curlen = 0;
        int maxlen = 0;
        int curstart = 0;
        for(int i=0;i<n;i++)
        {
            int current = curmap[s[i]];
            if(current==-1)
            {
               curmap[s[i]] = i;
               curlen++;
               if(maxlen<curlen)
                 maxlen = curlen;
            }
            else
            {
                while(curstart<=current)
                {
                    curmap[s[curstart]] = -1;
                    curstart++;
                }
                curlen = i-current;
                curmap[s[i]] = i;
            }
            
        }
        return maxlen;
    }

Leetcode: Longest Palindromic Substring in C++

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Solution:
void search(string& s, int& left, int& right, int curL, int curR)
    {
        while(curL>=0&&curR<s.size())
        {
                if(s[curL]!=s[curR])
                  break;
                curL--;
                curR++;
        }
        curL++;
        curR--;
        if(curR-curL>right-left)
        {
           left = curL;
       right = curR;
        }
    }
    string longestPalindrome(string s) {
        int maxlength = INT_MIN;
        int left  = 0;
        int right = 0;
        int pos = 0;
        while(pos<s.size()-1)
        {
            search(s, left, right,pos, pos);
            search(s, left, right,pos, pos+1);
            pos++;
        }
        return s.substr(left, right-left+1);
    }

Leetcode: Search for a Range in C++

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


Solution:
vector<int> searchRange(int A[], int n, int target) {
        vector<int> result(2, -1);
        int start =0;
        int end =n-1;
        int mid =0;
        while(start<=end)
        {
            mid = start+(end-start)/2;
            if(A[mid]==target)
            {
                int left = mid;
                int right = mid;
                while(left>=0&&A[left]==target) left--;
                while(right<n&&A[right]==target) right++;
                left++;
                right--;
                result[0] = left;
                result[1] = right;
                return result;
            }
            else if(A[mid]>target)
                end = mid-1;
            else
                start = mid+1;
        }
        return result;
    }

Leetcode: Swap Nodes in Pairs in C++

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.

Solution:

ListNode *swapPairs(ListNode *head) {
        if(!head)
        return NULL;
        ListNode* result;
        if(head->next)
        result = head->next;
        else
        return head;
        ListNode* cur = NULL;
        ListNode* pre = NULL;
        while(head&&head->next)
        {
            cur = head->next->next;
            head->next->next = head;
            if(pre)
            pre->next = head->next;
            head->next = NULL;
            pre = head;
            head = cur;
        }
        if(head&&pre)
        pre->next = head;
        return result;
    }

Leetcode: Multiply Strings in C++

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution:

string multiply(string num1, string num2) {
       int s1 = num1.size();
       int s2 = num2.size();
       string result(s1+s2+1, '0');
       std::reverse(num1.begin(),num1.end());
       std::reverse(num2.begin(),num2.end());
       int digit1 = 0;
       int carry = 0;
       for(int i =0;i<s1;i++)
       {
           digit1 = num1[i] - '0';
           carry = 0;
           for(int j=0;j<s2;j++)
           {
               int digit2 = num2[j] - '0';
               int exist = result[i+j] - '0';
               result[i+j] = (digit1*digit2+exist+carry)%10 + '0';
               carry = (digit1*digit2+exist+carry)/10;
           }
           if(carry>0)
           {
               result[i+s2] = carry+'0';
           }
       }
       std::reverse(result.begin(),result.end());
       int start = 0;
       while(result[start]=='0'&&start<result.size()) // skip leading '0'
       {
           start++;
       }
       if(start == result.size())
       return "0";
       else
       return result.substr(start);
    }

Code Practice: Reverse Linked List in C++

Node* ReverseLinkedList(Node* root)
{
     if(!root)
      return NULL;
      Node* pre = root;
      Node* next = root->next;
      root->next = NULL;
      while(root->next)
     {
           root = next
           next = root->next;
           root->next = pre;
           pre = root;
     }
      return root;
}

Leetcode: Substring with Concatenation of All Words in Java

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Solution:
public ArrayList<Integer> findSubstring(String S, String[] L) {
        HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
        HashMap<String, Integer> Smap = new HashMap<String, Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        int total = L.length;
        if(total==0)
        return result;
        for(int i=0;i<total;i++)
        {
            if(!Lmap.containsKey(L[i]))
            Lmap.put(L[i], 1);
            else
            {
                int k = Lmap.get(L[i]);
                Lmap.put(L[i], k+1);
            }
        }
        int len = L[0].length();
        for(int i=0;i<=S.length()-len*total;i++)
        {
            Smap.clear();
            int j = 0;
            for(;j<total;j++)
            {
                String s = S.substring(i+j*len, i+(j+1)*len);
                if(!Lmap.containsKey(s))
                    break;
                if(!Smap.containsKey(s))
                Smap.put(s, 1);
                else
                {
                    int k = Smap.get(s);
                    Smap.put(s, k+1);
                }
                if(Smap.get(s)>Lmap.get(s))
                    break;
            }
            if(j==total)
            {
                result.add(i);
            }
        }
        return result;
    }

Leetcode: Next Permutation in Java

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,23,2,1 → 1,2,31,1,5 → 1,5,1


Solution:
public void nextPermutation(int[] num) {
        int size = num.length-1;
        if(size<=0)
            return;
        int nonorder = 0;
        int tmp = 0;
        while(size>0&&num[size]<=num[size-1])
        {
            size--;
        }
        nonorder = size;
        if(nonorder>0)
        {
            nonorder--;
            size = num.length-1;
            while(size>=0&&num[size]<=num[nonorder])
            {
                size--;
            }
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
        }
        size =  num.length-1;
        while(nonorder<size)
        {
            tmp = num[size];
            num[size] = num[nonorder];
            num[nonorder] = tmp;
            nonorder++;
            size--;
        }
    }

Leetcode: Implement strStr() in C++

Implement strStr().

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

Solution:
char *strStr(char *haystack, char *needle) {
        int lenA = strlen(haystack);
        int lenB = strlen(needle);
        if(lenA>=0&&lenB==0)
        return haystack;
        if(lenA==0)
        return NULL;
        vector<int> next(lenB, 0);
        next[0] = -1;
        int cur = 0;
        int k =-1;
        while(cur<lenB-1)
        {
            if(k==-1||needle[cur]==needle[k])
            {
                cur++;
                k++;
                next[cur] = k;
            }
            else
                k = next[k];
        }
        k = -1;
        int curA = 0;
        int curB = 0;
        while(curA<lenA)
        {
            if(curB==-1||haystack[curA]==needle[curB])
            {
                curA++;
                curB++;
            }
            else
                curB = next[curB];
            if(curB == lenB)
                return &haystack[curA-curB];
        }
        return NULL;
    }

Leetcode: Valid Sudoku in C++

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Solution:
bool isValidSudoku(vector<vector<char> > &board) {
        vector<int> row(9, 0);
        vector<int> column(9, 0);
        vector<int> row1 = row;
        vector<int> column1 = column;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    if(row[board[i][j]-49]!=0)
                       return false;
                     else
                       row[board[i][j]-49] = 1;
                }
                if(board[j][i]!='.')
                {
                    if(column[board[j][i]-49]!=0)
                       return false;
                     else
                       column[board[j][i]-49] = 1;
                }
            }
            row = row1;
            column = column1;
        }
        for(int i=0;i<9;i+=3)
        {
            for(int j=0;j<9;j+=3)
            {
                for(int m=0;m<3;m++)
                {
                    for(int n=0;n<3;n++)
                    {
                        if(board[m+i][n+j]!='.')
                        {
                           if(row[board[m+i][n+j]-49]!=0)
                             return false;
                           else
                             row[board[m+i][n+j]-49] = 1;
                        }
                    }
                }
                row = row1;
            }
        }
        return true;
    }

Leetcode: Spiral Matrix in C++

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

Solution:
void spiral_input(vector<vector<int>> s,int lx,int ly,int m,int n, vector<int>& result)
    {
    if(m<=0||n<=0)
return;
for(int i=0;i<n;i++)
result.push_back(s[lx][ly+i]);
for(int i=1;i<m;i++)
result.push_back(s[lx+i][ly+n-1]);
    if(m!=1)
    {
        for(int i=n-2;i>=0;i--)
    result.push_back(s[lx+m-1][ly+i]);
    }
if(n!=1)
    {
        for(int i=m-2;i>=1;i--)
    result.push_back(s[lx+i][ly]);
    }
spiral_input(s,lx+1,ly+1,m-2,n-2, result);
    }
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> result;
        if(matrix.size()==0)
        return result;
        spiral_input(matrix,0,0,matrix.size(),matrix[0].size(),result);
        
    }

Leetcode: Letter Combinations of a Phone Number in C++

Given a digit string, return all possible letter combinations that the number could represent.
Solution:
vector<char> switchchar(char input)
    {
    vector<char> result;
switch(input)
{
case '2':
result.push_back('a');
result.push_back('b');
result.push_back('c');
break;
case '3':
result.push_back('d');
result.push_back('e');
result.push_back('f');
break;
case '4':
result.push_back('g');
result.push_back('h');
result.push_back('i');
break;
case '5':
result.push_back('j');
result.push_back('k');
result.push_back('l');
break;
case '6':
result.push_back('m');
result.push_back('n');
result.push_back('o');
break;
case '7':
result.push_back('p');
result.push_back('q');
result.push_back('r');
result.push_back('s');
break;
case '8':
result.push_back('t');
result.push_back('u');
result.push_back('v');
break;
case '9':
result.push_back('w');
result.push_back('x');
result.push_back('y');
result.push_back('z');
break;
   }
   return result;
    }
    void helper(string digits, string cur, int num, vector<string>& result )
    {
        if(num==digits.size())
        {
            result.push_back(cur);
        }
        char digit = digits[num];
        vector<char> option = switchchar(digit);
        for(int i=0;i<option.size();i++)
        {
            helper(digits, cur+option[i], num+1, result);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string cur = "";
        helper(digits, cur, 0, result);
        return result;
    }