List和ArrayList

List是接口，ArrayList是实现类，List还有其他实现类（如LinkedList、Vector）

List的List

正确：

1
2
3
4
5
6
7
8
9
10
List<List<Integer>> edges;
int[] visited;
boolean valid = true;

public boolean canFinish(int numCourses, int[][] prerequisites) {
    edges = new ArrayList<List<Integer>>();
    for(int i = 0; i < numCourses; i++) {
        edges.add(new ArrayList<Integer>());
    }
}

在力扣编程中编写了下列代码：

1
2
3
4
5
6
7
List<List<Integer>> edges;
int[] visited;
boolean valid = true;

public boolean canFinish(int numCourses, int[][] prerequisites) {
    edges = new ArrayList<ArrayList<Integer>>();
}

这是错误的，因为如果运行的话，java编译的时候看左边edges是List<List<Integer>>类型，那么后续假如运行edges.add(new LinkedList<Integer>)会报错，但实际上edges里面是ArrayList<Integer>。

所以编译器禁止List<List<Integer>> edges = new ArrayList<ArrayList<Integer>>(); // 编译错误，

遍历String并获取字符相对于a的位数

1
2
3
4
5
6
7
8
String str = "helloworld"; // 示例字符串（全小写字母）

// 遍历字符串中的每个字符
for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);

    // 计算相对于'a'的位数（'a' -> 0, 'b'->1, ..., 'z'->25）
    int position = c - 'a';
  • charAt()
  • 相对位数：c - 'a'

增强for循环遍历：

1
2
3
4
5
6
7
String str = "abcxyz";

// 将字符串转为字符数组，再用增强for循环遍历
for (char c : str.toCharArray()) {
    int position = c - 'a';
    System.out.println("字符 '" + c + "' 相对于'a'的位数是: " + position);
}
  • toCharArray()

length、length()、size()等长度

length(): String类型的长度。

1
2
String str = "abcxyz";
str.length();

length: int数组的长度

1
2
int[] answer;
answer.length

size()：ArrayList的长度、Stack（Deque）

1
2
List<Integer> route = new ArrayList<>();
route.size();

length——数组的属性；

length()——String的方法；

size()——集合的方法；

变量初始值

在java中，成员变量（类中声明的变量）会被自动赋予默认值，而局部变量（方法内部声明的变量）不会自动初始化，必须显式赋值后才能使用（否则编译报错）。

  • 成员变量分为静态变量和实例变量。
    • 实例变量属于某个对象的属性，必须创建了实例对象，其中的实例变量才会被分配空间，才能使用这个实例变量。
    • 静态变量不属于某个实例对象，而是属于类，所以也称为类变量，只要程序加载了类的字节码，不用创建任何实例对象，静态变量就会被分配空间，静态变量就可以被使用了。总之，实例变量必须创建对象后才可以通过这个对象来使用，静态变量则可以直接使用类名来引用。
类型 未赋值时的默认值
byte 0
short 0
int 0
long 0L
float 0.0f
double 0.0d
char '\u0000'
boolean false

引用类型变量为null。

力扣中少用static

https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked

力扣在运行多个测试用例时，会创建多个 Trie 实例。如果使用静态变量，前一个测试用例的数据会污染后一个测试用例，导致结果错误。

简单总结：在面向对象编程中，除非确实需要共享数据，否则应该使用实例变量而不是静态变量。

ArrayList常见api

  • 修改元素：set(int index, E element)
  • 删除元素：remove(int index)
  • 大小：size()
  • 判断是否存在：contains()
  • 排序：Collections.sort(list)
  • 访问某个元素：get(i)
  • 用于删除动态数组中的所有元素，使列表的大小变为 0：clear()

引用传递和对象复制

问题代码：

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
class Solution {
    private List<List<Integer>> answer;
    private List<Integer> tmp;
    int[] visit;

    public void dfs(int[] nums, int u) {
        if(u == nums.length) {
            // 出问题的代码，改成answer.add(new ArrayList<>(tmp))就行
            answer.add(tmp);
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(visit[i] == 0) {
                tmp.add(nums[i]);
                visit[i] = 1;
                dfs(nums, u + 1);
                visit[i] = 0;
                tmp.remove(tmp.size() - 1);
            }
        }

    }

    public List<List<Integer>> permute(int[] nums) {
        answer = new ArrayList<>();
        tmp = new ArrayList<>();
        visit = new int[nums.length];
        dfs(nums, 0);
        return answer;
    }
}

Java 中列表是引用类型，直接使用 answer.add(tmp) 存储的是 tmp 对象的引用，而不是当前 tmp 中的内容快照。

问题根源：引用传递的特性

在你的代码中，tmp 是一个全局的 List<Integer> 对象，整个回溯过程中始终是同一个对象（只是不断添加 / 删除元素）。

当你执行 answer.add(tmp) 时，本质是把 tmp 的引用地址添加到了 answer 中。而回溯过程中，tmp 会继续被修改（比如 tmp.remove(...)），这会导致 answer 中所有之前添加的 “排列” 都跟着一起变化（因为它们指向同一个 tmp 对象）。

最终，当回溯完成后，tmp 会回到空列表状态，answer 中存储的所有引用都会指向这个空列表，导致结果错误。

