Walls and Gates

 You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        LinkedList<int[]> queue = new LinkedList<>();
        int m = rooms.length;
        int n = rooms[0].length;
       
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.add(new int[] {i, j});
                }
            }
        }
        int dis = 0;
        while (!queue.isEmpty()) {
            int count = queue.size();
            while (count-- > 0) {
                int[] p = queue.poll();
                int x = p[0];
                int y = p[1];
                if (x - 1 >= 0 &&rooms[x - 1][y] == Integer.MAX_VALUE) {
                    rooms[x-1][y] = dis + 1;
                    queue.add(new int[] {x - 1, y});
                }
                if (x + 1 < m && rooms[x+1][y] == Integer.MAX_VALUE) {
                    rooms[x+1][y] = dis + 1;
                    queue.add(new int[] {x+1, y});
                }
                if (y - 1 >= 0 && rooms[x][y-1] == Integer.MAX_VALUE) {
                    rooms[x][y-1] = dis + 1;
                    queue.add(new int[] {x, y - 1});
                }
                if (y + 1 < n && rooms[x][y + 1] == Integer.MAX_VALUE) {
                   rooms[x][y+1] = dis + 1;
                    queue.add(new int[] {x, y + 1});
                }
            }
            dis++;
        }
    }
}

实现读写锁

Mulilple thread problem. When a reader is reading:.
CALL
1.readlock()
2. to do something
3. readunlcok()  (when the reader completes reading)

when a writer is writing:
CALL
1. writelock()
2. to do something
3. writeunlock() (complete writing). 1

public class Lock {

private int readingReaders = 0;

private int writingWriters = 0;

private int waitingWriters = 0;

private boolean writerFirst = true; // 写入优先

public synchronized void readLock() {
try {
while (writingWriters > 0 || (writerFirst && waitingWriters > 0)) {
wait();
}
} catch (InterruptedException e) {
}

readingReaders++;
}

public synchronized void readUnLock() {
readingReaders--;
writerFirst = true;
notifyAll();
}

public synchronized void writeLock() {
waitingWriters++;
try {
while (readingReaders > 0 || writingWriters > 0) {
wait();
}
} catch (InterruptedException e) {
} finally {
waitingWriters--;
}

writingWriters++;
}

public synchronized void writeUnLock() {
writingWriters--;
writerFirst = false;
notifyAll();
}

public static void main(String args[]) {

}
}

去除代码中的comment

// Given Program
//   /* Test program */
//   int main()
//   {
//      // variable declaration
//      int a, b, c;
//      /* This is a test
//          multiline
//          comment for
//          testing */
//  // b = a + c;
//      a = b + c;
//   }
//
// Modified Program
//   int main()
//   {
//             int a, b, c;
//
//          a = b + c;
//   }

public String removeComment(String str) {
StringBuilder sb = new StringBuilder();
int n = str.length();
boolean singleComment = false;
boolean multiComment = false;
for (int i = 0; i < str.length(); i++) {
if (i + 1 < n && str.charAt(i) == '/' && str.charAt(i + 1) == '*') {
multiComment = true;
i++;
} else if (i + 1 < n && str.charAt(i) == '*' && str.charAt(i + 1) == '/') {
multiComment = false;
i++;
} else if (i + 1 < n && str.charAt(i) == '/' && str.charAt(i + 1) == '/') {
singleComment = true;
i++;
} else if (singleComment && str.charAt(i) == '\n') {
singleComment = false;
i++;
} else if (singleComment || multiComment) {
i++;
continue;
} else {
sb.append(str.charAt(i));
}
}
return sb.toString();
}

数组中，如果是找任意k个数和为0呢？

 如果是找任意k个数和为0呢？

private List<List<Integer>> findKSum0(int[] arr, int k) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(arr);
helper(arr, k, 0, 0, new ArrayList<Integer>(), res);
for (List<Integer> list : res) {
// System.out.println(list);
}
return res;
}

