[LeetCode/LintCode] Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int first = 0, second = 0, sum=0;
        int minLen = INT_MAX;
        while(first<nums.size())
        {
            if(sum>=s)
            {
                minLen = min(minLen, second-first);
                sum -= nums[first++];
                continue;
            }
            if(second == nums.size()) break;
            sum += nums[second++];
        }
        return minLen == INT_MAX ? 0 : minLen;
    }
};

[LintCode] Sort Letters by Case

Given a string which contains only letters. Sort it by lower case first and upper case second.

Example

For "abAcD", a reasonable answer is "acbAD"

Note

It's not necessary to keep the original order of lower-case letters and upper case letters.

Challenge

Do it in one-pass and in-place.

class Solution {
public:
    void sortLetters(string &letters) {
        // write your code here
        int len = letters.length();
        int cur = -1;
        for(int i=0;i<len;i++)
        {
            if(cur == -1)
            {
                if(islower(letters[i])) continue;
                cur = i;
            }
            else if(islower(letters[i]))
            {
               swap(letters[cur++], letters[i]);
            }
        }
    }
};

[LeetCode] Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Analysis:

We can find the first row whose first element is less than target, and search within that row.

Alternatively, we can take the whole matrix as an array and binary search from start to end.

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int size = matrix.size();
        if(0 == size) return false;
        
        int len = matrix[0].size();
        if(0 == len) return false;
        int start = 0, end = size*len-1;
        
        while(start <= end)
        {
            int mid = start + (end-start)/2;
            int col = mid % len;
            int row = mid / len;
            if(matrix[row][col] > target) end = mid - 1;
            else if(matrix[row][col] < target) start = mid + 1;
            else return true;
        }
        return false;       
    }
};

[LeetCode] Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Analysis:

start            1          pivot              2           end

Let's do a binary search. If mid > target, there is only one case where we need to move the start pointer, i.e. target falls in interval 2, and mid falls in interval 1. For other cases, we need to move the end pointer.

If mid < target, there is only one case where we need to move the end pointer, i.e. target falls in interval 1 and mid falls in interval 2. For other cases, we need to move the start pointer.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0 ;
        int end = nums.size() - 1;
        while(start <= end)
        {
            int mid = start + (end-start)/2;
            if(nums[mid] == target) return mid;
            
            if(nums[mid] > target)
            {
                if(target <= nums[end] 
                    && nums[mid] > nums[end])
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
            else
            {
                if(target > nums[end] 
                    && nums[mid] < nums[end])
                {
                    end = mid - 1;
                }
                else
                {
                    start = mid + 1; 
                }
            }
        }
        return -1;
    }
};

[LeetCode] Trapping Rain Water

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. 

Analysis: From the left for each index i, find the next index j whose value is larger than or equal to i, so that the interval between i and j may trap some water. And repeat the procedure from j till end. Do the same from right, but only find the next index whose value is larger than it to avoid duplication.

class Solution 
{
    static bool lt(int a, int b){return a>b;}
    static bool le(int a, int b){return a>=b;}
    
    int trap(vector<int>& height, 
        const function <bool (int, int)>& comp) 
    {   
        int res =0, i=0, sum=0;
        int l = i++;
        for(;i<height.size();i++)
        {
            if(comp(height[i],height[l]))
            {
                res += max(0,(i-l-1)* height[l]-sum);
                l = i;
                sum = 0;
            }
            else sum += height[i];
        }
        return res;
    }
public:
    int trap(vector<int>& height)
    {
        int leftValue = trap(height, le);
        reverse(height.begin(), height.end());
        int rightValue = trap(height, lt);
        return leftValue + rightValue;
    }
};

[LeetCode] Minimum Window Substring

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.

class Solution {
public:
    string minWindow(string s, string t) {
        
        if(t.empty()) return "";
        vector<int> set(128,0), found(128,0);
        for(int i=0;i<t.length();i++) set[t[i]]++;
        queue<int> indexQueue;

        int minLen = INT_MAX, minStart=0, minEnd=0;
        int start = 0, end = start, ocurrence = 0;
        
        while(true){
            
            if(ocurrence < t.length())
            {
                while(end<s.length() && !set[s[end]]) end++;
                if(end == s.length()) break;
                char c = s[end];
                indexQueue.push(end);
                found[c] ++;
                
                if(found[c] <= set[c]) ocurrence ++;
                end ++;
            }
            
            while(ocurrence == t.length()){
                start = indexQueue.front();
                indexQueue.pop();
                if(found[s[start]]==set[s[start]])
                    ocurrence --;
                
                found[s[start]] --;
                int cur = end - start;
                if(cur < minLen)
                {
                    minLen = cur;
                    minStart = start;
                    minEnd = end;
                }
            }
        }
        return s.substr(minStart, minEnd-minStart);
    }
};

[LeetCod] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Analysis:
We need to maintain two points -- one for the tail of the nodes which are less than x, the other for the tail of the node which are greater than or equal to x. Loop the list, for any node, it will be following either of the tails.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode dummy(0);
        ListNode *sTail = &dummy, *lTail;
        sTail->next = head;
        ListNode *p = head;
        while(p)
        {
            if(p->val < x)
            {
                if(sTail->next != p)
                {
                    lTail->next = p->next;
                    p->next = sTail->next;
                    sTail->next = p;
                }
                sTail = p;
            }
            else
            {
                lTail = p;
            }
            p = p->next;
        }
        return dummy.next;
    }
};

[LeetCode] 3Sum Closest

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

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        
        int diff = INT_MAX; 
        int res = 0;
        
        for(int i=0;i<num.size()-2;i++)
        {
            if(i && num[i] == num[i-1]) continue;
            int start = i + 1;
            int end = num.size() - 1;

            while(start < end)
            {
                int sum = num[start] + num[end] + num[i];

                if(sum == target)
                {
                    return target;
                }
                int k = abs(sum-target);
                if(k < diff)
                {
                    diff = k;
                    res = sum;
                }
                
                sum > target ? end-- : start++;
                
            }
        }
        
        return res;
    }
};

[LeetCode] 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        int size = num.size();
        if(size < 3) return res;
        
        sort(num.begin(), num.end());
        
        for(int i=0;i<size-2;i++)
        {
            //thats key to avoid duplication!
            if(i && num[i] == num[i-1])continue;
            int start = i + 1;
            int end = size - 1;
            
            while(start < end)
            {
                int v = num[i]+num[start]+num[end];
                if(v < 0)
                {
                    start ++;
                }
                else if(v > 0)
                {
                    end --;
                }
                else
                {
                    vector<int> rec({num[i],num[start],num[end]});
                    res.push_back(rec);
                    start ++; end--;
      while (start<end&&num[start]==num[start - 1])
            start++;
                }
            }
        }
        return res;
    }
};

[LeetCode] Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.

class Solution {
public:
    int maxArea(vector& height) {
        int right = height.size() - 1;        
        int left = 0;
        int maxCap =0; 
        while(left<=right)
        {
            int sub = min(height[left], 
                    height[right])*(right-left);

            maxCap = max(maxCap, sub);
            if(height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return maxCap;
    }
};