算法题

整数反转

【中等】
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0
假设环境不允许存储 64 位整数（有符号或无符号）

示例 1：
输入：x = 123
输出：321

示例 2：
输入：x = -123
输出：-321

示例 3：
输入：x = 120
输出：21

示例 4：
输入：x = 0
输出：0

提示：-2^31 <= x <= 2^31 - 1

思路

通过取余和除法逐步提取原数的末位，构建反转后的数，同时在构建过程中判断是否溢出。

1. 初始化反转结果：用 res = 0 存储反转后的数。

2. 循环提取末位：

   • 每次取 x 的末位：digit = x % 10（注意负数取余的结果仍是负数，符合预期）。
   • 去除 x 的末位：x = x // 10（Python 中需用 x = int(x / 10) 处理负数，避免向下取整问题）。
   • 更新反转结果：res = res * 10 + digit。

3. 溢出判断：

   • 32 位有符号整数的范围是 [-2^31, 2^31 - 1]，即 [-2147483648, 2147483647]。

   • 在更新 res 前，需判断是否即将溢出：

     • 若 res > 214748364 或 (res == 214748364 and digit > 7)，则正数溢出。
     • 若 res < -214748364 或 (res == -214748364 and digit < -8)，则负数溢出。

   • 若溢出，直接返回 0。

代码实现

def reverse(x: int) -> int:
    INT_MAX = 2147483647  # 2^31 - 1
    INT_MIN = -2147483648  # -2^31
    res = 0
    while x != 0:
        # 取末位数字（处理负数时，Python的%会返回负数，符合预期）
        digit = x % 10
        # 去除末位（用int(x/10)避免负数除法的向下取整问题）
        x = int(x / 10)

        # 判断溢出
        if res > INT_MAX // 10 or (res == INT_MAX // 10 and digit > 7):
            return 0
        if res < INT_MIN // 10 or (res == INT_MIN // 10 and digit < -8):
            return 0

        # 更新反转结果
        res = res * 10 + digit
    return res

关键说明

• 负数处理：通过 x % 10 取末位时，负数的余数仍是负数（例如 -123 % 10 = -3），无需额外判断符号。
• 溢出判断时机：必须在更新 res 之前判断，否则一旦 res 已经溢出，后续计算会出错。
• 边界值处理：2147483647 的末位是 7，-2147483648 的末位是 -8，因此当 res 等于边界的前 9 位时，需单独判断末位是否超限。

该方法的时间复杂度为 O(log|x|)（x 的位数），空间复杂度为 O(1)，高效且符合题目要求。

---

搜索二维矩阵

【中等】
给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false

示例：

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
]
target = 3 → 存在（返回 true）；target = 13 → 不存在（返回 false）

问题说明

• 矩阵 matrix 每行元素从左到右递增。
• 每行的第一个元素大于上一行的最后一个元素（即矩阵按行拼接后是一个严格递增的一维数组）。
• 目标：判断目标值 target 是否存在于矩阵中。

思路

利用矩阵的 “整体有序性”，将二维矩阵视为一维有序数组，直接使用二分查找：

1. 映射二维索引到一维索引：设矩阵行数为 m，列数为 n，则总元素数为 m*n。对于一维索引 k，对应的二维坐标为：

   • 行索引：row = k // n
   • 列索引：col = k % n

2. 二分查找步骤：

   • 初始化左右指针 left = 0，right = m*n - 1。

   • 循环条件：left <= right，计算中间索引 mid，并映射为二维坐标 (row, col)。

   • 比较 matrix[row][col] 与 target：

     • 若相等，返回 true；
     • 若 matrix[row][col] < target，则目标在右侧，left = mid + 1；
     • 若 matrix[row][col] > target，则目标在左侧，right = mid - 1。

   • 循环结束后仍未找到，返回 false。

代码实现

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    m = len(matrix)
    if m == 0:
        return False
    n = len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = (left + right) // 2
        row = mid // n
        col = mid % n
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

复杂度分析：

• 时间复杂度：O(log(m*n))，等价于一维数组的二分查找。
• 空间复杂度：O(1)，仅用常数空间。

---

滑动窗口

题目

1. 输入: "abcabcbb"
   • 输出: 3
   • 最大无重复子串是 "abc"，长度是 3。
