Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

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


public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        while(n!=0) {
            if((n&1)==1) ret+=1;
            n = n>>>1;
        }
        return ret;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            ret += (n & 1);
            n = n >> 1;
        }
        return ret;
    }
}

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

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


public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int t = 0;
        for(int i=0;i<32;i++) {
            int b = n & (1<<i);
            if(b!=0) {
                t = t | (1<<(31-i));
            }
        }
        return t;
    }
}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

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

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class BSTIterator {
    private Stack<TreeNode> stk;
    public BSTIterator(TreeNode root) {
        stk = new Stack<TreeNode>();
        TreeNode p = root;
        while(p!=null) {
            stk.push(p);
            p = p.left;
        }
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stk.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        if(!hasNext()) {
            // error here
        }
        TreeNode node = stk.pop();
        if(node.right!=null) {
            TreeNode tmp = node.right;
            while(tmp!=null) {
                stk.push(tmp);
                tmp = tmp.left;
            }
        }
        return node.val;
    }
}
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

==========

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class BSTIterator {
   
    Stack<TreeNode> stk = new Stack<TreeNode>();
   
    public BSTIterator(TreeNode root) {
        addToStk(root);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stk.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stk.pop();
        addToStk(node.right);
        return node.val;
    }
   
    private void addToStk(TreeNode node) {
        TreeNode p = node;
        while (p != null) {
            stk.push(p);
            p = p.left;
        }
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

public class Solution {
    public int titleToNumber(String s) {
        int x  = 0;
        if(s==null || s.length()==0) {
            return x;
        }
        for(int i=0;i<s.length();i++) {
            x *= 26;
            x += s.charAt(i) - 'A' + 1;
        }
        return x;
    }
}

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

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


public class Solution {
    public int majorityElement(int[] num) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<num.length;i++) {
            int n = num[i];
            Integer count = map.get(n);
            if(count==null) {
                map.put(n, 1);
            } else {
                map.put(n, count.intValue()+1);
            }
        }
        for(Integer key : map.keySet()) {
            if(map.get(key) > num.length/2) {
                return key;
            }
        }
        return num[0];
    }
}

public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
        int threshold = nums.length / 2;
        for (int n : nums) {
            Integer f = freq.get(n);
            if (f == null) {
                freq.put(n, 1);
            } else {
                freq.put(n, f + 1);
                if (f + 1 > threshold) {
                    return n;
                }
            }
        }
        return nums[0];
    }
}

=======

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int majority = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                majority = nums[i];
                count = 1;
            } else {
                if (nums[i] == majority) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return majority;
    }
}

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

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


public class Solution {
    public int findPeakElement(int[] num) {
        int s = 0;
        int e = num.length;
        while(s<=e) {
            int m = (s+e)/2;
           
            if((m==0 || num[m]>num[m-1]) && (m==num.length-1 || num[m]>num[m+1])) {
                return m;
            } else if((m==0 || num[m]>num[m-1]) && (m!=num.length-1 && num[m]<num[m+1])) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return -1;
    }
}

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

class MinStack {
   
    Stack<Integer> s = new Stack<Integer>();
    Stack<Integer> minS = new Stack<Integer>();
   
    public void push(int x) {
        s.push(x);
        if(minS.isEmpty() || x <= minS.peek()) {
           minS.push(x);
        }
    //    if(minS.isEmpty()) {
     //       minS.push(x);
      //  } else {
    //        minS.push(Math.min(x, minS.peek()));
    //    }
    }
    public void pop() {
        int i = s.peek();
        s.pop();
        if(i==minS.peek()) {
            minS.pop();
        }
    }
    public int top() {
        return s.peek();
    }
    public int getMin() {
        return minS.peek();
    }
}

=====

class MinStack {
 
    Stack<Integer> stk = new Stack<Integer>();
    Stack<Integer> minStk = new Stack<Integer>();
 
    public void push(int x) {
        stk.push(x);
        if (minStk.isEmpty()) {
            minStk.push(x);
        } else {
            int top = minStk.peek();
            minStk.push(Math.min(x, top));
        }
    }

    public void pop() {
        stk.pop();
        minStk.pop();
    }

    public int top() {
        return stk.peek();
    }

    public int getMin() {
        return minStk.peek();
    }
}

========

public class MinStack { long min; Stack<Long> stack; public MinStack(){ stack=new Stack<>(); } public void push(int x) { if (stack.isEmpty()){ stack.push(0L); min=x; }else{ stack.push(x-min);//Could be negative if min value needs to change if (x<min) min=x; } } public void pop() { if (stack.isEmpty()) return; long pop=stack.pop(); if (pop<0) min=min-pop;//If negative, increase the min value } public int top() { long top=stack.peek(); if (top>0){ return (int)(top+min); }else{ return (int)(min); } } public int getMin() { return (int)min; } }

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

public class Solution {
    public List<String[]> solveNQueens(int n) {
        List<String[]> boards = new ArrayList<String[]>();
        if(n<0) return boards;
        char[][] board = new char[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                board[i][j] = '.';
            }
        }
        helper(n, boards, board, 0);
        return boards;
    }
   
    private void helper(int n, List<String[]> boards, char[][] board, int row) {
        if(row==n) {
            String[] copy = new String[n];
            for(int i=0;i<n;i++) {
                copy[i] = new String(board[i]);
            }
            boards.add(copy);
        } else if(row<n) {
            for(int i=0;i<n;i++) {
                if(check(board, row, i)) {
                    board[row][i] = 'Q';
                    helper(n, boards, board, row+1);
                    board[row][i] = '.';
                }
            }
        }
    }
   
