算法（java）

快读

注意：

1. 如果读取的字符串中含有空格，则使用上述方法读取字符串，会存在读取问题，读到空格就 停止本次的数据读入，因为StreamTokenizer在读取输入数据时，是以空格或回车换行为每次 输入数据的分隔，所以如果要读取含有空格的字符串，要使用下面的方法

2. 虽然StreamTokenizer 有提供方法，可以修改输入数据时的分隔符，但是由于大部分题目的输 入数据中都是以空格或换行为分隔符，所以不建议进行修改（如要修改可以参考： StreamTokenizer 使用详解）

3. 如果要将数值数据以字符串的形式读入，则不能使用上述的方法，需要使用下面的方法。 StreamTokenizer 以字符串的形式读取数值数据，读入后的字符串变量将指向null，即 StreamTokenizer 以字符串的形式读入数值数据读入的结果为空。

4. 用StreamTokenizer 快读读的数范围不能抄过1e16！否则可能会导致double转long 丢失精度！一行一行读的建议直接用BufferedReader

class fastRW { 
    static BufferedReader br = new BufferedReader(new  
                                                  InputStreamReader(System.in)); 
    static StreamTokenizer st = new StreamTokenizer(br); 
    //记得最后加上OUT.flush() 
    static PrintWriter OUT = new PrintWriter(new  
                                             BufferedOutputStream(System.out)); 
    public static int nextInt() throws Exception { 
        st.nextToken(); 
        return (int) st.nval; 
    } 
    public static long nextLong() throws Exception { 
        st.nextToken(); 
        return (long) st.nval; 
    } 

    public static double nextDouble() throws Exception { 
        st.nextToken(); 
        return st.nval; 
    } 

    //只能读取由字母和数字组成的字符串 
    public static String nextStr() throws Exception { 
        st.nextToken(); 
        return st.sval; 
    } 

    public static String nextLine() throws Exception { 
        return br.readLine(); 
    } 
}

BigInteger

abs()    //返回 this 的绝对值 
negate()   //返回 -this 
add(BigInteger val)  //返回 this + val 
subtract(BigInteger val) //返回 this - val 
multiply(BigInteger val) //返回 this * val 
divide(BigInteger val) //返回 this / val 
remainder(BigInteger val) //返回 this % val 
mod(BigInteger val)  //返回 this mod val 
pow(int e)   //返回 this^e 
and(BigInteger val)  //返回 this & val 
or(BigInteger val)  //返回 this | val 
not()    //返回 ~this 
xor(BigInteger val)  //返回 this ^ val 
shiftLeft(int n)  //返回 this << n 
shiftRight(int n)  //返回 this >> n 
max(BigInteger val)  //返回 this 与 val 的较大值 
min(BigInteger val)  //返回 this 与 val 的较小值 
bitCount()   //返回 this 的二进制中不包括符号位的 1 的个数 
bitLength()   //返回 this 的二进制中不包括符号位的长度 
getLowestSetBit()  //返回 this 的二进制中最右边的位置 
compareTo(BigInteger val) //比较 this 和 val 值大小 
toString()   //返回 this 的 10 进制字符串表示形式 
toString(int radix)。  //返回 this 的 raidx 进制字符串表示形式 
  
  
gcd(BigInteger val)  //返回this绝对值与 val 绝对值的最大公约数 
isProbablePrime(int val) //返回一个表示 this 是否是素数的布尔值 
nextProbablePrime()  //返回第一个大于 this 的素数 
modPow(BigInteger b, BigInteger p) //返回 this ^ b mod p 
modInverse(BigInteger p) //返回 a mod p 的乘法逆元

String

String 
    trim()// 除去任何前导和尾随空格，如果该字符串没有前导或尾随的空格，则
返回值为该字符串本身 
    split(String regex)// 根据指定字符串拆分 
    indexOf(char ch)// 返回指定字符在此字符串中第一次出现的索引 
    starstWith(String prefix)//判断字符串是否以prefix为前缀开头 
    endsWith(String suffix) 
    toLowerCase()//返回字符串的小写形式 
    toUpperCase() 
    contains(String s) 
StringBuilder 
 append(String str)// 在此字符串追加str【参数为StringBuilder也可以】 
    insert(int index, char[] c)// 在index处插入字符数组c【c也可以是单个字符或者其他类型】 
    delete(int start, int end)// 移除此序列从start到end-1的字符串 
    deleteCharAt(int index)// 移除指定索引上的字符 
    setCharAt(int index, char ch)// 将指定索引处的字符替换为ch 
    reverse()// 将此字符串反转 

