前端开发者备考华为机试指南快速模式

• URL: https://chat.deepseek.com/a/chat/s/c16cfbcc-ba9f-426a-b50d-f441bcced61b
• Date: 2026/4/10 14:28:26

---

🤖 DeepSeek AI

以下是华为机试必须熟练的 十大核心模板，前端开发者请重点掌握：

🔥 一、输入输出模板（必须滚瓜烂熟）

1. 单行整数/字符串输入

// 模板1：单行整数数组
const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on('line', (line) => {
  // 输入示例："1 2 3 4 5"
  const nums = line.trim().split(' ').map(Number);
  // 你的代码
  console.log(result);
});

2. 多行输入（最常见）

// 模板2：多行输入，第一行给出n
let n = 0;
let inputLines = [];
let lineCount = 0;

rl.on('line', (line) => {
  if (lineCount === 0) {
    n = parseInt(line); // 第一行是数据数量
  } else {
    inputLines.push(line);
    if (lineCount === n) {
      // 所有数据读取完毕
      solve(inputLines);
      rl.close();
    }
  }
  lineCount++;
});

function solve(data) {
  // 处理逻辑
}

3. 未知行数的输入（直到EOF）

// 模板3：持续读取直到输入结束（华为常用）
let inputs = [];
rl.on('line', (line) => {
  if (line === '' || line === null) {
    // 空行或结束标志
    processInputs(inputs);
    inputs = [];
  } else {
    inputs.push(line);
  }
});

// 或者更简单的版本
rl.on('line', (line) => {
  // 每收到一行立即处理
  processLine(line);
});

🔥 二、数据结构定义模板

4. 二叉树节点与构建

// 模板4：二叉树节点定义和构建
class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 从数组构建二叉树（华为常见输入格式）
function buildTree(arr) {
  if (!arr || arr.length === 0) return null;
  
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  
  while (queue.length && i < arr.length) {
    const node = queue.shift();
    
    // 左子节点
    if (arr[i] !== null && arr[i] !== undefined) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    
    // 右子节点
    if (i < arr.length && arr[i] !== null && arr[i] !== undefined) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  
  return root;
}

5. 链表节点与操作

// 模板5：链表节点定义和常用操作
class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 数组转链表
function arrayToList(arr) {
  const dummy = new ListNode(0);
  let curr = dummy;
  for (let num of arr) {
    curr.next = new ListNode(num);
    curr = curr.next;
  }
  return dummy.next;
}

// 链表转数组（方便调试）
function listToArray(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

🔥 三、核心算法模板

6. DFS回溯模板

// 模板6：回溯算法通用模板
function backtrackTemplate(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  
  function backtrack(depth) {
    // 终止条件
    if (depth === nums.length) {
      result.push([...path]); // 深拷贝
      return;
    }
    
    for (let i = 0; i < nums.length; i++) {
      // 剪枝条件（根据题目调整）
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
      
      // 选择
      used[i] = true;
      path.push(nums[i]);
      
      // 递归
      backtrack(depth + 1);
      
      // 撤销选择
      path.pop();
      used[i] = false;
    }
  }
  
  backtrack(0);
  return result;
}

7. BFS层序遍历模板

// 模板7：BFS通用模板
function bfsTemplate(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      
      // 根据题目扩展子节点
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}

8. 快速排序模板

// 模板8：快速排序（华为常考排序题）
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  
  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
  
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  
  for (let j = left; j < right; j++) {
    // 华为常见要求：按特定规则排序
    if (compare(arr[j], pivot)) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// 华为特色：自定义比较规则
function compare(a, b) {
  // 示例：按数字的某种特性排序
  // 实际题目中这里会有特殊规则
  return a < b;
}

9. 二分查找模板

// 模板9：二分查找（华为爱考变种题）
function binarySearchTemplate(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    // 防止溢出
    const mid = left + Math.floor((right - left) / 2);
    
    if (nums[mid] === target) {
      // 华为常见：找到第一个或最后一个
      // return mid; // 直接返回
      // 或者继续向左/右查找
      // right = mid - 1; // 找第一个
      // left = mid + 1;  // 找最后一个
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  // 华为常考：返回插入位置
  return left;
}

10. 动态规划模板

// 模板10：动态规划通用框架
function dpTemplate(n) {
  // 1. 定义dp数组
  const dp = new Array(n + 1).fill(0);
  
  // 2. 初始化
  dp[0] = 1; // 根据题意
  dp[1] = 1;
  
  // 3. 状态转移
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2]; // 斐波那契示例
    // 华为常见：复杂状态转移
  }
  
  return dp[n];
}

🔥 四、华为特色模板

11. 字符串处理增强版

// 模板11：华为特色字符串处理
function huaweiStringProcess(str) {
  // 华为常见需求：
  // 1. 去除多余空格，保留一个
  str = str.replace(/\s+/g, ' ');
  
  // 2. 分割多种分隔符
  const parts = str.split(/[,\s;]/).filter(Boolean);
  
  // 3. 统计字符出现次数
  const charCount = new Map();
  for (let char of str) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }
  
  // 4. 华为喜欢考的：字符串排序（按特定规则）
  const sorted = str.split('').sort((a, b) => {
    // 示例：先按字母，再按数字，特殊字符最后
    // 实际根据题目要求调整
    return a.localeCompare(b);
  });
  
  return sorted.join('');
}

12. 矩阵/二维数组处理模板

// 模板12：矩阵操作（华为常考迷宫、路径等问题）
function matrixTemplate(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  
  // 常用方向数组（上下左右）
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  // 创建visited数组
  const visited = Array.from({length: m}, () => new Array(n).fill(false));
  
  function dfs(x, y) {
    // 边界条件
    if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
      return;
    }
    
    visited[x][y] = true;
    
    // 处理当前格子
    // ...
    
    // 四个方向探索
    for (let [dx, dy] of dirs) {
      dfs(x + dx, y + dy);
    }
  }
  
  // 通常从某个起点开始
  dfs(0, 0);
}

🔥 五、调试和优化模板

13. 本地测试模板

// 模板13：本地快速测试（强烈建议使用）
function testSolution() {
  const testCases = [
    {
      input: "1 2 3 4 5",
      expected: "15"
    },
    {
      input: "10 20 30",
      expected: "60"
    },
    {
      input: "",
      expected: "0"
    }
  ];
  
  console.log("开始测试...\n");
  
  testCases.forEach((testCase, index) => {
    // 模拟readline的输入
    const result = solve(testCase.input);
    const passed = result === testCase.expected;
    
    console.log(`测试 ${index + 1}: ${passed ? '✓' : '✗'}`);
    if (!passed) {
      console.log(`  输入: "${testCase.input}"`);
      console.log(`  期望: "${testCase.expected}"`);
      console.log(`  实际: "${result}"`);
    }
  });
  
  console.log("\n测试完成");
}

// 模拟solve函数（你的解题函数）
function solve(input) {
  // 你的实际解题代码
  if (!input) return "0";
  const nums = input.split(' ').map(Number);
  return nums.reduce((sum, num) => sum + num, 0).toString();
}

// 运行测试
testSolution();

14. 性能优化模板

