Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Solution1: 

Run time complexity is O(n), constant space.

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        
        return nums.length;
    }
}

Solution2: binary search
Run time complexity is O(logn), constant space.

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution1: run time complexity is O(n), space complexity is O(n).

res = [n2*n3*n4, n1*n3*n4, n1*n2*n4, n1*n2*n3], 相当于
a1 = [1, n1, n1*n2, n1*n2*n3]和
a2 = [n2*n3*n4, n3*n4, n4, 1]相乘

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int[] a1 = new int[nums.length];
        int[] a2 = new int[nums.length];
        a1[0] = 1;
        a2[nums.length - 1] = 1;
        
        // scan from left to right -> a1 = [1, n1, n1*n2, n1*n2*n3]
        for (int i = 0; i < nums.length - 1; i++) {
            a1[i + 1] = nums[i] * a1[i];
        }
        
        // scan from right to left -> a2 = [n2*n3*n4, n3*n4, n4, 1]
        for (int i = nums.length - 1; i > 0; i--) {
            a2[i - 1] = nums[i] * a2[i];
        }
        
        // multiply -> res = [n2*n3*n4, n1*n3*n4, n1*n2*n4, n1*n2*n3]
        for (int i = 0; i < nums.length; i++) {
            res[i] = a1[i] * a2[i];
        }
        
        return res;
    }
}

Solution2: run time complexity is O(n), constant space.

用一个temp来保存每次的结果。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        res[0] = 1;
        int temp = 1;
        
        for (int i = 1; i < nums.length; i++) {
            temp = temp * nums[i - 1];
            res[i] = temp;
        }
        
        temp = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            temp = temp * nums[i + 1];
            res[i] *= temp;
        }
        
        return res;
    }
}

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

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

Solution:

两个游标（p1，p2）从头节点开始遍历链表，p1每次走一步，p2每次走两步，如果有环，那么p2始终会在环上与p1相遇。

假设链表长度为n，环开始的节点为到头节点有k步，p1和p2在距离环开始的节点m步的地方相遇（按顺时针），假设相遇节点到环开始的节点d步（按顺时针），那么p1走的路程为k+m，p2走的路程为k+m+d+m，显然p2走的路程为p1的2倍，于是2(k+m)=k+2m+d，于是我们推出d=k。

p1和p2相遇后，把p1只想头节点，然后p1,p2都一次走一步，走了k步后p1 p2相遇，该节点就是环开始的节点。

Time complexity is O(n), constant space.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null)
            return null;
            
        ListNode slow = head;
        ListNode fast = head;

        //找到第一次相遇点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;  //相遇
        }
        
        //检查是否因为有环退出或是因为碰到null而退出
        if(fast == null || fast.next == null)
            return null;
        
        // 把慢指针移到链表头，然后保持快慢指针同样的速度移动  
        // 再次相遇时即为环的入口 
        slow = head;
        while(fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        
        //快慢指针都指向入口
        return fast;
    }
}

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?

Solution:

复杂度O(n)的方法，使用两个指针slow,fast。两个指针都从表头开始走，slow每次走一步，fast每次走两步，如果fast遇到null，则说明没有环，返回false；如果slow==fast，说明有环，并且此时fast超了slow一圈，返回true。

two pointers, one traverses twice as fast as the other, return true if they meet