2. 输入: "bbbbb"
   • 输出: 1
   • 最大无重复子串是 "b"，长度是 1。
3. 输入: "pwwkew"
   • 输出: 3
   • 最大无重复子串是 "wke"，长度是 3。

代码实现

var lengthOfLongestSubstring = function (s) {
  let seen = new Set(); // 用来存储当前窗口内的字符
  let left = 0; // 左指针
  let maxLen = 0; // 最大长度

  for (let right = 0; right < s.length; right++) {
    // 当右指针指向的字符在窗口内已经存在时，移动左指针
    while (seen.has(s[right])) {
      seen.delete(s[left]); // 移除左指针指向的字符
      left++; // 左指针向右移动
    }

    // 将当前字符加入到窗口中
    seen.add(s[right]);

    // 更新最大长度
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
};

解释

1. 滑动窗口：使用 left 和 right 两个指针表示当前无重复字符的子串的边界。right 用来扩展窗口，left 用来收缩窗口，确保窗口内没有重复字符。
2. 哈希集合 ​seen​：用来记录当前窗口内的字符。当右指针遇到重复字符时，通过移动左指针将重复字符移出窗口。
3. 最大长度：每次右指针移动时，更新当前窗口的长度，计算最大长度。

时间复杂度是 O(n)，其中 n 是字符串的长度。每个字符至多被 left 和 right 指针遍历一次。
空间复杂度是 O(min(n, m))，其中 n 是字符串的长度，m 是字符集大小。我们使用了一个哈希集合来存储当前窗口中的字符。

这个问题的解法使用了 滑动窗口 的技巧，结合一个 哈希集合 来解决。让我一步步为你详细解释。

我们要找到字符串中 最长的无重复字符的子串。其中，子串是一个连续的部分，不能跳过字符。

滑动窗口技术

滑动窗口的思想就是通过两个指针来维护一个动态的窗口（即一个子串），这个窗口内的字符满足题目要求。你可以把这个窗口想象成一个区间，左指针表示区间的开始，右指针表示区间的结束。

代码逻辑

1. 初始化：

let seen = new Set(); // 哈希集合，记录当前窗口内的字符
let left = 0; // 左指针，初始化为0
let maxLen = 0; // 存储最长子串的长度，初始化为0

• seen: 用于存储当前窗口内的字符，确保窗口内没有重复字符。
• left: 左指针，指向当前窗口的左边界。最开始是指向字符串的开头。
• maxLen: 存储遇到的最大无重复子串的长度。

2. 右指针遍历：

for (let right = 0; right < s.length; right++) {

我们从字符串的左边开始，右指针 right 每次向右移动一个位置。每次右指针移动时，我们都会更新窗口中的内容。

3. 遇到重复字符时，移动左指针：

while (seen.has(s[right])) {
  seen.delete(s[left]); // 移除左指针指向的字符
  left++; // 左指针右移
}

• 当右指针遇到一个重复字符（即字符 s[right] 已经在窗口内出现过），我们需要确保窗口内没有重复字符。
• 我们通过移动左指针来解决这个问题。left 会右移，直到窗口内不再有重复字符。
• seen.delete(s[left]): 移除 left 指针当前指向的字符，并将左指针向右移动一位。

4. 将当前字符加入窗口：

seen.add(s[right]); // 将右指针指向的字符加入窗口

右指针指向的字符 s[right] 加入到 seen 中，表示它现在在当前窗口内。

5. 更新最大长度：

maxLen = Math.max(maxLen, right - left + 1);

• 每次右指针向右移动后，我们计算当前窗口的长度 right - left + 1。
• 如果当前窗口的长度比 maxLen 大，就更新 maxLen。

6. 返回最大长度：

return maxLen;

最终返回记录的最大长度 maxLen，即为字符串中最长的无重复字符的子串的长度。

举个例子

假设输入字符串是 "abcabcbb"

初始时，seen 是一个空集合，left = 0，maxLen = 0。

第一步：
right = 0，字符是 'a'，seen 加入 'a'。窗口是 "a"，长度是 1，更新 maxLen = 1。

第二步：

right = 1，字符是 'b'，seen 加入 'b'。窗口是 "ab"，长度是 2，更新 maxLen = 2。

第三步：

right = 2，字符是 'c'，seen 加入 'c'。窗口是 "abc"，长度是 3，更新 maxLen = 3。

第四步：

right = 3，字符是 'a'，发现 'a' 已经在窗口中。此时，左指针 left 向右移动，直到窗口没有 'a' 为止。seen 移除 'a' 和 'b'，left 变为 1，窗口变为 "bca"。

继续循环：

右指针继续移动，直到字符串结束，最终 maxLen 变为 3，即最长无重复字符的子串是 "abc"。

总结：

这个算法通过维护一个滑动窗口，动态地更新窗口的范围，确保每个时刻窗口内没有重复字符。每当右指针扩展时，检查并调整窗口，最终得出最长的无重复字符子串的长度。

---

红黑树

红黑树，说白了就是一种“自带平衡功能”的二叉搜索树。它为了避免树太“歪”（比如一边特别深），自己加了一套“红黑”规则来控制每次插入或删除后的“形状”。

是什么？

一、红黑树是啥？

就是一个特别版本的二叉搜索树（BST） ，但它有额外的“红黑规则”来保证树的高度不会太高，让查找变快。

二、为啥需要红黑树？

普通的二叉搜索树，最差情况下可能会长成一个“链表”，查询效率就变成 O(n)了，非常慢。

红黑树通过自己的“规则”，强制树保持一个大致平衡的形状，查询/插入/删除的效率稳定在 O(log n)。

三、它是怎么做到“平衡”的？

红黑树给每个节点染色，只有两种颜色：红色 或 黑色，然后制定了几个规则。

四、红黑树的五大规则：

1. 每个节点，不是红就是黑。

   • 就像每个人穿红衣服或黑衣服，没别的颜色。

2. 根节点必须是黑色的。

   • 头头必须穿黑衣服。

3. 红色节点不能连续，不能有两个红色连在一起（红的不能有红的孩子） 。

   • 红色的人不能带红色小弟，太乱了。

4. 每条从根到叶子的路径，经过的“黑色节点数量”必须一样。

   • 意思是，不管从哪里走到底，每条路上穿黑衣服的人数一样多，这样树才不会太歪。

5. 新插入的节点默认是红色。

   • 新人先穿红衣服，看能不能融入大队伍（可能会被“教育一下”，变颜色或者换位置）。

五、插入和删除的时候会做啥？

插入或删除节点时，如果破坏了上面这些规则，红黑树会自动“修整”自己：

• 变颜色（染色）
• 旋转节点（左旋、右旋）
  👉 有点像跳舞时换位置，保持队形整齐

这些操作是为了让树继续保持“平衡”，避免变成一边高一边低。

六、红黑树的好处：

• 插入、删除、查找：都能保证最坏情况是 O(log n)

• 非常适合做需要频繁插入删除查找的结构，比如：

  • Java 的 TreeMap / TreeSet
  • Linux 的进程调度红黑树

最后用个比喻总结：红黑树就像一个军队列队

• 每个士兵（节点）穿红衣或黑衣；
• 队长（根节点）穿黑衣；
• 红衣士兵不能带红衣小弟；
• 每条从队长到最末尾的路上，黑衣士兵数量要一样；
• 有新兵入队，就调整颜色、调整位置，保持队伍整齐、平衡有序。

应用

红黑树的最大优势是：在频繁插入、删除、查找数据时，能保证效率稳定在 O(log n) 。所以它常用于需要有序、快速查找+频繁修改的场景。

1. Java 的 TreeMap 和 TreeSet

• TreeMap：基于红黑树实现的有序键值对映射表（像 HashMap 但有顺序）。
• TreeSet：基于红黑树实现的有序不重复集合。

👉 实际用途：需要对键或值保持自动排序，比如排名榜、定时任务调度、日历事件排序等。

e.g. Java 的 TreeMap / TreeSet

示例一：TreeMap —— 自动按 key 排序的映射表（键值对）

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> scores = new TreeMap<>();

        scores.put(85, "Alice");
        scores.put(92, "Bob");
        scores.put(78, "Charlie");

        // 自动按 key（分数）升序排列
        for (Integer score : scores.keySet()) {
            System.out.println(score + " -> " + scores.get(score));
        }
    }
}