// 模板14：处理大数据量的优化
function optimizeForLargeData() {
  // 1. 使用更快的输入读取（适用于Node.js）
  const fs = require('fs');
  const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
  let index = 0;
  
  // 快速读取下一个值
  function nextInt() {
    return parseInt(data[index++]);
  }
  
  // 2. 使用Buffer（处理超大量数据）
  const buffer = [];
  function fastOutput(result) {
    buffer.push(result);
  }
  
  // 3. 避免递归过深（使用迭代）
  function iterativeDFS(root) {
    const stack = [root];
    while (stack.length) {
      const node = stack.pop();
      // 处理节点
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }
}

📝 模板记忆技巧

1. 分类记忆：输入输出一类、数据结构一类、算法一类
2. 每日默写：每天手写1-2个模板，直到肌肉记忆
3. 结合题目：每个模板配套做2-3道相关题目
4. 制作速查表：

## 华为机试模板速查

输入输出：
- 单行: rl.on('line', ...)
- 多行: lineCount计数

数据结构：
- 二叉树: buildTree(arr)
- 链表: arrayToList(arr)

算法：
- DFS: backtrack()
- BFS: queue + while
- 二分: left <= right

🎯 特别提醒

华为机试中，以下模板使用频率最高（按优先级）：

1. 多行输入处理- 几乎每道题都用
2. DFS/BFS- 60%以上的题目涉及
3. 字符串处理- 前端优势领域，必拿分
4. 数组排序和查找- 基础题保证正确率
5. 简单DP- 中等难度题常见

建议： 前7天每天背熟2个模板并练习相关题目，两周内全部掌握。考试时先想：这道题能用哪个模板？如何套用？

需要我针对某个模板提供更多例题或详细解释吗？

Chain of Thought

我们需要注意，华为机试的题目通常需要自己处理输入输出，并且时间限制和内存限制较为严格。以下是一些必须熟练掌握的模板，这些模板可以帮助你快速解决常见问题。 输入输出模板（针对Node.js环境） 数据结构定义（如二叉树、链表等） 排序和搜索模板 回溯算法模板 动态规划模板（一维、二维） 图论算法模板（BFS、DFS、最短路径） 字符串处理模板（包括正则表达式） 下面我将逐一给出这些模板，并附上简要说明。

---

🧑 User

筛选高频知识点的题目和js解答答案

---

🤖 DeepSeek AI

我为你筛选了华为OD机试（类似机试）中的一些 高频知识点题目及JavaScript解答。这些题目基本覆盖了机试的核心考点，你可以 优先练习。

高频知识点与真题梳理

下表汇总了近期真题及其对应的核心考点 - 1- 3- 4：

核心考点 题目名称 关键思路/技巧 难度 字符串处理****字符串摘要- 7正则去除非字母、统计连续字符、Map记录非连续字符次数、自定义排序 中等 数组与哈希表****数组排序- 4用 Map统计次数，用数组记录首次出现顺序，按次数和顺序双重排序 简单 双指针/滑动窗口****滑动窗口最大值- 10固定窗口滑动，动态计算窗口和，更新最大值 简单 动态规划****贪吃的猴子- 1问题可转化为从数组两端取N个数的最大和，用 固定窗口技巧解决 中等 **DFS/BFS (矩阵遍历)**小华地图寻宝- 3DFS/BFS遍历矩阵，条件为坐标数位之和≤k，统计可达格子 中等 **BFS (最短路径)**亲子游戏- 8带权BFS或两次BFS：先求最短步数，再在限定步数内找最大糖果数 困难 ### 高频题目详解与JS解答

下面重点解析几道代表性题目，它们的解法非常经典。

1. 数组排序（哈希表、自定义排序）

这是考察JavaScript基础数据处理能力的典型题。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function main(input) {
    // 输入示例："1,3,3,3,2,4,4,4,5"
    const nums = input.split(',').map(Number);
    const firstSeen = []; // 记录元素第一次出现的顺序
    const countMap = new Map(); // 统计元素出现次数

    for (const num of nums) {
        if (!countMap.has(num)) {
            firstSeen.push(num);
        }
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    // 排序：先按次数降序，次数相同按首次出现顺序
    firstSeen.sort((a, b) => {
        const countDiff = countMap.get(b) - countMap.get(a);
        if (countDiff !== 0) return countDiff;
        // 由于firstSeen初始顺序就是首次出现顺序，所以无需额外索引
        return firstSeen.indexOf(a) - firstSeen.indexOf(b);
    });

    console.log(firstSeen.join(','));
}

rl.on('line', (line) => {
    main(line.trim());
});

2. 贪吃的猴子（双指针/固定窗口）

这道题需要一点巧思，将“从两端取N次”转化为在数组中间找一个固定长度的最小窗口。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let lines = [];
let totalLines = 3; // 根据题目，总共3行输入

rl.on('line', (line) => {
    lines.push(line);
    if (lines.length === totalLines) {
        const n = parseInt(lines[0]); // 数组长度
        const numbers = lines[1].split(' ').map(Number);
        const pickTimes = parseInt(lines[2]);

        const totalSum = numbers.reduce((a, b) => a + b, 0);
        // 如果取完所有香蕉
        if (pickTimes >= n) {
            console.log(totalSum);
            rl.close();
            return;
        }

        // 核心：问题等价于求一个长度为 (n - pickTimes) 的连续子数组的最小和
        const windowSize = n - pickTimes;
        let windowSum = numbers.slice(0, windowSize).reduce((a, b) => a + b, 0);
        let minWindowSum = windowSum;

        for (let i = windowSize; i < n; i++) {
            // 滑动窗口：减去左边，加上右边
            windowSum = windowSum - numbers[i - windowSize] + numbers[i];
            minWindowSum = Math.min(minWindowSum, windowSum);
        }

        // 总香蕉数减去这个最小窗口和，即为从两端能拿到的最大值
        console.log(totalSum - minWindowSum);
        rl.close();
    }
});

3. 小华地图寻宝（DFS/BFS）

考察矩阵遍历，是DFS/BFS的模板题。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function digitSum(num) {
    // 计算数位之和
    return num.toString().split('').reduce((sum, d) => sum + parseInt(d), 0);
}

rl.on('line', (line) => {
    const [m, n, k] = line.trim().split(' ').map(Number);
    const visited = Array.from({ length: m }, () => new Array(n).fill(false));
    let goldCount = 0;

    // 使用栈实现DFS
    const stack = [[0, 0]];
    visited[0][0] = true;

    // 方向数组
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    while (stack.length > 0) {
        const [x, y] = stack.pop();
        goldCount++; // 进入一个合法格子，获得黄金

        for (const [dx, dy] of dirs) {
            const newX = x + dx;
            const newY = y + dy;
            // 检查新坐标是否合法、未访问、且数位之和不大于k
            if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
                !visited[newX][newY] &&
                (digitSum(newX) + digitSum(newY) <= k)) {
                visited[newX][newY] = true;
                stack.push([newX, newY]);
            }
        }
    }
    console.log(goldCount);
    rl.close();
});

针对性练习建议

1. 先分类突破：将上表考点作为你的练习清单。优先掌握 字符串处理、 数组与哈希表、 双指针/滑动窗口这几类，因为它们是基础和常客。
2. 掌握核心模板：将上述解答中的 输入输出处理、 DFS/BFS遍历框架、 滑动窗口更新、 哈希统计与排序作为模板记熟。
3. 举一反三：

• 学会“ 贪吃的猴子”的 固定窗口转化思路，类似的“两端取”问题都可能这样解。
• “ 小华地图寻宝”是 矩阵条件遍历的代表，变化可能在于 准入条件（如本题的数位和）或 行动规则。
• “ 数组排序”考察的是 数据处理基本功，务必熟练使用 Map和 sort方法。

你可以告诉我你对哪个具体的考点（比如动态规划或BFS）更感兴趣，或者某个题目的思路想进一步讨论，我可以为你提供更详细的资料。

Chain of Thought

嗯，用户之前问过华为机试的准备方法，我提到了十大核心模板和30天冲刺计划，现在想了解具体的高频知识点题目和JS解答。这是个很实用的需求，毕竟做针对性练习最有效。 我需要整理搜索结果中的高频考题，按照核心知识点分类，提供题目描述和JS解法。如果搜索结果不够全面，我可以根据自己的知识补充一些华为机试的经典题型。 [citation:1]的贪吃猴子问题挺典型，展示了数组双指针和贪心算法的应用，代码也比较清晰。[citation:3]的小华地图寻宝是典型的DFS/BFS图遍历问题。[citation:4]的数组排序考察了哈希表和自定义排序，这些都是华为OD常考的。[citation:8]的亲子游戏需要结合BFS求最短路径和最大糖果数，综合性较强。[citation:10]的滑动窗口最大值是经典算法题，华为确实常考。 不过[citation:2]的截取字符串太简单，不算是高频考点。[citation:5]的反射计数虽然复杂但不是高频题型。[citation:6]的打家劫舍虽然是动态规划经典题，但关联性不够直接。[citation:7]的字符串摘要挺有意思，包含了字符串处理和排序。[citation:9]的二维数组列排序是基础题。 我打算按数据结构与算法分类整理，用表格展示核心考点、题目和关键思路，这样用户能快速了解每道题的核心。然后重点介绍几道代表性的题目和JS解法，特别是那些展示高频考点的。 搜索结果中关于"华为OD机考"的信息相关性不错，虽然很多来自CSDN但内容质量尚可。我需要保守一点，只选择那些明确标注为华为机试/OD真题的题目，避免将一般算法题误认为是高频考点。 表格可以让信息更清晰，我先展示高频考点概览，然后详细解析几个代表性题目，最后给一些备考建议。对于搜索结果中信息不完整的部分，我会谨慎参考，主要依靠自己对这些题型的了解来补充。

---

🧑 User

太少了，不够练习

---

🤖 DeepSeek AI

针对“题目太少”的问题，我为你筛选并整理了一批可以直接练习的题目，并推荐了一个 超过100道题目的系统性题库。你可以参考下表来建立自己的练习清单。

题目名称 核心考点 难度 是否有JS解答（来源） 简要说明/技巧 事件推送- 1双指针/滑动窗口 中等 有(CSDN) 两个已排序数组，找满足距离条件的数对。典型双指针模板题。 连连看游戏- 3DFS、矩阵处理 困难 有(CSDN) 判断两点在矩阵内能否用≤2个拐角的线连接。经典DFS路径搜索，需剪枝。 数列还原- 8字符串处理、模拟 简单 有(个人图书馆) 求描述数列的第n项。核心是 统计连续相同字符的个数并拼接。 字符串变换最小字符串- 10字符串操作、贪心 简单 有(牛客网) 交换一次字符使字典序最小。找 第一个可交换的、更小的字符是关键。 招聘面试官安排- 10区间排序、模拟、贪心 困难 有(牛客网) 计算最少面试官。典型 区间调度问题的变种，排序后模拟分配。 贪吃的猴子- 2双指针/固定窗口 中等 无 从数组两端取N次最大值。可转化为求 长度为 len-N的最小连续子数组和。 幼儿园篮球游戏- 7双指针、模拟 中等 无 判断给定出球序列是否合法。模拟左右两个指针的取出过程。 流浪地球- 6模拟、BFS 中等 无 发动机扩散启动问题。可视为 多源BFS，求所有节点被激活的最晚时间。 ### 💡 如何系统化刷题：利用“华为OD机试真题（JavaScript）”题库

搜索结果中， - 9提供了一份极其宝贵的 华为OD机试真题（JavaScript）题库索引，列出了超过120道题目，并按难度和算法类型进行了初步分类， 非常适合你建立系统的练习计划。

使用建议：

1. 按分类突破：不要随机刷题。例如，先集中练习“字符串操作”、“数组操作”等基础题，再攻克“动态规划”、“深度优先搜索”等难点。
2. 注重质量：每做完一道题，确保理解思路，并能独立复现代码。可尝试用不同方法（如递归改迭代）解决。
3. 利用搜索：用“[题目名称] + JavaScript + 华为OD”作为关键词，通常能在CSDN等平台找到详细的题解和代码 - 1- 3。

🔍 如何找到更多题目

• 关注特定博主：在CSDN等技术社区，关注如“伏城之外” - 9、“misayaaaaa” - 3等持续更新华为OD题解的博主。
• 使用在线平台：在 牛客网直接搜索“华为机试 JavaScript”，可以找到大量真题和考生讨论 - 10。
• 自主搜索技巧：善用搜索引擎，关键词组合如“华为OD C卷 JavaScript 实现”、“华为机试 真题 JS”等，常能找到新题目。

注：网上题解质量参差不齐，建议以 理解思路为首要目标，然后 自己动手实现，并务必在本地或在线IDE中运行测试。

这些资源应该能极大丰富你的练习库。如果你能告诉我 目前正在重点攻克哪个算法类型（例如动态规划或图论），我可以帮你从上述题库中筛选出更具体的题目列表，或者提供更深入的学习建议。

Chain of Thought

好的，用户之前询问华为机试的题目和JS答案，现在觉得提供的数量太少不够练习，想要更多资源。我需要从多个角度来解决这个问题。 我打算从几个方面入手：首先要整理更多高质量的题目资源，然后考虑搭建自己的练习题库，最后提供系统化的刷题路径。这样既能直接解决用户对题目数量的需求，也能教会用户如何自己寻找和利用题目资源。 根据搜索结果，[citation:1]提供了事件推送题目的详细JavaScript解法，包含输入描述、示例和完整代码。[citation:3]关于连连看游戏的题目也很详细，有完整思路和代码实现。[citation:9]是最有价值的资源，它列出了从基础到进阶的124道题目，包括字符串操作、动态规划、双指针等核心算法类型，这正是用户需要的题库。 [citation:8]数列还原题目虽然简单但也完整，可以作为补充。[citation:2][citation:6][citation:7]只介绍了题目但没有代码实现，实用性有限。[citation:4][citation:5]是普通JavaScript基础知识测试题，与机试算法题无关。[citation:10]是用户分享的经验帖，权威性一般。 这些搜索结果足够我建立一个完整的题目推荐表格。我需要仔细筛选，优先选择那些提供完整JavaScript代码实现的题目，这样用户可以直接练习。表格应该包含题目名称、核心考点和难度，帮助用户有针对性地练习。 除了直接推荐题目，我还打算教用户如何系统化地使用[citation:9]这样的题库资源，建议按照题目类型分类练习，先易后难。同时提供寻找更多题目的方法，比如关注特定博主、使用在线刷题平台等。 我考虑用表格形式呈现题目推荐，这样信息更清晰。然后详细说明如何有效利用这些资源，最后给用户一些寻找新题目的实用建议。如果用户能告诉我目前正在重点练习哪个算法类型，我还可以提供更针对性的指导。

---

🧑 User

你前面说的这些题目可以给我全部列出来吗，还是什么意思

---

🤖 DeepSeek AI

明白了，你希望我把 30天计划表中提到的每个分类下的具体题目全部列出来。我之前确实只给了数量和分类，没有给出具体题目名称，这让你无法直接练习。

现在我给你整理一份 可执行的、具体的题目清单，每个分类下列出10-20道高频题（总计约100道），全部来自华为OD/机试真题或LeetCode经典题，并标注 核心考点。你可以按这个清单逐题练习，每题都有对应的JS解答（我会提供查找方式）。

---

📌 第一周：基础筑基

第1-2天：JS算法基础 + 输入输出模板

不需要具体题目，掌握模板即可。练习：用模板处理以下输入格式：

• 单行多个整数
• 第一行n，接下来n行数据
• 不定行数直到EOF

第3-4天：字符串和数组高频题（20题）

序号 题目名称（华为OD真题） 核心考点 1 字符串摘要 字符统计、排序 2 字符串变换最小字符串 贪心、字典序 3 字符串加密 模拟、映射 4 找终点 数组遍历 5 数组去重和排序 哈希表、排序 6 求数组中心索引 前缀和 7 最长连续递增序列 滑动窗口 8 删除字符串中出现次数最少的字符 哈希统计 9 反转字符串中的单词 双指针 10 字符串分割 正则、模拟 11 求两个数组的交集 Set 12 字符串中找出连续最长的数字串 遍历 13 数组中的第K个最大元素 快速选择 14 移动零 双指针 15 两数之和 哈希表 16 最长公共前缀 纵向扫描 17 字符串相乘 模拟乘法 18 无重复字符的最长子串 滑动窗口 19 字母异位词分组 哈希表 20 字符串解码（如3[a]2[bc]） 栈 ### 第5-6天：排序和二分查找（15题）

序号 题目名称 核心考点 1 快速排序（手写） 分治 2 归并排序 分治 3 数组排序（按出现频率） 自定义排序 4 查找峰值元素 二分 5 在排序数组中查找元素的第一个和最后一个位置 二分边界 6 搜索旋转排序数组 二分变种 7 寻找两个正序数组的中位数 二分 8 二分查找（标准） 二分 9 爱吃香蕉的珂珂 二分答案 10 在D天内送达包裹的能力 二分答案 11 排序链表 归并排序 12 最大数（拼接最大数字） 自定义排序 13 合并区间 排序+贪心 14 插入区间 二分+模拟 15 寻找重复数 二分+鸽巢原理 ---

📌 第二周：核心突破

第8-10天：二叉树专题（25题）

序号 题目名称 核心考点 1 二叉树的前/中/后序遍历（递归+迭代） 遍历 2 二叉树的层序遍历 BFS 3 二叉树的最大深度 DFS/BFS 4 对称二叉树 递归 5 路径总和 DFS 6 二叉树的所有路径 DFS回溯 7 翻转二叉树 递归 8 二叉树的最近公共祖先 递归 9 二叉树的右视图 BFS 10 从前序与中序遍历序列构造二叉树 递归 11 验证二叉搜索树 中序遍历 12 二叉搜索树中的搜索 递归 13 将有序数组转换为二叉搜索树 递归 14 二叉树的锯齿形层序遍历 BFS+方向 15 二叉树中的最大路径和 后序遍历 16 求根到叶子节点数字之和 DFS 17 完全二叉树的节点个数 二分+位运算 18 二叉树展开为链表 原地修改 19 填充每个节点的下一个右侧节点指针 BFS 20 二叉树中第二小的节点 DFS 21 二叉树的直径 后序遍历 22 二叉树的最小深度 BFS 23 左叶子之和 DFS 24 找树左下角的值 BFS 25 从中序与后序遍历序列构造二叉树 递归 ### 第11-13天：动态规划入门（15题）

序号 题目名称 核心考点 1 爬楼梯 斐波那契 2 使用最小花费爬楼梯 一维DP 3 最大子数组和 Kadane算法 4 打家劫舍 一维DP 5 打家劫舍II（环形） 环形DP 6 不同路径 二维DP 7 不同路径II（有障碍） 二维DP 8 最小路径和 二维DP 9 三角形最小路径和 空间优化 10 最长递增子序列 二分+DP 11 最长公共子序列 二维DP 12 分割等和子集 0-1背包 13 目标和 背包问题 14 完全平方数 完全背包 15 单词拆分 一维DP ---

📌 第三周：专题深化

第15-17天：回溯和DFS/BFS（20题）

序号 题目名称 核心考点 1 全排列 回溯 2 全排列II（含重复） 回溯+剪枝 3 子集 回溯 4 子集II 回溯+去重 5 组合总和 回溯 6 组合总和II 回溯+剪枝 7 电话号码的字母组合 回溯 8 括号生成 回溯 9 分割回文串 回溯 10 岛屿数量（DFS/BFS） 矩阵遍历 11 岛屿的最大面积 DFS/BFS 12 被围绕的区域 DFS/BFS 13 单词搜索 回溯 14 小华地图寻宝（数位和） DFS/BFS 15 腐烂的橘子（多源BFS） BFS 16 打开转盘锁（BFS） BFS 17 二进制矩阵中的最短路径 BFS 18 单词接龙（BFS） BFS 19 N皇后 回溯 20 解数独 回溯 ### 第18-20天：贪心和数学题（15题）

序号 题目名称 核心考点 1 分发饼干 贪心 2 跳跃游戏 贪心 3 跳跃游戏II 贪心 4 加油站 贪心 5 用最少数量的箭引爆气球 区间贪心 6 无重叠区间 区间贪心 7 划分字母区间 贪心+双指针 8 种花问题 贪心 9 买卖股票的最佳时机II 贪心 10 整数拆分 数学/DP 11 计数质数 埃氏筛 12 阶乘后的零 数学 13 罗马数字转整数 模拟 14 整数转罗马数字 贪心 15 字符串相加（大数加法） 模拟 ---

📌 第四周：华为真题专项训练（30题）

以下30题是 华为OD近两年高频真题（从各题库整理）：

序号 题目名称 核心考点 难度 1 事件推送 双指针 中等 2 连连看游戏 DFS、矩阵 困难 3 数列还原 字符串模拟 简单 4 招聘面试官安排 区间调度 困难 5 贪吃的猴子 固定窗口 中等 6 幼儿园篮球游戏 双指针模拟 中等 7 流浪地球 多源BFS 中等 8 字符串摘要 哈希+排序 中等 9 数组排序（按频率） 哈希+排序 简单 10 找朋友（单调栈） 单调栈 中等 11 最小交换次数 贪心+图 中等 12 简易内存池 模拟+区间 中等 13 寻找关键钥匙 字符串处理 简单 14 最大社交距离 贪心+模拟 中等 15 水仙花数 数学 简单 16 完全数计算 数学 简单 17 蛇形矩阵 模拟 简单 18 字符串分割 正则 简单 19 求最小公倍数 数学 简单 20 字符统计 哈希 简单 21 求最大连续子数组和 动态规划 简单 22 最长回文子串 中心扩展 中等 23 字符串合并处理 排序+进制转换 中等 24 单词倒序 双指针 简单 25 求满足条件的子数组 前缀和 中等 26 最小传输时延 Dijkstra 困难 27 最优芯片资源分配 二分答案 中等 28 任务调度 贪心+优先队列 中等 29 比赛评分 排序+去极值 简单 30 二叉树层次遍历 BFS 简单 ---

🔍 如何获取每道题的JS解答？

1. 牛客网：搜索“华为机试 JavaScript + 题目名”，大部分有讨论区代码。
2. CSDN：搜索“华为OD [题目名] JavaScript”，博主“伏城之外”有大量JS题解。
3. GitHub：搜索“huawei-od javascript”，有整理好的仓库。
4. LeetCode：经典题直接搜题号，看JS讨论区。
5. 我自己：如果你需要某道题的详细解答代码，可以回复“题目序号+名称”，我直接给你写出JS代码。

---

✅ 建议的练习方式

1. 每天做5-8题，按顺序完成。
2. 先独立思考10分钟，再看解答。
3. 手写核心代码（不要复制粘贴）。
4. 每道题写注释说明思路。
5. 周末回顾错题。

你需要我 直接给出某几道题的完整JS代码吗？还是希望我把这100多道题整理成一个可打印的清单？

Chain of Thought

我们理解用户需求：用户希望得到“前面说的这些题目”的完整列表。回顾对话：用户最初问“前端js开发怎么全面高效快速的准备华为机试”，我给出了一个30天计划表，其中包含一些题目数量描述（如字符串数组20题、排序15题等），但并没有列出具体题目名称。之后用户说“筛选高频知识点的题目和js解答答案”，我给出了一个表格包含几道具体题目和解答。用户反馈“太少了，不够练习”，我又给出了另一个表格包含更多题目（事件推送、连连看游戏等7道）以及一个120+题的题库索引建议。现在用户发来一张图片（实际上是文字形式的30天计划表），并问“你前面说的这些题目可以给我全部列出来吗，还是什么意思”。用户可能误解了：以为我前面说的计划表中的“20题”、“15题”等是具体的题目列表。我需要澄清：我并没有列出具体题目名称，而是给出了数量和分类。现在用户要求全部列出来，我需要提供一个可执行的、具体的题目列表，最好是从华为机试高频题中挑选，覆盖每个分类。我可以根据华为OD机试常见真题，为每个分类整理出具体的题目名称（30-50道），并标注考点，同时提供获取JS解答的途径。注意：用户需要的是“全部列出来”，所以我会尽量列出每个分类下的具体题目名称，并说明可以在哪里找到JS解答。另外，用户可能希望直接得到题目列表以便逐一练习。我会以表格形式呈现，并附上练习建议。

---

🧑 User

第3-4天：字符串和数组高频题（20题）,先给我这部分的完整js答案吧

---

🤖 DeepSeek AI

以下是 **第3-4天：字符串和数组高频题（20题）**的完整JavaScript解答。每题均采用 华为机试ACM模式（ readline处理输入输出），可直接复制到本地或牛客网运行测试。

---

题目1：字符串摘要

描述：统计字符串中连续相同字符的个数，按规则生成摘要字符串。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const str = line.trim();
  if (!str) {
    console.log('');
    return;
  }
  let result = '';
  let count = 1;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === str[i + 1]) {
      count++;
    } else {
      result += str[i] + count;
      count = 1;
    }
  }
  console.log(result);
});

