力扣Hot 100题

杂项

• 最大值：Integer.MAX_VALUE
• 最小值：Integer.MIN_VALUE

数组集合比较

Arrays.equals(array1, array2)

• 用于比较两个数组是否相等（内容相同）。
• 支持多种类型的数组（如 int[]、char[]、Object[] 等）。

int[] arr1 = {1, 2, 3};
int[] arr2 = {1, 2, 3};
boolean isEqual = Arrays.equals(arr1, arr2); // true

Collections 类本身没有直接提供类似 Arrays.equals 的方法来比较两个集合的内容是否相等。不过，Java 中的集合类（如 List、Set、Map）已经实现了 equals 方法

List<Integer> list1 = Arrays.asList(1, 2, 3);
List<Integer> list2 = Arrays.asList(1, 2, 3);
List<Integer> list3 = Arrays.asList(3, 2, 1);
System.out.println(list1.equals(list2)); // true
System.out.println(list1.equals(list3)); // false（顺序不同）

逻辑比较

boolean flag = false;
if (!flag) {    //! 是 Java 中的逻辑非运算符，只能用于对布尔值取反。
    System.out.println("flag 是 false");
}

if (flag == false) {             //更常用！
    System.out.println("flag 是 false");
}
//java中没有 if(not flag) 这种写法！

Character好用的方法

Character.isDigit(char c)用于判断一个字符是否是一个数字字符

Character.isLetter(char c)用于判断字符是否是一个字母（大小写字母都可以）。

Character.isLowerCase(char c)判断字符是否是小写字母。

Character.toLowerCase(char c)将字符转换为小写字母。

Integer好用的方法

Integer.parseInt(String s)：将字符串 s 解析为一个整数（int）。

Integer.parseInt(String s, int radix) ：指定进制，指定字符串所用的进制，返回十进制的int值

int num1 = Integer.parseInt("1010", 2);   // 二进制 1010 → 十进制 10
int num2 = Integer.parseInt("A", 16);     // 十六进制 A → 十进制 10
System.out.println(num1); // 10
System.out.println(num2); // 10

Integer.toString(int i)：将 int 转换为字符串。

Integer.compare(int a,int b) 比较a和b的大小，内部实现类似：

public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

避免了 整数溢出 的风险，在排序中建议使用Integer.compare(a,b)代替 a-b。注意，仅支持Integer[] arr，不支持int[] arr。

int->String

public class BaseConverter {
    // 将十进制数 n 转换为 base 进制（2 <= base <= 36）
    public static String toBase(int n, int base) {
        if (n == 0) return "0";

        StringBuilder sb = new StringBuilder();
        boolean negative = n < 0; // 处理负数
        if (negative) n = -n;

        while (n > 0) {
            int digit = n % base; // 取余得到最后一位
            if (digit < 10) {
                sb.append((char) (digit + '0')); // 0~9
            } else {
                sb.append((char) (digit - 10 + 'A')); // 10~35 → A~Z
            }
            n /= base;
        }

        if (negative) sb.append('-'); // 负数加符号
        return sb.reverse().toString(); // 翻转得到正确顺序
    }

    public static void main(String[] args) {
        System.out.println(toBase(255, 2));   // 二进制: 11111111
        System.out.println(toBase(255, 8));   // 八进制: 377
        System.out.println(toBase(255, 16));  // 十六进制: FF
        System.out.println(toBase(12345, 36));// 36进制: 9IX
    }
}

String

转为字符串：

String s1 = String.valueOf(123);     // "123"
String s2 = String.valueOf(true);    // "true"
String s3 = String.valueOf('a');     // "a"

比较：

a.compareTo(b); 比较字符串a和b的大小。

格式化：

String result = String.format(String format, Object... args);

format：格式模板（里面包含占位符）。

args：传入的参数，会依次替换占位符。

%s —— 字符串

%d —— 整数

%f —— 浮点数（默认保留 6 位小数）

%n —— 换行

//1. 拼接字符串
String name = "Alice";
int age = 23;

String result = String.format("My name is %s, I am %d years old.", name, age);
System.out.println(result);
// 输出: My name is Alice, I am 23 years old.

//2. 控制浮点数精度
double pi = 3.14159265358979;

String result = String.format("PI = %.2f", pi);
System.out.println(result);
// 输出: PI = 3.14

排序：

需要String先转为char [] 数组，排序好之后再转为String类型！！

char[] charArray = str.toCharArray();
Arrays.sort(charArray);  //{'2', '2', '9', '9'}
String sortedStr = new String(charArray);   "2299"

iter遍历,也要先转为char[]数组

int[]cnt=new int[26];
for (Character c : s.toCharArray()) {
   cnt[c-'a']++;
}

取字符：

• charAt(int index) 方法返回指定索引处的 char 值。
• char 是基本数据类型，占用 2 个字节，表示一个 Unicode 字符。
• HashSet<Character> set = new HashSet<Character>();

取子串：

• substring(int beginIndex, int endIndex) 方法返回从 beginIndex 到 endIndex - 1 的子字符串。
• 返回的是 String 类型，即使子字符串只有一个字符。

去除开头结尾空字符：

• trim()

分割字符串：

split() 方法，可以用来分割字符串，并返回一个字符串数组。参数是String类型的正则表达式。

String str = "apple, banana, orange grape";
String[] fruits = str.split(",\\s*");  // 按逗号后可能存在的空格分割
// apple  banana  orange grape

s = "ababbc"
String[] parts = s.split("c");
// ["ababb"]

仅用stringbuilder：

public static List<String> splitBySpace(String s) {
    List<String> words = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c != ' ') {
            // 累积字母
            sb.append(c);
        } else {
            // 遇到空格：如果 sb 里有内容，则构成一个单词
            if (sb.length() > 0) {
                words.add(sb.toString());
                sb.setLength(0);  // 清空，准备下一个单词
            }
            // 如果连续多个空格，则这里会跳过 sb.length()==0 的情况
        }
    }
    // 循环结束后，sb 里可能还剩最后一个单词
    if (sb.length() > 0) {
        words.add(sb.toString());
    }
    return words;
}

位运算

按位与 &：只有两个对应位都为 1 时，结果位才为 1。

int a = 5;       // 0101₂  
int b = 3;       // 0011₂  
int c = a & b;   // 0001₂ = 1  
System.out.println(c);  // 输出 1

典型用途：

清零低位：x & (~((1<<k)-1)) 清掉最低 k 位；

(1<<3)-1 = 0000_0111
~((1<<3)-1) = 1111_1000

判断奇偶：x & 1，若结果是 1 说明奇数，若 0 说明偶数；

掩码提取：只保留想要的位置，其他位置置 0。

取低8位：与0xFF（二进制 11111111）进行按位与（&）操作

按位或 |: 只要两个对应位有一个为 1，结果位就为 1。

int a = 5;       // 0101₂  
int b = 3;       // 0011₂  
int c = a | b;   // 0111₂ = 7  
System.out.println(c);  // 输出 7

典型用途：

• 置位：x | (1<<k) 把第 k 位置 1；
• 合并标志：将两个掩码或在一起。

按位异或 ^: 两个对应位不同则为 1，相同则为 0。

int a = 5;       // 0101₂  
int b = 3;       // 0011₂  
int c = a ^ b;   // 0110₂ = 6  
System.out.println(c);  // 输出 6

算术左移 <<: 整体二进制左移 n 位，右侧补 0；相当于乘以 2ⁿ。(因为最高位可能走出符号位，结果符号可能翻转)

int a = 3;       // 0011₂  
int b = a << 2;  // 1100₂ = 12  
System.out.println(b);  // 输出 12

逻辑（无符号）右移>>>:在最高位一律补 0，不管原符号位是什么。

Random

Random 是伪随机数生成器

import java.util.Random;
import java.util.stream.IntStream;

public class RandomDemo {
    public static void main(String[] args) {
        Random rnd = new Random();            // 随机种子
        Random seeded = new Random(2025L);    // 固定种子

        // 1) 随机整数
        int a = rnd.nextInt();               // 任意 int
        int b = rnd.nextInt(100);            // [0,100)
        System.out.println("a=" + a + ", b=" + b);

        // 2) 随机浮点数与布尔
        double d = rnd.nextDouble();          // [0.0,1.0)
        boolean flag = rnd.nextBoolean();
        System.out.println("d=" + d + ", flag=" + flag);
    }
}

想生成5 到 10 之间的整数：

public class RandomRangeDemo {
    public static void main(String[] args) {
        Random rnd = new Random();

        int min = 5;
        int max = 10;
        int n = rnd.nextInt(max - min + 1) + min;

        System.out.println("随机数 = " + n);
    }
}

常用数据结构

StringBuilder

StringBuffer 是线程安全的，它的方法是同步的 (synchronized)，这意味着在多线程环境下使用 StringBuffer 是安全的。