容器api

List 
  // 不要在 for/foreach 遍历 List 的过程中删除其中的元素，否则会抛出异常。 
  // 原因也很简单，list.size() 改变了，但在循环中已循环的次数却是没有随之变化。 
  // 原来预计在下一个 index 的数据,因为删除的操作变成了当前 index 的数据， 
  // 运行下一个循环时操作的会变为原来预计在下下个 index 的数据， 
  // 最终会导致操作的数据不符合预期。 
  add(int idx, Integer e) 
  set(int idx, Integer e)//修改 List 中第 idx 位置的值 
  
Queue 
  Queue<Integer> q = new LinkedList<>(); 
  // LinkedList 底层实现了 List 接口与 Deque 接口，而 Deque 接口继承自 Queue 接口， 
  // 所以 LinkedList 可以同时实现 List 与 Queue 。 
   
PriorityQueue //默认是小根堆 
  Queue<Integer> q2 = new PriorityQueue<>((x, y) -> {return y - x;});  // 大根堆 
  offer(Integer val) //入队  
  peek() //返回队头元素 
  poll() //返回队头元素并删除 
  
Deque //双端队列 
  push(Integer val) //将一个元素从队头加入Deque，等效于addFirst 
  add(Integer val) //将一个元素从队尾加入this 
  //add、remove 操作在遇到异常时会抛出异常，而offer、 poll 不会抛出异常。 
  
Set //元素不重复 
  addAll(Collection e)//将一个容器里的所有元素添加进 Set 
  retainAll(Collection e)//将 Set 改为两个容器内相同的元素 
  removeAll(Collection e)//将 Set 中与 e 相同的元素删除 
  HashSet//随机位置插入的 Set。 
  LinkedHashSet//保持插入顺序的 Set。 
  TreeSet//保持容器中元素有序的 Set，默认为升序。 
    Set<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // 降序  
    TreeSet<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // 降序  
    //TreeSet特有api 
 	  first() //返回 TreeSet 中第一个元素，无则返回 null 
      last() 
      floor(Integer val)//返回集合中 <=val 的第一个元素，无则返回 null 
      ceiling(Integer val)//返回集合中 >=val 的第一个元素，无则返回 null 
      higher(Integer val)//返回集合中 >val 的第一个元素，无则返回 null 
      lower(Integer val)//返回集合中 <val 的第一个元素，无则返回 null 
      pollFirst()//返回并删除 TreeSet 中第一个元素，无则返回 null 
      pollLast() 
  
Map //HashMap LinkedHashMap TreeMap与set中类似 
  keySet() //将 this 中所有元素的 key 作为集合返回 
  
//工具类 
Arrays 
  Arrays.sort() //排序区间为左闭右开 [firstIdx, lastIdx) 
  //Arrays.sort() 底层函数： 
    // 当你 Arrays.sort 的参数数组元素类型为基本数据类型 
    // （byte、short、char、int、long、double、float）时， 
    // 默认为 DualPivotQuicksort（双轴快排），复杂度最坏可以达到 O(n^2)。 
    // 当你 Arrays.sort 的参数数组元素类型为非基本数据类型时， 
    // 则默认为 legacyMergeSort 和 TimSort（归并排序），复杂度为O(nlog n)。 
  Arrays.binarySearch() //二分查找是否存在key，存在返回下标。不存在，返回一个负
数。 
 //源码 
     private static int binarySearch0(int[] a, int fromIndex, int toIndex, 
int key) { 
            int low = fromIndex; 
            int high = toIndex - 1; 
     
            while (low <= high) { 
                int mid = (low + high) >>> 1; 
                int midVal = a[mid]; 
     
                if (midVal < key) 
                    low = mid + 1; 
                else if (midVal > key) 
                    high = mid - 1; 
                else 
                    return mid; // key found 
            } 
            return -(low + 1);  // key not found. 
        } 
  
Collections 
  Collections.sort()//将其中所有元素转化为数组调用 Arrays.sort()， 
     //完成排序后再赋值给原本的集合。归并排序。 
  Collections.binarySearch()//该方法无法对指定区间进行搜索。 
  Collections.swap()// Collections.swap(list, i, j); 
  
//如果单纯是数值类型，-0.0 = 0.0 。若是对象类型，则 -0.0 != 0.0 。 
//倘若你尝试用 Set 统计斜率数量时,要把所有的斜率加入 Set 前将值增加 0.0。