算法思想

# 算法细节优化

# 二分查找中的mid优化

Binary Searchopen in new window中，对mid的赋值优化，从直观的Math.floor((left + right) / 2)优化为left + Math.floor((right-left)/2)。

在 JavaScript 中直接写 Math.floor((left + right) / 2) 也是完全可行的，因为它不会溢出，结果也正确。

但采用 left + Math.floor((right - left) / 2) 是一个跨语言的安全习惯，可以避免潜在溢出问题，并且让代码更易移植。同时，它明确地表达了从 left 开始，加上区间长度的一半的几何意义，在理解二分查找的缩小区间过程时也很有帮助。

所以，两种写法都可以，但推荐使用前者，尤其是当你在学习算法或参加面试时，这种细节会展现出你对算法实现的深入理解。

# 算法设计

# 原地算法

来自百度百科的解释：在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。

简单来说，就是我在做青椒炒肉，青椒和肉都被我切好了，放在菜板上，然后在同一个锅里炒熟，最后拿出来装盘，这是原地算法；

非原地算法是我把菜板上的肉丝和青椒，端到邻居家厨房，用别人家的菜板和锅，最后把成品端回来。

面试中喜欢考察，是因为在实际应用中内存有限，程序设计者需要有意识节省内存。

旋转图像open in new window的精髓在于设置一个temp变量来辅助交换：

// in-place algorithm
let temp = matrix[i][j]; // 这个 temp 就是“小的，固定数量的额外空间”
matrix[i][j] = matrix[n-1-i][j]; 
matrix[n-1-i][j] = temp; 
// out-place algorithm
let newMatrix = new Array(n).fill(0).map(() => new Array(n)); // 新画一个 n x n 的数组
newMatrix[j][n-1-i] = matrix[i][j]; // 把所有元素放到新数组里
return newMatrix;

# 递归算法

递归关系(recursive relation),数学和计算机科学中，指函数的定义使用函数本身的方法。recursion常用来描述以自相似的方式重复事物的过程。通俗理解我调用我自己。递归模型：斐波那契序列、河内塔。

本博客<<算法题-合并两个升序链表为一个升序链表>>中，要理解 l1.next = mergeTwoLists(l1.next, l2) 这行代码，需要从递归的本质、链表的连接逻辑以及子问题的定义三个维度入手。以下是详细解释：

# 一、递归的核心：分解问题为“当前步骤 + 子问题”

递归算法的本质是将原问题分解为规模更小、结构相同的子问题，并通过“解决子问题 + 处理当前步骤”来得到最终结果。在合并两个升序链表中：

• 原问题：合并链表 l1 和 l2，得到一个新的升序链表。
• 子问题：合并 l1 和 l2 中的“剩余部分”，得到一个升序链表。

关键步骤：

1. 比较当前节点：比较 l1 和 l2 的当前节点值，选择较小的节点作为结果链表的当前节点。
2. 递归处理剩余部分：将选中节点的 next 指针指向“剩余节点的合并结果”（即子问题的解）。

# 二、l1.next = mergeTwoLists(l1.next, l2) 的具体含义

假设当前递归层中：

• l1 指向节点 A（值为 l1.val），l1.next 指向节点 B（值为 l1.next.val）。
• l2 指向节点 X（值为 l2.val）。

当 l1.val < l2.val 时（即节点 A 的值小于节点 X 的值）：

1. 选择当前节点：将节点 A 作为结果链表的当前节点。
2. 递归处理剩余部分：由于节点 A 已被使用，剩余需要合并的是 l1.next（节点 B 及后续）和 l2（节点 X 及后续）。
3. 连接结果：将节点 A 的 next 指针指向“剩余部分的合并结果”，即 l1.next = mergeTwoLists(l1.next, l2)。

# 三、通过具体案例理解递归过程

假设输入链表：

l1: 1 → 3 → 5
l2: 2 → 4 → 6

1. 第一层递归：比较 l1.val(1) 和 l2.val(2)

• 由于 1 < 2，选择 l1（节点 1）作为结果链表的头节点。
• 剩余需要合并的是 l1.next(3→5) 和 l2(2→4→6)。
• 执行 l1.next = mergeTwoLists(l1.next, l2)，即 节点1.next = merge(3→5, 2→4→6)。

2. 第二层递归：比较 l1.next.val(3) 和 l2.val(2)

• 由于 3 > 2，选择 l2（节点 2）作为结果链表的当前节点。
• 剩余需要合并的是 l1.next(3→5) 和 l2.next(4→6)。
• 执行 l2.next = mergeTwoLists(l1.next, l2.next)，即 节点2.next = merge(3→5, 4→6)。