private void helper(int[] arr, int k, int cur, int curSum, List<Integer> list, List<List<Integer>> res) {
if (list.size() == k && curSum == 0) {
List<Integer> newList = new ArrayList<Integer>(list);
res.add(newList);
} else if (list.size() < k && cur < arr.length && curSum + arr[cur] <= 0) {
for (int i = cur; i < arr.length; i++) {
if (i != cur && arr[i] == arr[i - 1]) {
continue;
}
list.add(arr[i]);
helper(arr, k, i + 1, curSum + arr[i], list, res);
list.remove(list.size() - 1);
}
}
}

string 有多少palindrome substring。

string 有多少palindrome substring。
exp: 'aba' 返回4 , 'abba' 返回6

private int getNumOfPalinSubStr(String str) {
if (str == null || str.length() == 0) {
return 0;
}
int count = 0;
for (int i = 0; i < str.length(); i++) {
int start = i;
int end = i;
while (start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end)) {
count++;
start--;
end++;
}

start = i - 1;
end = i;
while (start >= 0 && end < str.length() && str.charAt(start) == str.charAt(end)) {
count++;
start--;
end++;
}
}
return count;
}

最长连续不下降子序列

最长连续不下降子序列:

private int getLongestNoDecrese2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] nums2 = Arrays.copyOf(nums, nums.length);
Arrays.sort(nums2);
int n = nums.length;
int dp[][] = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (nums[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][n];
}


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

private int getLongestNoDecrese2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int dp[] = new int[nums.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[i] >= nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
for (int d : dp) {
res = Math.max(d, res);
}
return res;
}

Print arbitrary binary tree by vertical levels / columns from left to right

example tree

      a
     / \
    b   c. more info on 1point3acres.com
   / \   \
  d   g   z
   \     /. visit 1point3acres.com for more.
    e   i
       /
      q. more info on 1point3acres.com
     /
    x
   /. 
  x1
/
x2

[x2]
[d, x1]. 
[b, e, x]
[a, g, q]
[c, i]
[z]

public void printTreeVertical(TreeNode node) {
if (node == null) return;
TreeMap<Integer, List<TreeNode>> treeMap = new TreeMap<Integer, List<TreeNode>>();
visit(node, 0, treeMap);
for (Entry<Integer, List<TreeNode>> entry : treeMap.entrySet()) {
for (TreeNode tmp : entry.getValue()) {
System.out.print(tmp.val);
}
System.out.println();
}
}

private void visit(TreeNode node, int column, TreeMap<Integer, List<TreeNode>> treeMap) {
if (node == null) {
return;
}
List<TreeNode> list = treeMap.get(column);
if (list == null) {
list = new ArrayList<TreeNode>();
treeMap.put(column, list);
}
list.add(node);
visit(node.left, column - 1, treeMap);
visit(node.right, column + 1, treeMap);
}

Inorder Successor in BST

 Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

