How to convert MP4 to GIF

1. Use Wondershare Video Editor to trim the video into xx seconds.

2. Use Final Cut Pro to add credits

3. Export using Compressor

4. Use iMovie to import the video file and export using Quicktime, save file as “Movie to Image Sequence”

5. Use Batch Resize Photos to batch resize all the pictures created by iMovie.

6. Use GIFfun to create gif.

OMG!!!!!!!!!!!! I NEED BETTER SOLUTIONS!!! But anyway, it finally works.

FacebookTwitterGoogle+Share

Leetcode: Merge Intervals

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

/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(intervals==null||intervals.size()<=1){
            return intervals;
        }
        //sort the intervals by the start time.
        //1. convert ArrayList to array
        Interval[] intervalArr = new Interval[intervals.size()];
        int index = 0;
        for(Interval interval:intervals){
            intervalArr[index++] = interval;
        }
        //2. use quick sort to sort intervals by the start time O(nlgn)
        sort(intervalArr,0,intervalArr.length-1);

        //3. only need to compare the new interval with the last interval in the sorted list
        ArrayList<Interval> merged = new ArrayList<Interval>();
        Interval last = intervalArr[0];
        for(int i=1;i<intervalArr.length;i++){
            if(last.end<intervalArr[i].start){
                merged.add(last);
                last = intervalArr[i];
            }else{
                Interval newInterval = new Interval(last.start, Math.max(last.end, intervalArr[i].end));
                last = newInterval;
            }
        }
        merged.add(last);

        return merged;
    }

    public void sort(Interval[] inters,int start, int end){
        int pivot = partition(inters, start, end);
        if(start<pivot-1){
            sort(inters, start, pivot-1);
        }
        if(pivot<end){
            sort(inters, pivot, end);
        }
    }

    public int partition(Interval[] inters, int start, int end){
        int middle = (start+end)/2;
        Interval pivot = inters[middle];

        int i=start;
        int j=end;
        while(i<=j){
            while(inters[i].start<pivot.start){
                i++;
            }

            while(inters[j].start>pivot.start){
                j--;
            }

            if(i<=j){
                swap(inters,i,j);
                i++;
                j--;
            }
        }

        return i;
    }

    public void swap(Interval[] inters, int i, int j){
        Interval tmp = inters[i];
        inters[i] = inters[j];
        inters[j] = tmp;
    }

}

So the overall time complexity is O(nlgn)

Leetcode: Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

 

public int lengthOfLastWord(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s==null||s.length()==0){
            return 0;
        }

        String[] words = s.split(" ");
        String lastword = "";
        if(words.length>0){
            lastword = words[words.length-1];
        }
        return lastword.length();
    }

Remind:
The string “boo:and:foo”, for example, yields the following results with these expressions:
Regex Result
: { “boo”, “and”, “foo” }
o { “b”, “”, “:and:f” }

So in this problem, if the input is ” “, the length of words is 0.

Leetcode: Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

 

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root==null){
            return;
        }
        if(root.left==null){
            flatten(root.right);
            return;
        }
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        if(right!=null){
            //find the right most element in root's left subtree
            //add root's right subtree to the element as a right child
            TreeNode runner = left;
            while(runner.right!=null){
                runner = runner.right;
            }
            runner.right = right;
        }
        root.right=left;
        flatten(left);
        
    }

Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(inorder.length==0){
            return null;
        }
        
        //last element of postorder is the root
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        //find the root element in the inorder array
        //elements occur before it are in its left sub-tree
        //elements occur after it are in its right sub-tree
        int index = 0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                index = i;
                break;
            }
        }
        int[] leftInOrder = new int[index];
        int[] leftPostOrder = new int[index];
        int[] rightInOrder = new int[inorder.length-index-1];
        int[] rightPostOrder = new int[inorder.length-index-1];
        
        for(int i=0;i<inorder.length;i++){
            if(i<index){
                leftInOrder[i] = inorder[i]; 
            }
            if(i>index){
                rightInOrder[i-index-1] = inorder[i];
            }
        }
        
        for(int i=0;i<postorder.length-1;i++){
            if(i<index){
                leftPostOrder[i] = postorder[i];
            }else{
                rightPostOrder[i-index]=postorder[i]; 
            }
        }
        
        root.left = buildTree(leftInOrder,leftPostOrder);
        root.right = buildTree(rightInOrder,rightPostOrder);
        return root;
    }
}