Daily Archives: March 15, 2013

Leetcode: Remove Element

Posted on by
Reply

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

 

public int removeElement(int[] A, int elem) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A==null||A.length==0){
            return 0;
        }
        int end = A.length-1;
        int index = 0;
        while(index<=end){
            if(A[index]==elem){
                swap(A, index, end);
                end--;
            }else{
                index++;
            }            
        }
        return end+1;
    }
    
    public void swap(int[] A, int i, int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
FacebookTwitterGoogle+Share

Leetcode: Swap Nodes in Pairs

Posted on by
Reply

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

 //non-recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode runner = head;
        ListNode newHead = null;
        ListNode tail = null;
        while(runner!=null && runner.next!=null){
            ListNode runnernext = runner.next;
            ListNode runnernextnext = runnernext.next;
            if(tail!=null){
                tail.next = runnernext;                
            }else{
                newHead=runnernext;
            }
            runnernext.next = runner;
            runner.next = null;
            tail=runner;
            runner = runnernextnext;
        }
        if(runner!=null){
            tail.next = runner;
        }
        return newHead;
    }
//recursive version
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head==null||head.next==null){
            return head;
        }
        ListNode headnext =head.next;
        ListNode headnextnext=headnext.next;
        head.next = swapPairs(headnextnext);
        headnext.next=head;
        return headnext;
    }

Leetcode: Permutation Sequence

Posted on by
Reply

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.

public String getPermutation(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> nums = new ArrayList<Integer>();
        for(int i=1;i<=n;i++){
            nums.add(i);
        }
        k--;//k originally starts from 1
        int index=0;
        while(k!=0){
            int frac = frac(n-index-1);
            int targetNumIndex = k/frac+index;
            int targetNum = nums.remove(targetNumIndex);
            nums.add(index,targetNum);
            index++;
            k=k%frac;
        }
        String output = "";
        for(Integer num:nums){
            output+=num;
        }
        return output;
    }
    
    public int frac(int n){
        int sum = 1;
        for(int i=1;i<=n;i++){
            sum*=i;
        }
        return sum;
    }

 

Leetcode: Binary Tree Level Order Traversal

Posted on by
Reply

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

 

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

1. One Queue Solution — Better

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    //one queue
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root != null) {
        q.offer(root);
    }
    while (!q.isEmpty()) {
        ArrayList<Integer> levelNodes = new ArrayList<>();
        int size = q.size(); //this is the # of nodes in current level
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();
            levelNodes.add(curr.val);
            if (curr.left != null) {
                q.offer(curr.left);
            }
            if (curr.right != null) {
                q.offer(curr.right);
            }
        }
        result.add(levelNodes);
    }
    return result;
}

2. Two Queues Solution — Easier to Understand

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> output= new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return output;
        }
        ArrayList<TreeNode> current = new ArrayList<TreeNode>();
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        current.add(root);
        while(current.size()!=0){
            children = new ArrayList<TreeNode>();
            ArrayList<Integer> levelNodes= new ArrayList<Integer>();
            for(TreeNode t : current){
                levelNodes.add(t.val);
                if(t.left!=null){
                    children.add(t.left);
                }
                if(t.right!=null){
                    children.add(t.right);
                }
            }
            output.add(levelNodes);
            current = children;
        }
        return output;
    }