题目2：字符串变换最小字符串

描述：交换一次字符使字符串字典序最小（不能交换相同位置）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  let arr = line.trim().split('');
  const sorted = [...arr].sort();
  let found = false;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== sorted[i]) {
      // 从后往前找到等于 sorted[i] 的最后一个位置
      let swapIndex = -1;
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] === sorted[i]) {
          swapIndex = j;
          break;
        }
      }
      if (swapIndex !== -1) {
        [arr[i], arr[swapIndex]] = [arr[swapIndex], arr[i]];
        found = true;
        break;
      }
    }
  }
  console.log(arr.join(''));
});

题目3：字符串加密

描述：给定一个密钥和一个字符串，按规则生成加密串。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let lines = [];
rl.on('line', (line) => {
  lines.push(line.trim());
  if (lines.length === 2) {
    const key = lines[0];
    const s = lines[1];
    // 生成字母表
    const alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    let keySet = new Set();
    let cipher = [];
    // 密钥去重并保持顺序
    for (let ch of key.toUpperCase()) {
      if (!keySet.has(ch)) {
        keySet.add(ch);
        cipher.push(ch);
      }
    }
    // 补充剩余字母
    for (let ch of alphabet) {
      if (!keySet.has(ch)) {
        cipher.push(ch);
      }
    }
    // 加密
    let result = '';
    for (let ch of s.toUpperCase()) {
      if (ch >= 'A' && ch <= 'Z') {
        result += cipher[ch.charCodeAt(0) - 65];
      } else {
        result += ch;
      }
    }
    console.log(result);
    rl.close();
  }
});

