Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it, each time your friend guesses a number, you give a hint, the hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"), your friend will use those hints to find out the secret number.

For example:

Secret number:  1807
Friend's guess: 7810

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)

According to Wikipedia: "Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking mind or paper and pencil game for two or more players, predating the similar commercially marketed board game Mastermind. The numerical version of the game is usually played with 4 digits, but can also be played with 3 or any other number of digits."

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows, in the above example, your function should return 1A3B.

You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Credits:

Special thanks to @jeantimex for adding this problem and creating all test cases.

public class Solution {
    public String getHint(String secret, String guess) {
        int a = 0;
        int b = 0;
        int[] nums = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            int c1 = secret.charAt(i) - '0';
            int c2 = guess.charAt(i) - '0';
            if (c1 == c2) {
                a++;
            } else {
                if (nums[c1] < 0) {
                    b++;
                }
                if (nums[c2] > 0) {
                    b++;
                }
                nums[c1]++;
                nums[c2]--;
            }
        }
        return a + "A" + b + "B";
    }
}

Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private int maxLen = 0;
   
    public int longestConsecutive(TreeNode root) {
        maxLen = 0;
        if (root == null) {
            return maxLen;
        }
        helper(root, 1);
        return maxLen;
    }
   
    private void helper(TreeNode node, int len) {
        if (node == null) return;
        maxLen = Math.max(maxLen, len);
        if (node.left != null) {
            if (node.left.val == node.val + 1) {
                helper(node.left, len + 1);
            } else {
                helper(node.left, 1);
            }
        }
        if (node.right != null) {
            if (node.right.val == node.val + 1) {
                helper(node.right, len + 1);
            } else {
                helper(node.right, 1);
            }
        }
    }
}

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
Special thanks to @Louis1992 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 Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node.val);
            if (node.left != null) {
                sb.append("l");
                queue.add(node.left);
            }
            if (node.right != null) {
                sb.append("r");
                queue.add(node.right);
            }
            sb.append("#");
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(0);
        int val = 0;
        int sign = 1;
        TreeNode node = root;
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) == '-') {
                sign = -1;
            } else if (Character.isDigit(data.charAt(i))) {
                val *= 10;
                val += data.charAt(i) - '0';
            } else if (data.charAt(i) == 'l') {
                node.left = new TreeNode(0);
                queue.add(node.left);
            } else if (data.charAt(i) == 'r') {
                node.right = new TreeNode(0);
                queue.add(node.right);
            } else {
                node.val = sign * val;
                val = 0;
                sign = 1;
                if (!queue.isEmpty())
                    node = queue.poll();
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

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

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node.val);
            if (node.left != null && node.right == null) {
                sb.append("l");
                queue.add(node.left);
            } else if (node.right != null && node.left == null) {
                sb.append("r");
                queue.add(node.right);
            } else if (node.right != null && node.right != null) {
                sb.append('b');
                queue.add(node.left);
                queue.add(node.right);
            } else {
                sb.append("e");
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(0);
        int val = 0;
        int sign = 1;
        TreeNode node = root;
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) == '-') {
                sign = -1;
            } else if (Character.isDigit(data.charAt(i))) {
                val *= 10;
                val += data.charAt(i) - '0';
            } else {
                if (data.charAt(i) == 'l') {
                    node.left = new TreeNode(0);
                    queue.add(node.left);
                } else if (data.charAt(i) == 'r') {
                    node.right = new TreeNode(0);
                    queue.add(node.right);
                } else if (data.charAt(i) == 'b') {
                    node.left = new TreeNode(0);
                    node.right = new TreeNode(0);
                    queue.add(node.left);
                    queue.add(node.right);
                }
                node.val = sign * val;
                val = 0;
                sign = 1;
                if (!queue.isEmpty())
                    node = queue.poll();
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Hint:

1. Try to solve it in one dimension first. How can this solution apply to the two dimension case?

public class Solution {
    public int minTotalDistance(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        ArrayList<Integer> xs = new ArrayList<>();
        ArrayList<Integer> ys = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    xs.add(i);
                    ys.add(j);
                }
            }
        }
        return getMin(xs) + getMin(ys);
    }
   
    private int getMin(ArrayList<Integer> list) {
        Collections.sort(list);
        int res = 0;
        int s = 0;
        int e = list.size() - 1;
        while (s <= e) {
            res += list.get(e--) - list.get(s++);
        }
        return res;
    }
}

Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:

