1.String.Join 方法 (A (String), B (String[]))

在指定 String 数组B的每个元素之间串联指定的分隔符 A，从而产生单个串联的字符串

1
2
3
4
String [] tmpStr = {abc, def, ghi};
String jn = string.Join("-", tmpStr);	// 此时输出为"abc-def-ghi"
// 常见用法:字符串数组chs->字符串str
String.join("",strings)//{"abcdefghi"}

2.split() 根据匹配给定的正则表达式来拆分字符串

1
2
3
4
5
6
String str = "Welcome-to-Runoob";
for (String retval: str.split("-")){
 	System.out.println(retval);
}  
// 分隔符返回值 :Welcome  to  Runoob
// 此方法常用来字符串->字符串数组(输入模式下的输入数组后的处理)

3.StringBuilder的delete()与deleteCharAt()

两个都是用来删除StringBuilder字符串指定索引处字符的方法

delete（int a,int b）有两个参数，删除索引从[a,b)的字符；

deleteCharAt（int a）只有一个参数，使用时删除索引为a的字符；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
StringBuffer buff = new StringBuffer("0123456789");
System.out.println("buff="+buff);

//删除下标从3到5的字符
buff.delete(3,5);
System.out.println("deletionBack="+ buff);

buff = new StringBuffer("0123456789");
//删除下标为8字符
buff.deleteCharAt(8);
System.out.println("delectCharAtBack="+buff);
// 输出如下:
// buff=0123456789
// deletionBack=01256789
// delectCharAtBack=012345679

4.List与数组互相转换

具体参考Java：List与数组相互转换


5.字符->字符串

1
String.valueOf(str.charAt(i))

6.StringBuilder的append()方法可以接受很多种类型


7.StringBuilder的setCharAt()方法

1
2
3
//第一个参数为索引,第二个参数为该索引处设置的值
public void setCharAt(int index, char ch)
sb.setCharAt(end, temp);

8.重载的remove()方法

ArrayList有两个remove()重载法，分别是:remove(int index) remove(Object o)

若参数输入为1，到底是删除对象1还是删除索引为1的元素呢?

最后发现：remove(1)是删除索引为1的元素；remove(new Integer(1))则删除元素1

因为1默认是基本类型int


9.数组转List集合方法：(注意包装类型)

1
2
3
4
5
6
7
8
9
方法1:
Integer[] nums = new Integer[5]; 	// 这里不能用int
Arrays.fill(nums,1);
List<Integer> list = Arrays.asList(nums);

方法2:
Integer[] nums = new Integer[5];
List<Integer> list = new ArrayList<>();
Collections.addAll(list, nums);

10.Java中的Math.atan2(double x, double y)方法

将指定的直角坐标(x, y)转换为极坐标(r, θ)，并返回弧度θ。

该方法通过计算 y/x 的反正切值来计算弧度θ，值域为(-π, π]。

atan2与atan区别：

参数个数不同：atan(double a)，而atan2(double y, double x)。

参数含义不同：atan中的参数a一般传y/x，也就是斜率k，而atan2中的两个参数就是实际中的x坐标和y坐标。

值域不同：atan值域为(-π/2,π/2)，而atan2的值域为[-π,π]。

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
    double x = 2, y = 2;
    System.out.println(Math.atan2(y, x)); // 0.7853981633974483
    System.out.println(Math.atan(y / x)); // 0.7853981633974483
    double x2 = 4, y2 = 3;
    double x1 = 2, y1 = 1;
    System.out.println(Math.atan2(y2 - y1, x2 - x1)); // 0.7853981633974483(45°)
    System.out.println(Math.atan((y2 - y1) / (x2 - x1))); // 0.7853981633974483
    // 下面有区别
    System.out.println(Math.atan2(y1 - y2, x1 - x2)); // -2.356194490192345(-135°)
    System.out.println(Math.atan((y1 - y2) / (x1 - x2))); // 0.7853981633974483
}

11.TreeSet返回最小元素与最大元素的API

1
2
3
4
TreeSet<Integer> set = new TreeSet<>(排序规则));
int first = set.first();	// 排序规则的首个元素
int last = set.last();	// 排序规则的最后一个元素
set.remove(o);	// 移除对应元素

12.关于TreeSet自定义排序规则后修改规则中元素的问题

与规则相关并有扰乱顺序的风险时，必须确保这个元素的排序是没有被影响过的，否则在remove()时，会出现定位失败，有可能删除失败，或者删除出错！

因此，当我们用TreeSet作为一个自动排序容器时，更新元素的位置，必须分三个步骤：

1、remove老的元素

2、修改

3、插入修改后的元素

PS:set.add(T t)如果存在了，将不会进行任何操作并返回false

6126. 设计食物评分系统

参考：关于TreeSet的排序对于删除操作的影响


13.List数组的正确写法

创建时候指定类型，然后统一初始化一次，后面直接add即可

这里也用到List存图的方式，比较适合稀疏图，因为List容量可变