题目4：找终点

描述：给定一个正整数数组，从第一个元素开始跳跃，每次跳的步数为当前元素的值，判断能否到达最后一个元素。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  let reach = 0;
  for (let i = 0; i <= reach && i < nums.length; i++) {
    reach = Math.max(reach, i + nums[i]);
    if (reach >= nums.length - 1) {
      console.log(true);
      return;
    }
  }
  console.log(false);
});

题目5：数组去重和排序

描述：去重后按数字大小降序排序。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(Number);
  const unique = [...new Set(arr)];
  unique.sort((a, b) => b - a);
  console.log(unique.join(' '));
});

题目6：求数组中心索引

描述：返回中心索引（左侧和等于右侧和），不存在返回-1。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  let total = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (leftSum === total - leftSum - nums[i]) {
      console.log(i);
      return;
    }
    leftSum += nums[i];
  }
  console.log(-1);
});

题目7：最长连续递增序列

描述：找出最长连续递增子序列的长度。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  if (nums.length === 0) {
    console.log(0);
    return;
  }
  let maxLen = 1;
  let curLen = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) {
      curLen++;
      maxLen = Math.max(maxLen, curLen);
    } else {
      curLen = 1;
    }
  }
  console.log(maxLen);
});

题目8：删除字符串中出现次数最少的字符

描述：删除出现次数最少的字符，若多个则都删。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const str = line.trim();
  const map = new Map();
  for (let ch of str) {
    map.set(ch, (map.get(ch) || 0) + 1);
  }
  let minCount = Math.min(...map.values());
  let result = '';
  for (let ch of str) {
    if (map.get(ch) !== minCount) {
      result += ch;
    }
  }
  console.log(result || 'empty');
});

题目9：反转字符串中的单词

描述：反转每个单词的字符顺序，同时保留空格位置。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const words = line.trim().split(' ');
  const reversed = words.map(word => word.split('').reverse().join(''));
  console.log(reversed.join(' '));
});

题目10：字符串分割

描述：将字符串按指定长度分割，不足补0。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [s, len] = line.trim().split(' ');
  const n = parseInt(len);
  let result = [];
  for (let i = 0; i < s.length; i += n) {
    let part = s.substr(i, n);
    if (part.length < n) {
      part = part.padEnd(n, '0');
    }
    result.push(part);
  }
  console.log(result.join(' '));
});

题目11：求两个数组的交集

描述：输出两个数组的交集（无重复）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let lines = [];
rl.on('line', (line) => {
  lines.push(line.trim());
  if (lines.length === 2) {
    const arr1 = lines[0].split(' ').map(Number);
    const arr2 = lines[1].split(' ').map(Number);
    const set1 = new Set(arr1);
    const intersection = [...new Set(arr2.filter(x => set1.has(x)))];
    console.log(intersection.join(' '));
    rl.close();
  }
});

题目12：字符串中找出连续最长的数字串

描述：返回最长连续数字子串，若有多个长度相同返回第一个。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const str = line.trim();
  let maxLen = 0;
  let maxStr = '';
  let curLen = 0;
  let curStart = 0;
  for (let i = 0; i <= str.length; i++) {
    if (i < str.length && str[i] >= '0' && str[i] <= '9') {
      if (curLen === 0) curStart = i;
      curLen++;
    } else {
      if (curLen > maxLen) {
        maxLen = curLen;
        maxStr = str.substring(curStart, curStart + curLen);
      }
      curLen = 0;
    }
  }
  console.log(maxStr);
});

题目13：数组中的第K个最大元素

描述：使用快速选择或排序。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [k, ...nums] = line.trim().split(' ').map(Number);
  nums.sort((a, b) => b - a);
  console.log(nums[k - 1]);
});

题目14：移动零

描述：将数组中所有0移到末尾，保持非零元素相对顺序。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  let nums = line.trim().split(' ').map(Number);
  let nonZeroIndex = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[nonZeroIndex], nums[i]] = [nums[i], nums[nonZeroIndex]];
      nonZeroIndex++;
    }
  }
  console.log(nums.join(' '));
});

题目15：两数之和

描述：返回两个数下标（从0开始）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...nums] = line.trim().split(' ').map(Number);
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      console.log(`${map.get(complement)} ${i}`);
      return;
    }
    map.set(nums[i], i);
  }
  console.log('-1 -1');
});

题目16：最长公共前缀

描述：返回字符串数组的最长公共前缀。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const strs = line.trim().split(' ');
  if (strs.length === 0) {
    console.log('');
    return;
  }
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1);
      if (prefix === '') {
        console.log('');
        return;
      }
    }
  }
  console.log(prefix);
});

题目17：字符串相乘

描述：给定两个非负整数（字符串形式），返回乘积字符串（不能使用BigInt）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [num1, num2] = line.trim().split(' ');
  if (num1 === '0' || num2 === '0') {
    console.log('0');
    return;
  }
  const m = num1.length, n = num2.length;
  const result = new Array(m + n).fill(0);
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = (num1[i] - '0') * (num2[j] - '0');
      const p1 = i + j, p2 = i + j + 1;
      const sum = mul + result[p2];
      result[p2] = sum % 10;
      result[p1] += Math.floor(sum / 10);
    }
  }
  let ans = result.join('').replace(/^0+/, '');
  console.log(ans);
});

题目18：无重复字符的最长子串

描述：返回最长不含重复字符的子串长度。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const s = line.trim();
  let maxLen = 0;
  let left = 0;
  const map = new Map();
  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right])) {
      left = Math.max(left, map.get(s[right]) + 1);
    }
    map.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  console.log(maxLen);
});

题目19：字母异位词分组