/**
 * 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 slow = head;
        ListNode fast = head.next;  //check head first. If head==null, no head.next exists
        boolean isMeeting = false;
        
        while(fast != null) {
            if(fast == slow) {
                isMeeting = true;
                break;
            }
            
            fast = fast.next;
            if(fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return isMeeting;
    }
}

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution: runtime complexity is O(n), constant space.
"we notice that A and B must be different at some bit at position t in their binary representations. So if we divide the set of numbers into 2 set, one is the set of all the numbers that have the same bit at position t as A, the other is the set of all numbers that have the same bit at position t as B. These 2 sub-sets have a special characteristic: all numbers appear 2 times, except 1. This bring us to the Single Number problem."
Reference: http://traceformula.blogspot.com/2015/09/single-number-iii-leetcode.html

public class Solution {
    public int[] singleNumber(int[] nums) {
        int A = 0;
        int B = 0;
        int AXORB = 0;
        
        for (int n : nums) {
            AXORB ^= n;
        }
        
        int lastBit = (AXORB & (AXORB - 1)) ^ AXORB;  // find the last bit that A differs from B
        
        for (int n : nums) {  
            // based on the last bit, group the items into groupA (include A) and groupB
            if ((lastBit & n) == 0) {
                A ^= n;
            } else {
                B ^= n;
            }
        }
        
        return new int[]{A, B};
    }
}

First Bad Version - LeetCode

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution: binary search

Time complexity is O(logn), constant space.

Notice that mid = begin + (end - begin) / 2, because when n is very large, (begining + end) may overflow.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n == 1) {
            return 1;
        }
        
        int l = 1;
        int r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;  // mid = begin + (end - begin) / 2
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        
        return r;
    }
}

First Bad Version - LintCode

The code base version is an integer and start from 1 to n. One day, someone commit a bad version in the code case, so it caused itself and the following versions are all failed in the unit tests.

You can determine whether a version is bad by the following interface: 

Java:    public VersionControl {        boolean isBadVersion(int version);    }
C++:    class VersionControl {    public:        bool isBadVersion(int version);    };
Python:    class VersionControl:        def isBadVersion(version)

Find the first bad version.

Note

You should call isBadVersion as few as possible. 

Please read the annotation in code area to get the correct way to call isBadVersion in different language. For example, Java is VersionControl.isBadVersion.

Example

Given n=5

Call isBadVersion(3), get false

Call isBadVersion(5), get true

Call isBadVersion(4), get true

return 4 is the first bad version

Challenge

Do not call isBadVersion exceed O(logn) times.

Solution: Binary search

/**
 * public class VersionControl {
 *     public static boolean isBadVersion(int k);
 * }
 * you can use VersionControl.isBadVersion(k) to judge wether 
 * the kth code version is bad or not.
*/
class Solution {
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        // write your code here
        if(n == 0)
            return 0;
        else if(n == 1)
            return 1;
        
        int l = 1, r = n;
        while(l < r) {
            int mid = (l + r) / 2;
            if(VersionControl.isBadVersion(mid))
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
}

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution1: dynamic programming
递推公式dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int len = nums.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        
        return dp[len];
    }
}

Solution2: time complexity is O(n), constant space.
Use two pointers (even, odd) to track maximum value.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int even = 0;
        int odd = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                even += nums[i];
                if (even < odd) {
                    even = odd;
                }
            } else {
                odd += nums[i];
                if (odd < even) {
                    odd = even;
                }
            }
        }
        
        if (even > odd) {
            return even;
        } else {
            return odd;
        }
    }
}

Reference: http://www.programcreek.com/2014/03/leetcode-house-robber-java/

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Solution1: time complexity is O(n^2), space complexity is O(n).

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null || (s.length() == 0 && t.length() == 0)) {
            return true;
        }
        
        if (s.length() != t.length()) {
            return false;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char cs = s.charAt(i);
            char ct = t.charAt(i);
            
            Character key = getKey(map, ct);
            if (key != null && key != cs) {   // deal with case: ab -> aa, different keys have same values
                return false;
            }
            
            if (map.containsKey(cs)) {
                if (ct != map.get(cs)) {
                    return false;
                }
            } else {
                map.put(cs, ct);
            }
        }
        return true;
    }
    
    public Character getKey(HashMap map, Character target) {
        for (Map.Entry entry : map.entrySet()) {
            if (entry.getValue().equals(target)) {
                return entry.getKey();
            }
        }
        return null;
    }
}

Reference: http://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/

Solution2: time complexity is O(n ^ 2), space complexity is O(n). 
Time complexity of HashMap.containsValue() is O(n).

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null || (s.length() == 0 && t.length() == 0)) {
            return true;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char cs = s.charAt(i);
            char ct = t.charAt(i);
            
            if (map.containsKey(cs)) {
                if (map.get(cs) != ct) {
                    return false;
                } else {
                    continue;
                }
            } else if (map.containsValue(ct)) {
                return false;
            }
            map.put(cs, ct);
        }
        return true;
    }
}

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Solution: 把非零数往前移，后面用零补齐。
Time complexity is O(n), constant space.

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int position = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[position] = nums[i];
                position++;
            }
        }
        
        for (int i = position; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution1: iteratively

Time complexity is O(n), constant space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode p1 = head;
        ListNode p2 = head.next;
        head.next = null;
        while (p1 != null && p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            if (temp != null) {
                p1 = p2;
                p2 = temp;
            } else {
                break;
            }
        }
        
        return p2;
    }
}

Solution2: recursively

Time complexity is O(n), stack space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode second = head.next;  
        head.next = null;  // 把每个node都打断
        
        ListNode rest = reverseList(second);
        second.next = head;  // 反向把node都连起来
        
        return rest;
    }
}

