LeetCoder - Pascal's Triangle II

Given an index k, return the k^th row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> last = new ArrayList<Integer>();
        if(rowIndex<0) {
            return last;
        }
        last.add(1);
        for(int i=0;i<rowIndex;i++) {
            ArrayList<Integer> cur = new ArrayList<Integer>();
            for(int j=0;j<=last.size();j++) {
                int a = 0;
                if(j-1>=0) {
                    a = last.get(j-1);
                }
                int b = 0;
                if(j<last.size()) {
                    b = last.get(j);
                }
                cur.add(a+b);
            }
            last = cur;
        }      
        return last;
    }
}


=========


public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; i++) {
            list.add(0);
        }
        list.set(0, 1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i; j > 0; j--) {
                int val = list.get(j) + list.get(j - 1);
                list.set(j, val);
            }
        }
        return list;
    }
}

LeetCoder - Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(numRows==0) {
            return ret;
        }
        ArrayList<Integer> first = new ArrayList<Integer>();
        first.add(1);
        ret.add(first);
        for(int i=1;i<numRows;i++) {
            ArrayList<Integer> last = ret.get(ret.size()-1);
            ArrayList<Integer> cur = new ArrayList<Integer>();
            for(int j=0;j<=last.size();j++) {
                int a = 0;
                if(j-1>=0) {
                    a = last.get(j-1);
                }
                int b = 0;
                if(j<last.size()) {
                    b = last.get(j);
                }
                cur.add(a+b);
            }
            ret.add(cur);
        }        
        return ret;
    }
}

LeetCoder - Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        return Math.abs(depth(root.left)-depth(root.right))<=1 && isBalanced(root.left) && isBalanced(root.right);
    }
 
    public int depth(TreeNode root) {
        if(root==null) {
            return 0;
        } else {
            return 1 + Math.max(depth(root.left), depth(root.right));
        }
    }
}


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) {
            return true;
        }
        return getDepth(root, 0)!=-1;
    }
   
    private int getDepth(TreeNode node, int curDepth) {
        if(node==null) {
            return curDepth;
        }
        int leftDep = curDepth;
        int rightDep = curDepth;
        if(node.left!=null) {
            leftDep = getDepth(node.left, leftDep + 1);
        }
        if(leftDep==-1) {
            return -1;
        }
        if(node.right!=null) {
            rightDep = getDepth(node.right, rightDep + 1);
        }
        if(rightDep==-1) {
            return -1;
        }
        int gap = (int) Math.abs(rightDep-leftDep);
        if(gap>1) return -1;
        else return Math.max(leftDep, rightDep);
    }
}

LeetCoder - Permutations

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

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        res.add(new ArrayList<Integer>());
        for(int n : num) {
            ArrayList<ArrayList<Integer>> cur = new ArrayList<ArrayList<Integer>>();
            for(ArrayList<Integer> tmp : res) {
                for(int j=0;j<=tmp.size();j++) {
                    ArrayList<Integer> tmp1 = new ArrayList<Integer>(tmp);
                    tmp1.add(j, n);
                    cur.add(tmp1);
                }
            }
            res = new ArrayList<ArrayList<Integer>>(cur);          
        }
        return res;
    }
}

LeetCoder - Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        // merge from the end
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        for(;k>=0;k--) {
            if(i>=0 && (j<0 || A[i]>B[j])) {
                A[k] = A[i--];
            } else {
                A[k] = B[j--];
            }
        }
    }
}

LeetCoder - Merge Two Sorted Lists

Merge Two Sorted Lists

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.

