Showing posts with label Divide and Conquer. Show all posts
Showing posts with label Divide and Conquer. Show all posts

Friday, February 10, 2017

Leetcode/各大家-- 380. Insert Delete GetRandom O(1) (Random + Design)

380. Insert Delete GetRandom O(1)
medium
https://leetcode.com/problems/insert-delete-getrandom-o1/
Design a data structure that supports all following operations in average O(1) time.
  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
思路:Use HashMap + ArrayList to build the data structure.
          Map store pairs of <val, index in list> and List is store the val existed.
          They are same size. Add and remove together
          When removal, list: replace the removed element with last added element.
                                    map: replace the index(val) of last added element, and remove val(key)

Complexity: Space: O(N)

ublic class RandomizedSet {
    Map<Integer, Integer> map;//<val, index in arrlist>
    List<Integer> list;//keep a record of value for get random 
    int size;//map and list are the same size
    Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        this.map = new HashMap<>();
        this.list = new ArrayList<>();
        this.size = 0;
        this.rand = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        map.put(val, size);
        list.add(val);
        size++;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(map.containsKey(val)){
            int last = list.get(size - 1);
            list.set(map.get(val), last);//use last added ele to fill the element to be removed 
            map.put(last, map.get(val));//update last added ele's index in list
            map.remove(val);
            list.remove(size - 1);//remove at end is constant
            size--;
            return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(size));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Friday, January 20, 2017

Quicksort

http://me.dt.in.th/page/Quicksort/

Quicksort 
Time:
O(nlgn) - lgn diving n times, n-1 comparsion, when picking pivot int middle, mid pivot is good
worst O(n^2) - pivot happen to be max/min, breaking down list n time, each with n-1 comparison
Space:
O(lgn) for stack

Tips:
avoid worst case by taking few samples and get median to be pivot

Ex:
   *      last
(low-1)|65138479 2(pivot)//1st: 1 & 6 switch 2nd: wall++
1|(in ex: 0)5638479 2
 pivot - bt
switch 1st ele on the right side of wall and switch with pivot
12|(swap at 1 = wall+1)638479 5(newpivot)


Recusive call:
- find pivot
- left (<pivot) wall right( > pivot)

recuse call reach subarray element that len is 1, sorted because been a pivot

public class quicksort {
    public static int partition(int[] arr, int low, int high){
        int pi = arr[high];
        int wall = low - 1;//wall is the index of last element in current sorted part
        for(int i = low; i <= high - 1; i++){//n-1 comparision            
            if(arr[i] <= pi){//swap
                wall++;
                int tmp = arr[wall];
                arr[wall] = arr[i];
                arr[i] = tmp;
            }
        }   
        //1st element right to wall is new pivot > old one        
        if(arr[wall + 1] > pi){
            wall++;
            arr[high] = arr[wall];
            arr[wall] = pi;
        }
        return wall;
    }
    public static void qsort(int[] arr, int low, int high){
        if(low < high){
            int wall = partition(arr, low, high);//wall is sorted
            //diving n times            
            qsort(arr, low, wall-1);//left subarray that val < pi            
            qsort(arr, wall+1, high);//right subarray that val > pi        
        }
    }
    public static void main(String[] args) {
        int[] arr = {6,5,1,3,8,4,9,2};
        qsort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

HackerRank -- Merge Sort Array



import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution { 
    // Main function that sorts arr[l..r] using
    // merge()
public static void sort(int[] arr, int left, int right)
    {
       if (left < right){
           int mid = left + (right-left)/2;
           sort(arr,left,mid);
           sort(arr,mid+1,right);
           merge(arr,left,mid,right);
       }
    }
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    //So arr[k](start from left) add by comparison of arr1[i] &arr2[j]
public static void merge(int arr[], int left, int mid, int right)
    {
        // Find sizes of two subarrays to be merged
        int len1 = mid - left + 1;
        int len2 = right - mid;
        int[] arr1 = new int[len1];
        int[] arr2= new int[len2];
        for(int i=0;i<len1;i++) arr1[i]=arr[left+i];
        for(int i=0;i<len2;i++) arr2[i]=arr[mid+1+i];
        int i=0,j=0;//index for both sub array
        int k = left;
        while(i<len1&&j<len2){
            if(arr1[i] <= arr2[j]){
                arr[k] = arr1[i];
                i++;
            }else{
                arr[k] = arr2[j];
                j++;
            }
            k++;
        }
        while(i<len1) arr[k++] = arr1[i++];
        while(j<len2) arr[k++] = arr2[j++];
    } 
    /* A utility function to print array of size n */
    static void printArray(int[] arr)
    {
        int n = arr.length;
        System.out.print("[");
        for (int i=0; i<n-1; ++i)
            System.out.print(arr[i] + ",");
        System.out.print(arr[n-1]+"]");
    }
 
    // Driver method
    public static void main(String args[])
    {
       Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr= new int[n];    
        for(int i=0;i<n;i++) arr[i]=sc.nextInt();

        sort(arr, 0, arr.length-1);      
        printArray(arr);
        
    }
}

Monday, January 16, 2017

Leetcode/各大家 -- 23. Merge k Sorted Lists (heap or Divide&Conquer)

23. Merge k Sorted Lists(heap or Divide&Conquer)
hard
https://leetcode.com/problems/merge-k-sorted-lists/


思路1: use priority queue to sort nodes (need comparator).
            First add the start of each lists to queue since they're the min of cur sorted list.
            Keep get top from heap and merge it to new list.
            Key is once get the min node from queue, insert the next node of cur list if not null
Complexity: Time O(nlogK) -- for each node insertion in heap O(logK)
                       space O(K) for priority queue, # of k nodes in heap

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            @Override
            public int compare (ListNode o1, ListNode o2){
                return o1.val - o2.val;
            }
        });
        for(int i = 0; i < lists.length; i++ ){
            if(lists[i]!=null)heap.add(lists[i]);
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(!heap.isEmpty()){
            cur.next = heap.remove();
            cur = cur.next;
            if(cur.next != null){//since it's sorted, keep adding the rest of cur list
                heap.add(cur.next);
            }
        }
        return dummy.next;
    }
}