Reference: http://www.programcreek.com/2014/05/leetcode-reverse-linked-list-java/

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Solution: 

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        if (C < E || G < A) {
            return (C - A) * (D - B) + (G - E) * (H - F);
        }
        
        if (D < F || B > H) {
            return (C - A) * (D - B) + (G - E) * (H - F);
        }
        
        int right = Math.min(C, G);
        int left = Math.max(A, E);
        int top = Math.min(D, H);
        int bottom = Math.max(B, F);
        
        return (C - A) * (D - B) + (G - E) * (H - F) - (right - left) * (top - bottom);
    }
}

Reference: http://www.programcreek.com/2014/06/leetcode-rectangle-area-java/

Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Solution:

class MyStack {
    LinkedList stack = new LinkedList();
    
    // Push element x onto stack.
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.add(x);
            return;
        }
        
        LinkedList temp = new LinkedList();
        
        while (!stack.isEmpty()) {
            temp.add(stack.poll());
        }
        
        stack.add(x);
        while (!temp.isEmpty()) {
            stack.add(temp.poll());
        }
    }

    // Removes the element on top of the stack.
    public void pop() {
        stack.poll();
    }

    // Get the top element.
    public int top() {
        return stack.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return stack.isEmpty();
    }
}

Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Solution1: recursive
Time complexity is O(n), space complexity is stack space (O(logn)).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right= temp;
        
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

Solution2: iterative
Time complexity is O(n), space complexity is O(n).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        
        LinkedList queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Solution1: time complexity is O(n), space complexity is O(n).
记录两个值 lowBound=nums[i], highBound=nums[i].  如果nums[i+1]  - highBound == 1, 则i++，highBound=nums[i], 继续比较。否则, 插入字符串 lowBound->highBound.

public class Solution {
    public ArrayList summaryRanges(int[] nums) {
        ArrayList res = new ArrayList();
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        for (int i = 0; i < nums.length; i++) {
            int lowBound = nums[i];
            int highBound = nums[i];
            while (i < nums.length - 1 && nums[i + 1] - highBound == 1) {
                i++;
                highBound = nums[i];
            }
            
            StringBuilder s = new StringBuilder();
            s.append(lowBound);
            if (lowBound == highBound) {
                res.add(s.toString());
            } else {
                s.append("->");
                s.append(nums[i]);
                res.add(s.toString());
            }
        }
        return res;
    }
}

Power of Two

Given an integer, write a function to determine if it is a power of two.
Solution1: 向右移1位 ＝ n / 2

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 1) {
            return true;
        }
        
        int temp = n;
        while (temp != 2) {
            if (temp % 2 != 0 || temp < 2) {
                return false;
            }
            temp = temp >> 1;
        }
        
        return true;
    }
}

Solution2: Better solution
如果一个整数是2的幂，那么它的二进制形式最高位为1，其余各位为0. 
等价于：n & (n - 1) = 0，且n > 0

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n > 0 && (n & (n - 1)) == 0) {
            return true;
        }
        
        return false;
    }
}

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution:

class MyQueue {
    Stack stack = new Stack();
    
    // Push element x to the back of queue.
    public void push(int x) {
        if (stack.empty()) {
            stack.push(x);
            return;
        }
        
        Stack temp = new Stack();
        while (!stack.empty()) {
            temp.push(stack.pop());
        }
        
        stack.push(x);
        while(!temp.empty()) {
            stack.push(temp.pop());
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
        stack.pop();
    }

    // Get the front element.
    public int peek() {
        return stack.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return stack.empty();
    }
}

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution: O(n) time and O(1) space. 

Set fast and slow pointers to split linked list in half, reverse the last half of list and compare with the first half of list. 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {   //注意这个判断条件
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;  // split the list
        slow.next = null;
        
        head2 = reverseList(head2);  // reverse second half of the list
        
        // compare two lists
        ListNode h1 = head;
        ListNode h2 = head2;
        while (h1 != null && h2 != null) {
            if (h1.val == h2.val) {
                h1 = h1.next;
                h2 = h2.next;
            } else {
                return false;
            }
        }
        
        return true;
    }
    
    public ListNode reverseList(ListNode head) {
        if (head.next == null) {
            return head;
        }
        
        ListNode p1 = head;
        ListNode p2 = head.next;
        head.next = null;
        
        while (p1 != null && p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            if (temp != null) {
                p2 = temp;
            } else {
                break;
            }
        }
        
        return p2;
    }
}

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Solution: Run time complexity is O(n), constant space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode node = newHead;
        
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        
        return newHead.next;
    }
}

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution: 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Solution1: sort two strings first and then comparing them. Run time complexity is O(n), space complexity is O(n).
Arrays.sort(int[] a) in recent JDK is implemented with Dual-pivot Quicksort algorithm which has O(n log n) average complexity and is performed in-place.

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } else if (s.length() == 0 && t.length() == 0) {
            return true;
        }
        
        char[] arrS = new char[s.length()];
        char[] arrT = new char[t.length()];
        for (int i = 0; i < s.length(); i++) {
            arrS[i] = s.charAt(i);
        }
        for (int i = 0; i < t.length(); i++) {
            arrT[i] = t.charAt(i);
        }
        
        Arrays.sort(arrS);
        Arrays.sort(arrT);
        
        for (int i = 0; i < arrS.length; i++) {
         if (arrS[i] != arrT[i]) {
             return false;
         }
        }
        return true;
    }
}