输出：

78 -> Charlie
85 -> Alice
92 -> Bob

✅ 特点：不用你手动排序，TreeMap 会自动根据 key 排序（这里是从小到大），因为底层是红黑树维护顺序。

示例二：TreeSet —— 自动排序的不重复集合

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> fruits = new TreeSet<>();

        fruits.add("Banana");
        fruits.add("Apple");
        fruits.add("Orange");

        // 自动按字典序排序（String默认比较规则）
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
}

输出：

Apple
Banana
Orange

✅ 特点：元素不会重复，而且自动按照自然顺序（字典序）排好，不需要你写排序逻辑。

小对比：

特性	TreeMap	TreeSet
类型	键值对 Map	单一元素 Set
自动排序依据	按 key 排序	按元素排序
可自定义排序	可以传入 Comparator	也可以传 Comparator
底层实现	红黑树	红黑树

• TreeMap: 排行榜、时间戳排序、按照 ID 查找某个对象等；
• TreeSet: 排序不重复名单、排行榜去重、查找最近元素（支持 higher/lower/floor/ceiling 方法）等。

2. C++ STL 的 map、set、multimap、multiset

• 这些容器背后通常用红黑树（或类似结构）实现，支持快速的：

  • 插入
  • 删除
  • 查找
  • 有序遍历

