Lowest Common Ancestor of a Binary Tree

 It's recursive and expands the meaning of the function. If the current (sub)tree contains both p and q, then the function result is their LCA. If only one of them is in that subtree, then the result is that one of them. If neither are in that subtree, the result is null/None/nil.

/**
 * 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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (right != null && left != null) {
            return root;
        } else {
            if (left == null) return right;
            else return left;
        }
    }
}

========

/**
 * 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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        List<TreeNode> ans1 = new ArrayList<TreeNode>();
        findAncestors(root, p, ans1);
        List<TreeNode> ans2 = new ArrayList<TreeNode>();
        findAncestors(root, q, ans2);
        TreeNode res = null;
        for (int i = 0; i < ans1.size() && i < ans2.size(); i++) {
            if (ans1.get(i) == ans2.get(i))
                res = ans1.get(i);
            else
                break;
        }
        return res;
    }
   
    private boolean findAncestors(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == null) {
            return false;
        }
        path.add(root);
        if (root == node) {
            return true;
        }
        if (findAncestors(root.left, node, path)) {
            return true;
        }
        if (findAncestors(root.right, node, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k);
        for (int n : nums) {
            queue.offer(n);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.poll();
    }
}

=======

public class Solution {
   
    private int partition(int[] nums, int from, int to) {
        java.util.Random r = new java.util.Random();
        int idx = from + r.nextInt(to - from + 1);
        swap(nums, idx, to);
        int start = from;
        for (int i = from; i < to; i++) {
            if (nums[i] < nums[to]) {
                swap(nums, start, i);
                start++;
            }
        }
        swap(nums, to, start);
        return start;
    }
   
    private void swap(int nums[], int p, int q) {
        int tmp = nums[p];
        nums[p] = nums[q];
        nums[q] = tmp;
    }
   
    private int quickSelect(int[] nums, int k) {
        int s = 0;
        int e = nums.length - 1;
        while (s <= e) {
            int m = partition(nums, s, e);
            if (m == k) {
                return nums[m];
            } else if (m < k) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return 0;
    }
   
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, nums.length - k);
    }
}

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = matrix.length;
        int column = matrix[0].length;
        int i = 0;
        int j = column - 1;
        while (i >= 0 && i < row && j >= 0 && j < column) {
            int val = matrix[i][j];
            if (target == val) {
                return true;
            } else if (target > val) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
       
        helper(k, n, 1, 0, new ArrayList<Integer>(), res);
        return res;
    }
   
    private void helper(int k, int n, int cur, int curSum, List<Integer> curList, List<List<Integer>> res) {
        if (curSum == n && curList.size() == k) {
            List<Integer> newList = new ArrayList<Integer>(curList);
            res.add(newList);
        } else if (curSum < n && curList.size() < k) {
            for (int i = cur; i <= 9; i++) {
                curList.add(i);
                helper(k, n, i + 1, curSum + i, curList, res);
                curList.remove(curList.size() - 1);
            }
        }
    }
}

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    int mK = 0;
    int val = 0;
   
    public int kthSmallest(TreeNode root, int k) {
        mK = k;
        visit(root);
        return val;
    }
   
    private void visit(TreeNode root) {
        if (root.left != null) {
            visit(root.left);
        }
        if (mK == 1) {
            val = root.val;
        }
        mK--;
        if (mK > 0 && root.right != null) {
            visit(root.right);
        }
    }
}

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.

class MyStack {
 
    Queue<Integer> queue1 = new LinkedList<Integer>();
    Queue<Integer> queue2 = new LinkedList<Integer>();
    int size = 0;
 
    // Push element x onto stack.
    public void push(int x) {
        queue1.add(x);
        size++;
    }

    // Removes the element on top of the stack.
    public void pop() {
        int tmp = size;
        while (tmp-- > 1) {
            queue2.add(queue1.poll());
        }
        queue1.poll();
        while (!queue2.isEmpty()) {
            queue1.add(queue2.poll());
        }
        size--;
    }

    // Get the top element.
    public int top() {
        int tmp = size;
        while (tmp-- > 1) {
            queue2.add(queue1.poll());
        }
        int top = queue1.poll();
        queue2.add(top);
        while (!queue2.isEmpty()) {
            queue1.add(queue2.poll());
        }
        return top;
    }

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

====

class MyStack {
 
    Queue<Integer> queue1 = new LinkedList<Integer>();
    int size = 0;
 
    // Push element x onto stack.
    public void push(int x) {
        queue1.offer(x);
        size++;
    }

    // Removes the element on top of the stack.
    public void pop() {
        for (int i = 0; i < size - 1; i++) {
            queue1.offer(queue1.poll());
        }
        queue1.poll();
        size--;
    }

    // Get the top element.
    public int top() {
        for (int i = 0; i < size - 1; i++) {
            queue1.offer(queue1.poll());
        }
        int top = queue1.poll();
        queue1.offer(top);
        return top;
    }

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

===========

class MyStack {
   
    Queue<Integer> queue1 = new LinkedList<Integer>();
   
    // Push element x onto stack.
    public void push(int x) {
        queue1.offer(x);
        int count = queue1.size();
        while (count-- > 1) {
            queue1.offer(queue1.poll());
        }
    }

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

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

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

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?

public class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int n : nums) {
            xor ^= n;
        }
        int diff = 1;
        for (int i = 0; i < 32; i++) {
            if ((diff & xor) != 0) {
                break;
            } else {
                diff = diff << 1;
            }
        }
        int[] res = new int[2];
        for (int n : nums) {
            if ((n & diff) == 0) {
                res[0] ^= n;
            } else {
                res[1] ^= n;
            }
        }
        return res;
    }
}

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

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        int start = nums[0];
        int pre = nums[0];
        for (int i = 1; i <= nums.length; i++) {
            int n = nums[0] - 1;
            if (i != nums.length) {
                n = nums[i];
            }
            if (n == pre + 1) {
                pre++;
            } else {
                StringBuilder sb = new StringBuilder();
                sb.append(start);
                if (start != pre) {
                    sb.append("->").append(pre);
                }
                list.add(sb.toString());
                start = n;
                pre = n;
            }
        }
        return list;      
    }
}

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            Integer index = map.get(n);
            if (index != null && i - index <= k) {
                return true;
            }
            map.put(n, i);
        }
        return false;
    }
}

=========

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return false;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i <= 0 + k && i < nums.length; i++) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }
        for (int i = k + 1; i < nums.length; i++) {
            set.remove(nums[i - 1 - k]);
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }
        return false;
    }
}

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        int leftDepth = getDepth(root, true);
        int rightDepth = getDepth(root, false);
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        } else {
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }
   
    private int getDepth(TreeNode node, boolean left) {
        int depth = 0;
        while (node != null) {
            if (left) {
                node = node.left;
            } else {
                node = node.right;
            }
            depth += 1;
        }
        return depth;
    }
}

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.

public class Solution {

    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

        int area = (C - A) * (D - B);

        area+ = (G - E) * (H - F);

        int left = Math.max(A, E);

        int right = Math.min(C, G);

        int bottom = Math.max(B, F);

        int top = Math.min(D, H);

        if (left < right && bottom < top) {

            area -= (right - left) * (top - bottom);

        }

        return area1 + area2;

    }

}

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

/**
 * 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<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if (root == null) {
            return res;
        }
        helper(root, new ArrayList<Integer>(), res);
        return res;
    }
   
    private void helper(TreeNode node, List<Integer> curList, List<String> res) {
        if (node.left == null && node.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < curList.size(); i++) {
                sb.append(curList.get(i)).append("->");
            }
            sb.append(node.val);
            res.add(sb.toString());
        } else {
            if (node.left != null) {
                curList.add(node.val);
                helper(node.left, curList, res);
                curList.remove(curList.size() - 1);
            }
            if (node.right != null) {
                curList.add(node.val);
                helper(node.right, curList, res);
                curList.remove(curList.size() - 1);
            }
        }
    }
}

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

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

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

/**
 * 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> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            res.add(queue.get(count - 1).val);
            while (count-- > 0) {
                TreeNode node = queue.pop();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return res;
    }
}

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.

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        HashMap<Character, Character> map1 = new HashMap<Character, Character>();
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (!map1.containsKey(c1)) {
                map1.put(c1, c2);
                if (set.contains(c2)) {
                    return false;
                }
                set.add(c2);
            } else {
                if (map1.get(c1) != c2) {
                    return false;
                }
            }
         
        }
        return true;
    }
}

===========

public class Solution {
    public boolean isIsomorphic(String s1, String s2) {
        int[] m = new int[512];
        for (int i = 0; i < s1.length(); i++) {
            if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;
            m[s1.charAt(i)] = m[s2.charAt(i)+256] = i + 1;
        }
        return true;
    }
}

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

/**
 * 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) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
       
        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

public class Solution {
    public boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(n);
        while (n != 1) {
            n = getNext(n);
            if (set.contains(n)) {
                return false;
            }
            set.add(n);
        }
        return true;
    }
 
    private int getNext(int n) {
        int ret = 0;
        while (n != 0) {
            ret += Math.pow(n % 10, 2);
            n /= 10;
        }
        return ret;
    }
}

==========

public class Solution {
    public boolean isHappy(int n) {
        int x = n;
        int y = n;
        while(x>1){
            x = cal(x) ;
            if(x==1) return true ;
            y = cal(cal(y));
            if(y==1) return true ;

            if(x==y) return false;
        }
        return true ;
    }
    public int cal(int n){
        int x = n;
        int s = 0;
        while(x>0){
            s = s+(x%10)*(x%10);
            x = x/10;
        }
        return s ;
    }
}

House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }      
        if (nums.length == 1) {
            return nums[0];
        }
        int[] maxRob = new int[nums.length + 1];
        int[] maxNoRob = new int[nums.length + 1];
        maxRob[1] = nums[0];
        int maxMoney = 0;
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            if (i != nums.length - 1) {
                maxNoRob[i + 1] = Math.max(maxNoRob[i - 1] + n, maxNoRob[i]);
                maxRob[i + 1] = Math.max(maxRob[i - 1] + n, maxRob[i]);
            } else {
                maxMoney = Math.max(maxRob[i], Math.max(maxNoRob[i - 1] + n, maxNoRob[i]) );
            }
        }
        return maxMoney;
    }
}

=====
public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int rob = nums[0];
        int noRob = 0;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (i != nums.length - 1) {
                int tmpRob = rob;
                rob = Math.max(rob, noRob + num);
                noRob = tmpRob;
            }
        }
        int res = Math.max(rob, noRob);
       
        rob = 0;
        noRob = 0;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int tmpRob = rob;
            rob = Math.max(rob, noRob + num);
            noRob = tmpRob;
        }
        return Math.max(res, Math.max(rob, noRob));
    }
}

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.

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

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

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.

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

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

public class Solution {

    public int missingNumber(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        for (int i = 0; i < nums.length; i++) {

            int n = nums[i];

            if (n < nums.length && nums[n] != n) {

                nums[i] = nums[n];

                nums[n] = n;

                i--;

            }

        }

        for (int i = 0; i < nums.length; i++) {

            if (i != nums[i]) {

                return i;

            }

        }

        return nums.length;

    }

}

2.Bitwise operation solution

public int MissingNumber(int[] nums) {
    int xorResult = 0;
    for(int i = 0; i < nums.Length; i++)
        xorResult ^= nums[i] ^ i;
    xorResult ^= nums.Length;
    return xorResult;
}

3.Math solution by sum total

public int MissingNumber(int[] nums) {
    int result = nums.Length * (nums.Length + 1) / 2;
    for(int i = 0; i < nums.Length; i++)
        result -= nums[i];
    return result;
}

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0) {

            return 0;

        }

        int row = grid.length;

        int column = grid[0].length;

        int num = 0;

        for (int i = 0; i < row; i++) {

            for (int j = 0; j < column; j++) {

                if (grid[i][j] == '1') {

                    num++;

                    tag(grid, i, j);

                }

            }

        }

        return num;

    }

    

    private void tag(char[][] grid, int i, int j) {

        int row = grid.length;

        int column = grid[0].length;

        if (grid[i][j] == '1') {

            grid[i][j] = '2';

            if (i - 1 >= 0) tag(grid, i - 1, j);

            if (i + 1 < row) tag(grid, i + 1, j);

            if (j - 1 >= 0) tag(grid, i, j - 1);

            if (j + 1 < column) tag(grid, i , j + 1);

        }

    }

}