3. 第三层递归：比较 l1.next.val(3) 和 l2.next.val(4)

• 由于 3 < 4，选择 l1.next（节点 3）作为结果链表的当前节点。
• 剩余需要合并的是 l1.next.next(5) 和 l2.next(4→6)。
• 执行 l1.next.next = mergeTwoLists(l1.next.next, l2.next)，即 节点3.next = merge(5, 4→6)。

4. 以此类推，直到递归终止（l1 或 l2 为空）

• 最终结果链表为：1 → 2 → 3 → 4 → 5 → 6。

# 四、递归的终止条件与回溯过程

• 终止条件：当 l1 或 l2 为空时，直接返回另一个链表（因为空链表与任何链表合并的结果就是另一个链表）。

  if (l1 === null) return l2;
  if (l2 === null) return l1;
  
• 回溯过程：递归返回时，每一层的结果会作为上一层的“剩余部分合并结果”被连接。例如，第三层递归返回 3 → 4 → 5 → 6，第二层将节点 2 的 next 指向该结果，得到 2 → 3 → 4 → 5 → 6；第一层将节点 1 的 next 指向该结果，最终得到完整的 1 → 2 → 3 → 4 → 5 → 6。

# 五、总结：递归的“选择-连接”逻辑

l1.next = mergeTwoLists(l1.next, l2) 这行代码的核心逻辑是：

1. 选择：由于 l1.val < l2.val，当前结果链表的节点为 l1。
2. 连接：将 l1 的 next 指针指向“剩余部分的合并结果”，即 l1.next（l1 的后续节点）和 l2（未使用的 l2 节点）的合并结果。

通过这种方式，递归会逐层处理链表的每个节点，确保最终结果链表保持升序。关键在于理解“当前节点的 next 指针指向剩余节点的合并结果”这一递归连接逻辑。

# 临界值判断的处理

# “刚好够用”的临界值

旋转字符串open in new window中，s+s正好提供了所有可能的起始位置来截取子串，所以s+s是最优选择。

这个思考可以推广到其他类似问题：先分析需要多少个不同的“视角”，然后构造一个能容纳所有这些视角的线性结构

# 数学思想

# 找到数学本质

算法竞赛和面试题中常见的思路：找到问题的数学本质，避免不必要的操作。

今天写了一道算法题：回文排列open in new window，题目的要求是给你一个字符串 s ，如果该字符串的某个排列是 回文串 ，则返回 true ；否则，返回 false 。

我知道回文有两种情况：

1. 如果字符串的长度是偶数，那么每个字符出现的次数都是偶数
2. 如果字符串的长度是奇数，那么只有一个字符出现的次数是奇数，其余字符出现的次数是偶数

我纠结的点在于如何让他排列成回文的顺序，如aba或者abba,而不是仅仅靠次数判断。但答案只对以上两种逻辑写了，我非常困惑。

我问了deepseek,它说这道题的目的根本不是检测 而是存在性证明：只要满足这个频率条件，就一定能排列出至少一个回文。最长回文串open in new window也是这个原理。

# 如何简化思路

还是【回文排列】这道题，我的思路是根据奇偶数分别判断，但优化后只根据奇数就可以判断：

function canPermutePalindrome(s){
    const map = new Map();

    // 统计每个字符出现的次数
    // 例1: s = "aab"
    // map: {'a' => 2, 'b' => 1}
    for(let char of s){
        // 获取当前字符的计数，如果没有则为0
        // 然后+1，再存回Map
        map.set(char,(map.get(char) || 0) + 1)
    }

    // 核心：统计出现奇数次的字符数量
    let oddCount = 0;

    for(let count of map.values()){
        if(count%2!==0){
            oddCount++
        }
    }
    // 关键理解点：最多只能有一个字符出现奇数次
    // 这个条件同时覆盖了：
    // 1. 偶数长度情况：oddCount必须为0
    // 2. 奇数长度情况：oddCount必须为1
    return oddCount<= 1
}

这个写法非常优雅。我原本的思路：

判断字符串 → 看长度奇偶 → 分情况判断 → 写if-else

优化后的思路：

判断字符串 → 分析回文的结构特性 → 发现"对称性"本质
→ 推导出"最多一个奇数字符"的统一规律 → 不分情况统一处理

练习方法：

• 看到问题，先问自己：这个问题的核心数学模式是什么？
• 尝试用一句话总结规律，不看代码细节

模式识别训练: