跳到主要内容
LeetCode Hot 100 精选:C 语言实现与思路解析(1-21) | 极客日志
C 算法
LeetCode Hot 100 精选:C 语言实现与思路解析(1-21) LeetCode Hot 100 系列精选 21 道高频算法题的 C 语言完整实现。涵盖数组、链表、二叉树及动态规划等核心考点,提供暴力解法与优化方案对比。重点解析哈希表、快慢指针、递归遍历等关键技巧,包含内存管理与边界处理细节。适合嵌入式开发或后端工程师进行面试突击与底层逻辑巩固,代码经过实测可运行,附带关键步骤注释与复杂度分析。
本文整理了 LeetCode Hot 100 中的 21 道经典题目,采用 C 语言实现,旨在帮助开发者在面试准备中强化基础算法能力。代码经过实测可运行,附带关键步骤注释。
1. 两数之和
给定一个整数数组 nums 和一个目标值 target,找出和为目标值的两个整数并返回下标。
分析 :这是最基础的入门题,虽然暴力双循环能过,但实际工程中更推荐哈希表优化。这里为了演示 C 语言特性,先展示暴力解法,逻辑简单直观。
int * twoSum (int * nums, int numsSize, int target, int * returnSize) {
int *a = (int *)malloc (sizeof (int )*2 );
int i, j;
for (i=0 ; i<numsSize; i++){
for (j=i+1 ; j<numsSize; j++){
if (nums[i]+nums[j]==target){
a[0 ]=i;
a[1 ]=j;
*returnSize=2 ;
return a;
}
}
}
return 0 ;
}
20. 有效的括号
判断字符串是否有效,需满足左括号闭合正确且顺序匹配。
分析 :典型的栈应用。遍历字符时,遇到左括号入栈,右括号则检查栈顶是否匹配。注意处理空栈和剩余元素的情况。
bool isValid (char * s) {
char stack [10001 ];
int top=0 ;
for (int i=0 ; s[i]!='\0' ; i++) {
char c=s[i];
if (c == || c == || c == ) {
[++top] = c;
} {
(top== ){ ;}
topChar = [top];
((c == && topChar != ) ||
(c == && topChar != ) ||
(c == && topChar != )) {
;
}
top--;
}
}
top== ;
}
'('
'{'
'['
stack
else
if
0
return
false
char
stack
if
')'
'('
'}'
'{'
']'
'['
return
false
return
0
21. 合并两个有序链表 分析 :递归写法很简洁,但尾插法更直观且节省栈空间。通过比较节点值,依次连接较小的节点到结果链表中。
struct ListNode* mergeTwoLists (struct ListNode* list1, struct ListNode* list2) {
struct ListNode dummy ;
struct ListNode *p = &dummy;
while (list1!=NULL && list2!=NULL ) {
if (list1->val<=list2->val) {
p->next=list1;
list1=list1->next;
} else {
p->next=list2;
list2=list2->next;
}
p=p->next;
}
p->next=list1?list1:list2;
return dummy.next;
}
70. 爬楼梯 每次可以爬 1 或 2 个台阶,求 n 阶有多少种方法。
分析 :本质是斐波那契数列。用迭代代替递归可以避免重复计算,空间复杂度降为 O(1)。
int climbStairs (int n) {
if (n <= 2 ) return n;
int prev2 = 1 ;
int prev1 = 2 ;
int curr;
for (int i = 3 ; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
94. 二叉树的中序遍历 分析 :中序即'左根右'。递归实现最简单,注意指针操作时的优先级问题,比如 (*returnSize)++ 必须加括号。
void inorder (struct TreeNode* root, int * tree, int * returnSize) {
if (root == NULL ) { return ; }
inorder(root->left, tree, returnSize);
tree[*returnSize] = root->val;
(*returnSize)++;
inorder(root->right, tree, returnSize);
}
int * inorderTraversal (struct TreeNode* root, int * returnSize) {
*returnSize = 0 ;
int *tree = malloc (sizeof (int ) * 300 );
inorder(root, tree, returnSize);
return tree;
}
101. 对称二叉树 分析 :递归判断左右子树是否镜像。核心逻辑是:左的左 vs 右的右,左的右 vs 右的左。
bool judge (struct TreeNode* left, struct TreeNode* right) {
if (right==NULL && left==NULL ){return true ;}
if (right==NULL || left==NULL ){return false ;}
if (right->val != left->val){return false ;}
return judge(left->left,right->right) && judge(left->right,right->left);
}
bool isSymmetric (struct TreeNode* root) {
if (root == NULL ) { return true ; }
return judge(root,root);
}
104. 二叉树的最大深度 分析 :最大深度等于左右子树最大深度的较大者加 1。递归终止条件是节点为空。
int maxDepth (struct TreeNode* root) {
if (root == NULL ) { return 0 ; }
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1 ;
}
121. 买卖股票的最佳时机 分析 :维护一个历史最低点 buy,每天计算当前价格与最低点的差值作为潜在利润,取最大值即可。
int maxProfit (int * prices, int pricesSize) {
int buy = prices[0 ];
int money = 0 ;
for (int i=0 ;i<pricesSize;i++) {
if (prices[i]-buy>money){money=prices[i]-buy;}
if (prices[i]<buy){buy=prices[i];}
}
return money;
}
136. 只出现一次的数字 分析 :官方最优解是利用异或运算的性质:a ^ a = 0, a ^ 0 = a。成对的数会抵消,最后剩下唯一的数。哈希表方案虽可行但占用额外空间。
int singleNumber (int * nums, int numsSize) {
int result = 0 ;
for (int i = 0 ; i < numsSize; i++) {
result ^= nums[i];
}
return result;
}
#define OFFSET 30000
#define SIZE 60001
int singleNumberHash (int * nums, int numsSize) {
int hash[SIZE] = {0 };
for (int i = 0 ; i < numsSize; i++) {
int idx = nums[i] + OFFSET;
hash[idx] ^= 1 ;
}
for (int i = 0 ; i < SIZE; i++) {
if (hash[i] == 1 ) { return i - OFFSET; }
}
return 0 ;
}
141. 环形链表 分析 :快慢指针法。如果存在环,快指针最终会追上慢指针。
bool hasCycle (struct ListNode *head) {
struct ListNode *fast = head;
struct ListNode *slow = head;
while (fast!=NULL && fast->next!=NULL ) {
fast=fast->next->next;
slow=slow->next;
if (fast==slow) { return true ; }
}
return false ;
}
160. 相交链表 分析 :双指针技巧非常优雅。让两个指针分别遍历完自己的链表后转向另一条链表,若相交必在交点相遇;若不相交则在终点相遇(均为 NULL)。
struct ListNode *getIntersectionNode (struct ListNode *headA, struct ListNode *headB) {
if (headA == NULL || headB == NULL ) return NULL ;
struct ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = (pA == NULL ) ? headB : pA->next;
pB = (pB == NULL ) ? headA : pB->next;
}
return pA;
}
169. 多数元素 分析 :摩尔投票法。不同元素'一命抵一命',最后剩下的候选人即为多数元素。
int majorityElement (int * nums, int numsSize) {
int a=nums[0 ];
int blood=1 ;
for (int i=1 ;i<numsSize;i++) {
int b=nums[i];
if (a==b) { blood++; }
else {
blood--;
if (blood<0 ) { a=nums[i]; blood=0 ; }
}
}
return a;
}
206. 翻转链表 分析 :原地反转只需修改指针指向。头插法也可以生成新链表,但不推荐因为涉及多次内存分配。
struct ListNode* reverseList (struct ListNode* head) {
struct ListNode *prev = NULL ;
struct ListNode *curr = head;
struct ListNode *next = NULL ;
while (curr != NULL ) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
226. 翻转二叉树 分析 :经典的递归问题。先递归翻转左右子树,再交换当前节点的左右指针。
struct TreeNode* invertTree (struct TreeNode* root) {
if (root == NULL ) { return NULL ; }
struct TreeNode * left = invertTree(root->left);
struct TreeNode * right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
234. 回文链表 分析 :最佳实践是快慢指针找中点,反转后半部分,然后比对。完成后记得恢复链表结构。
struct ListNode* reverseList (struct ListNode* head) {
struct ListNode *prev = NULL , *cur = head;
while (cur) {
struct ListNode * next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
bool isPalindrome (struct ListNode* head) {
if (head == NULL || head->next == NULL ) return true ;
struct ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode * secondHalfStart = reverseList(slow->next);
struct ListNode *firstHalfStart = head;
struct ListNode *secondHalfCopy = secondHalfStart;
bool result = true ;
while (secondHalfStart) {
if (firstHalfStart->val != secondHalfStart->val) {
result = false ;
break ;
}
firstHalfStart = firstHalfStart->next;
secondHalfStart = secondHalfStart->next;
}
slow->next = reverseList(secondHalfCopy);
return result;
}
283. 移动零 分析 :记录前面有多少个零,遇到非零元素就向前交换位置,避免多余拷贝。
void moveZeroes (int * nums, int numsSize) {
int cnt=0 ;
for (int i=0 ;i<numsSize;i++) {
if (nums[i]==0 ) {
cnt++;
} else {
int temp=nums[i-cnt];
nums[i-cnt]=nums[i];
nums[i]=temp;
}
}
}
338. 比特位计数 分析 :Brian Kernighan 算法利用 x & (x - 1) 消除最低位的 1,效率高于除二取余。
int countOnes (int x) {
int ones = 0 ;
while (x > 0 ) {
x &= (x - 1 );
ones++;
}
return ones;
}
int * countBits (int n, int * returnSize) {
int *a=malloc (sizeof (int )*(n+1 ));
*returnSize=n+1 ;
for (int i = 0 ; i <= n; i++) {
a[i] = countOnes(i);
}
return a;
}
448. 找到所有数组中消失的数字 分析 :利用数组本身作为哈希表。将访问到的数字对应索引处的值标记为负数,最后正数对应的索引即为缺失数字。
int * findDisappearedNumbers (int * nums, int numsSize, int * returnSize) {
for (int i = 0 ; i < numsSize; i++) {
int index = abs (nums[i]) - 1 ;
if (nums[index] > 0 ) {
nums[index] = -nums[index];
}
}
int * result = malloc (sizeof (int ) * numsSize);
int count = 0 ;
for (int i = 0 ; i < numsSize; i++) {
if (nums[i] > 0 ) {
result[count++] = i + 1 ;
}
}
*returnSize = count;
return result;
}
461. 汉明距离 分析 :先异或得到不同位,再用 Brian Kernighan 算法统计 1 的个数。GCC 编译器提供内置函数 __builtin_popcount 可直接使用。
int hammingDistance (int x, int y) {
unsigned int xor = x ^ y;
int count = 0 ;
while (xor) {
xor &= xor - 1 ;
count++;
}
return count;
}
543. 二叉树的直径 分析 :直径不一定经过根节点。需要在遍历过程中更新全局最大直径,即左深度 + 右深度。
int maxDepth (struct TreeNode* root, int * diameter) {
if (root == NULL ) return 0 ;
int left = maxDepth(root->left, diameter);
int right = maxDepth(root->right, diameter);
*diameter = (*diameter > left + right) ? *diameter : left + right;
return (left > right ? left : right) + 1 ;
}
int diameterOfBinaryTree (struct TreeNode* root) {
int diameter = 0 ;
maxDepth(root, &diameter);
return diameter;
}
617. 合并二叉树 分析 :递归合并十分干脆。若某节点为空直接返回另一个节点,否则创建新节点累加值并递归合并子树。
struct TreeNode* mergeTrees (struct TreeNode* t1, struct TreeNode* t2) {
if (t1 == NULL ) { return t2; }
if (t2 == NULL ) { return t1; }
struct TreeNode * merged = malloc (sizeof (struct TreeNode));
merged->val = t1->val + t2->val;
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online