Showing posts with label Two Pointers. Show all posts
Showing posts with label Two Pointers. Show all posts

Tuesday, March 7, 2017

Leetcode/各大家 -- 147. Insertion Sort List

147. Insertion Sort List(2 Ptr)
Medium
https://leetcode.com/problems/insertion-sort-list/?tab=Description
Sort a linked list using insertion sort.

思路: Use dummy head to point sorted list. Maintain 2 parts: sorted | unsorted.
          Use 2 ptr(cur-> current element & pre -> end of sorted list). When meeting invalid cur,
          Insert cur into sorted list by comparing with dummy head

Complexity: Time O(N^2) Space O(1)

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode pre = head;
        ListNode cur = head;
        dummy.next = pre;
        while(cur != null){
            if(pre.val > cur.val){
                pre.next = cur.next;
                ListNode headN = dummy;
                while(headN.next != null && headN.next.val < cur.val){
                    headN = headN.next;
                }
                cur.next = headN.next;
                headN.next = cur;
                cur = pre.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

Tuesday, January 31, 2017

Leetcode/G家 -- 159. Longest Substring with At Most Two Distinct Characters(window 2 ptr)

159. Longest Substring with At Most Two Distinct Characters (window 2 ptr)
Hard
https://leetcode.com/problems/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.
思路: Use window method, counter to track distinct character, when counter > 2, remove one distinct character(till count = 0) to track next substring.

public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        int counter = 0, len = 0;
        while(end < s.length()){
            char cur = s.charAt(end);
            if(!map.containsKey(cur)) map.put(cur, 0);
            map.put(cur, map.get(cur) + 1);
            if(map.get(cur) == 1) counter++;//new distinct char
            while(counter > 2){//
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) - 1);
                if(map.get(c2) == 0) counter--;
                start++;
            }
            len = Math.max(end - start + 1, len);
            end++;
        }
        return len;
    }

Leetcode/亚麻 -- 438. Find All Anagrams in a String (window2ptr)

438. Find All Anagrams in a String(window 2ptr)
easy
https://leetcode.com/problems/find-all-anagrams-in-a-string/
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

思路: string window套路 using 2 pointer, key is to check 'end - start + 1 == t.length()' to find valid anagram.
Complexity: O(N) time - loop, O(N) space - map

public class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        List<Integer> res = new ArrayList<Integer>();
        Map<Character, Integer> map = new HashMap<Character, Integer>();//<all char, freq in t>
        for(char c : s.toCharArray()) map.put(c, 0);
        for(char c : t.toCharArray()){
            if(map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else 
                return res;
        }
        int start = 0, end = 0;
        int counter = t.length();
        while(end < s.length()){
            char cur = s.charAt(end);
            if(map.get(cur) > 0) counter--;
            map.put(cur, map.get(cur) - 1);
            while (counter == 0){
                if(end - start + 1 == t.length()) res.add(start);
                char c2 = s.charAt(start);
                map.put(c2, map.get(c2) + 1);
                if(map.get(c2) > 0) counter++;
                start++;
            }
            end++;
        }
        return res;
    }
}

Sunday, January 22, 2017

Leetcode/F家 -- 209. Minimum Size Subarray Sum(window: two ptr)

209. Minimum Size Subarray Sum(window: two ptr)
Medium
https://leetcode.com/problems/minimum-size-subarray-sum/
相关题: http://rainykat.blogspot.com/2017/01/leetcode-76-minimum-window-substring.html
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

思路: 2 pointers. i is the start of subarray, j is end, keep tracking min of len = j-i +1;
          Outerloop: j<nums.length Since keep a window [i,j] subarray end at j,
          Innerloop: while(sum>=s) keep subtracting i, update len is min


public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length + 1;//any max value to be overwrite
        int i = 0, j = 0;
        int sum = 0;
        while(j < nums.length){//find min subarray[i,j]
            sum += nums[j];
            while(sum >= s){
                len = Math.min(len, j - i + 1);//i is valid at this point
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return len == nums.length + 1 ? 0:len;
    }

Thursday, January 19, 2017

Leetcode/G家 -- 259. 3Sum Smaller (3 ptr)

259. 3Sum Smaller (3 ptr)
Medium
https://leetcode.com/problems/3sum-smaller/
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
思路: like three sum. When calculating count, if sum < target, count += k-j since nums[i] + nums[j] + elements after k will also have sum<target.


public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int count = 0;
        Arrays.sort(nums);
        for (int i = 0; i + 2 < nums.length; i++) {
            int j = i + 1, k = nums.length - 1;  
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < target) {
                    count += k-j;//eg [-2,0,1,3] 4,so -2,0,3满足,-2,0,1也满足
                    j++;
                } else {
                    k--;
                }
            }
        }
        return count;
    }
}

