【算法】技巧总结

发表于2021-11-24更新于2022-03-02字数统计2.7k阅读时长19分阅读次数

常用 API

数组

初始化数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 如果不赋值，则[]内需要指定大小
int[] nums = new int[n];
// 如果同时要赋值的话，[]内不带值
int[] nums = new int[]{1,2,3,4};

// 二维数组
int[][] nums = new int[m][n];
int[][] nums = new int[][]{{1,3},{1,2},{4,5},{3,7}};

// 字符串数组的初始化与整型类似
char[] cstr = new char[n];
char[] cstr = new char[]{'a', 'b', 'c'};
// 也可以从String对象中提取出对应的字符串数组
char[] cstr = new String("abc").toCharArray();

// String数组的初始化需要带()
String[] str = new String()[n];
String[] str = new String()[]{"aaa", "bbb", "ccc"};
// 或者使用字面量形式
String[] str = {"aaa", "bbb", "ccc"};

总结：初始化时，若要通过{}赋值，则数组的[]内不能带数字；如果不赋值，则必须要带数字。因为使用{}赋值时，编译器会根据赋值的数量自动算出数组长度，因此[]内就不能加数字了。

数组操作：

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
47
48
49
50
int[][] nums = new int[][]{{1,3},{1,2},{4,5},{3,7}};

// 根据二维数组的某一位进行排序
// 最简洁的Lambda表达式
Arrays.sort(nums, (o1, o2) -> o1[0] - o2[0]);
// 或可以写多行的形式
Arrays.sort(nums, (o1, o2) -> {
    o1[0] - o2[0]
});
// 或匿名内部类
Arrays.sort(nums, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b){
        if(a[0]==b[0]){
            return a[1] - b[1];
        }else {
            return a[0] - b[0];
        }
    }
});


// 对数组集合进行反转
Collections.reverse(list);
// 集合的排序
Collections.sort(list, (o1, o2) -> o1 - o2);

// 从原始组中复制出来一份 [0, k]
Arrays.copyOf(arr, k);

// 数组快速填充数值
char[] board = new char[n];
Arrays.fill(board, '.'); // 快速填充
board[record[row]] = 'Q';


// 将数组中每个元素值都设置为 1
int[] arr = new int[10];
Arrays.fill(arr, 1);

// list 转 int[]
int[] ans = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
    ans[i] = list.get(i);
}

// List 中嵌套 int[] 时转换为 int[][]
List<int[]> list = new ArrayList();
int[][] ans = list.toArray(new int[list.size()][]);

字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 将数字转换为字符串（在字符串问题中非常常用）
String s = String.valueOf(num);
// 将字符串转换为数字
int n = Integer.parseInt(s);
// 或
int n = Integer.valueOf(s);

s.substring(a,b); // 截取 s 在区间 [a, b) 上的子字符串

char c = s.charAt(i); // 获取 s 在第 i 位置上的字符


s = s.trim(); // String 字符串删除首尾空格

Character.isLetter(ch);     // 判断某个字符是否是字母
Character.toLowerCase(ch);  // 将某个字母转为小写字母 
char[] str = s.toLowerCase();  // 将 String 转换成小写字母数组

// StringBuilder的API
// 添加字符串
sb.append(new String("123"));
// 删除字符串某个位置的元素
sb.deleteCharAt(i);

集合

LinkedList中add，addLast，offer，pollLast，removeLast等区别：https://blog.csdn.net/cpppp66/article/details/115759578。

  • addLast() 仅仅将元素链接到队列尾部。 然而 add() 不仅将元素链接到队列尾部，还返回true。
  • offer() 直接调用了 add() 方法。所以在 LinkedList中 add() 与 offer() 的使用相当于是一样的

总结：

  • 需要链接元素到队列尾时优先用 offer()
  • 查看元素优先使用 peek()
  • 删除元素优先使用 poll()

特别情况：

  • 想要在指定索引位置链接元素可以使用 add(int index, E element)
  • 获取指定索引的元素可以使用 get(int index)
  • 修改指定索引的元素可以使用 set(int index, E newElement)

其他：

1
2
3
4
5
6
7
// 对数组集合进行反转
Collections.reverse(list);
// 集合的排序
Collections.sort(list, (o1, o2) -> o1 - o2);

// 从原始组中复制出来一份 [0, k]
Arrays.copyOf(arr, k);

一些深度优先遍历问题，通常做法是创建一个全局的集合 path，其将随着递归栈的调用而被不断修改。在递归到底部满足条件进行保存结果时，注意需要另外创建一个新的集合变量，存储该 path 中的值，以防其随着递归栈的返回被修改。具体做法为：res.add(new LinkedList<Integer>(path))

代码：

1
2
3
4
5
6
7
8
9
10
List<List<Integer>> res = new LinkedList<List<Integer>>();
Deque<Integer> path = new LinkedList<Integer>();

public void dfs(TreeNode curr, int target) {
    // 假设如果满足某种条件，就将当前分支的内容保存到总结果集合 res 中
    // 则需要另外创建一个新的集合变量，存储该 path 中的值，以防其随着递归栈的返回被修改
    if (target == 0) {
        res.add(new LinkedList<Integer>(path));
    }
}

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Set<Integer> set = new HashSet<>();
// HashSet 添加元素
for (int i = 0; i < arr.length; i++) {
    set.add(arr[i]);
}
// 遍历 HashSet
for (Integer cur : set) {
    if (set.contains(cur + k)) {
        res.add(Arrays.asList(cur, cur + k));
    }
}


