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;
    }