private static class Node {
   private Node parent;
   private Node left;
   private Node right;
   private int value;

   public Node(int value) {
       this.value = value;
   }
}

public void remove(int value) {
   Node val = find(value);
   removeNode(val);
}

private void removeNode(Node val) {
   if (val == null) {
       throw new RuntimeException("SBT is not contain " + val.value);
   }
   if (val.left == null && val.right == null) {
       if (val.parent == root) {
           root = null;
       } else if (val.parent.left == val){
           val.parent.left = null;
       } else {
           val.parent.right = null;
       }
   } else if (val.left != null) {
       Node max = maxNode(val.left);
       swap(max, val);
       removeNode(max);
   } else {
       Node min = minNode(val.right);
       swap(min, val);
       removeNode(min);
   }
}

private void swap(Node n1, Node n2) {
   int tmp = n1.value;
   n1.value = n2.value;
   n2.value = tmp;
}

public boolean contains(int value) {
   Node cur = root;
   while (cur != null && cur.value != value) {
       if (cur.value < value) {
           cur = cur.right;
       } else {
           cur = cur.left;
       }
   }
   return cur != null;
}

public int max() {
   if (isEmpty()) {
       throw new RuntimeException("BST is empty.");
   }
   return maxNode(root).value;
}

private Node maxNode(Node root) {
   if (root == null) {
       return null;
   }
   Node cur = root;
   while (cur.right != null) {
       cur = cur.right;
   }
   return cur;
}

public int min() {
   if (isEmpty()) {
       throw new RuntimeException("BST is empty");
   }
   Node min = minNode(root);
   return min.value;
}

private Node minNode(Node root) {
   if (root == null) {
       return null;
   }
   Node cur = root;
   while (cur.left != null) {
       cur = cur.left;
   }
   return cur;
}

public int predecessor(int value) {
   if (!contains(value)) {
       throw new RuntimeException("BST not contains " + value);
   }
   Node val = find(value);
   if (val.left != null) {
       return maxNode(val.left).value;
   }

   Node p = val.parent;
   while (p != null && p.left == val) {
       val = p;
       p = val.parent;
   }
   if (p == null) {
       return Integer.MIN_VALUE; // 不存在 该如何处理 ？抛异常？
   } else {
       return p.value;
   }
}

public int successor(int value) {
   if (!contains(value)) {
       throw new RuntimeException("BST is not contain " + value);
   }
   Node val = find(value);
   if (val.right != null) {
       return minNode(val.right).value;
   }

   Node p = val.parent;
   while (p != null && p.right == val) {
       val = p;
       p = val.parent;
   }
   if (p == null) {
       return Integer.MAX_VALUE; // 不存在 该如何处理 ？抛异常？
   } else {
       return p.value;
   }
}

public List<Integer> preorder() {
// return preOrder(root);
   return preOrderNonRecursive();
}

private List<Integer> preOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.add(root.value);
   order.addAll(preOrder(root.left));
   order.addAll(preOrder(root.right));
   return order;
}

private List<Integer> preOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   order.add(root.value);
   Node cur = root.left;
   Node p;
   while (!stack.isEmpty()) {
       while (cur != null) {
           order.add(cur.value);
           stack.push(cur);
           cur = cur.left;
       }
       while (!stack.isEmpty()) {
           p = cur;
           cur = stack.peek().right;
           if (p == cur) {
               cur = stack.pop();
           } else {
               break;
           }
       }
   }
   return order;
}

private List<Integer> preOrderNonRecursive1() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   stack.push(root);
   Node cur;
   while (!stack.isEmpty()) {
       cur = stack.pop();
       order.add(cur.value);
       if (cur.right != null) {
           stack.push(cur.right);
       }
       if (cur.left != null) {
           stack.push(cur.left);
       }
   }
   return order;
}

public List<Integer> inorder() {
   return inOrder(root);
}

private List<Integer> inOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.addAll(inOrder(root.left));
   order.add(root.value);
   order.addAll(inOrder(root.right));
   return order;
}

private List<Integer> inOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   Node cur = root;
   while (cur != null || !stack.isEmpty()) {
       while (cur != null) {
           stack.push(cur);
           cur = cur.left;
       }
       if (!stack.isEmpty()) {
           cur = stack.pop();
           order.add(cur.value);
           cur = cur.right;
       }
   }
   return order;
}

public List<Integer> postorder() {
   return postOrder(root);
}

private List<Integer> postOrder(Node root) {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   order.addAll(postOrder(root.left));
   order.addAll(postOrder(root.right));
   order.add(root.value);
   return order;
}