StringBuilder 不是线程安全的，它的方法没有同步机制，因此在单线程环境中，StringBuilder 的性能通常要比 StringBuffer 更好。

它们都是 Java 中用于操作可变字符串的类，拥有相同的方法！

1.append(String str) 向字符串末尾追加内容。

2.insert(int offset, String str) 在指定位置插入字符串。（有妙用，头插法可以实现倒序）insert(0,str)

3.delete(int start, int end) 删除从 start 到 end 索引之间的字符。（包括start，不包括end）

4.deleteCharAt(int index) 删除指定位置的字符。

5.replace(int start, int end, String str) 替换指定范围内的字符。

6.reverse() 将字符串反转。String未提供

重要内容！！！！

7.toString() 返回当前字符串缓冲区的内容，转换为 String 对象。 sb.toString()会创建并返回一个新的、独立的 String 对象，之后setLength(0)不会影响这个 String 对象

8.setLength(int newLength) 设置字符串的长度。 //sb.setLength(0); 用作清空字符串

9.charAt(int index) 返回指定位置的字符。

10.length() 返回当前字符串的长度。

StringBuffer 的 append() 方法不仅支持添加普通的字符串，也可以直接将另一个 StringBuffer 对象添加到当前的 StringBuffer。

StringBuffer 插入int类型的数字时，会自动转为字符串插入。

HashMap

• 基于哈希表实现，查找、插入和删除的平均时间复杂度为 O(1)。
• 不保证元素的顺序。

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建 HashMap
        Map<String, Integer> map = new HashMap<>();

        // 添加键值对
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        // 获取值
        int appleCount = map.get("apple");   //如果获取不存在的元素，返回null
        System.out.println("Apple count: " + appleCount); // 输出 10

        // 遍历 HashMap
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // 输出：
        // apple: 10
        // banana: 20
        // orange: 30

        // 检查是否包含某个键
        boolean containsBanana = map.containsKey("banana");
        System.out.println("Contains banana: " + containsBanana); // 输出 true

        // 删除键值对
        map.remove("orange");   //删除不存在的元素也不会报错
        System.out.println("After removal: " + map); // 输出 {apple=10, banana=20}
    }
}

如何在创建的时候初始化？“双括号”初始化

Map<Integer, Character> map = new HashMap<>() {{
    put(1, 'a');
    put(2, 'b');
    put(3, 'c');
}};

记录二维数组中某元素是否被访问过，推荐使用：

int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];

// 访问 (i, j) 时标记为已访问
visited[i][j] = true;

而非创建自定义Pair二元组作为键用Map记录。

统计每个字母出现的次数：

int[] cnt = new int[26];
for (char c : magazine.toCharArray()) {
    cnt[c - 'a']++;
}

修改键值对中的键值：

Map<Character, Integer> counts = new HashMap<>();
counts.put(ch, counts.getOrDefault(ch, 0) + 1);

如何遍历Map?

只关心 键 的时候：

Map<String, Integer> map = new HashMap<>();
map.put("Tom", 18);
map.put("Jerry", 20);

// 遍历 key
for (String key : map.keySet()) {
    System.out.println("key = " + key);
}

只关心 值 的时候：

for (Integer value : map.values()) {
    System.out.println("value = " + value);
}

同时获取 键和值：

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

HashSet

• 基于哈希表实现，查找、插入和删除的平均时间复杂度为 O(1)。

• 不保证元素的顺序!!因此不太用iterator迭代，而是用contains判断是否有xx元素。

  import java.util.HashSet;
  import java.util.Set;
  
  public class HashSetExample {
      public static void main(String[] args) {
          // 创建 HashSet
          Set<Integer> set = new HashSet<>();
  
          // 添加元素
          set.add(10);
          set.add(20);
          set.add(30);
          set.add(10); // 重复元素，不会被添加
  
          // 检查元素是否存在
          boolean contains20 = set.contains(20);
          System.out.println("Contains 20: " + contains20); // 输出 true
  
          // 遍历 HashSet
          for (int num : set) {
              System.out.println(num);
          }
          // 输出：
          // 20
          // 10
          // 30
  
          // 删除元素
          set.remove(20);
          System.out.println("After removal: " + set); // 输出 [10, 30]
      }
  }

 public void isHappy() {
        Set<Integer> set1 = new HashSet<>(List.of(1,2,3));
        Set<Integer> set2 = new HashSet<>(List.of(2,3,1));
        Set<Integer> set3 = new HashSet<>(List.of(3,2,1));

        Set<Set<Integer>> sset = new HashSet<>();
        sset.add(set1);
        sset.add(set2);
        sset.add(set3);
    }

这里最终sset的size为1

如何从List中初始化Set？

Set<String> set1 = new HashSet<>(wordList);  //构造器直接初始化

如何从Array中初始化？

Set<String> set1 = new HashSet<>(Arrays.asList(wordList));  //构造器直接初始化

PriorityQueue

• 基于优先堆（最小堆或最大堆）实现，元素按优先级排序。
• 默认是最小堆，即队首元素是最小的。 new PriorityQueue<>(Comparator.reverseOrder());定义最大堆
• 支持自定义排序规则，通过 Comparator 实现。

常用方法：

add(E e) / offer(E e)：

• 功能：将元素插入队列。
• 时间复杂度：O(log n)
• 区别
  • add：当队列满时会抛出异常。
  • offer：当队列满时返回 false，不会抛出异常。

remove() / poll()：

• 功能：移除并返回队首元素。
• 时间复杂度：O(log n)
• 区别
  • remove：队列为空时抛出异常。
  • poll：队列为空时返回 null。

element() / peek()：

• 功能：查看队首元素，但不移除。
• 时间复杂度：O(1)
• 区别
  • element：队列为空时抛出异常。
  • peek：队列为空时返回 null。

clear()：

• 功能：清空队列。
• 时间复杂度：O(n)（因为需要删除所有元素）

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建 PriorityQueue（默认是最小堆）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 添加元素
        minHeap.add(10);
        minHeap.add(20);
        minHeap.add(5);

        // 查看队首元素
        System.out.println("队首元素: " + minHeap.peek()); // 输出 5

        // 遍历 PriorityQueue（注意：遍历顺序不保证有序）
        System.out.println("遍历 PriorityQueue:");
        for (int num : minHeap) {
            System.out.println(num);
        }
        // 输出：
        // 5
        // 10
        // 20

        // 移除队首元素
        System.out.println("移除队首元素: " + minHeap.poll()); // 输出 5

        // 再次查看队首元素
        System.out.println("队首元素: " + minHeap.peek()); // 输出 10

        // 创建最大堆（通过自定义 Comparator）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(5);

        // 查看队首元素
        System.out.println("最大堆队首元素: " + maxHeap.peek()); // 输出 20

        // 清空队列
        minHeap.clear();
        System.out.println("队列是否为空: " + minHeap.isEmpty()); // 输出 true
    }
}

自定义排序

按第二个元素的值构建小根堆

如果比较器返回负数，则第一个数排在前面->优先级高->在堆顶

public class CustomPriorityQueue {
    public static void main(String[] args) {
        // 定义一个 PriorityQueue，其中每个元素是 int[]，并且按照数组第二个元素升序排列
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> a[1] - b[1]
        );
        
        // 添加数组
        minHeap.offer(new int[]{1, 2});
        minHeap.offer(new int[]{3, 4});
        minHeap.offer(new int[]{0, 5});
        
        // 依次取出元素，输出结果
        while (!minHeap.isEmpty()) {
            int[] arr = minHeap.poll();
            System.out.println(Arrays.toString(arr));
        }
    }
}

不用lambda版本（不推荐）：

PriorityQueue<int[]> minHeap = new PriorityQueue<>(new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        return a[1] - b[1];
    }
});

自己实现小根堆

父节点：对于任意索引 i，其父节点的索引为 (i - 1) // 2。

左子节点：索引为 i 的节点，其左子节点的索引为 2 * i + 1。

右子节点：索引为 i 的节点，其右子节点的索引为 2 * i + 2。

上滤与下滤操作

• 上滤（Sift-Up）： 用于插入操作。将新加入的元素与其父节点不断比较，若小于父节点则交换，直到满足堆序性质。
• 下滤（Sift-Down）： 用于删除操作或建堆。将根节点或某个节点与其子节点中较小的进行比较，若大于子节点则交换，直至满足堆序性质。

建堆：从数组中最后一个非叶节点开始（索引为 heapSize/2 - 1），对每个节点执行下滤操作（sift-down）

插入元素：将新元素插入到堆的末尾，然后执行上滤操作（sift-up），以保持堆序性质。

弹出元素（删除堆顶）：弹出操作一般是删除堆顶元素（小根堆中即最小值），然后用堆尾元素替代堆顶，再进行下滤操作。

class MinHeap {
    private int[] heap; // 数组存储堆元素
    private int size;   // 当前堆中元素的个数