/**
 * 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 inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        TreeNode cur = root;
        Stack<TreeNode> stk = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stk.isEmpty()) {
            if (cur != null) {
                stk.push(cur);
                cur = cur.left;
            } else {
                cur = stk.pop();
                if (prev == p) {
                    return cur;
                }
                prev = cur;
                cur = cur.right;
            }
        }
        return null;
    }
}

=============
/**
 * 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 inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            TreeNode res = p.right;
            while (res.left != null) {
                res = res.left;
            }
            return res;
        } else {
            TreeNode parent = root;
            TreeNode res = null;
            while (parent != p) {
                if (parent.val > p.val) {
                    res = parent;
                    parent = parent.left;
                } else {
                    parent = parent.right;
                }
            }
            return res;
        }
       
    }
}

Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Show Hint 

Follow up: How would you extend your design to be generic and work with all types, not just integer?

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    LinkedList<Integer> queue = new LinkedList<Integer>();
 
public PeekingIterator(Iterator<Integer> iterator) {
   // initialize any member here.
   while (iterator != null && iterator.hasNext()) {
       queue.offer(iterator.next());
   }  
}

    // Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
        return queue.peek();
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
   return queue.poll();
}

@Override
public boolean hasNext() {
   return !queue.isEmpty();
}
}

=======

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer peek;
   
public PeekingIterator(Iterator<Integer> iterator) {
   this.iterator = iterator;
   this.peek = null;
}

    // Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
        if (peek == null) {
            peek = iterator.next();
        }
        return peek;
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
   if (peek != null) {
       Integer res = peek;
       peek = null;
       return res;
   } else {
       return iterator.next();
   }
}

@Override
public boolean hasNext() {
   return peek != null || iterator.hasNext();
}
}

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.

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

// 0,1,0,3,12
// 1,0,0,3,12
// 1,3,0,0,12
// 1,3,12,0,0

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (n == 0) {
                queue.add(i);
            } else {
                if (!queue.isEmpty()) {
                    int idx = queue.pop();
                    nums[idx] = n;
                    nums[i] = 0;
                    queue.add(i);
                }
            }
        }
    }
}

=====

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int firstZero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            } else {
                int tmp = nums[firstZero];
                nums[firstZero] = nums[i];
                nums[i] = tmp;
                firstZero++;
            }
        }
    }
}
========

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

Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

public class Solution {
    public String shortestPalindrome(String s) {
       if(s.length() <= 1){ return s; }
        String curs = s + " " + new StringBuilder(s).reverse().toString();
        int[] trace = new int[curs.length()];
        for(int i = 1 ; i < curs.length() ; i++){
            int curindex = trace[i-1];
            while(curindex > 0 && curs.charAt(curindex) != curs.charAt(i)){
                curindex = trace[curindex-1];
            }
            if(curs.charAt(curindex) == curs.charAt(i)){
                trace[i] = curindex+1;
            }
        }
        return new StringBuilder(s.substring(trace[curs.length()-1])).reverse().toString() + s;
    }
}

http://blog.csdn.net/v_july_v/article/details/7041827

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

public class Solution {
    public int countDigitOne(int n) {
        int count = 0;
        for (long k = 1; k <= n; k *= 10) {
            long r = n / k;
            long m = n % k;
           
            count += (r + 8)/ 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return count;
    }
}

System.out.println(s.countDigitOne(4135));

1:414 + 0 = 414
10:420 + 0 = 420
100:400 + 36 = 436
1000:1000 + 0 = 1000
2270

Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

public class Solution {

    public int strobogrammaticInRange(String low, String high) {
        if (low.length() > high.length() || (low.length() == high.length() && low.compareTo(high) > 0)) return 0;
        LinkedList<String> pre = new LinkedList<>();
        pre.add("");
        LinkedList<String> cur = new LinkedList<>();
        cur.add("1");
        cur.add("8");
        cur.add("0");
        int sl = low.length();
        int hl = high.length();
        int n = 1;
        int res = 0;
        while (true) {
            if (n >= sl && n <= hl) {
                for (String s : cur) {
                    if (s.charAt(0) == '0' && s.length() != 1) {
                        continue;
                    }
                    if (n == sl && s.compareTo(low) < 0) {
                        continue;
                    }
                    if (n == hl && s.compareTo(high) > 0) {
                        continue;
                    }
                    res++;
                }
            }
            if (n == hl) {
                break;
            }
            LinkedList<String> next = getNextStro(pre);
            pre = cur;
            cur = next;
            n++;
        }
        return res;
    }
   
    private LinkedList<String> getNextStro(LinkedList<String> pre) {
        int count = pre.size();
        while (count-- > 0) {
            String s = pre.poll();
            pre.addLast("0" + s + "0");
            pre.addLast("1" + s + "1");
            pre.addLast("8" + s + "8");
            pre.addLast("6" + s + "9");
            pre.addLast("9" + s + "6");
        }
        return pre;
    }
}

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

/**
 * 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> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<Integer>();
        PriorityQueue<Integer> queue = new PriorityQueue<>(
            new Comparator<Integer>() {
                public int compare(Integer i1, Integer i2) {
                    double sign = Math.abs(i1 - target) - Math.abs(i2 - target);
                    if (sign > 0) return 1;
                    else if (sign < 0) return -1;
                    else return 0;
                }
            }
            );
        visit(root, queue);
        while (k-- > 0) {
            res.add(queue.poll());
        }
        return res;
    }
 
    private void visit(TreeNode node, PriorityQueue<Integer> queue) {
        if (node == null) return;
        queue.add(node.val);
        visit(node.left, queue);
        visit(node.right, queue);
    }
}

======

/**
 * 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> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<Integer>();
        PriorityQueue<Integer> queue = new PriorityQueue<>(
            new Comparator<Integer>() {
                public int compare(Integer i1, Integer i2) {
                    double sign = Math.abs(i1 - target) - Math.abs(i2 - target);
                    if (sign > 0) return -1;
                    else if (sign < 0) return 1;
                    else return 0;
                }
            }
            );
        visit(root, queue, k, target);
        while (k-- > 0) {
            res.add(0, queue.poll());
        }
        return res;
    }
 
    private void visit(TreeNode node, PriorityQueue<Integer> queue, int k, double target) {
        if (node == null) return;
        if (queue.size() == k) {
            if (Math.abs(node.val - target) < Math.abs(queue.peek() - target)) {
                queue.poll();
                queue.offer(node.val);
            }
        } else {
            queue.offer(node.val);
        }
        visit(node.left, queue, k, target);
        visit(node.right, queue, k, target);
    }
}

======

/**
 * 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> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        List<Integer> big = new ArrayList<>();
       
        visitSmall(root, target, small);
        visitBig(root, target, big);
       
        int p1 = small.size() - 1;
        int p2 = big.size() - 1;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 < 0 || (p2 >= 0 && Math.abs(small.get(p1) - target) > Math.abs(big.get(p2) - target))) {
                res.add(big.get(p2));
                p2--;
            } else {
                res.add(small.get(p1));
                p1--;
            }
            if (res.size() == k) break;
        }
        return res;
    }
   
    private void visitSmall(TreeNode node, double target, List<Integer> res) {
        if (node == null) return;
        visitSmall(node.left, target, res);
        if (node.val > target) {
            return;
        }
        res.add(node.val);
        visitSmall(node.right, target, res);
    }
   
    private void visitBig(TreeNode node, double target, List<Integer> res) {
        if (node == null) return;
        visitBig(node.right, target, res);
        if (node.val <= target) {
            return;
        }
        res.add(node.val);
        visitBig(node.left, target, res);
    }
}

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Show Hint 

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0) return false;
        HashMap<Integer, HashSet<Integer>> edgeMap = new HashMap<>();
        for (int[] edge : edges) {
            int v1 = edge[0];
            int v2 = edge[1];
            HashSet<Integer> set1 = edgeMap.get(v1);
            if (set1 == null) {
                set1 = new HashSet<Integer>();
                edgeMap.put(v1, set1);
            }
            set1.add(v2);
         
            HashSet<Integer> set2 = edgeMap.get(v2);
            if (set2 == null) {
                set2 = new HashSet<Integer>();
                edgeMap.put(v2, set2);
            }
            set2.add(v1);
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        int count = 0;
        boolean visited[] = new boolean[n];
        while (!queue.isEmpty()) {
            int v = queue.pop();
            if (visited[v]) return false;
            count++;
            visited[v] = true;
            HashSet<Integer> nextVs = edgeMap.get(v);
            if (nextVs != null) {
                for (int next : nextVs) {
                    queue.add(next);
                    edgeMap.get(next).remove(v);
                }
            }
        }
        return count == n;
    }
}

=====

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        int nums[] = new int[n];
        Arrays.fill(nums, -1);
        for (int edge[] : edges) {
            int x = find(nums, edge[0]);
            int y = find(nums, edge[1]);
            if (x == y) return false;
            //nums[x] = y;
            nums[y] =x;
        }
        return edges.length == n - 1;
    }
   
    private int find(int[] nums, int x) {
        if (nums[x] == -1) {
            return x;
        }
        return find(nums, nums[x]);
    }
   
}

Alien Dictionary

 There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".
Note:

1. You may assume all letters are in lowercase.
2. If the order is invalid, return an empty string.
3. There may be multiple valid order of letters, return any one of them is fine.

public class Solution {
    public String alienOrder(String[] words) {
        HashMap<Character, Set<Character>> map = new HashMap<>();
        HashMap<Character, Integer> inDegree = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
            }
        }
        for (int i = 0; i < words.length; i++) {
            String w1 = words[i];
            for (int j = i + 1; j < words.length; j++) {
                String w2 = words[j];
                for (int k = 0; k < w1.length() && k < w2.length(); k++) {
                    char from = w1.charAt(k);
                    char to = w2.charAt(k);
                    if (from == to) continue;
                    Set<Character> tos = map.get(from);
                    if (tos == null) {
                        tos = new HashSet<Character>();
                        map.put(from, tos);
                    }
                    if (!tos.contains(to)) {
                        tos.add(to);
                        inDegree.put(to, inDegree.get(to) + 1);
                    }
                    break;
                }
            }
        }
        LinkedList<Character> queue = new LinkedList<Character>();
        StringBuilder sb = new StringBuilder();
        for (Character key : inDegree.keySet()) {
            if (inDegree.get(key) == 0) {
                queue.add(key);
            }
        }
        while (!queue.isEmpty()) {
            char c = queue.pop();
            sb.append(c);
            if (!map.containsKey(c)) continue;
            for (char to : map.get(c)) {
                inDegree.put(to, inDegree.get(to) - 1);
                if (inDegree.get(to) == 0) {
                    queue.add(to);
                }
            }
        }
        if (sb.length() != inDegree.size()) return "";
        else return sb.toString();
    }
}

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Credits:

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int n : nums) {
            max = Math.max(max, n);
            min = Math.min(min,n);
        }
        int n = nums.length;
        if (max == min) {
            return 0;
        }
        int gap = (int) Math.ceil((max - min) * 1.0 / (n - 1));
        int maxBucket[] = new int[n];
        for (int i = 0; i < n; i++) {
            maxBucket[i] = Integer.MIN_VALUE;
        }
        int minBucket[] = new int[n];
        Arrays.fill(minBucket, Integer.MAX_VALUE);
        for (int num : nums) {
            int id = (num - min) / gap;
            maxBucket[id] = Math.max(num, maxBucket[id]);
            minBucket[id] = Math.min(num, minBucket[id]);
        }
        int res = 0;
        int preMax = min;
        for (int i = 0; i < n; i++) {
            if (minBucket[i] > maxBucket[i]) {
                continue;
            }
            res = Math.max(res, minBucket[i] - preMax);
            preMax = maxBucket[i];
        }
        return res;
    }
}

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

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int n : nums) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        if (min == max) {
            return 0;
        }
        HashMap<Integer, int[]> bucket = new HashMap<>();
        int bucketSize = (int) Math.ceil((max - min) * 1.0 / nums.length);
        for (int n : nums) {
         //   if (n == min || n == max) continue;
            int bucketID = (n - min) / bucketSize;
            int[] scope = bucket.get(bucketID);
            if (scope == null) {
                scope = new int[2];
                scope[0] = n;
                scope[1] = n;
                bucket.put(bucketID, scope);
            } else {
                scope[0] = Math.min(scope[0], n);
                scope[1] = Math.max(scope[1], n);
            }
        }
        int res = bucketSize;
        int lastMax = min;
        for (int i = 0; i < nums.length; i++) {
            if (bucket.containsKey(i)) {
                int[] scope = bucket.get(i);
                res = Math.max(res, scope[0] - lastMax);
                lastMax = scope[1];
            }
        }
        res = Math.max(res, max - lastMax);
        return res;
    }
}

Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Related problem: Reverse Words in a String II

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

Show Tags

Show Similar Problems

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int left = nums.length - k;
        int right = k;
     
        int[] leftNums = new int[left];
        for (int i = 0; i < left; i++) {
            leftNums[i] = nums[i];
        }
        int[] rightNums = new int[right];
        for (int i = 0; i < right; i++) {
            rightNums[i] = nums[i + left];
        }
        for (int i = 0; i < right; i++) {
            nums[i] = rightNums[i];
        }
        for (int i = 0; i < left; i++) {
            nums[i + right] = leftNums[i];
        }
    }
}

===========

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
   
    private void reverse(int[] nums, int s, int e) {
        while (s < e) {
            int tmp = nums[s];
            nums[s] = nums[e];
            nums[e] = tmp;
            s++;
            e--;
        }
    }
}

Count Primes

Description:

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

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

Hint:

public class Solution {
    public int countPrimes(int n) {
        boolean notPrimes[] = new boolean[n + 1];
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrimes[i]) {
                res++;
                for (int j = 2; j * i < n; j++) {
                    notPrimes[i * j] = true;
                }
            }
        }
        return res;
    }
}