[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

class MedianFinder {

    PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer i1, Integer i2) {
            return i2.intValue() - i1.intValue();
        }
    });
   
    // maxQueue + minQueue

    // Adds a number into the data structure.
    public void addNum(int num) {
        if (maxQueue.size() == 0 || num < maxQueue.peek()) {
            maxQueue.add(num);
        } else {
            minQueue.add(num);
        }
        if (maxQueue.size() - minQueue.size() == 2) {
            minQueue.add(maxQueue.poll());
        } else if (minQueue.size() - maxQueue.size() == 2) {
            maxQueue.add(minQueue.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (maxQueue.size() == minQueue.size()) {
            return (maxQueue.peek() + minQueue.peek()) * 1.0 / 2.0;
        } else if (maxQueue.size() > minQueue.size()) {
            return maxQueue.peek();
        } else {
            return minQueue.peek();
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

task schedule

2）Task Schedule
Tasks : AABABCD. more info on 1point3acres.com
Cooled Time: 2
output ： 输出总共时间
要求保持Tasks 的执行顺序不变。执行一个task的时间是1， 求执行tasks系列一共需要多少时间，比如他的例子： A－－AB－ABCD return 10

public int getTime(String str, int cool) {
    HashMap<Character, Integer> map = new HashMap<>();
    int i = 0;
    int time = 0;
    while (i < str.length()) {
      char c = str.charAt(i);
      if (!map.containsKey(c) || map.get(c) <= time) {
        map.put(c, time + cool + 1);
        i++;
        time++;
      } else {
        time = map.get(c);
      }
    }
    return time;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.getTime("AABABCD", 2));
  }

small or big endian

int i = 1;

char* p = (char *) &i;

if (p) {

// smallEdian

} else {

// bigEndian

}

Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null) return false;
        return helper(pattern, str, 0, 0, new HashMap<>(), new HashSet<>());
    }
   
    private boolean helper(String pattern, String str, int p, int q, HashMap<Character, String> map, HashSet<String> set) {
        if (p == pattern.length() && q == str.length()) {
            return true;
        } else if (p < pattern.length() && q < str.length()) {
            char c = pattern.charAt(p);
            if (map.containsKey(c)) {
                String s = map.get(c);
                if (str.substring(q).startsWith(s)) {
                    return helper(pattern, str, p + 1, q + s.length(), map, set);
                }
            } else {
                for (int i = q; i < str.length(); i++) {
                    String s = str.substring(q, i + 1);
                    if (set.contains(s)) continue;
                    map.put(c, s);
                    set.add(s);
                    if (helper(pattern, str, p + 1, i + 1, map, set)) return true;
                    map.remove(c);
                    set.remove(s);
                }
            }
        }
        return false;
    }
}

Flip Game

 You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].


public class Solution {
    public List<String> generatePossibleNextMoves(String s) {
       List<String> res = new ArrayList<>();
       if (s == null || s.length() == 0) return res;
       char cs[] = s.toCharArray();
       for (int i = 1; i < s.length(); i++) {
           if (cs[i] == cs[i - 1] && cs[i] == '+') {
               cs[i] = '-';
               cs[i - 1] = '-';
               res.add(new String(cs));
               cs[i] = '+';
               cs[i - 1] = '+';
           }
       }
       return res;
    }
}

返回s中包含set中所有字符的最短substring。

给定一个String s和一个字母表Set<Character> a，返回s中包含字母表中所有字符的最短substring。

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  public String window(String str, Set<Character> set) {
    if (set.isEmpty()) return "";
    int req = set.size();
    HashMap<Character, Integer> map = new HashMap<>();
    for (char c : set) {
      map.put(c, 0);
    }
    int s = 0;
    int e = 0;
    String res = "";
    while (true) {
      if (req > 0) {
        if (e == str.length()) break;
        char c = str.charAt(e);
        if (map.containsKey(c)) {
          if (map.get(c) == 0) req--;
          map.put(c, map.get(c) + 1);
        }
        e++;
      }
      if (req == 0) {
        if (res.isEmpty() || res.length() > e - s) {
          res = str.substring(s, e);
        }
        char c = str.charAt(s);
        if (map.containsKey(c)) {
          if (map.get(c) == 1) {
            req++;
          }
          map.put(c, map.get(c) - 1);
        }
        s++;
      }
    }
    return res;
  }
 
  public static void main(String[] args) {
    Solution s = new Solution();
    Set<Character> set = new HashSet<Character>();
    set.add('a');
    set.add('b');
    set.add('c');
    System.out.println(s.window("abbcad", set));
  }
}

Nim Game

 You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Credits:

public class Solution {
    public boolean canWinNim(int n) {
        // if (n <= 3) return true;
        // boolean pre3 = true;
        // boolean pre2 = true;
        // boolean pre1 = true;
        // for (int i = 4; i <= n; i++) {
        //     boolean cur = !pre3 || !pre2 || !pre1;
        //     pre3 = pre2;
        //     pre2 = pre1;
        //     pre1 = cur;
        // }
        // return pre1;
        return !(n % 4 == 0);
    }
}

