Java后端算法笔记

symwssy2025-12-28

Java后端算法笔记

704.二分查找

因为是升序，所以可以直接和最大最小值比较。

如果存在，再用二分法找。

int mid = left + ((right - left) >> 1)

意思是右移一位。

安全计算区间 [left, right] 的中间索引，等价于 (left + right) / 2

为什么不直接写 `(left + right) / 2`？

这是最关键的点 ——避免整数溢出：

如果 left 和 right 都是很大的整数（比如接近 int 类型的最大值 2^31-1），left + right 会超出 int 的取值范围，导致溢出（结果变成负数）；
而 left + ((right - left) >> 1) 先算 right - left（结果远小于单个大数），再除以 2，最后加 left，完全不会溢出。

27.移除元素

快慢双指针

for循环中fastindex=0，fastindex++,第一次循环fastindex=0

如果fast=val，则slow不动，fast前移，直到fast！=val,让slow等于现在fast的值，slow再往前走

997.有序数组的平方

双指针法

因为是非递减顺序，只需判断负数平方后的位置，所以两边指针一起比就可以

242.有效的字母异位词

s.charAt(i) - 'a' 的返回值类型，核心结论很明确：这个表达式的返回值是 int 类型（整数）

charAt(i) 返回 char 类型，'a' 本身也是 char 类型，但在 Java 中，char 类型参与算术运算时会自动转换为 int 类型（基于字符的 ASCII 码值），因此 s.charAt(i) - 'a' 的最终结果是 int 类型。

增强 for 循环是 Java 5 引入的语法糖，专门用于遍历集合（Collection）或数组，核心适用场景是：只需要遍历元素，不需要操作索引、不需要修改数组 / 集合的结构（比如增删元素）。

s.length()

349.两个数组的交集

使用数组来做哈希的题目，是因为题目都限制了数值的大小。

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