private List<Integer> postOrderNonRecursive() {
   List<Integer> order = new ArrayList<>();
   if (root == null) {
       return order;
   }
   Stack<Node> stack = new Stack<>();
   Node cur = root;
   stack.push(cur);
   cur = root.left;
   Node p;
   while (!stack.isEmpty()) {
       while (cur != null) {
           stack.add(cur);
           cur = cur.left;
       }
       while (!stack.isEmpty()) {
           p = cur;
           cur = stack.peek().right;
           if (p == cur) {
               cur = stack.pop();
               order.add(cur.value);
           } else {
               break;
           }
       }
   }

   return order;
}

package io.github.ztmark;

import com.google.common.collect.ImmutableList;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Random;

public class BloomFilter<T> {

    private final BitSet bitSet;
    private final int bitSize;
    private final int expectedNumberOfElements;
    private final ImmutableList<HashFunction> hashFunctions;
    private final int k;
    private int addedNumberOfElements;



    public BloomFilter(int bitSize, int expectedNumberOfElements) {
        if (bitSize <= 0 || expectedNumberOfElements <= 0) {
            throw new RuntimeException("wrong parameters bitSize and expectedNumberOfElements should greater than zero.");
        }
        this.bitSize = bitSize;
        bitSet = new BitSet(bitSize);
        this.expectedNumberOfElements = expectedNumberOfElements;
        // k = m / n * ln2
        k = (int) Math.round(1.0 * bitSize / expectedNumberOfElements * Math.log(2));
        hashFunctions = HashFunctionGenerator.generateKHashFunctions(k);
        addedNumberOfElements = 0;
    }

    public void add(T elem) {
        for (HashFunction function : hashFunctions) {
            bitSet.set(Math.abs(function.hashInt(elem.hashCode()).asInt() / bitSize));
        }
        addedNumberOfElements++;
    }

    public boolean contains(T elem) {
        for (HashFunction function : hashFunctions) {
            if (!bitSet.get(Math.abs(function.hashInt(elem.hashCode()).asInt() / bitSize))) {
                return false;
            }
        }
        return true;
    }

    public double getFalsePositiveProbability() {
        // p = (1 - e^(-k * n / m)) ^ k
        return Math.pow((1 - Math.exp(-k * 1.0 * addedNumberOfElements / bitSize)), k);

    }

    public int getAddedNumberOfElements() {
        return addedNumberOfElements;
    }

    public int getBitSize() {
        return bitSize;
    }

    public int getExpectedNumberOfElements() {
        return expectedNumberOfElements;
    }

    public int getNumberOfHashFunction() {
        return k;
    }

    private static final class HashFunctionGenerator {

        public static HashFunction generateAHashFunction() {
            return Hashing.murmur3_128(new Random(System.currentTimeMillis()).nextInt());
        }

        public static ImmutableList<HashFunction> generateKHashFunctions(int k) {
            Random random = new Random(System.currentTimeMillis());
            List<HashFunction> hashFunctions = new ArrayList<HashFunction>();
            for (int i = 0; i < k; i++) {
                hashFunctions.add(Hashing.murmur3_128(random.nextInt()));
            }
            return ImmutableList.copyOf(hashFunctions);
        }

    }


}

private static int kmp(String text, String pattern) {
   int[] next = next(pattern);
   int j = 0;
   for (int i = 0; i < text.length(); i++) {
       while (true) {
           if (j == pattern.length()) {
               return i - j;
           }
           if (text.charAt(i) == pattern.charAt(j)) {
               j++;
               break;
           } else if (j == 0){
               break;
           } else {
               j = next[j - 1];
           }
       }
   }
   return -1;
}

private static int[] next(String pattern) {
   int[] next = new int[pattern.length()];
   next[0] = 0;
   for (int i = 1; i < pattern.length(); i++) {
       int j = i - 1;
       while (j >= 0) {
           if (pattern.charAt(next[j]) == pattern.charAt(i)) {
               next[i] = next[j] + 1;
               break;
           } else if (next[j] == 0){
               next[i] = 0;
               break;
           } else {
               j = next[j - 1];
           }
       }
   }
   return next;
}