    // 构造函数，初始化堆，capacity为堆的最大容量
    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // 插入元素：先将新元素添加到数组末尾，然后执行上滤操作恢复堆序性质
    public void insert(int value) {
        if (size >= heap.length) {
            throw new RuntimeException("Heap is full");
        }
        // 将新元素放到末尾
        heap[size] = value;
        int i = size;
        size++;

        // 上滤操作：不断与父节点比较，若新元素小于父节点则交换
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] < heap[parent]) {
                swap(heap, i, parent);
                i = parent;
            } else {
                break;
            }
        }
    }

    // 弹出堆顶元素：移除堆顶（最小值），用最后一个元素替换堆顶，然后下滤恢复堆序
    public int pop() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int min = heap[0];
        // 将最后一个元素移到堆顶
        heap[0] = heap[size - 1];
        size--;
        // 对新的堆顶执行下滤操作，恢复堆序性质
        minHeapify(heap, 0, size);
        return min;
    }

    // 建堆：将无序数组a构造成小根堆，heapSize为数组长度
    public static void buildMinHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) {
            minHeapify(a, i, heapSize);
        }
    }

    // 下滤操作：从索引i开始，将子树调整为小根堆
    public static void minHeapify(int[] a, int i, int heapSize) {
        int l = 2 * i + 1, r = 2 * i + 2;
        int smallest = i;
        // 判断左子节点是否存在且比当前节点小
        if (l < heapSize && a[l] < a[smallest]) {
            smallest = l;
        }
        // 判断右子节点是否存在且比当前最小节点小
        if (r < heapSize && a[r] < a[smallest]) {
            smallest = r;
        }
        // 如果最小值不是当前节点，交换后继续对被交换的子节点执行下滤操作
        if (smallest != i) {
            swap(a, i, smallest);
            minHeapify(a, smallest, heapSize);
        }
    }

    // 交换数组中两个位置的元素
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

改为大根堆只需要把里面 ''<'' 符号改为 ''>''

ArrayList

1.基本特性

基于数组实现，支持动态扩展。

随机访问效率高：get()、set() 时间复杂度为 O(1)。

末尾插入/删除效率高：add(E e)、remove(size-1) 时间复杂度为 O(1)（均摊）。

指定位置插入/删除效率低：add(int index, E e)、remove(int index) 时间复杂度为 O(n)，因为需要移动元素。

2.常用操作

添加元素

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);

获取大小

int size = list.size(); // 3

访问和修改元素

int first = list.get(0);   // 10
list.set(1, 25);           // 修改第二个元素为 25

删除元素

list.remove(2);  // 删除索引为2的元素

遍历

//增强 for：
for (int num : list) {
    System.out.println(num);
}
//普通 for：
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

3.批量操作

复制列表

List<Integer> list1 = new ArrayList<>();
// 假设 list1 中已有数据

// 方法一：addAll
List<Integer> list2 = new ArrayList<>();
list2.addAll(list1);

// 方法二：构造函数
List<Integer> list3 = new ArrayList<>(list1);

清空列表

list.clear();

复制到数组

推荐手动遍历；Java 自带 toArray 也能用但较麻烦。

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

4.二维 ArrayList

如果事先不知道嵌套列表的大小如何遍历呢？

//增强 for：
for (List<Integer> row : list) {
    for (int num : row) {
        System.out.print(num + " ");
    }
    System.out.println();
}
//普通 for：
for (int i = 0; i < list.size(); i++) {
    for (int j = 0; j < list.get(i).size(); j++) {
        System.out.print(list.get(i).get(j) + " ");
    }
    System.out.println();
}

数组（Array）

数组是一种固定长度的数据结构，用于存储相同类型的元素。数组的特点包括：

• 固定长度：数组的长度在创建时确定，无法动态扩展。
• 快速访问：通过索引访问元素的时间复杂度为 O(1)。
• 连续内存：数组的元素在内存中是连续存储的。

public class ArrayExample {
    public static void main(String[] args) {
        // 创建数组
        int[] array = new int[5]; // 创建一个长度为 5 的整型数组

        // 添加元素
        array[0] = 10;
        array[1] = 20;
        array[2] = 30;
        array[3] = 40;
        array[4] = 50;

        // 获取元素
        int firstElement = array[0];
        System.out.println("First element: " + firstElement); // 输出 10

        // 修改元素
        array[1] = 25; // 将第二个元素改为 25
        System.out.println("After modification:");
        for (int num : array) {
            System.out.println(num);
        }
        // 输出：
        // 10
        // 25
        // 30
        // 40
        // 50

        // 遍历数组
        System.out.println("Iterating through array:");
        for (int i = 0; i < array.length; i++) {
            System.out.println("Index " + i + ": " + array[i]);
        }
        // 输出：
        // Index 0: 10
        // Index 1: 25
        // Index 2: 30
        // Index 3: 40
        // Index 4: 50

        // 删除元素（数组长度固定，无法直接删除，可以通过覆盖实现）
        int indexToRemove = 2; // 要删除的元素的索引
        for (int i = indexToRemove; i < array.length - 1; i++) {
            array[i] = array[i + 1]; // 将后面的元素向前移动
        }
        array[array.length - 1] = 0; // 最后一个元素置为 0（或其他默认值）
        System.out.println("After removal:");
        for (int num : array) {
            System.out.println(num);
        }
        // 输出：
        // 10
        // 25
        // 40
        // 50
        // 0

        // 数组长度
        int length = array.length;
        System.out.println("Array length: " + length); // 输出 5
    }
}

复制数组：

int[] source = {1, 2, 3, 4, 5};
int[] destination = Arrays.copyOf(source, source.length);
int[] partialArray = Arrays.copyOfRange(source, 1, 4);   //复制指定元素，不包括索引4

初始化：

int double 数值默认初始化为0，boolean默认初始化为false

//一维
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);

//二维
int[][] test=new int[2][2];
for (int[] ints : test) {
    Arrays.fill(ints,1);
}

注意：数组求size： xx.length;

String求size：xx.length();

List求size：xx.size();

二维数组

int[][] res = new int[rows][];

只指定了二维数组的“行数”，没有指定“列数”。这是 Java 里允许的。

int rows = 3;
int cols = 3;
int[][] array = new int[rows][cols];
// 填充数据
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        array[i][j] = i * cols + j + 1;
    }
}
//创建并初始化
int[][] array = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 遍历二维数组，不知道几行几列
public void setZeroes(int[][] matrix) {
    // 遍历每一行
    for (int i = 0; i < matrix.length; i++) {
        // 遍历当前行的每一列
        for (int j = 0; j < matrix[i].length; j++) {
            // 这里可以处理 matrix[i][j] 的元素
            System.out.print(matrix[i][j] + " ");
        }
        System.out.println(); // 换行，便于输出格式化
    }
}

[[1, 0]] 是一行两列数组。

Queue

队尾插入，队头取！

import java.util.Queue;
import java.util.LinkedList;

public class QueueExample {
    public static void main(String[] args) {
        // 创建一个队列
        Queue<Integer> queue = new LinkedList<>();

        // 添加元素到队列中
        queue.add(10);       // 使用 add() 方法添加元素
        queue.offer(20);     // 使用 offer() 方法添加元素
        queue.add(30);
        System.out.println("队列内容：" + queue);

        // 查看队头元素，不移除
        int head = queue.peek();
        System.out.println("队头元素（peek）： " + head);

        // 移除队头元素
        int removed = queue.poll();
        System.out.println("移除的队头元素（poll）： " + removed);
        System.out.println("队列内容：" + queue);

        // 再次移除队头元素
        int removed2 = queue.remove();
        System.out.println("移除的队头元素（remove）： " + removed2);
        System.out.println("队列内容：" + queue);
    }
}

Deque(双端队列+栈)

支持在队列的两端（头和尾）进行元素的插入和删除。这使得 **Deque 既能作为队列（FIFO）又能作为栈（LIFO）使用。**栈可以看作双端队列的特例，即使用一端。

• LinkedList 是基于双向链表实现的，每个节点存储数据和指向前后节点的引用。
• ArrayDeque 则基于动态数组实现，内部使用循环数组来存储数据。
• ArrayDeque 在大多数情况下性能更好，因为数组在内存中连续，缓存友好，且操作（如 push/pop）开销更小。

栈

Deque<Integer> stack = new ArrayDeque<>();
//Deque<Integer> stack = new LinkedList<>();
stack.push(1);   // 入栈
Integer top1=stack.peek()
Integer top = stack.pop();   // 出栈

双端队列

在队头操作

• offerFirst(E e)：在队头插入元素，返回 true 或 false 表示是否成功。
• peekFirst()：查看队头元素，不移除；队列为空返回 null。
• pollFirst()：移除并返回队头元素；队列为空返回 null。
• poll() ：移除并返回队头元素

在队尾操作

