刷题参考《labuladong 的算法小抄》https://labuladong.github.io/algo/
二叉树
-
深度优先遍历 Depth First Search - DFS
-
前/中/后序遍历 代码执行顺序: 前序位置-自顶向下 后序位置-自底向上
-
-
广度优先遍历 Breath First Search - BFS
1、你理解的二叉树的前中后序遍历是什么，仅仅是三个顺序不同的 List 吗？
前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点，绝不仅仅是三个顺序不同的 List：
前序位置的代码在刚刚进入一个二叉树节点时执行
后序位置的代码在将要离开一个二叉树节点时执行
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树时执行
每个节点都有「唯一」属于自己的前中后序位置
为什么多叉树没有中序位置?
因为二叉树的每个节点只会进行唯一一次左子树切换右子树，而多叉树节点可能有很多子节点，会多次切换子树去遍历，所以多叉树节点没有「唯一」的中序遍历位置
2、请分析，后序遍历有什么特殊之处？
3、请分析，为什么多叉树没有中序遍历？
通用思考过程：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做
-
使用 HashMap 构造器
Map<String, Integer> map = new HashMap<>(); map.put("one", 1); map.put("two", 2); map.put("three", 3);
-
使用静态初始化块（Java 8 新特性）
通过创建一个匿名内部类，并在其中使用实例初始化块来添加键值对
❗这种方法创建了一个匿名子类，可能会增加不必要的开销并且序列化行为可能会变得复杂，因此不推荐在性能关键的代码中使用
Map<String, Integer> map = new HashMap<String, Integer>() {{ put("one", 1); put("two", 2); put("three", 3); }};
-
使用 Map.of 和 Map.ofEntries（Java 9+）
适合用于定义常量映射或在多线程环境中使用，创建的 Map 具有以下特点：
- 不可变：创建后不能修改（不能增删改条目）
- 不允许空键或空值：若尝试插入空键或空值，会抛出
NullPointerException - 防止重复键：若提供了重复的键，会抛出
IllegalArgumentException
Map<String, Integer> map = Map.of( "one", 1, "two", 2, "three", 3 ); Map<String, Integer> map = Map.ofEntries( Map.entry("one", 1), Map.entry("two", 2), Map.entry("three", 3) );
-
使用 Guava 库
Guava是Google提供的一个Java核心工具库，包含了大量实用的工具类和方法
引入 Maven 依赖
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>31.1-jre</version> <!-- 请根据需要选择最新版本 --> </dependency>
import com.google.common.collect.ImmutableMap; import com.google.common.collect.Maps; import java.util.Map; ... // 使用Guava的ImmutableMap进行初始化 // 不可变 Map,适用于创建常量 Map Map<String, Integer> immutableMap = ImmutableMap.of( "one", 1, "two", 2, "three", 3 ); // 使用Guava的ImmutableMap.Builder进行初始化 // 不可变 Map,适用于构建一个较大的 Map，或在运行时动态添加元素 Map<String, Integer> immutableMapWithBuilder = ImmutableMap.<String, Integer>builder() .put("one", 1) .put("two", 2) .put("three", 3) .build(); // 使用Guava的Maps.newHashMap进行初始化 // 可变 Map Map<String, Integer> mutableMap = Maps.newHashMap(); mutableMap.put("one", 1); mutableMap.put("two", 2); mutableMap.put("three", 3);
-
使用 String.format
double v = 123.456789; String s = String.format("%.2f", v); // 输出：123.46
-
使用 printf
System.out.printf("%.2f%n", v);
-
使用 DecimalFormat
DecimalFormat 是 NumberFormat 的一个具体子类，用于格式化十进制数字，主要靠 0 和 # 两个占位符号
import java.text.DecimalFormat; DecimalFormat df = new DecimalFormat("#.##"); System.out.println(df.format(v));
-
使用 BigDecimal
import java.math.BigDecimal; import java.math.RoundingMode; BigDecimal bd = new BigDecimal(v); bd = bd.setScale(2, RoundingMode.HALF_UP); // 设置小数位数为2，并四舍五入
-
使用 NumberFormat
import java.text.NumberFormat; // 是 DecimalFormat 的父类 NumberFormat nf = NumberFormat.getNumberInstance(); nf.setMaximumFractionDigits(2); nf.setMinimumFractionDigits(2); System.out.println(nf.format(v));
char int
09对应ASCII码4857
char c = '1';
// 输出1的ASCII码49 因为Java把char字符当做ASCII码值来对待,所以char可以直接转成int
int i = c;
int i1 = (int)c;
// 先转为String,再用Integer.parserInt()返回int类型值
String strc = String.valueOf(c);
int intc = Integer.parseInt(strc);
// 利用封装类Character的静态方法
int intc = Character.getNumericValue(numChar);int_char_string三种类型的相互转换
（在题目提交记录中）
普通程序中，即使是正则中，斜杠也就是斜杠
但是java中，由于string的设计，导致斜杠是特殊的转义字符，所以在正则中，如果想要写普通的正则的转义，比如'\d'表示数字，则要写成'\d'才可以
所以就变成了：其他程序中的''，java中，都要变成'\'
分离职责：
Node 类仅表示节点，List 类管理链表操作，职责清晰、单一
避免无限递归和循环引用：
直接在节点类中定义链表逻辑，容易导致循环引用或无限递归等问题. 例如，在节点构造函数中创建新的节点实例时，可能导致栈溢出错误. 将链表的操作逻辑分离出来，可以更好地控制和管理这些问题
如图，代码出现 StackOverflowError 报错是因为 Node 类中的 dummyhead 节点自身引用的循环问题. dummyhead 的初始化会触发新的 Node 实例的创建，从而形成无限递归，每一次递归调用都会在调用栈中增加一个新的帧，最终导致栈空间被耗尽. 构造函数只应该初始化节点的值和指向下一个节点的引用，而不应该创建新的节点
修正：
public class Node {
int val;
Node next;
Node() {}
Node(int val) {
this.val = val;
}
Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
class List {
int size;
Node dummyhead;
List() {
size = 0;
dummyhead = new Node(-1, null);
}
//链表操作
}