Or: 简洁一点的写法

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } 
        
        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();
        
        Arrays.sort(arrS);
        Arrays.sort(arrT);
        
        for (int i = 0; i < arrS.length; i++) {
         if (arrS[i] != arrT[i]) {
             return false;
         }
        }
        return true;
    }
}

Solution2: HashMap. Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        } else if (s.length() == 0 && t.length() == 0) {
            return true;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }
        
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
            } else {
                return false;
            }
        }
        
        Set keys = map.keySet();
        for (char k : keys) {
            if (map.get(k) != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution: DFS

/**
 * 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 binaryTreePaths(TreeNode root) {
        ArrayList result = new ArrayList();

        if (root == null) {
            return result;
        }
        
        dfs(root, result, new StringBuilder());

        return result;
    }
    
    public void dfs(TreeNode root, ArrayList result, StringBuilder path) {
        if (root.left == null && root.right == null) {
            path.append(root.val);
            result.add(path.toString());
            return;
        }
        
        path.append(root.val);
        path.append("->");
        
        if (root.left != null) {
            dfs(root.left, result, new StringBuilder(path));
        }
        
        if (root.right != null) {
            dfs(root.right, result, new StringBuilder(path));
        }
    }
}

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Solution1: with while loop

public class Solution {
    public int addDigits(int num) {
        if (num < 10) {
            return num;
        }
        
        int res = 0;
        while (num / 10 >= 1) {
            res = 0;
            res += num % 10;
            num = num / 10;
            res += num;
            num = res;
        }
        return res;
    }
}

Solution2: 观察得出规律，
if (in % 9 != 0) return in % 9;
else return 9;

public class Solution {
    public int addDigits(int num) {
        if (num == 0) {
            return 0;
        }
        
        if (num % 9 != 0) {
            return num % 9;
        } else {
            return 9;
        }
    }
}

Or:

public class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
}

Count Primes

Count the number of prime numbers less than a non-negative number, n.

Solution1: 超时了

public class Solution {
    public int countPrimes(int n) {
        int count = 0;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }
    
    public boolean isPrime(int x) {
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Solution2: Sieve of Eratosthenes

Run time complexity is O(n log log n), space complexity is O(n)

public class Solution {
    public int countPrimes(int n) {
        int result = 0;
        
        boolean[] notPrime = new boolean[n];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (!notPrime[i]) {
                int j = i * i;
                while (j < n) {
                    notPrime[j] = true;
                    j += i;
                } 
            }
        }
        
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                result++;
            }
        }
        
        return result;
    }
}

Or: 更加清晰一点

public class Solution {
    public int countPrimes(int n) {
        int result = 0;
        
        boolean[] isPrime = new boolean[n];
        for(int i = 0; i < n; i++) {
            isPrime[i] = true;
        }
        
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                int j = i * i;
                while (j < n) {
                    isPrime[j] = false;
                    j += i;
                } 
            }
        }
        
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                result++;
            }
        }
        
        return result;
    }
}

Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Solution1: recursive

public class Solution {
    public boolean isUgly(int num) {
        if (num < 1) {
            return false;
        }
        
        if (num == 1) {
            return true;
        }
        
        if (num % 2 == 0) {
            return isUgly(num / 2);
        }
        
        if (num % 3 == 0) {
            return isUgly(num / 3);
        }
        
        if (num % 5 == 0) {
            return isUgly(num / 5);
        }
        
        return false;
    }
}

Solution2: iterative

public class Solution {
    public boolean isUgly(int num) {
        int div = 2 * 3 * 5;
        
        while (num > 0 && div > 1) {
            if (num % div == 0) {
                num /= div;
            }
            
            if (num % 2 != 0 && div % 2 == 0) {
                div /= 2;
            }
            
            if (num % 3 != 0 && div % 3 == 0) {
                div /= 3;
            }
            
            if (num % 5 != 0 && div % 5 == 0) {
                div /= 5;
            }
        }
        
        return num == 1;
    }
}