数据范围

数据范围	算法时间复杂度	最小包含2进制位数
$10^{5}$	$O(n)或者O(nlogn)$	17
$3^{19}$	整型中3的最大次幂	1162261467
int 最大值	2147483647
long 最大值	9223372036854775807	$10^{18}$

常用结论

ID	Key Words	Conclusion
1	取余；MOD；乘积；	乘积的取余等于每个数取余的乘积再取余
2	数组；	升序数组中任意两元素差的最小值，一定是相邻两元素的差
3	树；搜索树；遍历	二叉搜索树中序遍历得到的值为升序序列
4	同余定理	(a - b) % k == 0 —> a % k == b % k
5	银行；高精度	银行处理数据用 BigDecimal: 可以处理任意精度的数据
6	三点共线	经过同一点的两条直线斜率相等，则两直线重合
7	向上取整	（ a + b - 1) / b
8	四舍五入	（ a + b / 2) / b
9	组合数求和公式	$C{n}^{0}+C{n}^{1}+…+C_{n}^{n}=2^{n}$
10	偶数长度时满足	$C{n}^{0}+C{n}^{2}+…=C{n}^{1}+C{n}^{3}+…=2^{n-1}$
11	1~n中平方数的个数	$\sqrt{n}$
12	卡塔兰数	满足递归式：$h(n)=h(0)h(n-1)+h(1)h(n-2)+…+h(n-1)*h(0)$ 可以用$C{0}=1,C{n+1}=\frac{2(2n+1)}{n+2}C_{n}$来计算一阶卡特兰数
13	正则表达式中需要转义的字符	``* . ? + $ ^ [ ] ( ) { }	\ /``
14	格雷码	G(i) = i ^ i >> 1 避免信号传输错误
15	逻辑运算符	将一个数变 为其相反数：其补码+1（-b = ~b + 1)
16	循环数组索引变化	offset_index 可正可负 index = ((now_index + index_offset) % n + n) % n;
17	Java基本类型clone	一维数组深克隆、多维数组浅克隆
18	布尔运算分配律	a&(b^c) = (a&b)^(a&c)
19	错排公式	$f(n)=(n - 1)*(f(n - 1)+f(n-2))(n>2)$ $f(1)=0,f(2)=1$
20	深入理解	DP本质是在有向无环图上按拓扑排序转移，点是状态，边是转移

字符串拼接效率比较

public static void main(String[] args) {
    long start = 0L;
    long end = 0L;


    System.out.println("字符串拼接执行效率比较：");

    String s1 = "";
    start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {//十万次
        s1 = s1 + "a";
    }
    end = System.currentTimeMillis();
    System.out.println("1、+ 方式拼接10万次耗时：" + (end - start) + "毫秒!");

    String s2 = "";
    start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {//十万次
        s2 += "b";
    }
    end = System.currentTimeMillis();
    System.out.println("2、+= 方式拼接10万次耗时：" + (end - start) + "毫秒!");

    StringBuffer bf = new StringBuffer();
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {//千万次
        bf.append("c");
    }
    end = System.currentTimeMillis();
    System.out.println("3、StringBuffer.append 方式拼接1000万次耗时：" + (end - start) + "毫秒!");

    StringBuilder bl=new StringBuilder();
    start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {//千万次
        bl.append("d");
    }
    end = System.currentTimeMillis();
    System.out.println("4、StringBuilder.append 方式拼接1000万次耗时：" + (end - start) + "毫秒!");
}

结果：

字符串拼接执行效率比较：
1、+ 方式拼接10万次耗时：4697毫秒!
2、+= 方式拼接10万次耗时：1207毫秒!
3、StringBuffer.append 方式拼接1000万次耗时：114毫秒!
4、StringBuilder.append 方式拼接1000万次耗时：90毫秒!

内存消耗：
+ > += > StringBuffer = StringBuilder

解释

+方式拼接的本质是 s = new StringBuilder(s).append('char').toString();

其中耗时最多的是toString()，执行一次toString()耗时在几微米到几毫秒不等。

结论

遇到需要大量字符串拼接的场景，StringBuilder是最好的选择。

Java中List转数组

1.List to int/long/double

关键是mapToInt/mapToLong/mapToDouble函数，它决定了Integer到int时值的映射关系。

List<Integer> list = new ArrayList<>();

// 1 : i -> i 为lambda表达式
int[] b = list.stream().mapToInt(i -> i).toArray();
// int[] b = list.stream().mapToInt(i -> i + 3).toArray(); // 表示转int时每个值加3

// 2 : 使用Integer.valueOf()方法来进行值的映射
int[] c = list.stream().mapToInt(Integer::valueOf).toArray();

2.List to String Array

List<String> list = new ArrayList<>();

// to String Array
String[] arr = list.toArray(new String[0]); // better
// or
String[] arr = list.toArray(new String[list.size()]);