三道经典算法题的 C 语言实现

今天来分享三道非常经典的算法题目分别涉及栈、链表和贪心算法。对于刚接触 C 语言函数的朋友来说这些题目既能巩固基础语法又能建立对常见数据结构的直观理解。一、有效的括号LeetCode 20题目描述给定一个只包括(、)、{、}、[、]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的相同类型的左括号思路分析这道题的核心是匹配和顺序。想象一下你正在逐字阅读这个字符串遇到左括号(、[、{时先把它记下来因为还不知道它什么时候会被闭合遇到右括号)、]、}时需要找最近的一个未匹配的左括号来配对这种后进先出的特性正是栈Stack的经典应用场景。在 C 语言中我们可以用一个字符数组来模拟栈遇到左括号 → 压入栈顶 遇到右括号 → 取出栈顶元素看是否匹配C 语言代码#include stdbool.h #include string.h bool isValid(char* s) { int len strlen(s); // 栈最多需要容纳所有字符 char stack[len]; int top -1; // 栈顶指针-1 表示栈空 for (int i 0; i len; i) { char c s[i]; // 左括号压栈 if (c ( || c [ || c {) { stack[top] c; } // 右括号尝试匹配 else { // 栈为空没有左括号可以匹配 if (top -1) return false; char topChar stack[top--]; // 弹出栈顶 // 检查是否匹配 if (c ) topChar ! () return false; if (c ] topChar ! [) return false; if (c } topChar ! {) return false; } } // 全部匹配完栈应该为空 return top -1; }关键点用数组stack和索引top模拟栈的操作top是入栈top--是出栈最后一定要检查栈是否为空——如果还有剩余的左括号说明不匹配二、合并两个有序链表题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。思路分析想象有两条已经排好队的队伍链表 1 和链表 2现在要合并成一条新队伍仍然保持从小到大排列。方法很简单每次从两个队伍的队首各取一人把较小的那个放到新队伍中。如果某一队已经没人了直接把另一队剩下的人接上去即可。在 C 语言中链表节点通常用结构体表示每个节点包含数据和一个指向下一个节点的链接。C 语言代码#include stdlib.h // 链表节点的定义 struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { // 创建一个虚拟头节点简化边界情况处理 struct ListNode dummy; struct ListNode *tail dummy; dummy.next NULL; // 同时遍历两个链表 while (list1 ! NULL list2 ! NULL) { if (list1-val list2-val) { tail-next list1; // 把 list1 的当前节点接上去 list1 list1-next; // list1 指针后移 } else { tail-next list2; // 把 list2 的当前节点接上去 list2 list2-next; // list2 指针后移 } tail tail-next; // 新链表的尾指针也后移 } // 其中一个链表已经遍历完直接把另一个链表剩余部分接上 if (list1 ! NULL) { tail-next list1; } else { tail-next list2; } return dummy.next; }关键点dummy虚拟头节点技巧避免单独处理新链表为空的特殊情况让代码更简洁tail始终指向新链表的最后一个节点循环结束后最多只有一个链表还有剩余节点直接链接即可三、买卖股票的最佳时机题目描述给定一个数组prices它的第i个元素prices[i]表示一支股票第i天的价格。你只能选择某一天买入并选择在未来的某一个不同的日子卖出。设计一个算法来计算你能获取的最大利润。如果无法获取利润返回0。思路分析这道题的关键在于对于第i天如果你要在这一天卖出那么买入的最佳时机一定是之前所有天中价格最低的那一天。所以我们可以在遍历数组时同时维护两个信息minPrice到目前为止遇到的最低价格最佳买入时机maxProfit到目前为止能获得的最大利润每到一个新的价格先算一下今天卖出能赚多少然后更新最大利润再更新最低价格。C 语言代码#include limits.h int maxProfit(int* prices, int pricesSize) { if (pricesSize 2) return 0; int minPrice prices[0]; // 记录历史最低价格 int maxProfit 0; // 记录最大利润 for (int i 1; i pricesSize; i) { // 计算今天卖出的利润 int profit prices[i] - minPrice; // 更新最大利润 if (profit maxProfit) { maxProfit profit; } // 更新历史最低价格 if (prices[i] minPrice) { minPrice prices[i]; } } return maxProfit; }关键点只需要一次遍历时间复杂度 O(n)空间复杂度 O(1)minPrice的更新要在计算利润之后——因为不能当天买当天卖如果价格一直下跌maxProfit始终保持为0符合题意总结这三道题目是算法面试中的经典基础题分别代表了不同的算法思想和数据结构应用题目核心思想数据结构/技巧时间复杂度空间复杂度有效的括号(LeetCode 20)后进先出匹配数组模拟栈O(n)O(n)合并两个有序链表(LeetCode 21)双指针逐个比较虚拟头节点O(nm)O(1)买卖股票的最佳时机(LeetCode 121)维护历史最小值贪心一次遍历O(n)O(1)学习建议理解优先先理解每道题的核心思想和解题思路不要急于看代码。动手实践在理解思路后自己动手实现一遍代码注意边界条件的处理。举一反三尝试思考每道题的变种问题比如「有效的括号」如果允许其他字符怎么办「合并链表」如果是 K 个链表如何合并复杂度分析养成分析时间复杂度和空间复杂度的习惯这是面试中的必考项。这三道题虽然基础但涵盖了栈、链表、贪心算法等核心概念是算法学习的良好起点。建议读者在掌握这些基础后可以进一步挑战更复杂的算法题目。如果在学习过程中有任何疑问或者有更好的解题思路欢迎在评论区交流讨论