为什么 answer.add(new ArrayList<>(tmp)) 能解决问题？

new ArrayList<>(tmp) 会创建一个新的列表对象，并将当前 tmp 中的所有元素复制到这个新对象中。此时添加到 answer 中的是新对象的引用，后续对 tmp 的修改不会影响这个新对象。

这样，answer 中存储的就是回溯过程中 tmp 在不同阶段的内容快照，最终能正确保留所有排列结果。

总结

  • 引用类型变量存储的是对象的地址，直接添加引用会导致后续修改影响已存储的内容。
  • 通过 new ArrayList<>(tmp) 创建新对象并复制内容，能确保每个排列结果被独立保存，不受后续回溯操作的影响。

表示几次方

math.pow(a, b);

位运算

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
51
52
53
54
55
56
57
58
59
60
// ==================== 基本位运算符 ====================
// 与运算 (AND)
int andResult = 5 & 3; // 0101 & 0011 = 0001 (1)

// 或运算 (OR)  
int orResult = 5 | 3; // 0101 | 0011 = 0111 (7)

// 异或运算 (XOR)
int xorResult = 5 ^ 3; // 0101 ^ 0011 = 0110 (6)

// 取反运算 (NOT)
int notResult = ~5; // ~0101 = 1010 (-6)

// 左移运算
int leftShift = 5 << 2; // 0101 << 2 = 10100 (20)

// 右移运算
int rightShift = 20 >> 2; // 10100 >> 2 = 00101 (5)

// 无符号右移
int unsignedRightShift = -20 >>> 2;


// ==================== 常用位运算技巧 ====================
// 检查第n位是否为1
int num = 13; // 1101
boolean isBitSet = ((num >> 2) & 1) == 1; // 检查第2位

// 设置第n位为1
int setBit = 9 | (1 << 1); // 1001 -> 1011 (11)

// 设置第n位为0  
int clearBit = 11 & ~(1 << 1); // 1011 -> 1001 (9)

// 切换第n位
int toggleBit = 9 ^ (1 << 1); // 1001 -> 1011 (11)

// 获取最低位的1
int lowestOneBit = 12 & -12; // 1100 -> 0100 (4)

// 判断奇偶性
boolean isEven = (7 & 1) == 0; // false

// 判断是否为2的幂
boolean isPowerOfTwo = (16 & (16 - 1)) == 0; // true

// 计算二进制中1的个数
int count = 0;
int number = 13; // 1101
while (number != 0) {
    number = number & (number - 1);
    count++;
}
// count = 3


// 3. 注意负数的右移
int negative = -5;
int arithmeticShift = negative >> 1;  // 算术右移，保留符号位
int logicalShift = negative >>> 1;    // 逻辑右移，不保留符号位

StringBuilder的API

String的API

子串是substring()，都是小写

Stack的API

在Java中，我们用Deque可以实现Stack的功能：

  • 初始化：Deque<Integer> stack = new LinkedList<>();

  • 把元素压栈：push(E)/addFirst(E)

  • 把栈顶的元素“弹出”：pop()/removeFirst()

  • 取栈顶元素但不弹出：peek()/peekFirst()

  • 大小：size()

小顶堆/大顶堆的API

1
2
3
4
// 默认小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); 

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

  • 添加元素：offer()

  • 移除并返回队头：poll()

  • 查看队头：peek()

字符转数字

错误写法：

1
2
3
String digits = "23";
int x = (int)digits.charAt(0);
// 这样x不会是预想的2，而是50，ASCII值，0的ASCII值是48

正确写法：

1
int x = digits.charAt(0) - '0'; // 字符转数字（如 '2' - '0' = 2）

Boolean和boolean

boolean（基本类型）

  • 只有两个值：true 或 false
  • 不能为 null
  • 默认值为 false

Boolean（包装类）

  • 有三个可能值：true、false、null

数学运算

开根号：Math.sqrt(a)或Math.pow(a, 0.5)

数组复制

Arrays.copyOf()

1
2
3
4
5
6
7
8
9
// 原数组
int[] original = {1, 2, 3, 4, 5};

// 复制数组（值相同，独立内存）
int[] newArray = Arrays.copyOf(original, original.length);

// 验证：修改新数组，原数组不受影响
newArray[0] = 100;
System.out.println(original[0]); // 输出 1（原数组未变）

参数传递

Java中传递引用数据类型的时候也是值传递。（复制的是引用数据类型的地址）

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
public boolean isPalindrome(ListNode head) {
    ListNode copy = reverseList(head); // 传递head引用的副本
    // 此时head仍然指向原链表的第一个节点
    while (copy != null) {
        if (head.val != copy.val) {
            return false;
        }
        head = head.next; // 这里修改的是isPalindrome方法中的head引用
        copy = copy.next;
    }
    return true;
}

// 这里面head在变，但是外面的head没变
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode node = new ListNode(head.val);
        node.next = prev;
        prev = node;
        head = head.next; // 这里修改的是reverseList方法中的head参数（原head的副本）
    }
    return prev;
}

// 会修改原链表，head.next = prev
private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev; // 这里直接修改了原链表节点的next指针
        prev = head;
        head = next;
    }
    return prev;
}