smallest window contains query array, preserving order

 给一个string，比如UAXXBAUB，给一个pattern，比如AB，返回包含pattern的最短
substring，结果是AUB,考虑pattern是有序的。


import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  public String findShortestSnippet(String doc, String query) {
    HashMap<Character, List<Integer>> invertedIndex = new HashMap<>();
    for (char c : query.toCharArray()) {
      invertedIndex.put(c, new ArrayList<Integer>());
    }
    for (int i = 0; i < doc.length(); i++) {
      char c = doc.charAt(i);
      if (invertedIndex.containsKey(c)) {
        invertedIndex.get(c).add(i);
      }
    }
    int[] points = new int[query.length()];
    String res = "";
    while (points[0] < invertedIndex.get(query.charAt(0)).size()) {
      boolean find = true;
      for (int i = 1; i < points.length; i++) {
        if (points[i] == invertedIndex.get(query.charAt(i)).size()) {
            find = false;
            break;
        }
        while (invertedIndex.get(query.charAt(i)).get(points[i]) <= invertedIndex.get(query.charAt(i - 1)).get(points[i - 1])) {
          points[i]++;
          if (points[i] == invertedIndex.get(query.charAt(i)).size()) {
            find = false;
            break;
          }
        }
        if (!find) {
          break;
        }
      }
      if (find) {
        int end = invertedIndex.get(query.charAt(query.length() - 1)).get(points[points.length - 1]);
        int start = invertedIndex.get(query.charAt(0)).get(points[0]);
        int len = end - start + 1;
        if (res.isEmpty() || len < res.length()) {
          res = doc.substring(start, end + 1);
        }
      }
      points[0]++;
    }
    return res;
  }
 
  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.findShortestSnippet("abcbdbbefgg", "bb"));
  }
}

https://www.quora.com/Given-an-input-array-of-integers-of-size-n-and-a-query-array-of-integers-of-size-k-how-do-I-find-the-smallest-window-of-the-input-array-that-contains-all-the-elements-of-the-query-array-preserving-order?redirected_qid=1374998

find pairs of words that can be a palindrome

Given a string list，find all pairs of strings which can be combined to be a palindrome. eg: cigar + tragic -> cigartragic, none + xenon -> nonexenon。如果有n个词，每个词长度m，用HashSet可以用O(nm)做出来。第二道是find distance between two nodes in a binary tree。做到这道题的时候只剩十分钟左右了，做的险象环生，还好最后做出来了。

把所有的词丢进hashset。然后对每一个word, for each i in [0, word.length()), 将word拆成两个substring [0, i] and [i + 1, word.length())，如果一个词是palindrome而另一个词在set里，说明可以combine成palindrome，然后就可以返回这个pair了。

private void findPalinPair(String[] arr) {
HashSet<String> set = new HashSet<String>();
for (String a : arr) {
set.add(a);
}
for (String s : arr) {
for (int i = 0; i < s.length(); i++) {
String s1 = s.substring(0, i);
String s2 = s.substring(i);
if (isPalin(s1)) {
char cs[] = s2.toCharArray();
reverse(cs);
if (set.contains(new String(cs))) {
System.out.println(new String(cs) + "" + s);
}
}
}
}
}

private void reverse(char cs[]) {
int s = 0;
int e = cs.length - 1;
while (s <= e) {
char tmp = cs[s];
cs[s] = cs[e];
cs[e] = tmp;
s++;
e--;
}
}

private boolean isPalin(String str) {
int s = 0;
int e = str.length() - 1;
while (s <= e) {
if (str.charAt(s++) != str.charAt(e--)) {
return false;
}
}
return true;
}

Sorted insert for circular linked list

http://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  public static class LinkNode {
    LinkNode next;
    int val;
    public LinkNode(int v) {
      this.val = v;
    }
  }
 
  public LinkNode head;

  public void insert(int val) {
    LinkNode node = new LinkNode(val);
    if (head == null) {
      head = node;
      head.next = node;
    } else {
      if (node.val < head.val) {
        LinkNode tail = head;
        while (tail.next != head) tail = tail.next;
        node.next = head;
        tail.next = node;
        head = node;
      } else {
        LinkNode p = head;
        while (true) {
          if (p.next == head || p.next.val > val) {
            LinkNode next = p.next;
            p.next = node;
            node.next = next;
            break;
          }
          p = p.next;
        }
      }
    }
  }
 
  public void print() {
    LinkNode p = head;
    if (p == null) return;
    while (true) {
      System.out.print(p.val + " ");
      p = p.next;
      if (p == head) {
        break;
      }
    }
    System.out.println();
  }
 
  public static void main(String[] args) {
    Solution s = new Solution();
    s.print();
    s.insert(5);s.print();
    s.insert(3);s.print();
    s.insert(4);s.print();
    s.insert(2);s.print();
    s.insert(1);s.print();
  }
}