👉 实际用途：开发中广泛使用，比如做排行榜、缓存机制、有序索引等。

3. Linux 内核的调度器/内存管理器

Linux 内核中用红黑树实现了：

• 进程调度（CFS 调度器） ：用红黑树快速选出哪个进程该运行。
• 内存区域管理（虚拟内存 VMAs） ：用红黑树管理每个进程的内存块。

👉 这是对效率要求非常高的场景，红黑树提供了稳定的性能。

4. 数据库的索引结构（部分场景）

虽然数据库索引多数用 B+树，但**内存中的临时数据结构（比如缓存区、查询优化器的中间结果）**有时会用红黑树来维护有序数据。

5. 操作系统和编译器的符号表 / 调试信息

• 在编译器中，维护符号表（比如变量名和内存地址的映射）经常使用红黑树。
• 调试工具里管理断点、变量信息等，也可能使用红黑树做快速有序查找。

6. 网络路由表 / 防火墙规则表

• 这些规则表通常需要快速查找、插入、删除，同时保持顺序（如 IP 范围的顺序）。
• 红黑树适合做这类规则匹配、查找。

小结：何时选择红黑树？

场景特点	是否适合红黑树
需要按顺序存储并快速查找	✅ 非常适合
需要频繁插入/删除	✅ 保证稳定性能
只关心快速查找（不关心顺序）	❌ 用哈希表更快
超大规模数据，磁盘上的结构	❌ 用 B+树更合适（IO 优化）

---

HashMap

HashMap 就是一个“键值对”的集合。你可以把它想象成一个抽屉柜子，每个抽屉都有一个编号（key），里面放着具体的东西（value）。

• key（键） ：抽屉的标签
• value（值） ：抽屉里装的东西

举个例子：

HashMap<String, String> map = new HashMap<>();
map.put("中国", "北京");
map.put("日本", "东京");
map.put("美国", "华盛顿");

现在 map 就像这样：

key	value
中国	北京
日本	东京
美国	华盛顿

🧠 为什么叫“Hash”Map？

“Hash”是“哈希算法”的意思，也叫“散列”。意思是：

它用某种公式把 key（比如字符串）转换成一个数字，然后用这个数字来决定这个键值对在内存中的位置。

这样查找速度非常快，几乎是秒查（平均是 O(1) 的时间复杂度）。

常用操作

操作	大白话解释	Java 示例
put(k, v)	把 v 放进 k 这个抽屉里	map.put("苹果", "红色")
get(k)	打开 k 这个抽屉，看里面有什么	map.get("苹果")返回"红色"
remove(k)	把 k 这个抽屉连东西带标签一块儿扔掉	map.remove("苹果")
containsKey(k)	看有没有叫 k 的抽屉	map.containsKey("苹果")
size()	有几个抽屉	map.size()

底层原理是什么？

HashMap 是 Java 和很多其他语言中常见的数据结构，用于存储键值对（key-value pair）。它的底层原理结合了数组 + 链表 + 红黑树的思想，实现了高效的插入、查找和删除操作。

简单说法（大白话）：你可以把 HashMap 想成是一个“抽屉柜”（数组），每个“抽屉”用来放一堆钥匙和它们对应的值。