    private boolean check(char[][] board, int row, int column) {
        for(int i=0;i<row;i++) {
            if(board[i][column]=='Q') return false;
            if((column- (row-i))>=0 && board[i][column- (row-i)]=='Q') return false;
            if((column+(row-i))<board.length && board[i][column+(row-i)]=='Q') return false;
        }
        return true;
    }
}


=========

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        int[] board = new int[n];
        helper(board, 0, res);
        return res;
    }
   
    private void helper(int[] board, int k, List<List<String>> res) {
        if (k == board.length) {
            List<String> ret = new ArrayList<String>();
            for (int i = 0; i < board.length; i++) {
                char cs[] = new char[board.length];
                Arrays.fill(cs, '.');
                cs[board[i]] = 'Q';
                ret.add(new String(cs));
            }
            res.add(ret);
        } else if (k < board.length) {
            for (int i = 0; i < board.length; i++) {
                board[k] = i;
                if (check(board, k)) {
                    helper(board, k + 1, res);
                }
            }
        }
    }
   
    private boolean check(int[] board, int k) {
        for (int i = 0; i < k; i++) {
            if (board[i] == board[k] || Math.abs(board[i] - board[k]) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }
}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

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

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class BSTIterator {
    private Stack<TreeNode> stk;
    public BSTIterator(TreeNode root) {
        stk = new Stack<TreeNode>();
        TreeNode p = root;
        while(p!=null) {
            stk.push(p);
            p = p.left;
        }
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stk.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        if(!hasNext()) {
            // error here
        }
        TreeNode node = stk.pop();
        if(node.right!=null) {
            TreeNode tmp = node.right;
            while(tmp!=null) {
                stk.push(tmp);
                tmp = tmp.left;
            }
        }
        return node.val;
    }
}
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

public class Solution { public int maxProduct(int[] A) { if (A == null || A.length == 0) { return 0; } int max = A[0], min = A[0], result = A[0]; for (int i = 1; i < A.length; i++) { int temp = max; max = Math.max(Math.max(max * A[i], min * A[i]), A[i]); min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]); if (max > result) { result = max; } } return result; } }

=======

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int min = nums[0];
        int max = nums[0];
        int res = nums[0];
       
        for (int i = 1; i < nums.length; i++) {
            int tmpMin = min;
            int tmpMax = max;
           
            int n = nums[i];
            if (n > 0) {
                min = Math.min(n, tmpMin * n);
                max = Math.max(n, tmpMax * n);
            } else {
                min = Math.min(n, tmpMax * n);
                max = Math.max(n, tmpMin * n);
            }
           
            // min = Math.min(nums[i], Math.min(tmpMin * nums[i], tmpMax * nums[i]));
            // max = Math.max(nums[i], Math.max(tmpMin * nums[i], tmpMax * nums[i]));
           
            res = Math.max(res, max);
        }
        return res;
    }
}

Best Time to Buy and Sell Stock IV

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

 public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k >= len / 2) return quickSolve(prices);

        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }


    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }

Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

public class Solution {
    public int findMin(int[] num) {
        int s = 0;
        int e = num.length-1;
        if(num[s]<num[e]) return num[s];
       
        while(s<e && num[s]==num[s+1]) s++;
        while(s<e && num[e]==num[e-1]) e--;
        while(s<=e) {
            int m = (s+e)/2;
            if(m!=0 && num[m]<num[m-1]) {
                return num[m];
            }
            if(num[s]==num[e]) {
                s++;
            } else if(num[s]<num[e]) {
                return num[s];
            } else {
                if(num[m]>=num[s]) {
                    s = m+1;
                } else {
                    e = m-1;
                }
            }
        }
        return num[0];
    }
}


public class Solution {
    public int findMin(int[] num) {
        int s = 0;
        int e = num.length-1;
        if(num[s]<num[e]) return num[s];
       
        while(s<=e) {
            int m = (s+e)/2;
            if(m!=0 && num[m]<num[m-1]) {
                return num[m];
            }
            if(num[s]<num[e]) {
                return num[s];
            }
            if(num[s]==num[e]) {
                if(num[s]>num[0]) s++;
                else e--;
            } else {
                if(num[m]>=num[s]) {
                    s = m+1;
                } else {
                    e = m-1;
                }
            }
        }
        return num[0];
    }
}

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

public class Solution {
    public int findMin(int[] num) {
        int lo = 0;
        int hi = num.length - 1;
        int mid = 0;

        while(lo <= hi) {
            mid = lo + (hi - lo) / 2;

            if (num[mid] < num[hi]) {
                hi = mid;
            }
            else if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
}

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

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

public class Solution {
    public int trailingZeroes(int n) {
        int total = 0;
        int base = 5;
        while(n>=base) {
            total += n/base;
            if(base>Integer.MAX_VALUE/5) break;
            base *= 5;
        }
        return total;
    }
}

5倍数的个数，25倍数的个数，125倍数的个数，725倍数的个数。。。

=====

public class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        int fives = 5;
        int max = Integer.MAX_VALUE / 5;
        while (true) {
            int num = n / fives;
            if (num == 0) break;
            res += num;
         
            if (max < fives) break;
            fives *= 5;
        }
        return res;
    }
}

=======

public class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        if (n <= 0) {
            return res;
        }
        while (n != 0) {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
}

Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

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

public class Solution {

    public int compareVersion(String version1, String version2) {

        

        String tks1[] = version1.split("\\.");

        String tks2[] = version2.split("\\.");

        for(int i=0;i<tks1.length || i<tks2.length;i++) {

            int v1 = 0;

            int v2 = 0;

            if(i<tks1.length) v1 = Integer.parseInt(tks1[i]);

            if(i<tks2.length) v2 = Integer.parseInt(tks2[i]);

            if(v1<v2) return -1;

            else if(v1>v2) return 1;

        }

        return 0;

    }

}