备考中的小插曲：五道算法题的思考与 CSharp 解答
Doc Map
前言
最近真的是一头扎进了数据结构的海洋里，感觉自己成了一个活生生的节点（Node），被各种指针（Pointer）和引用（Reference）牵着鼻子走。和之前啃计组的时候差不多，这一块对我来说也是“硬骨头”。老实说，我是从大三才正式开始刷 LeetCode 的，大一大二几乎没怎么碰过算法题，偶尔兴致来了刷几道最终也会因为难题而放弃，所以刚开始的时候真的挺劝退的。计组已经够难了，现在又要天天和各种指针、递归死磕，脑子简直要打结。
但奇怪的是，虽然经常被题目虐得头大，每次通过测试用例的时候，那种小小的成就感就像打游戏升级一样，会让我觉得：行吧，还是值得坚持。说真的，刷题这事儿，一旦入了门，还挺上头的。它不像那些死记硬背的知识，算法是活的，每一次 AC (Accepted) 就像是成功解锁了一个新成就，爽得不行。
我选的语言是 C# —— 虽然计组课程我选择了 C 语言（毕竟计算机硬件底层知识的学习，C 作为最接近底层的高级语言确实更合适），但在算法学习的道路上，我想坚持使用 C#。
说实话，在国内算法圈，C# 确实不像 C++ 和 Java 那样主流，但这恰恰让我更想证明它的实力。C# 的优雅设计让我在学习过程中享受到了编程的乐趣 —— LINQ 的表达力让复杂操作变得简洁明了，.NET 集合类库的完善设计让算法实现更加得心应手。
很多人对 C# 有刻板印象，认为它偏应用层、不适合算法竞赛，但我偏不信这个邪！通过实际的刷题经历，我深深体会到：语言的优雅不会限制算法的表达，反而能让解决方案更加清晰高效。C# 在算法实现上同样能够写出简洁、高效的代码，这一点在我解决各种数据结构问题时得到了充分验证。
这次我挑了五道比较经典的题目，有入门必备的“开胃菜”，也有能让你对数据结构理解更深的“硬菜”。咱们就不摆什么高大上的理论了，还是用点日常的思路，一起看看这些题能怎么玩。（以下看法仅供参考学习）
哈希表的优雅——两数之和 (Two Sum)
给定一个整数数组 nums 和一个目标值 target，在数组中找出和为目标值的两个整数，并返回它们的数组下标。
示例：
输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]解题思路
初看题目，直觉就是双重循环暴力破解：
// 暴力解法 - O(n²)
for (int i = 0; i < nums.Length; i++)
{
for (int j = i + 1; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
{
return new int[] { i, j };
}
}
}但算法的追求是效率！如果你的数据量非常庞大呢？O(n²) 在大数据量时完全不可行。
核心思路：查字典的艺术
想象你要找数字 B 满足 A + B = T，即 B = T - A。
与其在数组中线性查找，不如用 Dictionary 记录已遍历的数字和位置：
- 遍历到数字 A 时，检查字典是否存在值 T - A
- 存在则找到答案，不存在则将 A 存入字典
C# 实现
public int[] TwoSum(int[] nums, int target)
{
Dictionary<int, int> numMap = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (numMap.TryGetValue(complement, out int complementIndex))
{
return new int[] { complementIndex, i };
}
numMap[nums[i]] = i;
}
throw new ArgumentException("No two sum solution");
}总结反思
哈希表以空间换时间：牺牲 O(n) 空间复杂度，将时间复杂度从 O(n²) 优化到 O(n)。这种思想在查找、计数、去重等问题中广泛应用。
反转链表 (Reverse Linked List)
反转一个单链表
示例：
输入：1→2→3→4→5→NULL
输出：5→4→3→2→1→NULL解题心路
链表操作最怕指针错乱！反转链表时，稍不留神就会”断链”，让后面的节点彻底失联。
核心思路：“三剑客”迭代法
需要三个指针默契配合：
- prev：指向已反转部分的头节点
- current：当前处理节点
- nextTemp：临时保存下一节点
就像改造流水线：先记录下一工序，修改当前连接，然后指针前进。
C# 实现
public ListNode ReverseList(ListNode head)
{
ListNode prev = null;
ListNode current = head;
while (current != null)
{
ListNode nextTemp = current.next; // 保存下一跳
current.next = prev; // 反转指向
prev = current; // prev 前进
current = nextTemp; // current 前进
}
return prev; // 新头节点
}总结反思
链表操作，画图是王道！理解三个指针的配合，就掌握了链表操作的核心：修改引用前务必备份。迭代法的 O(1) 空间复杂度在实际应用中更优。
有效的括号 (Valid Parentheses)
给定只包含 (){}[] 的字符串，判断括号是否有效。
有效条件：
- 左括号必须用相同类型右括号闭合
- 左括号必须以正确顺序闭合
解题心路
最初以为简单计数就行，直到遇到 ([]){} 正确而 ([)] 错误的情况！顺序是关键，这让我想到叠盘子：先放的后取。
核心思路：栈的完美应用
栈 (Stack) 的后进先出特性完美匹配括号规则：
- 遇左括号：入栈
- 遇右括号：检查栈顶是否匹配
- 最终栈空则有效
C# 实现
public bool IsValid(string s)
{
if (s.Length % 2 != 0)
return false;
Stack<char> stack = new Stack<char>();
Dictionary<char, char> mappings = new Dictionary<char, char>
{
{ ')', '(' },
{ ']', '[' },
{ '}', '{' }
};
foreach (char c in s)
{
if (mappings.ContainsKey(c))
{
char topElement = stack.Count == 0 ? '#' : stack.Pop();
if (topElement != mappings[c])
return false;
}
else
{
stack.Push(c);
}
}
return stack.Count == 0;
}总结反思
栈在”撤销操作”、“历史记录”、“最近优先”等场景中威力巨大。浏览器的前进后退、编译器语法解析都离不开栈。
合并两个有序数组
将两个非递减顺序排列的数组合并到 nums1 中，结果同样有序。
注意： 结果存储在 nums1 中，nums1 长度为 m + n。
解题心路
暴力解法直接复制后排序：
Array.Copy(nums2, 0, nums1, m, n);
Array.Sort(nums1); // O((m+n)log(m+n))但这浪费了数组已排序的重要信息！
核心思路：倒序合并，避免覆盖
从尾部开始比较，避免从头合并时的覆盖问题：
- p1：nums1 有效末尾
- p2：nums2 末尾
- p：合并位置
比较两数组末尾元素，较大者放入合并位置。
C#实现
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0)
{
nums1[p--] = (nums1[p1] >= nums2[p2]) ? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0)
{
nums1[p--] = nums2[p2--];
}
}总结与反思
双指针 + 逆向思维 是数组原地操作的黄金法则。利用有序性和额外空间，时间复杂度优化到 O(m+n)。
二叉树的中序遍历
给定二叉树根节点，返回中序遍历结果。
挑战： 递归简单，能否用迭代实现？
解题心路
递归写法简单优雅：
private void InorderHelper(TreeNode node, IList<int> result)
{
if (node == null)
return;
InorderHelper(node.left, result); // 左
result.Add(node.val); // 根
InorderHelper(node.right, result); // 右
}但递归使用系统栈，树过深可能栈溢出。
核心思路：手动栈模拟递归
用 Stack
- 一直向左，节点入栈
- 走到尽头，弹出栈顶（根）并处理
- 转向右子树重复过程
C# 迭代实现
public IList<int> InorderTraversal(TreeNode root)
{
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || stack.Count > 0)
{
while (current != null) // 一直向左
{
stack.Push(current);
current = current.left;
}
TreeNode node = stack.Pop(); // 处理根节点
result.Add(node.val);
current = node.right; // 转向右子树
}
return result;
}总结反思
- 递归：人类思维，简洁优雅
- 迭代：计算机底层，栈显式控制
掌握迭代中序遍历，前序、后序只是处理时机和入栈顺序的调整。
结语
终于把这五道题写完了，感觉不光是输出了一篇博客，更像是一次对知识的再梳理。写下来、讲出来，本身就是最好的复习方式。
虽然我现在才刚刚开始刷 LeetCode，但我越来越相信一句话：坚持，就是最好的算法。刷题就像打怪升级，Two Sum 让我觉得我行了，结果链表指针把我绕晕，树又让我逻辑大乱。但只要硬着头皮坚持，画图、调试、再画图，总能慢慢发现：每一道题背后，都有一套优雅而简洁的逻辑在等着你。
说到底，数据结构和算法并不是冰冷的符号，它其实是一门关于“如何处理信息”的艺术。解题不是目的，真正的收获是逻辑思维和抽象能力的提升。
所以，备考的伙伴们，一起加油！别怕那些看不懂的 O(n log n)，也别被 O(1) 吓到。记住，每一次 AC，每一次你用 O(n) 战胜 O(n²) 的暴力解法，都是在节省计算资源，创造更高效的可能。这就是我们未来程序员的浪漫。
碎碎念的最后一句： 累了就看看天空，但别忘了，你的 Stack 里，还压着一个 “明天要解决的 BUG” 呢！加油！