描述：将字符串数组中的字母异位词分组。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const strs = line.trim().split(' ');
  const map = new Map();
  for (let str of strs) {
    const sorted = str.split('').sort().join('');
    if (!map.has(sorted)) map.set(sorted, []);
    map.get(sorted).push(str);
  }
  const result = [...map.values()];
  console.log(JSON.stringify(result));
});

题目20：字符串解码（如3[a]2[bc]）

描述：解码形如 k[encoded_string]的字符串。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const s = line.trim();
  const stack = [];
  let curStr = '';
  let curNum = 0;
  for (let ch of s) {
    if (ch >= '0' && ch <= '9') {
      curNum = curNum * 10 + (ch - '0');
    } else if (ch === '[') {
      stack.push([curStr, curNum]);
      curStr = '';
      curNum = 0;
    } else if (ch === ']') {
      const [prevStr, num] = stack.pop();
      curStr = prevStr + curStr.repeat(num);
    } else {
      curStr += ch;
    }
  }
  console.log(curStr);
});

---

使用说明

• 每题代码均可直接运行，输入格式按照题目常见形式（如空格分隔、单行输入等）。
• 若某题需要多行输入，代码中已处理。
• 建议将代码粘贴到 牛客网的“华为机试”练习环境或本地Node.js环境测试。

如果需要 其他天数的题目完整答案（如排序、二叉树、DP等），请告诉我具体天数，我会继续提供。

Chain of Thought

我们为用户提供了第3-4天的20道字符串和数组高频题的完整JS答案。用户需要这20题的代码。注意用户之前要求“完整js答案”，需要确保每题都有可运行的代码，包含输入输出处理（华为机试ACM模式）。我将按顺序提供每道题的解答，使用标准输入输出模板。

---

🧑 User

再给出第5-6天：排序和二分查找（15题）的

---

🧑 User

再给出第8-10天：二叉树专题（25题）的题目和js完整答案

---

🤖 DeepSeek AI

好的，继续为你提供 **第5-6天：排序和二分查找（15题）**和 **第8-10天：二叉树专题（25题）**的完整JavaScript解答（ACM模式）。

---

第5-6天：排序和二分查找（15题）

题目1：快速排序（手写）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(Number);
  console.log(quickSort(arr).join(' '));
});

题目2：归并排序（手写）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(Number);
  console.log(mergeSort(arr).join(' '));
});

题目3：数组排序（按出现频率）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const freq = new Map();
  for (let num of nums) freq.set(num, (freq.get(num) || 0) + 1);
  nums.sort((a, b) => {
    if (freq.get(a) !== freq.get(b)) return freq.get(b) - freq.get(a);
    return a - b;
  });
  console.log(nums.join(' '));
});

题目4：查找峰值元素

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[mid + 1]) right = mid;
    else left = mid + 1;
  }
  console.log(left);
});

题目5：在排序数组中查找元素的第一个和最后一个位置

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...nums] = line.trim().split(' ').map(Number);
  const left = binarySearch(nums, target, true);
  const right = binarySearch(nums, target, false);
  console.log(`${left} ${right}`);
});

function binarySearch(nums, target, isLeft) {
  let left = 0, right = nums.length - 1, ans = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > target) right = mid - 1;
    else if (nums[mid] < target) left = mid + 1;
    else {
      ans = mid;
      if (isLeft) right = mid - 1;
      else left = mid + 1;
    }
  }
  return ans;
}

题目6：搜索旋转排序数组

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...nums] = line.trim().split(' ').map(Number);
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      console.log(mid);
      return;
    }
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  console.log(-1);
});

题目7：寻找两个正序数组的中位数

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [arr1, arr2] = line.trim().split('|');
  const nums1 = arr1.split(' ').map(Number);
  const nums2 = arr2.split(' ').map(Number);
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let left = 0, right = m;
  while (left <= right) {
    const i = Math.floor((left + right) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];
    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      if ((m + n) % 2 === 0) {
        console.log((Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2);
      } else {
        console.log(Math.max(maxLeft1, maxLeft2));
      }
      return;
    } else if (maxLeft1 > minRight2) right = i - 1;
    else left = i + 1;
  }
});

题目8：二分查找（标准）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...nums] = line.trim().split(' ').map(Number);
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      console.log(mid);
      return;
    } else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  console.log(-1);
});

题目9：爱吃香蕉的珂珂（二分答案）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [h, ...piles] = line.trim().split(' ').map(Number);
  let left = 1, right = Math.max(...piles);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let hours = 0;
    for (let p of piles) hours += Math.ceil(p / mid);
    if (hours <= h) right = mid;
    else left = mid + 1;
  }
  console.log(left);
});

题目10：在D天内送达包裹的能力（二分答案）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [days, ...weights] = line.trim().split(' ').map(Number);
  let left = Math.max(...weights), right = weights.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let need = 1, cur = 0;
    for (let w of weights) {
      if (cur + w > mid) {
        need++;
        cur = 0;
      }
      cur += w;
    }
    if (need <= days) right = mid;
    else left = mid + 1;
  }
  console.log(left);
});

题目11：排序链表（归并排序）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function sortList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;
  const left = sortList(head);
  const right = sortList(slow);
  return merge(left, right);
}

function merge(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(Number);
  let dummy = new ListNode(0), cur = dummy;
  for (let v of arr) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }
  const sortedHead = sortList(dummy.next);
  const result = [];
  while (sortedHead) {
    result.push(sortedHead.val);
    sortedHead = sortedHead.next;
  }
  console.log(result.join(' '));
});

题目12：最大数（拼接最大数字）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(String);
  nums.sort((a, b) => (b + a) - (a + b));
  if (nums[0] === '0') console.log('0');
  else console.log(nums.join(''));
});

题目13：合并区间

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const intervals = [];
  const parts = line.trim().split(' ');
  for (let i = 0; i < parts.length; i += 2) {
    intervals.push([parseInt(parts[i]), parseInt(parts[i + 1])]);
  }
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (let interval of intervals) {
    if (!merged.length || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }
  console.log(merged.flat().join(' '));
});

题目14：插入区间

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [newStart, newEnd, ...rest] = line.trim().split(' ').map(Number);
  const intervals = [];
  for (let i = 0; i < rest.length; i += 2) {
    intervals.push([rest[i], rest[i + 1]]);
  }
  const newInterval = [newStart, newEnd];
  const result = [];
  let i = 0;
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);
  while (i < intervals.length) result.push(intervals[i++]);
  console.log(result.flat().join(' '));
});

题目15：寻找重复数（二分+鸽巢原理）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  let left = 1, right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let count = 0;
    for (let num of nums) if (num <= mid) count++;
    if (count > mid) right = mid;
    else left = mid + 1;
  }
  console.log(left);
});

---

第8-10天：二叉树专题（25题）

前置：二叉树节点定义与输入处理（所有题目共用）

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 从数组构建二叉树（层序遍历格式，null表示空节点）
function buildTree(arr) {
  if (!arr || arr.length === 0 || arr[0] === null) return null;
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  while (queue.length && i < arr.length) {
    const node = queue.shift();
    if (arr[i] !== null && arr[i] !== undefined) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    if (i < arr.length && arr[i] !== null && arr[i] !== undefined) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

题目1：二叉树的前序遍历（递归+迭代）

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  // 递归
  function preorderRecur(node, res = []) {
    if (!node) return res;
    res.push(node.val);
    preorderRecur(node.left, res);
    preorderRecur(node.right, res);
    return res;
  }
  // 迭代
  function preorderIter(root) {
    if (!root) return [];
    const stack = [root], res = [];
    while (stack.length) {
      const node = stack.pop();
      res.push(node.val);
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
    return res;
  }
  console.log(preorderIter(root).join(' '));
});

题目2：二叉树的中序遍历（递归+迭代）

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function inorderIter(root) {
    const stack = [], res = [];
    let cur = root;
    while (cur || stack.length) {
      while (cur) {
        stack.push(cur);
        cur = cur.left;
      }
      cur = stack.pop();
      res.push(cur.val);
      cur = cur.right;
    }
    return res;
  }
  console.log(inorderIter(root).join(' '));
});

题目3：二叉树的后序遍历（递归+迭代）

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function postorderIter(root) {
    if (!root) return [];
    const stack = [root], res = [];
    while (stack.length) {
      const node = stack.pop();
      res.unshift(node.val);
      if (node.left) stack.push(node.left);
      if (node.right) stack.push(node.right);
    }
    return res;
  }
  console.log(postorderIter(root).join(' '));
});

题目4：二叉树的层序遍历

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  if (!root) {
    console.log('');
    return;
  }
  const queue = [root], res = [];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  console.log(res.map(l => l.join(' ')).join(' | '));
});

题目5：二叉树的最大深度

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function maxDepth(node) {
    if (!node) return 0;
    return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
  }
  console.log(maxDepth(root));
});

题目6：对称二叉树

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function isMirror(left, right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return left.val === right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left);
  }
  console.log(isMirror(root, root));
});

题目7：路径总和（是否存在根到叶子路径和等于target）

rl.on('line', (line) => {
  const [target, ...vals] = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(vals);
  function hasPathSum(node, sum) {
    if (!node) return false;
    if (!node.left && !node.right) return sum === node.val;
    return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
  }
  console.log(hasPathSum(root, target));
});

题目8：二叉树的所有路径

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  const res = [];
  function dfs(node, path) {
    if (!node) return;
    path += node.val;
    if (!node.left && !node.right) res.push(path);
    else {
      path += '->';
      dfs(node.left, path);
      dfs(node.right, path);
    }
  }
  dfs(root, '');
  console.log(res.join(' '));
});

题目9：翻转二叉树

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function invert(node) {
    if (!node) return null;
    [node.left, node.right] = [invert(node.right), invert(node.left)];
    return node;
  }
  const newRoot = invert(root);
  // 输出层序遍历结果
  const queue = [newRoot], out = [];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      out.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else out.push(null);
  }
  while (out[out.length - 1] === null) out.pop();
  console.log(out.join(' '));
});

题目10：二叉树的最近公共祖先

