计算机学习笔记 力扣真题带练

📚 7月28日课程复习笔记：算法入门与核心能力训练（详细版）

本次课程以现场刷题为核心，通过实战演练的方式，系统讲解了多个经典算法问题的解法。课程不仅关注具体题目的实现，更强调了高效解题所需的核心能力，如快速阅读、瞬时记忆和心算能力，旨在帮助学员建立竞赛级的解题状态。

第一部分：算法训练规范与目标

• 训练目标：通过完成不同难度的算法题来提升编程能力，最终目标是获得算法竞赛的省三、省一乃至国一奖项。
• 时间标准：课程规定了严格的解题时限，超时完成则视为无效。这是衡量是否真正掌握知识的关键标准。
  • 简单题：10分钟内完成（15分钟算半题）。
  • 中等题：25分钟内完成（35分钟算半题）。
  • 困难题：40分钟内完成（55分钟算半题）。
• 学习原则：强调必须在规定时间内独立完成题目，培养“读完题即出思路”的高效状态。拖延时间学会的知识不算真正掌握。建议通过刷题（如200道简单题）来达到省三水平，再通过挑战中等和困难题目来进一步提升。

第二部分：核心算法题精讲

1. 字符串处理：千分位分隔符

• 题目：给定一个整数n，要求从右往左每隔三位添加一个点.作为千分位分隔符，并返回字符串。
• 解法一：字符串操作
  1. 将整数转换为字符串。
  2. 从后往前遍历字符串，每处理三位字符就插入一个点。
  3. 对于题目给定的数据范围（最多10位），直接使用字符串拼接的性能损耗可以忽略。
• 解法二：数学运算
  1. 通过% 10和/ 10操作逐位取出数字。
  2. 同样从后往前拼接，每三位加点。
• 优化与关键点：
  • 性能考量：如果数字特别长（如1000位），字符串拼接会频繁创建新对象，影响性能。此时应使用StringBuilder或预分配固定大小的char数组来处理，最后再转成字符串，这样可以显著降低内存消耗。
  • 边界情况：注意数字不足三位时保持不变。从后往前处理是核心思路。
  • 循环控制：需要一个计数器来跟踪拼接次数，达到三次就执行加点操作。

2. 完全二叉树的最近公共祖先 (LCA)

• 题目：在一个完全二叉树中，找到两个指定节点的最近公共祖先。
• 核心思想：利用完全二叉树的特性，可以通过数组索引来模拟树的结构，从而快速定位父子关系。
• 数组映射规律：
  • 对于任意节点i，其左子节点编号为2*i + 1，右子节点编号为2*i + 2。
  • 反过来，对于任意子节点j，其父节点编号为(j-1) / 2（若j为奇数，是左子节点）或(j-2) / 2（若j为偶数，是右子节点）。
• 解法：
  1. 分别追溯两个目标节点的祖先路径，直到根节点。
  2. 比较两条路径，第一个重合的节点即为最近公共祖先。
• 遍历方式：
  • 广度优先遍历 (BFS)：借助队列实现层级遍历。处理父节点前，需先将其子节点入队。遍历时，即使子节点为空（null），也需存入数组，以准确还原树的结构关系。
  • 深度优先遍历 (DFS)：使用递归实现，代码更简洁。可以从上往下快速定位目标节点。

3. 字符串数值转换与求和

• 题目：将字符串中的每个字母转换为其在字母表中的位置值（a=0, b=1, ...），然后将这些数字按顺序连接成一个整数。判断两个字符串转换后的数值之和是否等于目标字符串的数值。
• 解法：
  • 字符转数字：利用ASCII码的连续性，通过字符 - 'a'即可得到其对应的数值，无需复杂的if判断。
  • 数字拼接：遍历字符串，将每个字符转换后的数值拼接到结果中。拼接逻辑为：result = result * 10 + new_digit。
• 关键点：理解字符在内存中是连续编码的，这是该算法成立的底层基础。

4. 数组操作：正整数与-1

• 题目：给定一个包含正整数和-1的数组，需要为每个-1找到一个对应的正整数。规则是：正整数被添加到结果数组的头部；遇到-1时，统计从当前位置开始连续的-1的个数k，若k不超过结果数组的长度，则取出第k个元素添加到结果数组；若k超过长度，则添加-1。
• 解法：
  • 遍历原数组，根据遇到的元素类型（正整数或-1）执行相应操作。
  • 需要一个变量来标记上一个数是否为-1，以正确统计连续的-1个数k。
• 关键点：这道题极其考验瞬时记忆力和对复杂规则的理解能力。题干描述繁琐，需要耐心梳理逻辑。可以尝试用“倒序取数”的思路来规避“整体前移”的性能损耗。

第三部分：解题核心能力要求

课程强调，算法竞赛不仅是编程能力的比拼，更是综合素质的较量。

• 高效阅读：读题速度要快，能在2-3分钟内快速理解题意，抓住核心规则。
• 瞬时记忆力：需要高度集中注意力，准确记住题目的所有细节和规则，避免过度依赖草稿纸。
• 大脑计算速度：提升心算和瞬时推演能力，能在脑海中快速模拟多种解决方案，减少对纸笔的依赖。
• 心态调整：面对长题干和复杂逻辑时，要保持耐心和专注，将其视为对心理素质的考验。长题干不仅是考点，更是心理战，专门用来淘汰心态浮躁的参赛者。