• 每把钥匙（key）都被加工处理（通过 hash 函数）变成一个数字，这个数字决定了钥匙应该放到哪个抽屉。
• 如果两个钥匙“太像了”，被分到了同一个抽屉，就会把它们串成一串（链表）或排序（红黑树）。
• 查找的时候，就是先找到抽屉，再在抽屉里翻一翻就行了。

详细原理：

1. 哈希函数（hash function）

• HashMap 使用 key.hashCode() 计算哈希值。
• 这个哈希值会被进一步“扰动”（hash spreading）然后对数组长度取模，定位到数组的某个槽位（bucket）。

int hash = hash(key.hashCode());
int index = hash % table.length;

2. 数组（table）

• 底层维护一个 Node[] 数组（Node 是内部类，包含 key, value, hash, next）。
• 每个 table[i] 是一个 bucket（桶），最开始为空。

3. 哈希冲突（Hash Collision）

• 不同的 key 有可能落在同一个 bucket（抽屉），就发生冲突。
• Java 8 之前：冲突的元素用 链表 连接起来。
• Java 8 之后：当冲突数量大于一定阈值（默认为 8），并且数组长度大于 64 时，链表转为 红黑树，提高查找效率。

4. 扩容机制（Resize）

• 默认容量是 16，负载因子是 0.75。

• 当当前元素数量 > 负载因子 × 容量，就会触发扩容。

  • 扩容时，容量变为原来的 2 倍。
  • 所有元素重新 hash 分配（可能会迁移到不同的桶中）。

5. 时间复杂度

操作	最佳情况	最坏情况
插入/查找	O(1)	O(logN)（树）或 O(N)（链表）
删除	O(1)	O(logN)或 O(N)

e.g.

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);

• "apple".hashCode() 经过计算后落到数组第 3 个位置，存入 bucket[3]。
• 如果 "banana" 的哈希值也落在 bucket[3]，就加在链表后面（或红黑树中）。

总结：

组件	作用
哈希函数	决定 key 应该放在数组的哪个位置
数组	存储数据的主要结构，按索引访问
链表/红黑树	处理哈希冲突，提高性能
扩容机制	保证性能的稳定，避免过多冲突

HashMap 的优缺点

HashMap 就是一个查得快的键值对存储器，通过哈希算法让你可以“秒查”东西，但它的顺序是乱的，多线程时要小心。

✅ 优点：

• 查找、插入速度快（平均 O(1)）
• key 可以是任何对象（但要实现 hashCode() 和 equals()）

❌ 缺点：

• 无序（加进去的顺序不一定和取出来的一样）
• 多线程下不安全（需要用 ConcurrentHashMap）

---

对比 HashMap 和 TreeMap

容器	一句话说明
HashMap	查得快，但乱序
TreeMap	自动排序，但查找没那么快

详细对比：

对比点	HashMap	TreeMap
是否有序	❌ 无序，加入顺序不一定能保留	✅ 自动按 key 排序（默认是升序）
查找速度	✅ 非常快，平均 O(1)	❌ 较慢，O(log n) （因为是树结构）
底层结构	哈希表（数组 + 链表 + 红黑树）	红黑树（平衡二叉排序树）
key 需要实现接口	hashCode()和equals()	Comparable接口，或提供Comparator
是否允许 null key	✅ 允许一个 null key	❌ 不允许 null key（会抛异常）
应用场景	查得快但不在乎顺序	需要对 key 排序或做范围查询

e.g.

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("banana", 3);
hashMap.put("apple", 5);
hashMap.put("pear", 2);
System.out.println(hashMap);
// 输出顺序可能是乱的，例如：{pear=2, banana=3, apple=5}

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 3);
treeMap.put("apple", 5);
treeMap.put("pear", 2);
System.out.println(treeMap);
// 输出是排序的：{apple=5, banana=3, pear=2}

什么时候用谁？

需求	用哪个？
要求快，不在乎顺序	用HashMap
要按 key 排序（如字母序）	用TreeMap
需要范围操作（比如找大于某个 key 的所有数据）	用TreeMap

小结：

特点	HashMap	TreeMap
是否有序	❌ 无序	✅ 有序
查找速度	✅ 快（O(1)）	❌ 稍慢（O(log n)）
底层结构	哈希表	红黑树
null key 支持	✅ 支持	❌ 不支持

