Leetcode–Merge Two Sorted Lists

The Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Notes:

  1. This is a basic question, just pay attention to the head and null.

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(l1!=null && l2 != null){
            if(l1.val < l2.val){
                pre.next = l1;
                l1 = l1.next;
            }
            else{
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        if(l1!= null){
            pre.next = l1;
        }
        if(l2!= null){
            pre.next = l2;
        }
        return fkHead.next;
    }
}
Advertisements

Leetcode–Merge k Sorted Lists

The Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Notes:

  1. First straightforward solution: just like doing merge two sorted list. Examine head node of each list, add the min one to result, complexity is O(k*k*n), k is number of lists, n is number of element in each list.
  2. A better solution is to maintain a priority queue of k candidates from each list, each iteration update the queue and get the min number, no need to traverse k numbers again to get min, complexity is O(k*n).

Java Solution I

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        int k = lists.size();
        if(k==0) return null;
        ListNode[] pointers = new ListNode[k];
        for(int i = 0; i < k; i++){
            pointers[i] = lists.get(i);
        }
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(true){
            int min = Integer.MAX_VALUE;
            int useindex = -1;
            for(int i = 0; i < k; i++){
                if(pointers[i] != null && pointers[i].val < min){
                    min = pointers[i].val;
                    useindex = i;
                }
            }
            if(useindex==-1)
                break;
            pre.next = pointers[useindex];
            pre = pre.next;
            pointers[useindex] = pointers[useindex].next;
        }
        pre.next = null;
        return fkHead.next;
    }
}

Java Solution II

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        int k = lists.size();
        if(k==0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue(k, new NodeComp());

        for(int i = 0; i < k; i++){
            if(lists.get(i)!= null){
                queue.add(lists.get(i));   
            }
        }
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(true){
            if(queue.size()==0)
                break;
            ListNode min = queue.poll();
            pre.next = min;
            pre = pre.next;
            if(min.next != null)
                queue.add(min.next);
        }
        pre.next = null;
        return fkHead.next;
    }
    
    
}
class NodeComp implements Comparator<ListNode>{
    public int compare(ListNode a, ListNode b){
        return a.val-b.val;
    }
}

Leetcode–Merge Intervals

The Problem:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Notes:

  1. First needs to sort the list by the start of intervals, use Java collections.sort, but need to implement a comparator.
  2. While iterating the list, record the previous one, if found overlap, update the previous one with merged end, then delete the current one.

Java Solution

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size()==0) return intervals;
        Collections.sort(intervals, new Comp());
        
        ListIterator<Interval> iterator = intervals.listIterator();
        Interval pre = iterator.next();
        while(iterator.hasNext()){
            Interval cur = iterator.next();
            if(cur.start > pre.end){
                pre = cur;
                continue;
            }
            else{
                pre.end = Math.max(pre.end, cur.end);
                iterator.remove();
            }
        }
        return intervals;
    }
}

class Comp implements Comparator<Interval>{
    public int compare(Interval a, Interval b){
        return a.start-b.start;
    }
}

Leetcode–Insert Interval

The Problem:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Notes:

  1. The original list is valid, so we can take advantage of that, when traversing the list, if the new interval overlap with any in the original list, remove the one in the list, and update the new interval to the merge of those two.
  2. Use iterator to operate (add/remove) on the list at the same time of traversing. Note that when doing add(), should go to previous first, because when get to know the location of add, in fact we need add in front of current.
  3. To make the code concise and easy to read : For the condition to find overlapping can be very messy to list 4 overlapping ways, instead find those no-overlapping case first, and all overlapping case will be in else, then the merge can be done using Math.min/max instead of consider each case individually.

Java Solution

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals.size()==0 ){
            intervals.add(newInterval);
            return intervals;
        }
        
        ListIterator<Interval> iterator = intervals.listIterator();
        boolean added = false;
        while(iterator.hasNext()){
            Interval  iter= iterator.next();
            
            if(iter.end < newInterval.start){
                continue;
            }
            else if (iter.start > newInterval.end){
                iterator.previous();
                iterator.add(newInterval);
                return intervals;
            }
            else{
                newInterval.start = Math.min(newInterval.start, iter.start);
                newInterval.end = Math.max(newInterval.end, iter.end);
                iterator.remove();
            }

        }
        intervals.add(newInterval);
        return intervals;
    }
}

Leetcode–Convert Sorted List to Binary Search Tree

The Problem:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Notes:

  1. Similar to Convert Sorted Array to Binary Search Tree, but in this problem we don’t have easy access to the middle element.
  2. A bottom-up approach is used here, the treenodes will be constructed by the order of listnode in p. The trick is keep a pointer to the current ListNode p, p is “global” and gets updated in each recursion. So inside each recursion, treenode should be constructed exactly in order left->parent->right, because p will get updated in branches also.

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode p; // p need to be passed in and out of constructTree
    public TreeNode sortedListToBST(ListNode head) {
        int len = getLength(head);
        if(len == 0) return null;
        p = head;
        return constructTree(0, len-1);
    }
    
    private int getLength(ListNode head){
        int len = 0;
        while(head!= null){
            head = head.next;
            len++;
        }
        return len;
    }
    
    private TreeNode constructTree(int start, int end){
        if(start > end) return null;
        int mid = (start+end)/2;
        TreeNode parent = new TreeNode(0);
        //--!!--here the order should be :
        // 1. left (p got updated there also) 2. parent (AND UPDATE p) 3. right
        parent.left = constructTree(start, mid-1);
        parent.val = p.val;
        p = p.next;
        parent.right = constructTree(mid+1, end);
        return parent;
    }
}

Leetcode–Permutation Sequence

The Problem:

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Notes:

  1. The key is to use an array or list to record the numbers to be added, then can access that number just according to the index calculated from k. Also I used linkedlist to store the numbers which makes it easier to remove each number after chosen.
  2. input k should be decreased first before treating as index

Java Solution

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new LinkedList<Integer>();
        int multiplys = 1;
        for(int i= 0; i<n; i++){
            multiplys= multiplys*(i+1);
            numbers.add(i+1);
        }
        
        k--; //---!! k is not array index
        StringBuilder result  = new StringBuilder();
        for(int i =0; i < n; i++){
            multiplys = multiplys/(n-i);
            int index = k/multiplys;
            result.append(numbers.get(index));
            numbers.remove(index);
            k = k%multiplys;
        }
        return result.toString();
    }
}

Leetcode–Permutations II

The Problem:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Notes:

  1. Solution 1 is just same as Permutations, with a hash set to check if the list is already in the result. Could directly use list.toString() and store the string in set to check for duplicates.
  2. Solution 2 I will add later…

Java Solution I:

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(num.length==0)return result;
        
        HashSet<String> set = new HashSet<String>();
        List<Integer> first = new LinkedList<Integer>();
        first.add(num[0]);
        result.add(first);
        
        for(int i = 1; i < num.length; i++){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(int j = 0; j < result.size(); j++){
                List<Integer> one = result.get(j);
                for(int k = 0; k <= one.size(); k++){
                    List<Integer> newone = new LinkedList<Integer>(one);
                    newone.add(k, num[i]);
                    if(!set.contains(newone.toString())){
                        temp.add(newone);
                        set.add(newone.toString());
                    }
                }
            }
            result = temp;
        }
        return result;
    }
}