• offerLast(E e)：在队尾插入元素，返回 true 或 false 表示是否成功。
• offer(E e) : 把元素放到 队尾
• peekLast()：查看队尾元素，不移除；队列为空返回 null。
• pollLast()：移除并返回队尾元素；队列为空返回 null。

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeExampleSafe {
    public static void main(String[] args) {
        // 使用 ArrayDeque 实现双端队列
        Deque<Integer> deque = new ArrayDeque<>();

        /* ========= 在队列两端“安全”地添加元素 ========= */
        deque.offerFirst(10); // 队头 ← 10
        deque.offerLast(20);  //          20 ← 队尾
        deque.offerFirst(5);  // 队头 ← 5,10,20
        deque.offerLast(30);  // 队尾 → 5,10,20,30

        System.out.println("双端队列内容：" + deque);

        /* ========= “安全”地查看队头/队尾 ========= */
        Integer first = deque.peekFirst(); // 队头元素（5）
        Integer last  = deque.peekLast();  // 队尾元素（30）
        System.out.println("队头元素：" + first);
        System.out.println("队尾元素：" + last);

        /* ========= “安全”地移除队头/队尾 ========= */
        Integer removedFirst = deque.pollFirst(); // 移除并返回队头（5）
        System.out.println("移除队头元素：" + removedFirst);

        Integer removedLast  = deque.pollLast();  // 移除并返回队尾（30）
        System.out.println("移除队尾元素：" + removedLast);

        System.out.println("双端队列最终内容：" + deque);
    }
}

栈和双端队列的对应关系

栈只有队头！

• 添加元素：push(e) ⇒ addFirst(e) （安全版：offerFirst(e)）
• 删除元素：pop() ⇒ removeFirst() （安全版：pollFirst()）
• 查看栈顶：peek() ⇒ peekFirst()

Iterator

• HashMap、HashSet、ArrayList 和 PriorityQueue 都实现了 Iterable 接口，支持 iterator() 方法。

Iterator 接口中包含以下主要方法：

1. hasNext()：如果迭代器还有下一个元素，则返回 true，否则返回 false。
2. next()：返回迭代器的下一个元素，并将迭代器移动到下一个位置。
3. remove()：从迭代器当前位置删除元素。该方法是可选的，不是所有的迭代器都支持。

import java.util.ArrayList;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        // 创建一个 ArrayList 集合
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        // 获取集合的迭代器
        Iterator<Integer> iterator = list.iterator();

        // 使用迭代器遍历集合并输出元素
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            System.out.println(element);
        }
    }
}

Collections工具类

1.排序

参数必须是 List<T>

Collections.sort(list); 

• 对 list 进行升序排序（要求元素实现了 Comparable 接口，比如 Integer、String）。

Collections.sort(list, Collections.reverseOrder()); 

2.反转

参数也是 List<?>。

Collections.reverse(list);  //[1,2,3] → [3,2,1]

3.最大 / 最小值

参数是 Collection，可以是Set

Collections.max(list);
Collections.min(list);

查找

二分查找

public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length; // 注意 right = arr.length，而不是 arr.length-1
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= target) {
                right = mid; // 收缩右边界
            } else {
                left = mid + 1; // 收缩左边界
            }
        }
        return left; // 最终 left 就是答案
    }

排序

快速排序

基本思想：

快速排序是一种基于“分治”思想的排序算法，通过选定一个“枢轴元素（pivot）”，将数组划分为左右两个子区间：左边都小于等于 pivot，右边都大于等于 pivot；然后对这两个子区间递归排序，最终使整个数组有序。

public class QuickSort {

    /**
     * 对数组 arr 在下标 low 到 high 范围内进行快速排序
     * 使用“挖坑填坑”方式，不再调用 swap 方法
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotPos = partition(arr, low, high); // 划分
            quickSort(arr, low, pivotPos - 1);        // 递归排序左子表
            quickSort(arr, pivotPos + 1, high);       // 递归排序右子表
        }
    }
    
    /**
     * 划分函数：以 arr[low] 作为枢轴，通过“挖坑—填坑”将小于枢轴的元素移到左边，
     * 大于枢轴的元素移到右边，最后返回枢轴的最终下标
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];  // 先保存枢轴
      
        while (low < high) {
            // 从右向左找第一个小于 pivot 的元素，填到 left 这个“坑”里
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];

            // 从左向右找第一个大于 pivot 的元素，填到 right 这个“坑”里
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        // 最后把枢轴填回中心位置
        arr[low] = pivot;
        return low;
    }
}

时间复杂度： 1）单次划分（partition）：每次调用 partition，都要从数组的两端向中间扫描一遍，直到两个指针相遇。所以 一次 partition 操作的时间复杂度是 O(n)

2）快速排序的核心是 分治：每次划分，把数组分成左右两个子数组，然后分别递归排序。如果每次 pivot 都把数组近似平均分成两半，那么递归树高度大约是 log n。

Java随机

mport java.util.Random;

public class RandomDemo {
    public static void main(String[] args) {
        Random random = new Random();
        int num = random.nextInt(6); // 生成 [0, 5] 的随机整数
        System.out.println(num);
    }
}

快速选择

时间复杂度: O(n)

public class QuickSelect {

    /**
     * 在数组 arr 的 [low..high] 区间内，寻找第 k 小的元素（k 从 0 开始计数）
     * 使用快速选择（Quick Select）算法，平均时间复杂度 O(n)
     */
    public int quickselect(int[] arr, int low, int high, int k) {
        if (low <= high) {
            int pivotPos = partition(arr, low, high); // 划分操作，返回枢轴的最终下标

            if (pivotPos == k) {
                // 找到了第 k 小的元素
                return arr[pivotPos];
            } else if (k < pivotPos) {
                // 如果第 k 小元素在枢轴左边
                return quickselect(arr, low, pivotPos - 1, k);
            } else {
                // 如果第 k 小元素在枢轴右边
                return quickselect(arr, pivotPos + 1, high, k);
            }
        }

        // 正常情况下不会走到这里（除非 k 越界）
        throw new IllegalArgumentException("k is out of bounds");
    }

    /**
     * 划分函数（partition）—— 挖坑填坑法
     * 功能：以 arr[low] 为枢轴，将小于 pivot 的放左边，大于 pivot 的放右边
     * 返回枢轴的最终位置（low == high 时）
     */
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选取枢轴（第一个元素）

        // “挖坑填坑”过程
        while (low < high) {
            // 从右向左找第一个小于 pivot 的元素
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high]; // 填到左边的“坑”里

            // 从左向右找第一个大于 pivot 的元素
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low]; // 填到右边的“坑”里
        }

        // 最后将枢轴填回当前位置
        arr[low] = pivot;
        return low; // 返回枢轴的最终位置
    }

    /**
     * 返回数组中第 k 大的元素（k 从 1 开始）
     * 例如：k=1 表示最大值，k=2 表示次大值
     */
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 第 k 大 == 第 (n - k) 小
        return quickselect(nums, 0, n - 1, n - k);
    }
}

冒泡排序

基本思想：

【每次将最小/大元素，通过依次交换顺序，放到首/尾位。】

• 从后往前（或从前往后）两两比较相邻元素的值，若为逆序, 则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置）；
• 下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置。
• ……这样最多做n - 1趟冒泡就能把所有元素排好序。
• 如若有一趟没有元素交换位置，则可提前说明已排好序。

public void bubbleSort(int[] arr){
        //n-1 趟冒泡
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag=false;
            //冒泡
            for (int j = arr.length-1; j >i ; j--) {
                if (arr[j-1]>arr[j]){
                    swap(arr,j-1,j);
                    flag=true;
                }
            }
            //本趟遍历后没有发生交换，说明表已经有序
            if (!flag){
                return;
            }
        }
    }
    private void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

归并排序

数组归并排序

基本思想：

将待排序的数组视为多个有序子表，每个子表的长度为 1，通过两两归并逐步合并成一个有序数组。

实现思路

• 分解：递归地将数组拆分成两个子数组，直到每个子数组只有一个元素。
• 合并：将两个有序子数组合并为一个有序数组。

时间复杂度： O(n log n)，无论最坏、最好、平均情况。

public class MergeSort {

