Leetcode Climbing Stairs

One dimension DP.

public int climbStairs(int n) {
        int[] steps = new int[n+1];
        steps[0] = 1;
        steps[1] = 1;
        for (int i=2; i<=n; i++) {
            steps[i] = steps[i-1] + steps[i-2];
        }
        return steps[n];
    }

Leecode Search Insert Position

O(logn) Binary Search

 public int searchInsert(int[] A, int target) {
        if (A == null) return 0;
        return searchInsert(A,target, 0, A.length-1);
    }
    private int searchInsert(int[] A, int target, int start, int end) {
        int mid = (start+end)/2;
        if (target == A[mid]) {
            return mid;
        } else if (target < A[mid]) {
            return start < mid ? searchInsert(A, target, start, mid-1) : start;
        } else {
            return end > mid ? searchInsert(A, target, mid+1, end) : (end + 1);
        }
       
    }

LeetCode Populating Next Right Pointers I&II in Each Node

Recursive method:

public void connect(TreeLinkNode root) {
        if (root == null) return;
        if (root.left != null) {
            root.left.next = root.right;
        }
        if (root.right != null && root.next != null) {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }

Iterative method:

public void connect(TreeLinkNode root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (root == null)
return;
TreeLinkNode currentNode = root;
TreeLinkNode topNode = root;
TreeLinkNode firstNode = root.left;
currentNode.next = null;

while (topNode != null && topNode.left != null) {
while (topNode != null) {
currentNode = topNode.left;
currentNode.next = topNode.right;
currentNode = currentNode.next;
topNode = topNode.next;
currentNode.next = (topNode == null) ? null : topNode.left;
}
topNode = firstNode;
firstNode = (topNode == null) ? null : topNode.left;
}
    }

For II, still use two variables to contain the prev and nextLevel. The only thing we need to pay attention, sometimes we may meet the null pointer node.

public void connect(TreeLinkNode root) {
        if (root==null) return;
        while (root!=null) {
            TreeLinkNode nextLevel=null;
            TreeLinkNode prev=null;
            while (root!=null) {
                if (nextLevel==null) nextLevel= (root.left != null) ? root.left : root.right;
                if (root.left!=null) {
                    if (prev!=null) {
                        prev.next=root.left;
                    }
                    prev=root.left;
                }
                if (root.right!=null) {
                    if (prev!=null) {
                        prev.next=root.right;
                    }
                    prev=root.right;
                }
                root=root.next;
            }
            root=nextLevel;
        }
    }

LeetCode Binary Tree Preorder Traversal

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
       
        while (!stack.empty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
           
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
           
        }
        return list;
    }

LeetCode Binary Tree Inorder Traversal

Using stack to store all the elements on the left

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p!=null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode temp = stack.pop();
                list.add(temp.val);
                p = temp.right;
            }
        }
        return list;
    }

LeetCode Linked List Cycle II

1. Find the cycle
2. Move the slow to the head

2(a+b) = a+b + b+ c; so a = c;

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //Finding the cycle
        //Slow and fast meet at Z point
        while(true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
           
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
       
    }

LeetCode Linked List Cycle

Using two pointers.


public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return false;
       
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
           
            if (fast == slow) {
                return true;
            }
        }
        return false;
       
    }