cyclical buffer of bytes

/ Implement a cyclical buffer of bytes of fixed size n.

// Support the creation and enqueue/dequeue operations.

// The buffer is intended to be use in a high throughput environment.

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
 
  int nums[];
  int head = 0;
  int size = 0;
  int count = 0;
 
  public Solution(int n) {
    this.size = n;
    this.nums = new int[n];
  }
 
  private void enque(int v) {
    if (count == size) {
      System.out.println("queue is full");
      return;
    }
    nums[(head + count) % size] = v;
    count++;
  }
 
  private int deque() {
    if (count == 0) {
      System.out.println("queue is empty");
      return 0;
    }
    int res = nums[head];
    head++;
    if (head == size) head = 0;
    count--;
    return res;
  }
 
  public static void main(String[] args) {
    Solution s = new Solution(2);
    s.enque(1);
    s.enque(2);
    System.out.println(s.deque());
    s.enque(3);
    System.out.println(s.deque());
    s.enque(4);
    System.out.println(s.deque());
    System.out.println(s.deque());
    System.out.println(s.deque());
  }
}

implement function strstrp(String a, String b) returns index where any permutation of b is a substring of a.

第二题是leetcode上strstr那道的衍生题, 要求implement function strstrp(String a, String b) returns index where any permutation of b is a substring of a.
e.g.
strstrp("hello", ''ell") returns 1
strstrp("hello",  "lle") returns 1
strstrp("hello",  "wor") returns -1

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {

  public static boolean isExist(String str, String t) {
    int req = t.length();
    HashMap<Character, Integer> map = new HashMap<>();
    for (char c : t.toCharArray()) {
      if (map.containsKey(c)) map.put(c, map.get(c) + 1);
      else map.put(c, 1);
    }
    int s = 0;
    int e = 0;
    while (true) {
      if (e - s < t.length()) {
        if (e == str.length()) break;
        char c = str.charAt(e);
        if (map.containsKey(c)) {
          if (map.get(c) > 0) {
            req--;
          }
          map.put(c, map.get(c) - 1);
        }
        e++;
      }
      if (e - s == t.length()) {
        if (req == 0) return true;
        char c = str.charAt(s);
        if (map.containsKey(c)) {
          if (map.get(c) >= 0) {
            req++;
          }
          map.put(c, map.get(c) + 1);
        }
        s++;
      }  
    }
    return false;
  }

  public static void main(String[] args) {
    System.out.println(isExist("hello", "oleld"));
  }
}

  private static boolean isSame(int[] arr, int[] arr1) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] != arr1[i]) return false;
    }
    return true;
  }
 
  public static boolean isExist(String str, String t) {
    int req = t.length();
    int arr[] = new int[256];
    for (char c : t.toCharArray()) {
      arr[c]++;
    }
    int s = 0;
    int e = 0;
    int arr2[] = new int[256];
    for (int i = 0; i < t.length(); i++) {
      arr2[str.charAt(i)]++;
    }
    for (int i = t.length(); i <= str.length(); i++) {
      boolean isSame = isSame(arr, arr2);
      if (isSame) return true;
      arr2[str.charAt(i - t.length())]--;
      if (i != str.length()) arr2[str.charAt(i)]++;
    }
    return false;
  }
 

http://www.geeksforgeeks.org/anagram-substring-search-search-permutations/

streaming median

让我找streaming median

private void getMedian(int nums[]) {

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {

public int compare(Integer i1, Integer i2) {

return i2.intValue() - i1.intValue();

}

});

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

int n = nums[i];

if (maxHeap.size() == 0 || n <= maxHeap.peek()) {

maxHeap.add(n);

} else {

minHeap.add(n);

}

if (maxHeap.size() - minHeap.size() >= 2) {

int val = maxHeap.poll();

minHeap.add(val);

}

if (minHeap.size() - maxHeap.size() >= 2) {

maxHeap.add(minHeap.poll());

}

if (maxHeap.size() == minHeap.size()) {

System.out.println((maxHeap.peek() + minHeap.peek()) / 2);

} else if (maxHeap.size() > minHeap.size()) {

System.out.println(maxHeap.peek());

} else{

System.out.println(minHeap.peek());

}

}

}