Sunday, January 15, 2017

Leetcode/F家 -- 92. Reverse Linked List II (Iteration)

92. Reverse Linked List II(Iteration)
medium
https://leetcode.com/problems/reverse-linked-list-ii/
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
思路: 4 pointers
1. dummy - track head position (dummy.next = head) case: if head is reversed
2. pre - point to the start of the reversed list  (0 to m-1)
3. start -  point to beginning of sub-list to be reversed(itself val unchanged) (0 to n-m swap)
4. then - point  to the node will be reversed(overall traverse the list)


public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null||head.next==null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i=0;i<m-1;i++)pre = pre.next;
        ListNode start = pre.next, then = start.next;
        for(int i=0;i<n-m;i++){
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        
        return dummy.next;
    }
}

Friday, January 13, 2017

Leetcode -- 148. Sort List (MergeSort)

148. Sort List(MergeSort)
  • Difficulty: Medium
 https://leetcode.com/problems/sort-list/
Sort a linked list in O(n log n) time using constant space complexity.

思路: Use the idea merge sort to recursively half linked list and merge lists
Complexity: O(n log n), Space O(n) for merge

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        // step 1. cut the list to two halves
        ListNode prev = null, slow = head, fast = head;//prev is end of 1st half
        while(fast!=null&&fast.next!=null){
            prev = slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        prev.next = null;
        // step 2. sort each half
        ListNode l1 = sortList(head);//if recursion return sth, need to assign it!
        ListNode l2 = sortList(slow);
        // step 3. merge l1 and l2
        return merge(l1, l2);
    }
  
  ListNode merge(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        if(l1.val<l2.val){
            l1.next = merge(l1.next,l2);
            return l1;
        }else{
            l2.next = merge(l1,l2.next);
            return l2;
        }
  }
}

Iterative way of merge
ListNode merge(ListNode l1, ListNode l2) {
        ListNode l = new ListNode(0), p = l;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1!=null)p.next = l1;
        if(l2!=null)p.next = l2;
        return l.next;
  }

Monday, January 2, 2017

Leetcode/F家--88. Merge Sorted Array(Merge Sort)

88. Merge Sorted Array(Merge Sort)
  • Difficulty: Easy
https://leetcode.com/problems/merge-sorted-array/
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Company: Microsoft Bloomberg Facebook

思路:就是MergeSort的Merge part,建一个tmp array把nums[1]的elements copy过去,
           compare tmp[i] vs nums2[j], store the smaller one in nums[1]
关键字:Merge Sort

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] tmp= new int [m];
        for(int i = 0;i < m;i++){
            tmp[i]=nums1[i];
        }
        int i=0,j=0,k=0;
        while (i<m && j<n){
            if(tmp[i]<nums2[j]){
                nums1[k]=tmp[i];
                i++;
            }else{
                nums1[k]=nums2[j];
                j++;
            }
            k++;
        }
        while (i<m) nums1[k++]=tmp[i++];
        while (j<n) nums1[k++]=nums2[j++];
    }
}

Full Merge sort
https://www.hackerrank.com/contests/hw1/challenges/merge-sort/copy-from/8324041
Sort function:
public void sort(int left, int right, int[] arr){
           if(left<right){
                      int mid = left + (right-left)/2;
                      sort(left,mid);
                      sort(mid+1,right);
                      merge(left,mid,right,arr);
          }
}