备考中的小插曲：五道算法题的思考与 CSharp 解答 Verified

前言

最近真的是一头扎进了数据结构的海洋里，感觉自己成了一个活生生的节点（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” 呢！加油！