    /**
     * 归并排序（入口函数）
     * @param arr 待排序数组
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 边界条件
        }
        int[] temp = new int[arr.length]; // 辅助数组
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (right + left) / 2; 
            mergeSort(arr, left, mid, temp);     // 递归左子数组
            mergeSort(arr, mid + 1, right, temp); // 递归右子数组
            merge(arr, left, mid, right, temp);  // 合并两个有序子数组
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;    // 左子数组起始指针
        int j = mid + 1; // 右子数组起始指针
        int t = 0;       // 辅助数组指针

        // 1. 按序合并两个子数组到temp
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) { // 注意等号保证稳定性
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        // 2. 将剩余元素拷贝到temp
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }

        // 3. 将temp中的数据复制回原数组
        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

链表归并排序

// 简易链表归并排序示意
ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // ① 快慢指针找中点并断链
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;
    // ② 递归排序左右两段
    ListNode left  = sortList(head);
    ListNode right = sortList(mid);
    // ③ 合并
    return merge(left, right);
}

ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(-1), p = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { p.next = a; a = a.next; }
        else               { p.next = b; b = b.next; }
        p = p.next;
    }
    p.next = (a != null ? a : b);
    return dummy.next;
    
}

快慢指针找 “中点” 和找 “环” 的出发点为什么会不一样？

总之：自己模拟一遍，奇数和偶数的情况。

堆排序

下滤

从一个节点出发，如果它不满足堆的性质（父节点比子节点小——针对最大堆），就和它的较大子节点交换， 然后继续向下检查，直到满足堆性质或到达叶子节点。

堆排序示例

初始数组：[7, 3, 4, 2, 6, 8]

1️⃣ 建堆（Build Max Heap） 使整个数组满足“父节点 ≥ 子节点”的性质。

从最后一个非叶子节点开始下滤（i = n/2 - 1 = 2）

(1) i = 2 → 元素 4

子节点：5=8 → 8 比 4 大 → 交换 → [7, 3, 8, 2, 6, 4]

(2) i = 1 → 元素 3

子节点：3=2, 4=6 → 最大子节点为 6 → 交换 → [7, 6, 8, 2, 3, 4]

(3) i = 0 → 元素 7

子节点：1=6, 2=8 → 最大子节点是 8 → 交换 → [8, 6, 7, 2, 3, 4]

建堆完成（最大堆）

2️⃣ 交换堆顶与末尾元素 把最大值放到数组末尾，相当于固定下来了。

3️⃣ 调整堆（Heapify） 重新调整剩余部分为最大堆。

4️⃣ 重复步骤 2 和 3，直到排序完成。

基数排序

时间复杂度：

• O(d × (n + k)) 其中 d 是数字的位数，k 是每位的取值范围（例如 0–9）。

排序0-999范围的整数：

1. 创建10个桶（对应数字0-9）
2. 按个位数字分配到桶中
3. 按十位数字重新分配
4. 按百位数字最后分配
5. 按顺序收集桶中元素

示例：

[352, 143, 129, 457, 65, 97, 8, 452, 72, 290]

第一步：按个位数分配

桶0: 290
桶1: 
桶2: 352, 452, 72
桶3: 143
桶4: 
桶5: 65
桶6: 
桶7: 457, 97
桶8: 8
桶9: 129

收集结果：[290, 352, 452, 72, 143, 65, 457, 97, 8, 129]

第二步：按十位数分配

桶0: 8
桶1: 
桶2: 129
桶3: 
桶4: 143
桶5: 352, 452, 457
桶6: 65
桶7: 72
桶8: 
桶9: 290, 97

收集结果：[8, 129, 143, 352, 452, 457, 65, 72, 290, 97]

第三步：按百位数分配

桶0: 8, 65, 72, 97
桶1: 129, 143
桶2: 290
桶3: 352
桶4: 452, 457
桶5: 
桶6: 
桶7: 
桶8: 
桶9:

收集结果：[8, 65, 72, 97, 129, 143, 290, 352, 452, 457]

数组排序

1）默认升序：

Arrays.sort(array) 会对整个数组升序排序。

也可以指定区间 [fromIndex, toIndex)，只排序部分数组。

import java.util.Arrays;

public class ArraySortExample {
    public static void main(String[] args) {
        int[] numbers = {5, 2, 9, 1, 5, 6};

        Arrays.sort(numbers); // 全部升序排序
        System.out.println(Arrays.toString(numbers)); // [1, 2, 5, 5, 6, 9]

        Arrays.sort(numbers, 1, 4); // 只对下标 [1,4) → {2,9,1} 排序
        System.out.println(Arrays.toString(numbers));
    }
}

2）自定义降序：

如果数组元素是 对象类型（如 Integer[]、String[] 或自定义类），可以直接使用 Comparator 实现复杂排序规则。

import java.util.*;

public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] arr = {5, 2, 9, 1, 5, 6};

        // 使用 Comparator + Lambda 实现降序
        Arrays.sort(arr, (a, b) -> Integer.compare(b, a));

        // 或者使用内置的 reverseOrder()
        Arrays.sort(arr, Collections.reverseOrder());

        // 也可以指定区间 [1,4)，对 {2,9,1} 排序
        Arrays.sort(arr, 1, 4, Collections.reverseOrder());

        System.out.println(Arrays.toString(arr));
    }
}

3）基本类型数组的降序

Arrays.sort() 对基本类型（int[]、double[] 等）只支持 升序。

如果要降序，需要先升序，再反转数组。

public class DescendingPrimitiveSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};

        // 先排序（升序）
        Arrays.sort(arr);

        // 反转数组
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }

        // 输出结果
        System.out.println(Arrays.toString(arr));
    }
}

集合排序

java 里通常说的“集合”，是指 实现了 java.util.Collection 接口的类，以及 Map 相关的类。

1）自然顺序排序（默认升序）：

Collections.sort(numbers);

等价于：

numbers.sort(null); // Java 8 推荐写法

适用于元素实现了 Comparable 接口（如 Integer、String）。

2）降序排序

Collections.sort(numbers, Collections.reverseOrder());

或者：

numbers.sort((a, b) -> Integer.compare(b,a));

3）自定义降序（Comparator + Lambda）

List<String> names = Arrays.asList("Tom", "Jerry", "Alice", "Bob");

// 按字符串长度升序
names.sort((s1, s2) -> Integer.compare(s1.length(), s2.length()));

补充：

Comparator.reverseOrder()  // `Comparator<T>` 接口的静态方法
//等价于
Collections.reverseOrder()

自定义排序Comparator 说明

要实现接口自定义排序，必须实现 Comparator<T> 接口的 compare(T o1, T o2) 方法。

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);  // 唯一抽象方法 ✅

    // 以下都是 default 或 static 方法（不是抽象方法）
    default Comparator<T> reversed() { ... }
    static <T extends Comparable<? super T>> Comparator<T> reverseOrder() { ... }
}

Comparator 接口中定义的 compare(T o1, T o2) 方法返回一个整数（非布尔值！！），这个整数的正负意义如下：

• 如果返回负数，说明 o1 排在 o2前面。
• 如果返回零，说明 o1 等于 o2。
• 如果返回正数，说明 o1 排在 o2后面。

示例：对象排序（按年龄升序）

import java.util.*;

class Person {
    String name;
    int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class ComparatorExample {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 25),
            new Person("Bob", 20),
            new Person("Charlie", 30)
        );

        // 使用 Comparator + Lambda 按年龄排序
        people.sort((p1, p2) -> Integer.compare(p1.age, p2.age));

        System.out.println(people); // [Bob (20), Alice (25), Charlie (30)]
    }
}

补充：String比较

a.compareTo(b);

题型

常见术语

子串（Substring）：子字符串 是字符串中连续的 非空 字符序列

回文串(Palindrome)：回文 串是向前和向后读都相同的字符串。

子序列（(Subsequence)）：可以通过删除原字符串中任意个字符（不改变剩余字符的相对顺序）得到的序列，不要求连续。例如 "abc" 的 "ac" 就是一个子序列。

子数组：数组中连续的部分。

前缀 (Prefix) ：从字符串起始位置开始的连续字符序列，如 "leetcode" 的前缀 "lee"。

字母异位词 (Anagram)：由相同字符组成但排列顺序不同的字符串。例如 "abc" 与 "cab" 就是异位词。

子集、幂集：数组的 子集 是从数组中选择一些元素（可能为空）。例如，对于集合 S = {1, 2}，其幂集为： { ∅, {1}, {2}, {1, 2} }，子集有{1}

链表

“头插法”本质上就是把新节点“插”到已构建链表的头部

1.反转链表

2.从头开始构建链表（逆序插入）

ListNode buildList(int[] arr) {
    ListNode head = null;
    for (int i = 0; i < arr.length; i++) {
        ListNode node = new ListNode(arr[i]);
        node.next = head;  // 头插：新节点指向原 head
        head = node;       // head 指向新节点
    }
    return head;
}
// 结果链表的顺序是 arr 最后一个元素在最前面，如果你想保持原序，可以倒序遍历 arr。

输入：arr[0] -> arr[1] -> … -> arr[n-1]

输出：arr[n-1]-> arr[n-2]-> …->arr[0]

Floyd判环法：快慢指针

public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    // 快慢指针都从 head 出发
    ListNode slow = head;
    ListNode fast = head;

    // 当 fast 或 fast.next 为 null 时，说明已经到链表末尾，无环
    while (fast != null && fast.next != null) {
        slow = slow.next;          // 慢指针走一步
        fast = fast.next.next;     // 快指针走两步

        // 每走一步就检查一次相遇
        if (slow == fast) {
            return true;           // 相遇则有环
        }
    }

    return false;                  // 跳出循环说明没有环
}

何时需要定义dummy节点？

当你的操作有可能“改”到原始的头节点（插入到最前面，或删除掉第一个节点）时，就定义一个 dummy，把它挂在 head 之前，之后所有插入/删除都操作 dummy.next 及其后继，最后返回 dummy.next。

哈希

问题分析：

• 确定是否需要快速查找或存储数据。
• 判断是否需要统计元素频率或检查元素是否存在。

适用场景

1. 快速查找：
   • 当需要频繁查找元素时，哈希表可以提供 O(1) 的平均时间复杂度。
2. 统计频率：
   • 统计元素出现次数时，哈希表是常用工具。
3. 去重：
   • 需要去除重复元素时，HashSet 可以有效实现。

双指针

题型：

• 同向双指针：两个指针从同一侧开始移动，通常用于滑动窗口或链表问题。
• 对向双指针：两个指针从两端向中间移动，通常用于有序数组或回文问题。重点是考虑移动哪个指针可能优化结果！！！
• 快慢指针：两个指针以不同速度移动，通常用于链表中的环检测或中点查找。

适用场景：

有序数组的两数之和：

• 在对向双指针的帮助下，可以在 O(n) 时间内找到两个数，使它们的和等于目标值。

滑动窗口：

• 用于解决子数组或子字符串问题，如同向双指针可以在 O(n) 时间内找到满足条件的最短或最长子数组。

链表中的环检测：

• 快慢指针可以用于检测链表中是否存在环，并找到环的起点。

回文问题：

• 对向双指针可以用于判断字符串或数组是否是回文。

合并有序数组或链表：

• 双指针可以用于合并两个有序数组或链表，时间复杂度为 O(n)。

前缀和

1. 前缀和的定义
   定义前缀和 preSum[i] 为数组 nums 从索引 0 到 i 的元素和，即
   $$ \text{preSum}[i] = \sum_{j=0}^{i} \text{nums}[j] $$

2. 子数组和的关系
   对于任意子数组 nums[i+1..j]（其中 0 ≤ i < j < n），其和可以表示为
   $$ \text{sum}(i+1,j) = \text{preSum}[j] - \text{preSum}[i] $$ 当这个子数组的和等于 k 时，有
   $$ \text{preSum}[j] - \text{preSum}[i] = k $$ 即
   $$ \text{preSum}[i] = \text{preSum}[j] - k $$ $\text{preSum}[j] - k$表示 "以当前位置结尾的子数组和为k"

3. 利用哈希表存储前缀和
   我们可以使用一个哈希表 prefix 来存储每个前缀和出现的次数。

   • 初始时，prefix[0] = 1，表示前缀和为 0 出现一次（对应空前缀）。
   • 遍历数组，每计算一个新的前缀和 preSum，就查看 preSum - k 是否在哈希表中。如果存在，则说明之前有一个前缀和等于 preSum - k，那么从该位置后一个位置到当前索引的子数组和为 k，累加其出现的次数。

4. 时间复杂度
   该方法只需要遍历数组一次，时间复杂度为 O(n)。

遍历二叉树

递归法中序

public void inOrderTraversal(TreeNode root, List<Integer> list) {
    if (root != null) {
        inOrderTraversal(root.left, list);     // 遍历左子树
        list.add(root.val);                    // 访问当前节点
        inOrderTraversal(root.right, list);    // 遍历右子树
    }
}

迭代法中序

public void inOrderTraversalIterative(TreeNode root, List<Integer> list) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        // 一路向左入栈
        while (curr != null) {
            stack.push(curr);  // push = addFirst
            curr = curr.left;
        }
        // 弹出栈顶并访问
        curr = stack.pop();     // pop = removeFirst
        list.add(curr.val);
        // 转向右子树
        curr = curr.right;
    }
}

迭代法前序

public void preOrderTraversalIterative(TreeNode root, List<Integer> list) {
    if (root == null) return;

    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        list.add(node.val); // 先访问当前节点

        // 注意：先压右子节点，再压左子节点
        // 因为栈是“后进先出”的，先弹出的是左子节点
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

层序遍历BFS

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
        
        return result;
    }

回溯法

回溯算法用于 搜索一个问题的所有的解 ，即爆搜（暴力解法），通过深度优先遍历的思想实现。核心思想是：

1.逐步构建解答：

回溯算法通过逐步构造候选解，当构造的部分解满足条件时继续扩展；如果发现当前解不符合要求，则“回溯”到上一步，尝试其他可能性。

2.剪枝（Pruning）：

在构造候选解的过程中，算法会判断当前部分解是否有可能扩展成最终的有效解。如果判断出无论如何扩展都不可能得到正确解，就立即停止继续扩展该分支，从而节省计算资源。

3.递归调用

回溯通常通过递归来实现。递归函数在每一层都尝试不同的选择，并在尝试失败或达到终点时返回上一层重新尝试其他选择。

例：以数组 [1, 2, 3] 的全排列为例。

先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列（注意：递归结构体现在这里）； 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列； 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

public class Permute {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 用来标记数组中数字是否被使用
        boolean[] used = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        backtrack(nums, used, path, res);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        // 当path中元素个数等于nums数组的长度时，说明已构造出一个排列
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 遍历数组中的每个数字
        for (int i = 0; i < nums.length; i++) {
            // 如果该数字已经在当前排列中使用过，则跳过
            if (used[i]) {
                continue;
            }
            // 选择数字nums[i]
            used[i] = true;
            path.add(nums[i]);
            // 递归构造剩余的排列
            backtrack(nums, used, path, res);
            // 回溯：撤销选择，尝试其他数字
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

大小根堆

题目描述：给定一个整数数组 nums 和一个整数 k，返回出现频率最高的前 k 个元素，返回顺序可以任意。

解法一：大根堆（最大堆）

思路：

1. 使用 HashMap 统计每个元素的出现频率。
2. 构建一个大根堆（PriorityQueue + 自定义比较器），根据频率降序排列。
3. 将所有元素加入堆中，弹出前 k 个元素即为答案。

适合场景：

• 实现简单，适用于对全部元素排序后取前 k 个。
• 时间复杂度：O(n log n)，因为需要将所有 n 个元素都加入堆。

**解法二：小根堆（最小堆）**推荐

思路：

1. 使用 HashMap 统计频率。
2. 构建一个小根堆，堆中仅保存前 k 个高频元素。
3. 遍历每个元素：
   • 如果堆未满，直接加入。
   • 如果当前元素频率大于堆顶（最小频率），则弹出堆顶，加入当前元素。
4. 最终堆中保存的就是前 k 个高频元素。

动态规划

解题步骤：

确定 dp 数组以及下标的含义（很关键！不跑偏）

• 目的：明确 dp 数组中存储的状态或结果。
• 关键：下标往往对应问题中的一个“阶段”或“子问题”，而数组的值则表示这一阶段的最优解或累计结果。
• 示例：在背包问题中，可以设 dp[i] 表示前 i 个物品能够达到的最大价值。

确定递推公式

• 目的：找到状态之间的转移关系，表明如何从已解决的子问题求解更大规模的问题。

• 关键：分析每个状态可能来源于哪些小状态，写出数学或逻辑表达式。

• 示例：对于 0-1 背包问题，递推公式通常为 $$ dp[i]=max⁡(dp[i],dp[i−weight]+value) $$

dp 数组如何初始化

• 目的：给定初始状态，为所有可能情况设置基础值。
• 关键：通常初始化基础的情况（如 dp[0]=0），或者用极大或极小值标示未计算状态。
• 示例：在求最短路径问题中，可以用较大值（如 infinity）初始化所有状态，然后设定起点状态为 0。

确定遍历顺序

• 目的：按照正确的顺序计算每个状态，确保依赖的子问题都已经计算完毕。
• 关键：遍历顺序需要与递推公式保持一致，既可以是正向（从小到大）也可以是反向（从大到小），取决于问题要求。
• 示例：对背包问题，为避免重复计算，每个物品的更新通常采用反向遍历。

举例推导 dp 数组

• 目的：通过一个具体例子来演示递推公式的应用，直观理解每一步计算。
• 关键：选择简单案例，从初始化、更新到最终结果展示整个过程。
• 示例：对一个简单的路径问题，展示如何从起点逐步更新 dp 数组，最后得到终点的最优解。

例题

• 题目： 746. 使用最小花费爬楼梯 (MinCostClimbingStairs)
• 描述：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
• 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
• 请你计算并返回达到楼梯顶部的最低花费。

示例 2： 输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。

• 链接：https://leetcode.cn/problems/min-cost-climbing-stairs/

1.确定dp数组以及下标的含义

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

2.确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3.dp数组如何初始化

看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]、dp[1]推出。

由“你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” =》初始化 dp[0] = 0，dp[1] = 0

4.确定遍历顺序

因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

5.举例推导dp数组

拿示例：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

背包问题

总结：背包问题不仅可以求能装的物品的最大价值，还可以求背包是否可以装满，还可以求组合总和。

背包是否可以装满示例说明

假设背包容量为 10，物品的重量分别为 [3, 4, 7]。我们希望判断是否可以恰好填满容量 10。

其中 dp[j] 表示在容量 j 下，能装入的最大重量（保证不超过 j）。如果dp[10]=10，代表能装满

public boolean canFillBackpack(int[] weights, int capacity) {
        // dp[j] 表示在不超过背包容量 j 的前提下，能装入的最大重量
        int[] dp = new int[capacity + 1];
        // 初始状态: 背包容量为0时，能够装入的重量为0，其他位置初始为0
        
        // 遍历每一个物品（0/1背包，每个物品只能使用一次）
        for (int i = 0; i < weights.length; i++) {
            // 逆序遍历背包容量，防止当前物品被重复使用
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + weights[i]);
            }
        }
        
        // 如果 dp[capacity] 恰好等于 capacity，则说明背包正好被装满
        return dp[capacity] == capacity;
    }

求组合总和

统计数组中有多少种组合（子集）使得其和正好为 P ？

dp[j] 表示从数组中选取若干个数，使得这些数的和正好为 j 的方法数。

状态转移： 对于数组中的每个数字 num，从 dp 数组后向前（逆序）遍历，更新：

dp[j]=dp[j]+dp[j−num]

这里的意思是：

• 如果不选当前数字，方法数保持不变；
• 如果选当前数字，那么原来凑出和 j−num 的方案都可以扩展成凑出和 j 的方案。

初始条件：

• dp[0] = 1，代表凑出和为 0 只有一种方式，即不选任何数字。

代码随想录

完全背包是01背包稍作变化而来，即：完全背包的物品数量是无限的。

0/1背包（一）

描述：有n件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

1.确定dp数组以及下标的含义

因为有两个维度需要分别表示：物品 和 背包容量，所以 dp为二维数组。

即 dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式

考虑 dp[i][j]，有两种情况：

• 不放物品i：背包容量为 j ，里面不放物品 i 的最大价值是 dp[i - 1][j]。
• 放物品i：背包空出物品i的容量后，背包容量为 j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i] 且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组如何初始化

（1）首先从 dp[i][j] 的定义出发，如果背包容量 j 为0的话，即 dp[i][0] ，无论是选取哪些物品，背包价值总和一定为0。

（2）由状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么 i 为0的时候就一定要初始化。

此时就看存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

（3）其他地方初始化为0

4.确定遍历顺序

都可以，但推荐先遍历物品

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

5.举例推导dp数组

略

代码：

 public int knapsack(int[] weight, int[] value, int capacity) {
        int n = weight.length; // 物品的总个数
        
        // 定义二维 dp 数组：
        // dp[i][j] 表示从下标为 [0, i] 的物品中任意选择，放入容量为 j 的背包中，能够获得的最大价值
        int[][] dp = new int[n][capacity + 1];
        
        // 1. 初始化第 0 行：只考虑第 0 个物品的情况
        // 当背包容量 j >= weight[0] 时，可以选择放入第 0 个物品，价值为 value[0]；否则为 0
        for (int j = 0; j <= capacity; j++) {
            if (j >= weight[0]) {
                dp[0][j] = value[0];
            } else {
                dp[0][j] = 0;
            }
        }
        
        // 2. 状态转移：从第 1 个物品开始，逐步填表
        // 遍历物品，物品下标从 1 到 n-1
        for (int i = 1; i < n; i++) {
            // 遍历背包容量，从 0 到 capacity
            for (int j = 0; j <= capacity; j++) {
                // 情况一：不放第 i 个物品，则最大价值不变，继承上一行的值
                dp[i][j] = dp[i - 1][j];
                
                // 情况二：如果当前背包容量 j 大于等于物品 i 的重量，则考虑放入当前物品
                if (j >= weight[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        
        // 返回考虑所有物品，背包容量为 capacity 时的最大价值
        return dp[n - 1][capacity];
    }

0/1背包（二）

可以将二维 dp 优化为一维 dp 的典型条件包括：

1.状态转移只依赖于之前的状态（例如上一行或上一个层次），而不是当前行中动态更新的状态。

• 例如在 0/1 背包问题中，二维 dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j - weight[i]]。

2.存在确定的遍历顺序（例如逆序或正序）能够确保在更新一维 dp 时，所依赖的值不会被当前更新覆盖。

• 逆序遍历：例如 0/1 背包问题，为了防止同一个物品被重复使用，需要对容量 j 从大到小遍历，确保 dp[j - weight] 的值还是上一轮（上一行）的。

• 正序遍历：在一些问题中，如果状态更新不会导致当前状态被重复利用（例如完全背包问题），可以顺序遍历。

3.状态数足够简单，不需要记录多维信息，仅一个维度的状态即可准确表示和转移问题状态。

1.确定 dp 数组以及下标的含义

使用一维 dp 数组 dp[j] 表示「在当前考虑的物品下，背包容量为 j 时能够获得的最大价值」。

2.确定递推公式 当考虑当前物品 i （重量为 weight[i]，价值为 value[i]）时，有两种选择：

• 不选当前物品 i： 此时的最大价值为 dp[j]（即前面的状态没有变化）。
• 选当前物品 i： 当背包容量至少为 weight[i] 时，如果选择物品 i ，剩余容量变为 j - weight[i]，则最大价值为 dp[j - weight[i]] 加上 value[i]。

因此，状态转移方程为：

dp[0] = 0，表示当背包容量为 0 时，能获得的最大价值自然为 0。

对于其他容量 dp[j] ，初始值也设为 0，dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。确保值不被初始值覆盖即可。

4.一维dp数组遍历顺序

外层遍历物品： 从第一个物品到最后一个物品，依次做决策。

内层遍历背包容量（逆序遍历）： 遍历容量从 capacity 到当前物品的重量，进行状态更新。

• 逆序遍历的目的在于确保当前物品在更新过程中只会被使用一次，因为 dp[j - weight[i]] 代表的是上一轮（当前物品未使用前）的状态，不会被当前物品更新后的状态覆盖。

假设物品 $w=2$, $v=3$，背包容量 $C=5$。

错误的正序遍历（$j=2 \to 5$）

1. $j=2$:
   $dp[2] = \max(0, dp[0]+3) = 3$
   $\Rightarrow dp = [0, 0, 3, 0, 0, 0]$
2. $j=4$:
   $dp[4] = \max(0, dp[2]+3) = 6$
   $\Rightarrow$ 错误：物品被重复使用两次！

5.举例推导dp数组

略

代码：

public int knapsack(int[] weight, int[] value, int capacity) {
        int n = weight.length;
        // 定义 dp 数组，dp[j] 表示背包容量为 j 时的最大价值
        int[] dp = new int[capacity + 1];

        // 初始化：所有 dp[j] 初始为0，dp[0] = 0（无须显式赋值）

        // 外层：遍历每一个物品
        for (int i = 0; i < n; i++) {
            // 内层：逆序遍历背包容量，保证每个物品只被选择一次
            for (int j = capacity; j >= weight[i]; j--) {
                // 更新状态：选择不放入或者放入当前物品后的最大价值
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        
        // 返回背包总容量为 capacity 时获得的最大价值
        return dp[capacity];
    }

完全背包(一)

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

例：背包最大重量为4，物品为：

1. 确定dp数组以及下标的含义

dp[i][j] 表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

2. 确定递推公式

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

01背包中是 dp[i - 1][j - weight[i]] + value[i])

因为在完全背包中，物品是可以放无限个，所以 即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放 物品0 和 物品1 的最大价值即： dp[1][1]， 而不是 dp[0][1]。而0/1背包中，既然空出物品1，那背包中也不会再有物品1，即dp[0][1]。

for (int i = 1; i < n; i++) {
    for (int j = 0; j <= capacity; j++) {
        // 不选物品 i，价值不变
        dp[i][j] = dp[i - 1][j];
        // 如果当前背包容量 j 能放下物品 i，则考虑选取物品 i（完全背包内层循环正序或逆序都可以，但这里通常建议正序）
        if (j >= weight[i]) {
            // 注意：这里选取物品 i 后仍然可以继续选取物品 i，
            // 所以状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
            dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i]);
        }
    }
}

3. dp数组如何初始化

• 如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
• 由递推公式，有一个方向 i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。即：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

for (int j = 0; j <= capacity; j++) {
    // 当 j 小于第 0 个物品重量时，无法选取，所以价值为 0
    if (j < weight[0]) {
        dp[0][j] = 0;
    } else {
        // 完全背包允许多次使用物品 0，所以递归地累加
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }
}

4. 确定遍历顺序

先物品或先背包容量都可，但推荐先物品。

完全背包（二）

压缩成一维dp数组，也就是将上一层拷贝到当前层。

将上一层dp[i-1] 的那一层拷贝到 当前层 dp[i] ，那么递推公式由 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) 变成： dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

压缩成一维，即dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

• 根据题型选择先遍历物品或者背包， 如果求组合数就是外层for循环遍历物品，内层for遍历背包。 如果求排列数就是外层for遍历背包，内层for循环遍历物品。 组合数（顺序不同的序列视为相同）排列数（顺序不同的序列视为不同）排列数大于等于组合数！！！。
• 内层循环正序，不要逆序！因为要利用已经更新的dp数组，允许同一物品重复使用！

注意，完全背包和0/1背包的一维dp形式的递推公式一样，但是遍历顺序不同！！

public int completeKnapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    // dp[j] 表示容量为 j 时的最大价值，初始化为 0
    int[] dp = new int[capacity + 1];

    // 遍历每件物品
    for (int i = 0; i < n; i++) {
        // 完全背包：正序遍历容量
        for (int j = weight[i]; j <= capacity; j++) {
            // 如果拿 i 号物品，更新 dp[j]
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

多重背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

把每种物品按数量展开，就转化为0/1背包问题了！相当于物品0-a 物品0-b 物品1-a ....，每个只能用一次。

public int multipleKnapsack(int V, int[] weight, int[] value, int[] count) {
    // 将每件物品按数量展开成 0/1 背包的多个物品
    List<Integer> wList = new ArrayList<>();
    List<Integer> vList = new ArrayList<>();
    for (int i = 0; i < weight.length; i++) {
        for (int k = 0; k < count[i]; k++) {
            wList.add(weight[i]);
            vList.add(value[i]);
        }
    }
    // 0/1 背包 DP
    int[] dp = new int[V + 1];
    int N = wList.size();
    for (int i = 0; i < N; i++) {
        int wi = wList.get(i);
        int vi = vList.get(i);
        for (int j = V; j >= wi; j--) {
            dp[j] = Math.max(dp[j], dp[j - wi] + vi);
        }
    }
    return dp[V];
}

并查集

for (int i = 0; i < 26; i++) {
            parent[i] = i;   //初始化
}

public void union(int[] parent, int index1, int index2) {
    // 先分别找到 index1 和 index2 的根节点，再把 root(index1) 的父指针指向 root(index2)
    parent[find(parent, index1)] = find(parent, index2);
}
//查找 index 元素所在集合的根节点（同时做路径压缩）
public int find(int[] parent, int index) {
    // 当 parent[index] == index 时，说明已经是根节点
    while (parent[index] != index) {
        // 路径压缩：将当前节点直接挂到它父节点的父节点上
        // 这样可以让树变得更扁平，后续查找更快
        parent[index] = parent[parent[index]];
        // 跳到上一级，继续判断是否到根
        index = parent[index];
    }
    // 循环结束时，index 即为根节点下标
    return index;
}

快速幂

LeetCode 50. Pow(x, n) 实现函数 pow(x, n)，即计算 x 的 n 次幂（x^n）。

• 输入：x = 2.00000, n = 10
• 输出：1024.00000

快速幂思想

核心思想： 快速幂就是把指数写成二进制，每一位对应一个“平方后的 x”，如果那一位是 1，就把它乘进结果里。

例子：

n = 13 (二进制 1101)
13 = 8 + 4 + 1
x^13 = x^(8+4+1) = x^8 * x^4 * x^1

也就是说：

• 我们只需要把 x 不断平方，得到 x^1, x^2, x^4, x^8 ...
• 然后根据 n 的二进制位是否为 1，决定是否把这个幂次乘到答案里。

算法步骤

1. 如果 n < 0，转换为 x = 1/x, n = -n。 （注意：n 可能是 Integer.MIN_VALUE，取负数会溢出，所以要先转成 long。）
2. 初始化结果 ans = 1.0。
3. 循环处理指数的每一位：
   • 如果最低位是 1，就把当前的 x 累乘进结果。
   • 每次循环后，x 自身平方，指数右移一位。
4. 循环结束，返回结果。

JAVA实现

public class MyPow {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        if (n == 0) return 1;

        // 处理负指数，注意转为 long 防止溢出
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double ans = 1.0;
        while (N > 0) {
            if ((N & 1) == 1) {  // 判断最低位是否为 1
                ans *= x;
            }
            x *= x;   // 翻倍：x, x^2, x^4, x^8 ...
            N >>= 1;  // 右移一位，处理下一位
        }
        return ans;
    }
}

ACM风格输入输出

**
 * 题目描述
 *
 * 给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
 *
 * 输入描述
 *
 * 第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
 * 输入示例：
 * 5
 * 1
 * 2
 * 3
 * 4
 * 5
 * 0 1
 * 1 3
 *输出：
 * 3
 * 9
 * 输出每个指定区间内元素的总和。
 */

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 快速 IO
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String line;
        