rl.on('line', (line) => {
  const [pVal, qVal, ...vals] = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(vals);
  function findNode(root, val) {
    if (!root) return null;
    if (root.val === val) return root;
    return findNode(root.left, val) || findNode(root.right, val);
  }
  const p = findNode(root, pVal);
  const q = findNode(root, qVal);
  function lowestCommonAncestor(node, p, q) {
    if (!node || node === p || node === q) return node;
    const left = lowestCommonAncestor(node.left, p, q);
    const right = lowestCommonAncestor(node.right, p, q);
    if (left && right) return node;
    return left || right;
  }
  const lca = lowestCommonAncestor(root, p, q);
  console.log(lca ? lca.val : -1);
});

题目11：二叉树的右视图

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  if (!root) {
    console.log('');
    return;
  }
  const queue = [root], rightView = [];
  while (queue.length) {
    let levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      if (i === levelSize - 1) rightView.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  console.log(rightView.join(' '));
});

题目12：从前序与中序遍历序列构造二叉树

rl.on('line', (line) => {
  const [preStr, inStr] = line.trim().split('|');
  const preorder = preStr.split(' ').map(Number);
  const inorder = inStr.split(' ').map(Number);
  const idxMap = new Map();
  inorder.forEach((val, idx) => idxMap.set(val, idx));
  function build(preStart, preEnd, inStart, inEnd) {
    if (preStart > preEnd) return null;
    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);
    const rootIdx = idxMap.get(rootVal);
    const leftSize = rootIdx - inStart;
    root.left = build(preStart + 1, preStart + leftSize, inStart, rootIdx - 1);
    root.right = build(preStart + leftSize + 1, preEnd, rootIdx + 1, inEnd);
    return root;
  }
  const root = build(0, preorder.length - 1, 0, inorder.length - 1);
  // 输出后序遍历验证
  function postorder(node, res = []) {
    if (!node) return res;
    postorder(node.left, res);
    postorder(node.right, res);
    res.push(node.val);
    return res;
  }
  console.log(postorder(root).join(' '));
});

题目13：验证二叉搜索树

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let prev = -Infinity;
  let isValid = true;
  function inorder(node) {
    if (!node || !isValid) return;
    inorder(node.left);
    if (node.val <= prev) isValid = false;
    prev = node.val;
    inorder(node.right);
  }
  inorder(root);
  console.log(isValid);
});

题目14：二叉搜索树中的搜索

rl.on('line', (line) => {
  const [target, ...vals] = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(vals);
  function searchBST(node, val) {
    if (!node) return null;
    if (node.val === val) return node;
    if (val < node.val) return searchBST(node.left, val);
    else return searchBST(node.right, val);
  }
  const subRoot = searchBST(root, target);
  // 输出子树层序遍历
  const queue = [subRoot], out = [];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      out.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else out.push(null);
  }
  while (out[out.length - 1] === null) out.pop();
  console.log(out.join(' '));
});

题目15：将有序数组转换为二叉搜索树

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  function sortedArrayToBST(left, right) {
    if (left > right) return null;
    const mid = Math.floor((left + right) / 2);
    const node = new TreeNode(nums[mid]);
    node.left = sortedArrayToBST(left, mid - 1);
    node.right = sortedArrayToBST(mid + 1, right);
    return node;
  }
  const root = sortedArrayToBST(0, nums.length - 1);
  // 输出前序遍历
  function preorder(node, res = []) {
    if (!node) return res;
    res.push(node.val);
    preorder(node.left, res);
    preorder(node.right, res);
    return res;
  }
  console.log(preorder(root).join(' '));
});

题目16：二叉树的锯齿形层序遍历

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  if (!root) {
    console.log('');
    return;
  }
  const queue = [root], result = [];
  let leftToRight = true;
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    if (!leftToRight) level.reverse();
    result.push(level);
    leftToRight = !leftToRight;
  }
  console.log(result.map(l => l.join(' ')).join(' | '));
});

题目17：二叉树中的最大路径和

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let maxSum = -Infinity;
  function maxGain(node) {
    if (!node) return 0;
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);
    const currentSum = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, currentSum);
    return node.val + Math.max(leftGain, rightGain);
  }
  maxGain(root);
  console.log(maxSum);
});

题目18：求根到叶子节点数字之和

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let total = 0;
  function dfs(node, curSum) {
    if (!node) return;
    curSum = curSum * 10 + node.val;
    if (!node.left && !node.right) total += curSum;
    dfs(node.left, curSum);
    dfs(node.right, curSum);
  }
  dfs(root, 0);
  console.log(total);
});

题目19：完全二叉树的节点个数

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function countNodes(node) {
    if (!node) return 0;
    let leftDepth = 0, rightDepth = 0;
    let left = node, right = node;
    while (left) { leftDepth++; left = left.left; }
    while (right) { rightDepth++; right = right.right; }
    if (leftDepth === rightDepth) return Math.pow(2, leftDepth) - 1;
    return 1 + countNodes(node.left) + countNodes(node.right);
  }
  console.log(countNodes(root));
});

题目20：二叉树展开为链表（原地，右指针）

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function flatten(node) {
    if (!node) return null;
    const leftTail = flatten(node.left);
    const rightTail = flatten(node.right);
    if (node.left) {
      leftTail.right = node.right;
      node.right = node.left;
      node.left = null;
    }
    return rightTail || leftTail || node;
  }
  flatten(root);
  // 输出右指针链表
  let cur = root;
  const res = [];
  while (cur) {
    res.push(cur.val);
    cur = cur.right;
  }
  console.log(res.join(' '));
});

题目21：填充每个节点的下一个右侧节点指针（完美二叉树）

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function connect(root) {
    if (!root) return null;
    let leftmost = root;
    while (leftmost.left) {
      let head = leftmost;
      while (head) {
        head.left.next = head.right;
        if (head.next) head.right.next = head.next.left;
        head = head.next;
      }
      leftmost = leftmost.left;
    }
    return root;
  }
  connect(root);
  // 输出层序遍历并显示next（简化：输出节点值）
  const queue = [root], out = [];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      out.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    }
  }
  console.log(out.join(' '));
});

题目22：二叉树中第二小的节点

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let first = root.val;
  let second = Infinity;
  function dfs(node) {
    if (!node) return;
    if (node.val > first && node.val < second) second = node.val;
    else if (node.val === first) {
      dfs(node.left);
      dfs(node.right);
    }
  }
  dfs(root);
  console.log(second === Infinity ? -1 : second);
});

题目23：二叉树的直径

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let diameter = 0;
  function depth(node) {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    diameter = Math.max(diameter, left + right);
    return Math.max(left, right) + 1;
  }
  depth(root);
  console.log(diameter);
});

题目24：二叉树的最小深度

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  function minDepth(node) {
    if (!node) return 0;
    if (!node.left) return minDepth(node.right) + 1;
    if (!node.right) return minDepth(node.left) + 1;
    return Math.min(minDepth(node.left), minDepth(node.right)) + 1;
  }
  console.log(minDepth(root));
});

题目25：左叶子之和

rl.on('line', (line) => {
  const arr = line.trim().split(' ').map(v => v === 'null' ? null : parseInt(v));
  const root = buildTree(arr);
  let sum = 0;
  function dfs(node, isLeft) {
    if (!node) return;
    if (isLeft && !node.left && !node.right) sum += node.val;
    dfs(node.left, true);
    dfs(node.right, false);
  }
  dfs(root, false);
  console.log(sum);
});

---

说明

• 所有代码均为完整可运行的Node.js脚本，使用 readline读取标准输入。
• 二叉树输入格式：层序遍历， null表示空节点，例如： 3 9 20 null null 15 7
• 输出格式根据题目要求调整，方便验证。

如果需要 **第11-13天：动态规划（15题）**或后续其他天数的答案，请告诉我。

Chain of Thought

我们继续：第5-6天排序和二分查找15题的完整JS答案，以及第8-10天二叉树专题25题的完整JS答案。我会分两部分给出。

---

🧑 User

再来第11-13天：动态规划（15题）的完整题目和js解答

---

🤖 DeepSeek AI

以下是 **第11-13天：动态规划（15题）**的完整JavaScript解答（ACM模式）。每道题均包含题目描述和可直接运行的代码。

---

第11-13天：动态规划（15题）

题目1：爬楼梯

描述：每次可以爬1或2个台阶，求爬到n阶有多少种方法。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const n = parseInt(line.trim());
  if (n <= 2) {
    console.log(n);
    return;
  }
  let dp1 = 1, dp2 = 2;
  for (let i = 3; i <= n; i++) {
    const temp = dp1 + dp2;
    dp1 = dp2;
    dp2 = temp;
  }
  console.log(dp2);
});

题目2：使用最小花费爬楼梯

描述：每阶有一个花费，可以从0或1开始，每次爬1或2阶，求到达顶楼的最小花费。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const cost = line.trim().split(' ').map(Number);
  const n = cost.length;
  let dp0 = 0, dp1 = 0; // dp0: 到达第0阶花费, dp1: 到达第1阶花费
  for (let i = 2; i <= n; i++) {
    const cur = Math.min(dp0 + cost[i - 2], dp1 + cost[i - 1]);
    dp0 = dp1;
    dp1 = cur;
  }
  console.log(dp1);
});

题目3：最大子数组和

描述：找出和最大的连续子数组，返回最大和。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  let maxSum = nums[0];
  let curSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curSum = Math.max(nums[i], curSum + nums[i]);
    maxSum = Math.max(maxSum, curSum);
  }
  console.log(maxSum);
});

题目4：打家劫舍

描述：不能偷相邻房屋，求能偷的最大金额。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  if (nums.length === 0) {
    console.log(0);
    return;
  }
  if (nums.length === 1) {
    console.log(nums[0]);
    return;
  }
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  console.log(prev1);
});

题目5：打家劫舍II（环形）

