算法思想

# 数学思想

# 找到数学本质

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

今天写了一道算法题：回文排列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

优化后的思路：

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

练习方法：

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

模式识别训练:

# 递归思想

递归关系(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 指针指向剩余节点的合并结果”这一递归连接逻辑。