通常来说邻接矩阵适合稠密图，稀疏图可以采用HashMap（离散化程度大）或者List数组(离散化程度小/节点索引为[1,n]情形)

207. 课程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public boolean canFinish(int n, int[][] pres) {
    /*
    拓扑排序:
    只要课程没有循环依赖(成环)，就可以顺利按照拓扑排序的规则完成所有课程
    思路就是优先消除入度为0的课程，因为这个课程可以直接学不用依赖别的课程
    消除到最后看看还有没有没哟被消去的课程即可
     */
    // 存储课程之间的依赖关系，比如0->1，list[0]中就有1
    List<Integer>[] list = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        list[i] = new ArrayList<>();
    }
    for (int[] p : pres) {
        int next = p[0], pre = p[1];
        list[pre].add(next);
    }
    int[] inDegree = new int[n];    // 入度数组
    for (int i = 0; i < n; i++) {
        for (int num : list[i]) {
            inDegree[num]++;
        }
    }
    int cnt = 0;    // 统计入度为0的节点
    Queue<Integer> que = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            que.add(i);
            cnt++;
        }
    }
    while (!que.isEmpty()) {
        int poll = que.poll();
        for (int num : list[poll]) {
            if (--inDegree[num] == 0) {
                que.add(num);
                cnt++;
            }
        }
    }
    return cnt == n;
}

14.关于static关键字在力扣提交的速度优化

375. 猜数字大小 II

优化前代码如下 (67ms/40.2MB) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    int[][] memo;   // memo[i][j]记录猜中区间[i,j]之间所需的最少钱数
    int INF = 0x3f3f3f3f;

    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }

    private int dfs(int i, int j) {
        // base case
        if (j - i <= 0) return 0;
        // memo中存在
        if (memo[i][j] != 0) return memo[i][j];
        int min = INF;   // 最小值
        for (int k = i; k <= j; k++) {
            // 维护合法分割点的最小钱数
            // 当前分割点的钱数=分割点k猜错的开销+左右区间开销大的一边(保证任意数字都可通过该最大开销猜中)
            int cur = k + Math.max(dfs(i, k - 1), dfs(k + 1, j));
            min = Math.min(min, cur);
        }
        memo[i][j] = min;   // 记录猜中当前区间的最小钱值
        return min;
    }
}

static优化后 (8ms/38.1MB) ：

注意static的优化要在成员里面加上static并且有相应的初始化器

static int[][] memo = new int[201][201];

static int INF = 0x3f3f3f3f;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    static int[][] memo = new int[201][201];   // memo[i][j]记录猜中区间[i,j]之间所需的最少钱数
    static int INF = 0x3f3f3f3f;

    public int getMoneyAmount(int n) {
        return dfs(1, n);
    }

    private int dfs(int i, int j) {
        // base case
        if (j - i <= 0) return 0;
        // memo中存在
        if (memo[i][j] != 0) return memo[i][j];
        int min = INF;   // 最小值
        for (int k = i; k <= j; k++) {
            // 维护合法分割点的最小钱数
            // 当前分割点的钱数=分割点k猜错的开销+左右区间开销大的一边(保证任意数字都可通过该最大开销猜中)
            int cur = k + Math.max(dfs(i, k - 1), dfs(k + 1, j));
            min = Math.min(min, cur);
        }
        memo[i][j] = min;   // 记录猜中当前区间的最小钱值
        return min;
    }
}

从67ms直接优化到8ms优化效果超级理想

注意：有部分题型不能在成员中初始化static变量否则会出错！如下：

877. 石子游戏

664. 奇怪的打印机


15.维护两个集合（数组）中前两个最大值

有时候我们不仅要求最大值，有可能还要实时维护次大值，次大值可能会用到

如何高效地维护最大值与次大值呢？最高效的方法就是利用两个变量max1（最大值）与max2（次大值）进行滚动维护

当遇到下一个数字nums[i]>max1大，此时max2=max1；max1=nums[i]

也就是说原来的max1取代了原来的max2，而nums[i]取代原来max1位置（卷起来了）

而max1>=nums[i]>max2时，我们令nums[i]取代原来max2位置，原来的max2就被取代了

当nums[i]==max2 可以维持原状，当nums[i]

PS： 当然，如果我们不熟悉的话可以用优先队列去维护，甚至维护前k大元素都可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int minimumOperations(int[] nums) {
        /*
        考虑两种间隔的前两个最大值+分类讨论
        要想最少操作次数，就要充分利用原理有出现的数字
        记偶数索引的最多出现的数字为a1，次多出现的数字为a2
        记奇数索引的最多出现的数字为b1，次多出现的数字为b2
        1.当a1!=b1 这是最理想的结果，直接将其他数字改成a1与b1，总的操作次数为n-(m1[a1]+m2[b1])
        2.当a1==b1 此时就有点麻烦了，不能同时将其他数字变为a1与b1因为会产生冲突
            此时我们可以有两种选择:选a1与b2 或 a2与b1 (a2与b2数目不多于前两者可以忽略)
            取数目总和大的，最后结果为:n-max(m1[a1]+m2[b2],m1[a2]+m2[b1])
        重点就是如何维护两个最大值了
         */
        int n = nums.length;
        int[] m1 = new int[100010], m2 = new int[100010];
        int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                // 偶数索引
                m1[nums[i]]++;
                int cur = m1[nums[i]];  // cur为当前数字nums[i]出现的次数
                if (a1 == 0 || cur > m1[a1]) {  // 最大出现次数的数字还没出现||当前数字出现次数已经大于a1出现次数
                    // nums[i]取代a1位置，之前的a1退居a2位置
                    a2 = a1;
                    a1 = nums[i];
                } else if (nums[i] != a1 && (a2 == 0 || cur > m1[a2])) {
                    // nums[i]!=a1说明这个nums[i]不是最大值的，此时若次大值处还没赋值或者nums[i]出现次数比原先的a2多
                    // 那么nums[i]可以取代原来a2的位置
                    a2 = nums[i];
                }
            } else {
                // 奇数索引
                m2[nums[i]]++;
                int cur = m2[nums[i]];
                if (b1 == 0 || cur > m2[b1]) {
                    b2 = b1;
                    b1 = nums[i];
                } else if (nums[i] != b1 && (b2 == 0 || cur > m2[b2])) {
                    b2 = nums[i];
                }
            }
        }
        if (a1 != b1) return n - (m1[a1] + m2[b1]);
        return n - Math.max(m1[a1] + m2[b2], m1[a2] + m2[b1]);
    }
}

16.最大公约数gcd与最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class BiggestFactor {
    @Test
    public void test() {
        int a = 8, b = 5;
        System.out.println(a + "与" + b + "最大公约数为:" + maxCommonFactor(a, b));
        System.out.println(a + "与" + b + "最小公倍数为:" + minCommonMultiple(a, b));
    }

    // 最小公倍数:结合最大公约数
    private int minCommonMultiple(int a, int b) {
        return a * b / maxCommonFactor(a, b);
    }

    // 最大公约数:辗转相除法
    private int maxCommonFactor(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
        // return b > 0 ? gcd(b, a % b) : a; (一步到位写法)
    }
}

拓展：求一个数组的最大公约数-> 滚动因子 O(N)

6122. 使数组可以被整除的最少删除次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int minOperations(int[] nums, int[] numsDivide) {
    /*
    求最大公因数问题：
    原问题等价于求numsDivide的最大公因数maxFac，只要在nums中找到一个可以整除maxFac的数字，那么该数字必定可以被numsDivide所有数整除
    将nums排序后找出最小的可以满足上述条件的数字，那么该数字前面的数字就是要删除的数字数目
    关键是怎样在接近O(N)时间复杂度内求解数组的最大公因数?
    答案是利用前面部分的maxFac与numsDivide[i]求最大公因数，求出来的就表示满足numsDivide[0,i-1]+numsDivide[i]=numsDivide[0,i]的最大公因数
    当遍历整个数组就是整个数组的最大公因数
     */
    Arrays.sort(nums);
    int m = numsDivide.length, n = nums.length;
    // 求数组的最大公因数
    int maxFac = numsDivide[0];
    for (int i = 1; i < m; i++) {
        maxFac = gcd(maxFac, numsDivide[i]);
    }
    for (int i = 0; i < n; i++) {
        if (maxFac % nums[i] == 0) return i;
    }
    return -1;
}

// 求a与b的最大公约数
private int gcd(int a, int b) {
    return b > 0 ? gcd(b, a % b) : a;
}

同理可以求得整个数组的最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private int minCommonMultiple_(int[] nums) {
    int res = nums[0];
    for (int i = 1; i < nums.lebnght; i++) {
        res = minCommonMultiple(res, nums[i]);
    }
    return res;
}    
// 最小公倍数
private int minCommonMultiple(int a, int b) {
    return a * b / maxCommonFactor(a, b);
}

// 最大公约数:辗转相除法
private int maxCommonFactor(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
    // return b > 0 ? gcd(b, a % b) : a; (一步到位写法)
}

17.螺旋矩阵模拟转向trick

6111. 螺旋矩阵 IV

周赛中发现了灵神的这个模拟转向的小trick 可以应用至任意的螺旋矩阵题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        /*
        一个模拟的万能转向trick(参考灵神)
         */
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(res[i], -1);
        }
        ListNode cur = head;
        // 上右下左四个进给方向
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // idx为进给方向,x与y是遍历指针
        int idx = 0, x = 0, y = -1; // 为了进给第一步向右走了之后才赋值,初始化(x,y)=(0.-1)
        // 链表还没走完就继续循环
        while (cur != null) {
            int newX = x + dirs[idx][0], newY = y + dirs[idx][1];
            // 越界或者碰到已经覆盖过的->转向
            if (newX < 0 || newX >= m || newY < 0 || newY >= n || res[newX][newY] != -1) idx = (idx + 1) % 4;
            x += dirs[idx][0];
            y += dirs[idx][1];
            res[x][y] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}