        // 1）读数组长度
        line = br.readLine();
        if (line == null) return;
        int n = Integer.parseInt(line.trim());
        
        // 2）读数组元素并构造前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            line = br.readLine();
            if (line == null) throw new IOException("Unexpected EOF when reading array");
            prefix[i + 1] = prefix[i] + Long.parseLong(line.trim());
        }
        
        // 3）依次读查询直到 EOF
        //    每行两个整数 a, b (0 ≤ a ≤ b < n)
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            StringTokenizer st = new StringTokenizer(line);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // 区间和 = prefix[b+1] - prefix[a]
            long sum = prefix[b + 1] - prefix[a];
            out.println(sum);
        }
        
        out.flush();
    }
}

line.trim() 是把原 line 首尾的所有空白字符（空格、制表符、换行符等）都去掉之后的结果。

StringTokenizer st = new StringTokenizer(line);把一整行字符串 line 按默认的分隔符（空格、制表符、换行符等）拆成一个一个的“词”（token）

StringTokenizer st = new StringTokenizer(line, ",;"); 第二个参数 ",;" 中的每个字符都会被当作分隔符；如果想把空白也当分隔符，可以在里边加上空格 " ,; "

Scanner版本：简单，但效率低。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 把分隔符改成 “逗号 或 空白” 默认只能按空格分隔！！！
        sc.useDelimiter("[,\\s]+");

        // 1）读数组长度
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();

        // 2）读数组元素并构造前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + sc.nextLong();
        }

        // 3）依次读查询直到 EOF
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            long sum = prefix[b + 1] - prefix[a];
            System.out.println(sum);
        }
    }
}