//方法1：将结果集合转为数组
        return res.stream().mapToInt(Integer::intValue).toArray();
        /**
         * 将 Set<Integer> 转换为 int[] 数组：
         * 1. stream() : Collection 接口的方法，将集合转换为 Stream<Integer>
         * 2. mapToInt(Integer::intValue) : 
         *    - 中间操作，将 Stream<Integer> 转换为 IntStream
         *    - 使用方法引用 Integer::intValue，将 Integer 对象拆箱为 int 基本类型
         * 3. toArray() : 终端操作，将 IntStream 转换为 int[] 数组。

类型	获取长度的方式	原因
数组（如 int []）	数组名.length	是数组的成员属性字符串（String）
字符串（String）	字符串名.length()	`length()` 是 String 类的成员方法
集合（如 List）	集合名.size()	`size()` 是 Collection 接口的方法

Set set1 = new HashSet<>();

202.快乐数

无限循环意味着会重复

1.两数之和

Map 的键值对模型：键（key）→ 值（value）

比如 map.put("name", "张三")，"name" 是 key，"张三" 是 value；
key 是自定义、无序、唯一的 “标识”，作用等价于数组的 “下标”（用来定位），value 则是对应 “下标” 的 “元素”。

nums==null 判断数组为空

nums.length==0判断数组不为0

map.get(temp) 的核心作用是根据指定的 key（temp）查找 Map 中对应的 value；

1	Map<Integer, Integer> map = new HashMap<>();

454.四数相加||

map.getOrDefault(sum, 0) 是get()方法的增强版，传入两个参数：

第一个参数sum：要查找的键（key）；
第二个参数0：默认值（当 key 不存在时返回的值）。

如果 Map 中存在以sum为 key 的键值对，返回该 key 对应的value；

如果 Map 中不存在该 key，直接返回指定的默认值（这里是0），而非null。

383.赎金信

其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效！

`magazine.toCharArray()` 的核心含义

magazine 是一个 String 类型的变量，调用 toCharArray() 方法后：

会创建一个新的 char 类型数组；
数组的长度和字符串magazine的长度一致；
数组的每个元素依次对应字符串的每一个字符（包括空格、符号等）；
返回这个新的字符数组。

简单来说，这个方法的作用就是 “把字符串拆成单个字符，装进数组里”，方便对字符串的每一个字符进行遍历、修改等操作（因为 String 本身是不可变的，而字符数组是可变的）。

15.三数之和

所有满足条件且不重复，去重很关键！

使用双指针法要比哈希法高效一些

不能有重复的三元组，但三元组内的元素是可以重复的！

`List<List<Integer>> result`

List<Integer>：表示一个存储 Integer 类型元素的列表（比如 [1,2,3]）；
List<List<Integer>>：表示一个存储 “Integer 列表” 的列表（即嵌套列表 / 二维列表），比如 [[1,2], [3,4], [5]]；
result：是这个嵌套列表的变量名。

简单来说，这行声明的意思是：定义一个名为result的变量，它的类型是 “装着 Integer 列表的列表”，可以理解为 “整数类型的二维数组”（但比数组更灵活，支持动态增删）。

1	Arrays.sort（）

Arrays.asList() 是java.util.Arrays类提供的静态方法，核心作用是：

将指定的数组转换为一个固定大小的 List 集合；

先记录下满足条件的元组，再去重b，c

18.四数之和

问题 1：第二层循环的去重逻辑错误（最关键）

1
2
3

if(i>0&&nums[i]==nums[i-1]){ // 错误代码
    continue;
}

问题原因：i 的起始位置是 k+1，去重应该判断 i > k+1 而非 i > 0。如果用 i>0，会错误跳过 i=k+1 时和 nums[0] 重复的合法元素（比如 k=0, i=1 时，若 nums[1]==nums[0]，本应保留，但会被错误跳过）。
举例：数组 [-2,-1,-1,1,2]，k=0 时 i=1（nums[i]=-1），i>0 成立且 nums[1]==nums[0]，会错误跳过这个合法的 i，导致漏解。

344.反转字符串

自反性：a ^ a = 0（一个数异或自身等于 0）；
归零性：a ^ 0 = a（一个数异或 0 等于自身）；
交换律 / 结合律：a ^ b = b ^ a、(a ^ b) ^ c = a ^ (b ^ c)。

基于这三个特性，可以推导出不用临时变量交换两个数的逻辑：

// 初始：a = x, b = y
a = a ^ b;  // a = x ^ y, b = y
b = a ^ b;  // b = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
a = a ^ b;  // a = (x ^ y) ^ x = y ^ (x ^ x) = y ^ 0 = y
// 最终：a = y, b = x，完成交换

写法	等价展开（编译器实际执行）	类型转换处理
s[a] ^= s[b]	s[a] = (char) (s[a] ^ s[b])	编译器自动添加`(char)`强制转换
s[a] = s[a] ^ s[b]	s[a] = s[a] ^ s[b]	无自动转换，直接赋值 int→char 报错

541.反转字符串Ⅱ

初始化结果容器：StringBuffer 是可变字符串，适合频繁拼接/反转操作 StringBuffer res = new StringBuffer();

为什么用 `Math.min(ch.length - 1, start + k - 1)`

这个 min 操作是为了处理「剩余字符不足 k 个」的边界情况：

当 start + k - 1 < ch.length - 1 时（剩余字符 ≥k 个）：
- end = start + k - 1，此时反转区间是 [start, end]（正好 k 个字符），符合 “反转前 k 个” 的规则；
当 start + k - 1 ≥ ch.length - 1 时（剩余字符 <k 个）：
- end = ch.length - 1，此时反转区间是 [start, ch.length - 1]（所有剩余字符），符合 “剩余不足 k 个则反转所有” 的规则。

**Java 的语法规则不允许省略乘法运算符 ***，2k 这种写法在 Java 中会被判定为语法错误，编译器根本无法识别。

54.替换数字

这是字符串替换中常见的一种优化策略，从后向前替换的主

要原因是：

核心原因：避免覆盖未处理的字符

151.反转字符串中的单词

new String(newArr,0,newArrPos-1)这行代码的目的是：从 newArr 字符数组中，截取从索引 0 开始、长度为 newArrPos-1 的部分，转换成一个新的字符串返回。

55.右旋字符串

in.nextLine()：调用 Scanner 对象的 nextLine() 方法，读取控制台中用户输入的一整行内容（直到用户按回车键为止），返回值是 String 类型；

Integer.parseInt(...)：把字符串类型的数字（比如 "10"、"200"）转换成 int 类型的整数；

28.找出字符串中第一个匹配项的下标

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

先用前缀表统一减一得到的next数组，求得文本串s里是否出现过模式串t

循环体 j = next[j - 1]

这是 KMP 算法最核心的 “回退逻辑”：

next[j-1]：表示「前缀 0~j-1 这段子串的最长相等前后缀长度」；
把 j 赋值为 next[j-1]，相当于让 j 回退到「更短的、能和当前后缀匹配的前缀末尾位置」—— 避免从头开始匹配，实现 “高效回退”。

next[x] 表示字符串前 x+1 个字符（0~x）的最长相等前后缀长度

459.重复的子字符串

next[n-1]：整个字符串 s 的最长相等前后缀长度（比如 “ababab” 的最长相等前后缀是 “abab”，长度为 4）。

n - next[n-1]：整个字符串中，最长相等前后缀没有覆盖到的那部分子串的长度（比如 “ababab” 中，6-4=2，就是 “ab” 的长度）。

这段代码的核心逻辑是：

构建 KMP 算法的前缀表 (next 数组)，其中next[i]表示以索引i结尾的子串的最长相等前后缀长度。
利用前缀表的特性判断：如果字符串长度n能被n - next[n-1]（最长相等前后缀不包含的子串长度）整除，且next[n-1] > 0，说明字符串由重复子串构成。

252.用队列实现栈

queue.offer(x) 的核心作用是将元素 x 添加到队列尾部，添加成功返回true，失败（队列满）返回false（无异常）。

它和add()的核心区别是失败时不抛异常，更适合非阻塞、需要优雅处理队列满的场景。

queue.poll() 是 Java 中 Queue（队列）接口的核心方法，作用是：

移除并返回队列的头部元素（遵循 FIFO 先进先出原则）；

如果队列非空，返回队首元素，且该元素会被从队列中移除；
如果队列为空，返回 null（不会抛出异常）。

20.有效的括号

Deque：全称 Double Ended Queue，即「双端队列」，是 Java 集合框架的接口，允许你在队列的头部和尾部都能执行添加 / 删除操作（普通队列 Queue 只能队尾加、队首取）；

stack.peek() 是 Java 中 Stack 类（栈）的核心方法，作用是：

查看栈顶元素，但不会将该元素从栈中移除（仅读取，不修改栈结构）；

1047.删除字符串中的所有相邻重复项

拿字符串直接作为栈，省去了栈还要转为字符串的操作。

特性	StringBuilder	StringBuffer
线程安全	非线程安全	线程安全（方法加了 `synchronized` 锁）
执行效率	高（无锁开销）	低（锁会带来性能损耗）
适用场景	单线程环境（90% 的日常开发场景）	多线程环境（如多线程拼接字符串）

150.逆波兰表达式

Java 官方明确建议：优先使用 Deque 接口（如 LinkedList/ArrayDeque 实现）模拟栈，而非直接使用 java.util.Stack 类—— 本质原因是 Stack 类设计老旧且存在诸多缺陷，而 Deque 既能完美实现栈的所有功能，又具备更优的设计和灵活性。

104.二叉树的最大深度

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

111.二叉树的最小深度

**小深度是从根节点到最近叶子节点的最短路径上的节点数量。**注意是**叶子节点**。

什么是叶子节点，左右孩子都为空的节点才是叶子节点！

所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

513.找树左下角的值

TreeNode poll = queue.poll()

从一个存储 TreeNode 类型元素的队列（queue）中，取出并移除队列的头部元素，然后把这个元素赋值给名为 poll 的 TreeNode 变量。

106.从中序与后序遍历序列构造二叉树

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，就是以后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间

700.二叉搜索树中的搜索

二叉搜索树（BST）核心特点：

若它的左子树非空，则左子树上所有节点的值 小于该根节点的值；

若它的右子树非空，则右子树上所有节点的值 大于该根节点的值；

它的左、右子树本身也分别是二叉搜索树（递归定义）。

对一棵二叉搜索树执行 中序遍历（遍历顺序：左子树 → 根节点 → 右子树），得到的序列一定是：

严格递增的有序序列

131.分割回文串

回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

93.复原IP地址

s.charAt(start) - '0' == 0 是判断字符代表的数字是 0，而 s.charAt(start) == 0 是判断字符的 ASCII 码值等于 0，两者完全不是一个概念。

Integer.parseInt() 是 Java 中 Integer 类提供的一个静态方法，作用是把符合整数格式的字符串转换成对应的 int 类型整数（32 位整数）。

简单来说：它能把 "123" 变成数字 123，把 "255" 变成数字 255，是字符串和整数之间的 “转换器”。

substring(int beginIndex, int endIndex) 是 Java String 类的方法，作用是截取字符串中从 beginIndex 开始、到 endIndex 结束的子串（左闭右开）。

491.非递减子序列

HashSet 最核心的特点是元素不重复、无序，基于哈希表实现；

允许存一个 null，查找 / 增删效率高（平均 O (1)），但无索引、非线程安全；

常用于需要 “去重” 且不关注顺序的场景，是 Java 中去重的首选集合之一

47.全排列II

Arrays.fill() 是 Java 中 java.util.Arrays 类提供的一个静态方法，核心作用是将数组的所有元素填充为指定的值。

1005. K 次取反后最大化的数组和

nums = IntStream.of(nums)          // 步骤1：将int数组转为IntStream（基本类型流）
		     .boxed()               // 步骤2：将基本类型int包装为Integer对象（转为Stream<Integer>）
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))  // 步骤3：按绝对值降序排序
		     .mapToInt(Integer::intValue)  // 步骤4：将Integer转回int基本类型
		     .toArray();            // 步骤5：将流转回int数组

Java后端算法笔记

704.二分查找

为什么不直接写 (left + right) / 2？

27.移除元素

997.有序数组的平方

242.有效的字母异位词

349.两个数组的交集

202.快乐数

1.两数之和

454.四数相加||

383.赎金信

magazine.toCharArray() 的核心含义

15.三数之和

List<List<Integer>> result

18.四数之和

问题 1：第二层循环的去重逻辑错误（最关键）

344.反转字符串

541.反转字符串Ⅱ

为什么用 Math.min(ch.length - 1, start + k - 1)

54.替换数字

核心原因：避免覆盖未处理的字符

151.反转字符串中的单词

55.右旋字符串

28.找出字符串中第一个匹配项的下标

459.重复的子字符串

252.用队列实现栈

20.有效的括号

1047.删除字符串中的所有相邻重复项

150.逆波兰表达式

104.二叉树的最大深度

111.二叉树的最小深度

513.找树左下角的值

106.从中序与后序遍历序列构造二叉树

700.二叉搜索树中的搜索

131.分割回文串

93.复原IP地址

491.非递减子序列

47.全排列II

1005. K 次取反后最大化的数组和

为什么不直接写 `(left + right) / 2`？

`magazine.toCharArray()` 的核心含义

`List<List<Integer>> result`

为什么用 `Math.min(ch.length - 1, start + k - 1)`