Leetcode/Bloomberg -- 16. 3Sum Closest(3 ptr)

16. 3Sum Closest (3 ptr)
medium
https://leetcode.com/problems/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).

思路: like 3 sum,closes means calculate abs diffrenence, default res is sum of first 3 elements

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res = nums[0] + nums[1] + nums[nums.length - 1];
        for(int i = 0; i+2 < nums.length; i++){
            int j = i+1, k = nums.length - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > target){
                    k--;
                }else{
                    j++;
                }
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
            }
        }
        return res;
    }
}

Leetcode/各大家 -- 26.80. Remove Duplicates from Sorted Array (two ptr)


26.80 Remove Duplicates from Sorted Array (Two ptr)


easy & medium
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
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 nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
80. allowing 2 dup
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

思路: Two pointer: i iterate array. j point to the 1st pos after end of the non-dup array, which is length
Use dup to track the last number in non-dup arrary. Till i find a number: nums[i] != dup, overwrite j with i and move j forward, update dup to nums[i]
public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 1){return nums.length;}
        int dup = nums[0];
        int j = 1;//j point to the 1st post after last ele of non dup arr
        for(int i = 1; i < nums.length; i++){
            if(nums[i]!=dup){
                nums[j] = nums[i];
                dup = nums[i];
                j++;
            }
        }
        return j;
    }
}

思路: 2nd part, is just we need to keep 2 dup #, if nums[i] == dup1, it indicates there are >3 dups. Keep iterating until find a distinct nums[i] to dup1, update dup1 to dup2, and update dup2 to nums[i] 
eg: [0,0,1,1]

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2) return nums.length;
        int dup1 = nums[0];
        int dup2 = nums[1];
        int j = 2;//point to 1st pos after last ele of non-dup arr = length
        for(int i = 2; i < nums.length; i++ ){
            if(nums[i] != dup1){//find the next distinct # to overwrite dup
                nums[j] = nums[i];
                j++;
                dup1 = dup2;
                dup2 = nums[i];
            }//else we have >=3 dup
        }
        return j;
    }
}

Monday, January 16, 2017

Leetcode/F家微软 -- 75. Sort Colors(two pointer & counting sort)

75. Sort Colors (two pointer & counting sort)
 Medium
https://leetcode.com/problems/sort-colors/
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

解法1:3 pointer: 'i' point to the current position ,'left' point to the position right after 0, 'right' point to the position right before 2.


public class Solution {
    public void sortColors(int[] nums) {
        int i=0,left = 0,right=nums.length-1;
        while(i<=right){
            if(nums[i]==0){
                swap(nums,i,left);
                left++;
                i++;//left side is sorted already
            }else if(nums[i]==2){
                swap(nums,i,right);
                right--;
            }else{
                i++;//skip 1
            }
        }
    }
    public void swap(int[]nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

解法2: counting sort-- count frequency of 0,1,2 in nums. And fill back to nums.

public class Solution {
    public void sortColors(int[] nums) {
        int[] freq = new int[3];
        for(int i=0;i<nums.length;i++){
            freq[nums[i]]+=1;
        }
        int j = 0;//j is index in nums
        for(int i=0;i<freq.length;i++){
            int count  = freq[i];
            while (count>0){
                nums[j] = i;
                j++;
                count--;
            }
        }
    }
}

Leetcode/G家 344.345. Reverse Vowels of a String (2pointer)

345. Reverse Vowels of a String(2pointer)
easy
https://leetcode.com/problems/reverse-vowels-of-a-string/
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
思路: convert to char array, use two pointer: i - track the vowel from begin; j - track the vowel from end
          once both i & j point to vowel, swap char

public class Solution {
    public String reverseVowels(String s) {
        char[] word = s.toCharArray();
        Set<Character> set = new HashSet<Character>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        int i = 0,j = word.length-1;
        while(i<j){
            char a = word[i];
            char b = word[j];
            if(!set.contains(a)){
                i++;
            }else if(!set.contains(b)){
                j--;
            }else{//a & b both vowel
                word[i] = b;
                word[j] = a;
                i++;
                j--;
            }
        }
        return new String(word);
    }
}

304, simply reverse string

思路: use two pointer i from start, j from end, keep swaping i++, j-- while i < j
public class Solution {
    public String reverseString(String s) {
        char[] word = s.toCharArray();
        int i = 0,j = word.length-1;
        while(i<j){
            char tmp = word[i];
            word[i] = word[j];
            word[j] = tmp;
            i++;
            j--;
        }
        return new String(word);
    }
}