---

链表与数组的优缺点

数组（Array）

优点

1. 支持随机访问，访问速度快

   • 可以通过索引直接访问任意元素，时间复杂度是 $O(1)$。

   arr[5]; // 直接访问第6个元素

2. 空间利用率高，缓存友好

   • 数组在内存中是连续存储的，CPU 缓存命中率高，访问速度快。

缺点

1. 插入/删除效率低（特别是中间位置）

   • 插入/删除操作需要移动大量元素，时间复杂度是 $O(n)$。

   // 插入一个元素到第3位，后面的元素要整体后移

2. 扩容代价高

   • 如果数组大小固定，空间不足时需要申请新内存并复制所有元素。

3. 大小固定（静态数组）

   • 一般需要提前指定数组大小，使用不灵活（虽然动态数组如 std::vector、ArrayList 解决了部分问题）。

链表（Linked List）

链表就像是一串手拉手的人:

• 每个人（节点）手里有两个东西：

  1. 自己的号码（数据/值）
  2. 下一个人的地址（指针）

举个例子：
假设我们有 3 个节点，分别装着数字 10、20、30，像这样拉着手：

[10] → [20] → [30] → null

最后一个人（30）没有人可以再拉了，所以他的“手”是空的（null）。

链表的种类

1. 单向链表：一个人只拉下一个人
   [A] → [B] → [C]
2. 双向链表：两只手，能往前也能往后拉
   [A] ⇄ [B] ⇄ [C]
3. 循环链表：最后一个又拉回第一个，像围成一个圈
   [A] → [B] → [C] → [A] → ...

优点

1. 插入和删除操作效率高

   • 在已知节点位置时，插入/删除的时间复杂度是 $O(1)$，不需要移动元素。

   node->next = newNode; // 插入只需修改指针

2. 动态分配，大小灵活

   • 不需要提前分配固定大小，可以根据需要动态增长或缩小。

缺点

1. 不支持随机访问

   • 访问某个元素必须从头开始遍历，时间复杂度是 $O(n)$。

2. 额外空间开销

   • 每个节点都需要额外存储一个指针，空间利用率比数组低。

3. 缓存不友好

   • 链表节点在内存中不连续，可能导致较多的缓存未命中，访问效率较低。

对比

特性	数组（Array）	链表（Linked List）
内存布局	连续	分散
随机访问	✅ 快 ($O(1)$)	❌ 慢 ($O(n)$)
插入/删除	❌ 慢 ($O(n)$)	✅ 快 ($O(1)$, 若已定位)
空间利用率	✅ 高	❌ 低（需存指针）
动态扩展	❌ 麻烦（需复制）	✅ 灵活
缓存友好	✅ 是	❌ 否

如果你在设计程序数据结构，不确定该选哪一个，可以根据以下建议：

• 频繁插入/删除，尤其是中间位置 → 用链表
• 需要快速随机访问，数据量固定或变化不大 → 用数组
• 需要缓存性能、空间效率优先 → 用数组
• 空间不是问题，且结构变化频繁 → 用链表

总结

• 如果你要频繁地查找第几个元素 ➜ 用数组
• 如果你要频繁地插入/删除 ➜ 用链表

✅ 数组：查找快，插删慢，固定大小，内存连续
✅ 链表：查找慢，插删快，动态扩展，内存分散

---

回文数

回文数就是正着读和反着读都一样的数字

数字	正着读	反着读	是不是回文数？
121	121	121	✅ 是
12321	12321	12321	✅ 是
123	123	321	❌ 不是
10	10	01	❌ 不是
0	0	0	✅ 是

你就把数字当成一个字符串看，比如 12321，从前往后读是“12321”，从后往前读也是“12321”，没变——那它就是个回文数。

拓展一下：

• 负数比如 -121 不是回文数（因为有负号，反过来是 121-，不一样）。
• 0110 这种看起来对称的数字，写成整数是 110，不是回文数。所以前导零不能有。

代码实现

public boolean isPalindrome(int x) {
    if (x < 0) return false;
    String s = Integer.toString(x);
    String reversed = new StringBuilder(s).reverse().toString();
    return s.equals(reversed);
}

---

最大子数组和（Kadane’s Algorithm）