/**
 * 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) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(l1==null && l2==null) {
            return null;
        } else if (l1==null && l2!=null) {
            return l2;
        } else if (l1!=null && l2==null) {
            return l1;
        } else {
            ListNode head = null;
            ListNode p1 = null;
            ListNode p2 = null;
           
            if(l1.val<l2.val) {
                head = l1;
                p1 = head.next;
                p2 = l2;
            } else {
                head = l2;
                p1 = l1;
                p2 = head.next;
            }
            ListNode cur = head;
            while(p1!=null || p2!=null) {
                if(p1==null || (p2!=null && p2.val<p1.val)) {
                    cur.next = p2;
                    cur = p2;
                    p2 = p2.next;
                } else if(p2==null || (p1!=null && p1.val<=p2.val)) {
                    cur.next = p1;
                    cur = p1;
                    p1 = p1.next;
                }
            }
            return head;
        }
    }
}

LeetCoder - Remove Element

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 class Solution {
    public int removeElement(int[] A, int elem) {
        int rm = 0;      
        for(int i=0;i<A.length && i<A.length - rm;i++) {
            int a = A[i];
            if(a==elem) {
                A[i] = A[A.length - rm - 1];
                rm++;
                i--;
            }
        }
        return A.length - rm;
    }
}

LeetCoder - Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

public class Solution {
    public int numTrees(int n) {
        int c[] = new int[n+1];
        c[0] = 1;
        c[1] = 1;
        for(int i=2;i<n+1;i++) {
            for(int j=0;j<i;j++) {
                c[i] += c[j] * c[i-j-1];
            }
        }
        return c[n];
    }
}

LeetCoder - Single Number II

 Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int count[] = new int[32];
        int result = 0;
        for (int i = 0;i < 32;++i) {
            count[i] = 0;
            for (int j = 0;j < A.length;++j) {
                if (((A[j] >> i) & 1) == 1) {
                    count[i] = (count[i] + 1) % 3;
                }
            }
            result |= (count[i] << i);
        }
        return result;
    }
}

LeetCoder - Linked List Cycle

 Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null) {
            return false;
        }
        ListNode n1 = head;
        ListNode n2 = head;
       
        while(true) {
            n1 = n1.next;
            if(n1==null) {
                return false;
            }
            n2 = n2.next;
            if(n2==null) {
                return false;
            }
            n2 = n2.next;
            if(n2==null) {
                return false;
            }
            if(n1==n2) {
                return true;
            }
        }
    }
}

LeetCoder - Insertion Sort List

Sort a linked list using insertion sort.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode newHead = head;
        while(true) {
            if(cur==null) {
                break;
            }
            ListNode tmp = cur;
            ListNode tmpPre = pre;
            pre = cur;
            cur = cur.next;
            if(tmp.val<newHead.val) {
                tmpPre.next = tmp.next;
                tmp.next = newHead;
                newHead = tmp;
                pre = tmpPre;
            } else if(tmp.val<tmpPre.val){
                ListNode tmp2 = newHead;
                while(tmp2.next!=tmp) {
                    if(tmp.val<tmp2.next.val) {
                    tmpPre.next = tmp.next;
                        tmp.next = tmp2.next;
                        tmp2.next = tmp;
                        break;
                    }
                    tmp2 = tmp2.next;
                }
                pre = tmpPre;
            }
        }
        return newHead;
    }
}

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode p1 = head;
        while(p1!=null) {
            ListNode p2 = p1.next;
            ListNode p0 = dummy;
            boolean insert = false;
            while(p0.next!=null) {
                if(p1.val<p0.next.val) {
                    ListNode tmp = p0.next;
                    p0.next = p1;
                    p1.next = tmp;
                    insert = true;
                    break;
                }
                p0 = p0.next;
            }
            if(!insert) {
                p0.next = p1;
                p1.next = null;
            }
            p1 = p2;
        }
        return dummy.next;
    }
}


====================

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        while (p != null) {
            ListNode nextP = p.next;
           
            ListNode from = dummy;
            while (from.next != null && p.val > from.next.val) {
                from = from.next;
            }
            ListNode p2 = from.next;
            from.next = p;
            p.next = p2;
            p = nextP;
        }
        return dummy.next;
    }
}

Leetcoder - Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> lst = new ArrayList<Integer>();
        Stack<TreeNode> fronties = new Stack<TreeNode>();
        if(root==null) {
            return lst;
        }
        fronties.push(root);
        Stack<TreeNode> output = new Stack<TreeNode>();
        while(!fronties.isEmpty()) {
            TreeNode top = fronties.pop();
            output.push(top);
            if(top.left!=null) {
                fronties.push(top.left);
            }
            if(top.right!=null) {
                fronties.push(top.right);
            }
        }
        while(!output.isEmpty()) {
            lst.add(output.pop().val);
        }
        return lst;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);
        while (!stk.isEmpty()) {
            TreeNode node = stk.pop();
            res.add(0, node.val);
            if (node.left != null) {
                stk.push(node.left);
            }
            if (node.right != null) {
                stk.push(node.right);
            }
        }
        return res;
    }
}