public String longestPalindrome(String s) {

        if (s == null || s.length() == 0 || s.length() == 1) return s;

        // 添加#符号
        // 这里应该有一个候选的符号列表，从该符号列表选取符号
        // 先检测字符串s是否包含该符号，如果包含就重新选一个，不包含才进行添加
        StringBuilder sb = new StringBuilder(s.length() * 2 + 1);
        sb.append('#');
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append('#');
        }

        String origin = s;
        s = sb.toString();

        int[] R = new int[s.length()];
        int id = 0;
        int maxR = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i < maxR) {
                // 2 * id - i是i关于id的对称点
                // 因为题目里有说s的length最大为1000
                // 所以这里 2 * id是安全的
                R[i] = Math.min(R[2 * id - i], maxR - i);
            } 
            //else {
              //  R[i] = 0; // 默认也是0
            //}

            while (i - R[i] >= 0 && i + R[i] < s.length() && s.charAt(i - R[i]) == s.charAt(i + R[i])) {
                R[i]++;
            }
            R[i]--; // 减去s[i-0] == s[i+0]时加的

            if (i + R[i] > maxR) {
                maxR = i + R[i];
                id = i;
            }
        }

        id = 0;
        for (int i = 0; i < R.length; i++) {
            if (R[i] > R[id]) {
                id = i;
            }
        }
        // 慢一些 36ms
        //return s.substring(id - R[id], id + R[id]).replaceAll("#", "");

        // 计算出在原始字符串的位置 快一些 18ms
        int start = 0;
        int end = 0;
        if (s.charAt(mid) == '#') {
            start = mid / 2 - max / 2;
            end = mid / 2 + max / 2;
        } else {
            start = (mid - 1) / 2 - (max - 1) / 2;
            end = (mid - 1) / 2 + (max + 1) / 2;
        }
        return origin.substring(start, end);
    }

import java.util.Arrays;

public class LongestIncreasingSubsequence300 {
	// 算法一
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            int max = dp[i];
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    int tmp = dp[j] + 1;
                    max = max < tmp ? tmp : max;
                }
            }
            dp[i] = max;
            if (dp[i] > res) {
                res = dp[i];
            }
        }
        return res;
    }

    /*
    算法二
    
    dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值  越小
    那么就有更大的可能后面的的数比这个大 从而使整个递增子序列 更长

    dp 数组是递增的  可以用反证法证明
    */
    public int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length + 1]; // dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值
        dp[0] = Integer.MIN_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int j = 0;
            for (; j < res; j++) {
                if (dp[j] == nums[i]) {
                    break;
                } else if (dp[j] > nums[i]) { // 原来的长度为i的递增子序列的最后一个数的可能的最小值 大于 当前遍历到的数
                    dp[j] = nums[i];
                    break;
                }
            }
            if (j == res) { // 当前遍历的数比dp之前的数都大，那么就出现了长度更长的递增子序列
                dp[res++] = nums[i]; 
            }
        }
        return res;
    }

    /*
    算法三
    
    对2的改进
    因为dp是递增的，所以可以将线性遍历改为二分查找
    */
    public int lengthOfLIS3(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp[] = new int[nums.length + 1]; // dp[i]表示长度为i的递增子序列的最后一个数的可能的最小值
        dp[0] = Integer.MIN_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // Arrays.binarySearch 在 数组的 [fromIndex, toIndex) 不包含toIndex 查找指定的数
            // 找不到 返回  -insertIndex-1
            int p = Arrays.binarySearch(dp, 0, res + 1, nums[i]);
            if (p < 0) {
                p = - (p + 1);
                dp[p] = nums[i];
                res = p > res ? p : res;
            }
        }
        return res;
    }
}

public static <T extends Comparable<? super T>> void bubbleSort(T[] array) {
        for (int i = 0; i < array.length - 1; i++) { // n-1次循环就可以，n-1个元素在正确的位置上，那唯一个元素也一定在正确的位置上
            for (int j = 1; j < array.length - i; j++) { // i 是排好序的元素个数，且是数组中最大的i个元素，在数组的尾部
                if (array[j-1].compareTo(array[j]) > 0) {
                    swap(array, j-1, j);
                }
            }
        }
    }

public static <T extends Comparable<? super T>> void cocktailSort(T[] array) {
        //一趟来回遍历将两个元素排好序，将所有元素都排好序需要array.length/2趟
        for (int i = 0; i < array.length / 2; i++) {
            //将大值置换到尾部
            for (int j = i; j < array.length - 1; j++) {
                if (array[j].compareTo(array[j+1]) > 0) {
                    swap(array, j, j+1);
                }
            }
            //将小值置换到头部
            for (int j = array.length - 1 - i; j > i + 1; j--) {
                if (array[j].compareTo(array[j-1]) < 0) {
                    swap(array, j-1, j);
                }
            }
        }
    }

public static <T extends Comparable<? super T>> void insertionSort(T[] array, int left, int right) {
        for (int i = left+1; i <= right; i++) { // 第一个元素是排好序的
            T tmp = array[i];
            int j = i;
            while (j > 0 && tmp.compareTo(array[j-1]) < 0) { // 向前寻找适合位置
                array[j] = array[j-1];
                j--;
            }
            array[j] = tmp;
        }
    }