描述：房屋环形排列，首尾相连。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function robRange(nums, start, end) {
  let prev2 = nums[start];
  let prev1 = Math.max(nums[start], nums[start + 1]);
  for (let i = start + 2; i <= end; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const n = nums.length;
  if (n === 0) console.log(0);
  else if (n === 1) console.log(nums[0]);
  else if (n === 2) console.log(Math.max(nums[0], nums[1]));
  else {
    const res1 = robRange(nums, 0, n - 2);
    const res2 = robRange(nums, 1, n - 1);
    console.log(Math.max(res1, res2));
  }
});

题目6：不同路径

描述：m×n网格，从左上到右下，只能向右或向下，求不同路径数。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [m, n] = line.trim().split(' ').map(Number);
  const dp = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
  console.log(dp[n - 1]);
});

题目7：不同路径II（有障碍）

描述：网格中有障碍物（用1表示），求路径数。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const grid = [];
  const parts = line.trim().split('|');
  for (let part of parts) {
    grid.push(part.split(' ').map(Number));
  }
  const m = grid.length, n = grid[0].length;
  if (grid[0][0] === 1) {
    console.log(0);
    return;
  }
  const dp = new Array(n).fill(0);
  dp[0] = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dp[j] = 0;
        continue;
      }
      if (j > 0 && grid[i][j - 1] !== 1) {
        dp[j] += dp[j - 1];
      }
    }
  }
  console.log(dp[n - 1]);
});

题目8：最小路径和

描述：从左上到右下，路径上数字和最小。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const grid = [];
  const parts = line.trim().split('|');
  for (let part of parts) {
    grid.push(part.split(' ').map(Number));
  }
  const m = grid.length, n = grid[0].length;
  const dp = new Array(n).fill(0);
  dp[0] = grid[0][0];
  for (let j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
  for (let i = 1; i < m; i++) {
    dp[0] += grid[i][0];
    for (let j = 1; j < n; j++) {
      dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
    }
  }
  console.log(dp[n - 1]);
});

题目9：三角形最小路径和

描述：给定三角形，从顶部到底部的最小路径和。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const triangle = [];
  const parts = line.trim().split('|');
  for (let part of parts) {
    triangle.push(part.split(' ').map(Number));
  }
  const dp = triangle[triangle.length - 1].slice();
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
    }
  }
  console.log(dp[0]);
});

题目10：最长递增子序列

描述：求最长严格递增子序列的长度。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const tails = [];
  for (let num of nums) {
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    tails[left] = num;
  }
  console.log(tails.length);
});

题目11：最长公共子序列

描述：给定两个字符串，求最长公共子序列长度。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [text1, text2] = line.trim().split(' ');
  const m = text1.length, n = text2.length;
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  console.log(dp[m][n]);
});

题目12：分割等和子集

描述：判断能否将数组分割成两个和相等的子集（0-1背包）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) {
    console.log(false);
    return;
  }
  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (let num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  console.log(dp[target]);
});

题目13：目标和

描述：给数组每个数前加+或-，使得和为target，求表达式数目。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...nums] = line.trim().split(' ').map(Number);
  const sum = nums.reduce((a, b) => a + b, 0);
  if ((sum + target) % 2 !== 0 || Math.abs(target) > sum) {
    console.log(0);
    return;
  }
  const subsetSum = (sum + target) / 2;
  const dp = new Array(subsetSum + 1).fill(0);
  dp[0] = 1;
  for (let num of nums) {
    for (let j = subsetSum; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }
  console.log(dp[subsetSum]);
});

题目14：完全平方数

描述：给定整数n，求最少需要几个完全平方数（1,4,9,...）相加得到n。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const n = parseInt(line.trim());
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  console.log(dp[n]);
});

题目15：单词拆分

描述：给定字符串s和单词字典，判断s是否能被分割成字典中的单词。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [s, ...dict] = line.trim().split(' ');
  const wordSet = new Set(dict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  console.log(dp[s.length]);
});

---

使用说明

• 输入格式：每道题按常见方式设计（空格分隔、单行或多行等）。
• 动态规划题目通常需要转化为一维或二维DP，代码已做空间优化。
• 可直接复制到牛客网华为机试环境或本地Node.js运行。

如果需要 **第15-17天：回溯和DFS/BFS（20题）**或其他部分，请继续告诉我。

Chain of Thought

我们继续提供第11-13天：动态规划（15题） 的完整JavaScript解答（ACM模式）。每道题均包含题目描述和可直接运行的代码。 描述：每次可以爬1或2个台阶，求爬到n阶有多少种方法。 描述：每阶有一个花费，可以从0或1开始，每次爬1或2阶，求到达顶楼的最小花费。 描述：找出和最大的连续子数组，返回最大和。 描述：不能偷相邻房屋，求能偷的最大金额。 描述：房屋环形排列，首尾相连。 描述：m×n网格，从左上到右下，只能向右或向下，求不同路径数。 描述：网格中有障碍物（用1表示），求路径数。 描述：从左上到右下，路径上数字和最小。 描述：给定三角形，从顶部到底部的最小路径和。 描述：求最长严格递增子序列的长度。 描述：给定两个字符串，求最长公共子序列长度。 描述：判断能否将数组分割成两个和相等的子集（0-1背包）。 描述：给数组每个数前加+或-，使得和为target，求表达式数目。 描述：给定整数n，求最少需要几个完全平方数（1,4,9,...）相加得到n。 描述：给定字符串s和单词字典，判断s是否能被分割成字典中的单词。 输入格式：每道题按常见方式设计（空格分隔、单行或多行等）。 动态规划题目通常需要转化为一维或二维DP，代码已做空间优化。 可直接复制到牛客网华为机试环境或本地Node.js运行。 如果需要第15-17天：回溯和DFS/BFS（20题） 或其他部分，请继续告诉我。

---

🧑 User

再给出第15-17天：回溯和DFS/BFS（20题）的完整题目和js解答

---

🤖 DeepSeek AI

以下是 **第15-17天：回溯和DFS/BFS（20题）**的完整JavaScript解答（ACM模式）。每道题包含题目描述、输入输出处理和完整代码，可直接在牛客网或本地Node.js环境运行。

---

题目1：全排列

描述：给定一个不含重复数字的数组，返回所有可能的全排列。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }
  backtrack();
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目2：全排列II（含重复元素）

描述：给定一个可包含重复数字的数组，返回所有不重复的全排列。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  let nums = line.trim().split(' ').map(Number);
  nums.sort((a, b) => a - b);
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }
  backtrack();
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目3：子集

描述：给定一个不含重复元素的数组，返回所有可能的子集（幂集）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const nums = line.trim().split(' ').map(Number);
  const result = [];
  const path = [];
  function backtrack(start) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(0);
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目4：子集II（含重复元素）

描述：给定一个可能包含重复元素的数组，返回所有不重复的子集。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  let nums = line.trim().split(' ').map(Number);
  nums.sort((a, b) => a - b);
  const result = [];
  const path = [];
  function backtrack(start) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(0);
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目5：组合总和

描述：给定无重复元素数组和目标值，找出所有组合（可重复使用元素）使其和等于目标。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...candidates] = line.trim().split(' ').map(Number);
  const result = [];
  const path = [];
  function backtrack(start, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backtrack(i, sum + candidates[i]);
      path.pop();
    }
  }
  backtrack(0, 0);
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目6：组合总和II

描述：给定可能有重复元素的数组和目标值，找出所有组合（每个元素只能用一次），结果不重复。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, ...candidates] = line.trim().split(' ').map(Number);
  candidates.sort((a, b) => a - b);
  const result = [];
  const path = [];
  function backtrack(start, sum) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      path.push(candidates[i]);
      backtrack(i + 1, sum + candidates[i]);
      path.pop();
    }
  }
  backtrack(0, 0);
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目7：电话号码的字母组合

描述：给定数字字符串（2-9），返回所有可能的字母组合（手机九宫格）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const digits = line.trim();
  if (!digits) {
    console.log('');
    return;
  }
  const map = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
  };
  const result = [];
  function backtrack(idx, path) {
    if (idx === digits.length) {
      result.push(path);
      return;
    }
    const letters = map[digits[idx]];
    for (let ch of letters) {
      backtrack(idx + 1, path + ch);
    }
  }
  backtrack(0, '');
  console.log(result.join(' '));
});

题目8：括号生成

描述：给定n对括号，生成所有有效的括号组合。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const n = parseInt(line.trim());
  const result = [];
  function backtrack(left, right, path) {
    if (left === n && right === n) {
      result.push(path);
      return;
    }
    if (left < n) backtrack(left + 1, right, path + '(');
    if (right < left) backtrack(left, right + 1, path + ')');
  }
  backtrack(0, 0, '');
  console.log(result.join(' '));
});

题目9：分割回文串

描述：给定字符串，将其分割成若干回文子串，返回所有可能的分割方案。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function isPalindrome(s, l, r) {
  while (l < r) if (s[l++] !== s[r--]) return false;
  return true;
}

rl.on('line', (line) => {
  const s = line.trim();
  const result = [];
  const path = [];
  function backtrack(start) {
    if (start === s.length) {
      result.push([...path]);
      return;
    }
    for (let end = start; end < s.length; end++) {
      if (isPalindrome(s, start, end)) {
        path.push(s.substring(start, end + 1));
        backtrack(end + 1);
        path.pop();
      }
    }
  }
  backtrack(0);
  console.log(result.map(arr => arr.join(' ')).join(', '));
});

题目10：岛屿数量（DFS/BFS）

描述：二维网格（'1'陆地，'0'水），求岛屿数量（上下左右相连）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let grid = [];
let m, n;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];

function dfs(x, y) {
  if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] !== '1') return;
  grid[x][y] = '0';
  for (let [dx, dy] of dirs) dfs(x + dx, y + dy);
}

rl.on('line', (line) => {
  if (!line.trim()) return;
  grid.push(line.trim().split(''));
});
rl.on('close', () => {
  m = grid.length;
  if (m === 0) { console.log(0); return; }
  n = grid[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }
  console.log(count);
});

题目11：岛屿的最大面积