Scanner 是 按空白分隔符（空格、换行、制表符）来划分输入的。

也就是说，sc.nextInt() 会忽略一切空白，把下一个整数读出来，不管它是在同一行还是下一行。

sc.useDelimiter("[,\\s]+");

这里的 [,] 就表示：分隔符可以是 , 这个字符。

[,\\s] 外面的 + 表示匹配“一个或多个” ，即有连续的空格、逗号它也能匹配。

Scanner 读取字符串

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 用 next() 读
        System.out.print("请输入两个单词（中间空格分隔）: ");
        String word1 = sc.next();   // 读第一个单词
        String word2 = sc.next();   // 读第二个单词
        System.out.println("next() 得到: " + word1 + " 和 " + word2);

        sc.nextLine(); // 把上一次输入残余的换行符吃掉

        // 用 nextLine() 读
        System.out.print("请输入一整行文本: ");
        String line = sc.nextLine();  // 读整行
        System.out.println("nextLine() 得到: " + line);
    }
}
//输入
//hello world
//I love Java programming

//输出：
//请输入两个单词（中间空格分隔）: next() 得到: hello 和 world
//请输入一整行文本: nextLine() 得到: I love Java programming

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.useDelimiter("[,\\s]+");   // 逗号或空白分隔

        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();

        long[] arr = readArray(sc, n);        // 只读输入
        PrefixSum ps = new PrefixSum(arr);     // 核心逻辑

        StringBuilder out = new StringBuilder();
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            out.append(ps.query(a, b)).append('\n');   // 调用核心
        }
        System.out.print(out.toString());
    }

    // === IO 辅助：读取 n 个 long ===
    private static long[] readArray(Scanner sc, int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        return a;
    }

    // === 核心：前缀和与区间查询（不涉及 IO）===
    static final class PrefixSum {
        private final long[] pref; // pref[i] = a[0..i-1] 之和

        PrefixSum(long[] a) {
            pref = new long[a.length + 1];
            for (int i = 0; i < a.length; i++) pref[i + 1] = pref[i] + a[i];
        }

        /** 查询闭区间 [l, r] 的和 */
        long query(int l, int r) {
            if (l < 0 || r >= pref.length - 1 || l > r) {
                throw new IllegalArgumentException("Invalid range: [" + l + ", " + r + "]");
            }
            return pref[r + 1] - pref[l];
        }
    }
}