public static <T extends Comparable<? super T>> void selectionSort(T[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            T min = array[i];
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if (min.compareTo(array[j]) > 0) {
                    min = array[j];
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] array) {
    T[] tmp = (T[]) new Comparable[array.length];
    mergeSort(array, tmp, 0, array.length-1);
}

private static <T extends Comparable<? super T>> void mergeSort(T[] array, T[] tmpArray, int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        mergeSort(array, tmpArray, left, center);
        mergeSort(array, tmpArray, center+1, right);
        merge(array, tmpArray, left, center+1, right);
    }
}

private static <T extends Comparable<? super T>> void merge(T[] array, T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int num = rightEnd - leftPos + 1;
    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        if (array[leftPos].compareTo(array[rightPos]) < 0) {
            tmpArray[tmpPos++] = array[leftPos++];
        } else {
            tmpArray[tmpPos++] = array[rightPos++];
        }
    }
    while (leftPos <= leftEnd) {
        tmpArray[tmpPos++] = array[leftPos++];
    }
    while (rightPos <= rightEnd) {
        tmpArray[tmpPos++] = array[rightPos++];
    }
    // 将tmpArray中的 leftPos 到 rightEnd 的数据 拷贝到 array的对应位置上
    // 上面leftPos,rightPos都变了，rightEnd没有变，所以上面是先算了个数，这里用到
    for (int i = 0; i < num; i++,rightEnd--) {
        array[rightEnd] = tmpArray[rightEnd];
    }
}

public static <T extends Comparable<? super T>> void shellSort(T[] array) {
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < array.length; i++) { //i++ 对所有间隔gap的数进行插入排序
                T tmp = array[i];
                int j = i;
                while (j >= gap && tmp.compareTo(array[j-gap]) < 0) {
                    array[j] = array[j-gap];
                    j -= gap;
                }
                array[j] = tmp;
            }
        }
    }

public static <T extends Comparable<? super T>> void heapSort(T[] array) {
        for (int i = array.length / 2; i >= 0; i--) { // build heap
            percDown(array, i, array.length);
        }
        for (int i = array.length-1; i >= 0; i--) {
            swap(array, 0, i); // delete max ， i 是heap的逻辑大小 将max放在heap的最后面
            percDown(array, 0, i);
        }

    }

    /*
    build max heap
    i  是要下沉的节点
    n  是heap的大小
     */
    private static <T extends Comparable<? super T>> void percDown(T[] array, int i, int n) {
        T tmp = array[i];
        while (leftChild(i) < n) {
            int child = leftChild(i);
            if (child != n-1 && array[child+1].compareTo(array[child]) > 0) {
                child++;
            }
            if (tmp.compareTo(array[child]) < 0) {
                array[i] = array[child];
            } else {
                break;
            }
            i = child;
        }
        array[i] = tmp;
    }

    private static int leftChild(int i) {
        return 2 * i + 1;
    }

public static <T extends Comparable<? super T>> void quickSort(T[] array) {
        quickSort(array, 0, array.length-1);
    }
    
    private static <T extends Comparable<? super T>> void quickSort(T[] array, int left, int right) {
        //当数组的个数较少时（比如说10），使用插入排序
        if (left + 10 <= right) {
            T pivot = median3(array, left, right);
            int i = left, j = right - 1;
            while (true) {
                while (array[++i].compareTo(pivot) < 0) {} //通过median3可以知道第i个元素一定是小于pivot的
                while (array[--j].compareTo(pivot) > 0) {} //通过median3可以知道第j个元素就是pivot
                if (i < j) { // 这里通过上面的两个空的while循环可以知道 如果 i==j ,则array[i]==pivot
                    swap(array, i, j);
                } else {
                    break;
                }
            }
            swap(array, i, right-1); // 将pivot放再中间位置
            quickSort(array, left, i - 1);
            quickSort(array, i+1, right);
        } else {
            insertionSort(array, left, right);
        }
    }

    //选择pivot
    private static <T extends Comparable<? super T>> T median3(T[] array, int left, int right) {
        int center = (left + right) / 2;
        // 比较的顺序！！！
        if (array[center].compareTo(array[left]) < 0) {
            swap(array, left, center);
        }
        if (array[left].compareTo(array[right]) > 0) {
            swap(array, left, right);
        }
        if (array[center].compareTo(array[right]) > 0) {
            swap(array, center, right);
        }
        swap(array, center, right-1);
        return array[right-1];
    }