给你一个整数数组 nums, 请你找出拥有最大和的连续子元素（至少包含一个元素）， 并返回这个最大和

代码实现

function maxSubArray(nums) {
  let maxSoFar = nums[0]; // 当前最大值
  let currentSum = nums[0]; // 当前子数组的和

  for (let i = 1; i < nums.length; i++) {
    // 如果当前值比加上前面的和还大，就从当前值重新开始一段子数组
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    // 更新最大值
    maxSoFar = Math.max(maxSoFar, currentSum);
  }

  return maxSoFar;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 输出 6（子数组为 [4,-1,2,1]）

• 一边遍历数组，一边“积攒”连续的和；
• 如果某一项加上前面的和反而更小了，就“清零重来”，从当前项重新开始累加；
• 过程中记录出现过的最大值

---

flatten 数组

通力电梯要求我用 js 代码写：实现一个 flatten 函数，能够将任意嵌套的数组拍平（扁平化）为一维数组。要求支持指定拍平的深度（默认拍平到最深层）

我通过递归的方式来实现这个 flatten 函数，支持指定拍平的深度。以下是一个示例代码：

function flatten(arr, depth = Infinity) {
  let result = [];

  arr.forEach((item) => {
    if (Array.isArray(item) && depth > 0) {
      // 递归调用，深度减1
      result = result.concat(flatten(item, depth - 1));
    } else {
      result.push(item);
    }
  });

  return result;
}

// 测试示例
const nestedArr = [1, [2, [3, [4, 5]]], 6];
console.log(flatten(nestedArr)); // 完全扁平化，输出 [1, 2, 3, 4, 5, 6]
console.log(flatten(nestedArr, 2)); // 只扁平化 2 层，输出 [1, 2, 3, [4, 5], 6]

代码解释

1. flatten 函数接受两个参数：

   • arr：要扁平化的数组。
   • depth：指定扁平化的深度，默认为 Infinity，表示完全扁平化。

2. 使用 forEach 遍历数组的每个元素。

3. 对于每个元素，如果它是一个数组并且 depth > 0，则递归调用 flatten 函数，深度减 1，扁平化子数组。

4. 如果元素不是数组，直接将其添加到 result 中。

• 如果没有传递 depth，会完全扁平化。
• 如果传递了 depth，只会扁平化到指定深度。

拆解

function flatten(arr, depth = Infinity) {

• 这行代码定义了一个叫 flatten 的函数。
• arr 是你传进来的数组，可能是嵌套的。
• depth 是可选的参数，用来指定拍平的深度，默认是 Infinity（意思是会拍平到最深）。

let result = [];

• 这里我们声明了一个空数组 result，用来存储扁平化后的结果。

arr.forEach(item => {

• 这行代码开始遍历数组 arr 中的每个元素。
• item 就是数组中的每个元素。

if (Array.isArray(item) && depth > 0) {

• 这行代码判断当前的 item 是否是一个数组（Array.isArray(item) 判断是否是数组）。
• 还会检查 depth > 0，也就是如果深度还有剩余，就继续去扁平化。

result = result.concat(flatten(item, depth - 1));

• 如果 item 是数组并且深度没有耗尽，就递归调用 flatten，将当前的 item 继续拍平，并且把深度减一（depth - 1）。
• concat 会把扁平化后的数组拼接到 result 数组的后面。

} else {
  result.push(item);
}

• 如果 item 不是数组，直接把它放到 result 数组里面。

});

• forEach 遍历结束，所有的元素都被处理完了。

return result;

• 最后，返回 result 数组，它就是扁平化后的数组。

const nestedArr = [1, [2, [3, [4, 5]]], 6];
console.log(flatten(nestedArr)); // 输出 [1, 2, 3, 4, 5, 6]

• 这里测试了一个嵌套数组 nestedArr，调用 flatten 函数把它拍平。
• 默认情况下，深度是 Infinity，也就是会把数组扁平化到最深。

console.log(flatten(nestedArr, 2)); // 输出 [1, 2, 3, [4, 5], 6]

• 这个例子是指定了深度为 2，也就是只扁平化两层，第三层的嵌套数组不会被扁平化。

总结来说，代码的核心思路就是遍历数组，判断每个元素是否是数组，若是数组则递归拍平，并且根据传入的深度来控制扁平化的层数。