Map<String, Integer> map = new HashMap<>();
// 遍历 HashMap
for (Entry<String, Integer> entry : map.entrySet()) {
    // 获取每一个 key
    String str = entry.getKey();
    // 获取每一个 value
    Integer times = entry.getValue();
}

概率

1
2
3
4
5
// 随机获得一个[0, i]内的随机整数，注意是左闭右开，是不包含 i + 1 的
int d = rand.nextInt(i + 1);

// 随机生成 0-4 + 1 = 0-5 的数字
int d = (int)(Math.random() * 5) + 1;

运算

获取每个数字最右侧为 1 的位数、

原理：除了最低位之外，0 取反变成了 1，1 取反变成了 0，所以取与操作肯定都是 0，但最低位因为加了 1 所以会得到 1。

1
2
3
4
// 以补码加一的形式将 n 取相反数
rightOne = n & (~n + 1);
// 等价于直接取反
rightOne = n & -n;

两个整数相除向上取整

两个整数相除的向下取整为：

1
int res = a / b;

两个整数相除的向上取整为：

1
2
3
4
5
6
int res = (a + b - 1) / b;
// 等价于：
int res = (a - 1) / b + 1;  // 这样更好理解一些

// 或者：
int res = (a / b) + (a % b == 0 ? 0 : 1);

这里分两种情况：

  • a / b 没有余数：例如 14 / 7，则 (14 + 6) / 7 还是等于 2，此时 a 加上的 b - 1 没有带来额外的进位（这就是要减一的原因）
  • a / b 有余数：例如 15 / 7，则 (15 + 6) / 7 等于 3，此时原本 15 / 7 会被省略掉的余数因为加上了 b - 1，从而额外进了一位，因此达到了向上取整的效果。即使 15 / 7 只余下 1，也会因为加上了 b - 1，从而多算了一个 b / b = 1，因此多进了一位。

判断某个数字 x 是否是 n 的完全开平方

问题：判断 x 是否等于 sqrt(n)。

技巧：如果直接判断 x * x ?= n，则可能因 x 过大而发生溢出；此时我们可以使用如下判断：

1
n % x == 0 && n / x == x

n % x == 0 保证了 n 能整除 x，否则肯定不满足 x * x == n；其次使用 n / x == x 来防止 x * x 溢出。

int 类型范围

int 类型的范围： -2147483648 ～ 2147483647

在一些题目里，如果 n 取了 int 类型的最小值 -2147483648，则对其直接取反后，会超出 int 的最大值 2147483647，导致 -n != n， 因此要先将 n 变成 long 类型进行操作。最后再变回 int。

例如：50. Pow(x, n) 这道题，n 如果取到最小值，这时对其反转，得到的就不是想要的值，而应该将 n 转换成 long 类型再计算。

数组的前缀和

如果要频繁的获取数组中某个区间内的累加和，则可以使用前缀和的技巧进行加速。具体方法为：

  • 创建一个 sum[] 数组。sum[i] 代表原数组在 [0, i] 范围内的累加和。
  • 遍历一遍整个数组，计算出 sum[] 数组每个位置上的值
  • 这样再想计算某个区间 [L, R] 上的累加和，就只需要计算 sum[R] - sum[L-1] 即可。

或的短路原则

在需要多条路径进行递归时，可以使用 || 的短路原则，缩短搜索时间。例如：

1
2
boolean res = dfs(i + 1, j, k + 1, board, words) || dfs(i, j + 1, k + 1, board, words)
    || dfs(i - 1, j, k + 1, board, words) || dfs(i, j - 1, k + 1, board, words);

上述代码中只需要前面的某一条分支返回true，就无需再递归判断后续的其他分支，从而节省了大量时间。

摩尔投票法

剑指 Offer 39. 数组中出现次数超过一半的数字：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

摩尔投票法：可以类比打擂台。如果台上没人，则当前的人作为擂主，之后如果遇到己方阵营（和自己相等），则台上人数加一，如果遇到对方阵营（和自己不相等），则台上人数减一（同归于尽），最后台上剩下的阵营一定是众数（如果题目不保证一定存在众数，则在找到该数字后再遍历一遍数组判断当前数字是不是众数即可）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        int x = 0;
        int votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                // 如果当前擂台上没人（可能之前没人上或之前人都同归于尽了），则当前的人作为擂主
                x = num; 
                // 注意！！！这里别忘了votes++，令当前票数+1，或者下面的votes += ... 不要放到else里
                votes++;
            } else {
                // 如果当前擂台上的擂主不是己方阵营，则当前人和擂主阵营中的一个人同归于尽，votes--；如果是同一方阵营，则votes++
                votes += (x == num) ? 1 : -1;
            }
        }
        // 最后擂主一定是众数（如果题目不保证一定存在众数，则在找到该数字后再遍历一遍数组判断当前数字是不是众数即可）
        return x;
    }
}

一年中的第几天

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。请你计算并返回该日期是当年的第几天。通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。

思路：注意闰年的判断方式：闰年的判定方法为：year 是 400 的倍数，或者 year 是 4 的倍数且不是 100 的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int dayOfYear(String date) {
    int year = Integer.parseInt(date.substring(0, 4));
    int month = Integer.parseInt(date.substring(5, 7));
    int day = Integer.parseInt(date.substring(8));

    int[] amount = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
        ++amount[1];
    }

    int ans = 0;
    for (int i = 0; i < month - 1; ++i) {
        ans += amount[i];
    }
    return ans + day;
}