描述：求最大岛屿面积（连通'1'的格子数）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let grid = [];
let m, n;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];

function dfs(x, y) {
  if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] !== 1) return 0;
  grid[x][y] = 0;
  let area = 1;
  for (let [dx, dy] of dirs) area += dfs(x + dx, y + dy);
  return area;
}

rl.on('line', (line) => {
  if (!line.trim()) return;
  grid.push(line.trim().split(' ').map(Number));
});
rl.on('close', () => {
  m = grid.length;
  if (m === 0) { console.log(0); return; }
  n = grid[0].length;
  let maxArea = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        maxArea = Math.max(maxArea, dfs(i, j));
      }
    }
  }
  console.log(maxArea);
});

题目12：被围绕的区域

描述：二维矩阵，'X'和'O'，将被'X'包围的'O'全部变成'X'（边界上的'O'不被包围）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let board = [];
let m, n;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];

function dfs(x, y) {
  if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] !== 'O') return;
  board[x][y] = '#';
  for (let [dx, dy] of dirs) dfs(x + dx, y + dy);
}

rl.on('line', (line) => {
  if (!line.trim()) return;
  board.push(line.trim().split(' '));
});
rl.on('close', () => {
  m = board.length;
  if (m === 0) { console.log(''); return; }
  n = board[0].length;
  // 标记边界上的O
  for (let i = 0; i < m; i++) {
    if (board[i][0] === 'O') dfs(i, 0);
    if (board[i][n-1] === 'O') dfs(i, n-1);
  }
  for (let j = 0; j < n; j++) {
    if (board[0][j] === 'O') dfs(0, j);
    if (board[m-1][j] === 'O') dfs(m-1, j);
  }
  // 转换
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      else if (board[i][j] === '#') board[i][j] = 'O';
    }
  }
  console.log(board.map(row => row.join(' ')).join('\n'));
});

题目13：单词搜索

描述：二维网格，判断是否存在给定单词（相邻格子组成，不可重复使用）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let board = [];
let word = '';
let m, n;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];

function dfs(x, y, idx) {
  if (idx === word.length) return true;
  if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] !== word[idx]) return false;
  const temp = board[x][y];
  board[x][y] = '#';
  for (let [dx, dy] of dirs) {
    if (dfs(x + dx, y + dy, idx + 1)) return true;
  }
  board[x][y] = temp;
  return false;
}

let lines = [];
rl.on('line', (line) => {
  lines.push(line.trim());
});
rl.on('close', () => {
  word = lines[0];
  for (let i = 1; i < lines.length; i++) {
    board.push(lines[i].split(''));
  }
  m = board.length;
  n = board[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, 0)) {
        console.log(true);
        return;
      }
    }
  }
  console.log(false);
});

题目14：小华地图寻宝（华为真题）

描述：m×n矩阵，从(0,0)出发，可上下左右移动，要求坐标数位之和≤k，求可到达的格子数。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

function digitSum(num) {
  let sum = 0;
  while (num > 0) { sum += num % 10; num = Math.floor(num / 10); }
  return sum;
}

rl.on('line', (line) => {
  const [m, n, k] = line.trim().split(' ').map(Number);
  const visited = Array.from({ length: m }, () => new Array(n).fill(false));
  let count = 0;
  const queue = [[0, 0]];
  visited[0][0] = true;
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  while (queue.length) {
    const [x, y] = queue.shift();
    count++;
    for (let [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] &&
          digitSum(nx) + digitSum(ny) <= k) {
        visited[nx][ny] = true;
        queue.push([nx, ny]);
      }
    }
  }
  console.log(count);
});

题目15：腐烂的橘子（多源BFS）

描述：网格中0空，1新鲜，2腐烂。每分钟腐烂橘子会感染上下左右新鲜橘子，求全部腐烂所需分钟数，否则-1。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let grid = [];
rl.on('line', (line) => {
  if (!line.trim()) return;
  grid.push(line.trim().split(' ').map(Number));
});
rl.on('close', () => {
  const m = grid.length, n = grid[0].length;
  let fresh = 0;
  const queue = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j, 0]);
      else if (grid[i][j] === 1) fresh++;
    }
  }
  if (fresh === 0) { console.log(0); return; }
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  let minutes = 0;
  while (queue.length) {
    const [x, y, t] = queue.shift();
    minutes = t;
    for (let [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1) {
        grid[nx][ny] = 2;
        fresh--;
        queue.push([nx, ny, t + 1]);
      }
    }
  }
  console.log(fresh === 0 ? minutes : -1);
});

题目16：打开转盘锁（BFS）

描述：四位密码锁，初始"0000"，每次旋转一个拨轮（+1或-1），给定死亡数字列表，求到目标的最少步数，不能经过死亡数字。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [target, deadStr] = line.trim().split(' ');
  const deadends = deadStr.split(',');
  const deadSet = new Set(deadends);
  if (deadSet.has('0000')) { console.log(-1); return; }
  const queue = [['0000', 0]];
  const visited = new Set(['0000']);
  while (queue.length) {
    const [cur, step] = queue.shift();
    if (cur === target) { console.log(step); return; }
    for (let i = 0; i < 4; i++) {
      for (let delta of [-1, 1]) {
        let digit = (parseInt(cur[i]) + delta + 10) % 10;
        let next = cur.slice(0, i) + digit + cur.slice(i + 1);
        if (!deadSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, step + 1]);
        }
      }
    }
  }
  console.log(-1);
});

题目17：二进制矩阵中的最短路径（BFS）

描述：n×n网格，0可走，1障碍，从(0,0)到(n-1,n-1)，每次8方向（可斜走），求最短路径长度，不存在返回-1。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let grid = [];
rl.on('line', (line) => {
  if (!line.trim()) return;
  grid.push(line.trim().split(' ').map(Number));
});
rl.on('close', () => {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n-1][n-1] === 1) { console.log(-1); return; }
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  const queue = [[0, 0, 1]];
  const visited = Array.from({ length: n }, () => new Array(n).fill(false));
  visited[0][0] = true;
  while (queue.length) {
    const [x, y, dist] = queue.shift();
    if (x === n-1 && y === n-1) { console.log(dist); return; }
    for (let [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 0 && !visited[nx][ny]) {
        visited[nx][ny] = true;
        queue.push([nx, ny, dist + 1]);
      }
    }
  }
  console.log(-1);
});

题目18：单词接龙（BFS）

描述：给定开始单词、结束单词、单词列表，每次改变一个字母变成列表中的单词，求最短转换序列长度（包含开始单词），不存在返回0。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const [beginWord, endWord, ...wordList] = line.trim().split(' ');
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) { console.log(0); return; }
  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  while (queue.length) {
    const [cur, step] = queue.shift();
    if (cur === endWord) { console.log(step); return; }
    for (let i = 0; i < cur.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const next = cur.slice(0, i) + String.fromCharCode(c) + cur.slice(i + 1);
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, step + 1]);
        }
      }
    }
  }
  console.log(0);
});

题目19：N皇后

描述：n皇后问题，返回所有不同解（'Q'和'.'表示棋盘）。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

rl.on('line', (line) => {
  const n = parseInt(line.trim());
  const result = [];
  const cols = new Set();
  const diag1 = new Set(); // r + c
  const diag2 = new Set(); // r - c
  const board = new Array(n).fill(0).map(() => new Array(n).fill('.'));
  function backtrack(row) {
    if (row === n) {
      result.push(board.map(row => row.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;
      cols.add(col);
      diag1.add(row + col);
      diag2.add(row - col);
      board[row][col] = 'Q';
      backtrack(row + 1);
      board[row][col] = '.';
      cols.delete(col);
      diag1.delete(row + col);
      diag2.delete(row - col);
    }
  }
  backtrack(0);
  console.log(result.map(board => board.join(',')).join('|'));
});

题目20：解数独

描述：填写数独（9x9），空位用'.'表示，返回填充后的棋盘。

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });

let board = [];
rl.on('line', (line) => {
  if (!line.trim()) return;
  board.push(line.trim().split(' '));
});
rl.on('close', () => {
  function isValid(board, row, col, num) {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num || board[i][col] === num) return false;
    }
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[startRow + i][startCol + j] === num) return false;
      }
    }
    return true;
  }
  function solve() {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === '.') {
          for (let num = 1; num <= 9; num++) {
            const ch = num.toString();
            if (isValid(board, i, j, ch)) {
              board[i][j] = ch;
              if (solve()) return true;
              board[i][j] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  solve();
  console.log(board.map(row => row.join(' ')).join('\n'));
});

---

使用说明

• 输入格式按常见题目设计，例如数组元素空格分隔，矩阵行用空格或换行等。
• 所有代码均为完整可运行脚本，可直接在牛客网或本地测试。
• 回溯类题目注意剪枝和去重；BFS类题目注意方向数组和visited。

如果需要 **第18-20天：贪心和数学题（15题）**或后续内容，请继续告诉我。

Chain of Thought

我们继续提供第15-17天：回溯和DFS/BFS（20题）的完整题目和JS解答。注意，回溯和DFS/BFS在华为机试中非常高频，需要重点掌握。 由于题目较多，我会给出20道经典题目的完整代码，每题都包含题目描述、输入输出处理。为了保证代码可以直接运行，我会使用Node.js的readline接口，并按常见输入格式设计。 以下是20道题目的列表（按难度和类型排列）： 全排列 全排列II（含重复元素） 子集 子集II（含重复元素） 组合总和 组合总和II 电话号码的字母组合 括号生成 分割回文串 岛屿数量（DFS/BFS） 岛屿的最大面积 被围绕的区域 单词搜索 小华地图寻宝（数位和，华为真题） 腐烂的橘子（多源BFS） 打开转盘锁（BFS） 二进制矩阵中的最短路径（BFS） 单词接龙（BFS） N皇后 解数独 我会为每道题提供详细代码。由于代码量较大，我会分块给出，但确保所有题目都在这个回答中。为了清晰，我会使用标题分隔。