跳到主要内容 LeetCode Hot 100 刷题笔记(C 语言版)1-21 | 极客日志
C 算法
LeetCode Hot 100 刷题笔记(C 语言版)1-21 本文整理了 LeetCode Hot 100 系列中部分题目(编号 1-21 左右)的 C 语言解法。涵盖数组、链表、树、栈及位运算等数据结构与算法。内容包括两数之和、有效括号、合并链表、爬楼梯、二叉树遍历与深度、股票买卖、只出现一次的数字、环形链表、多数元素、回文链表等经典问题。针对每道题提供了问题分析、多种解题思路(如暴力枚举、哈希表、递归、双指针)及完整的 C 语言代码实现,旨在帮助读者巩固 C 语言基础并提升算法思维能力。
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
分析 :经典入门题,难度不高。直接暴力双循环解决,也有用哈希表来做的。
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 NULL ;
}
20.有效的括号
给定一个只包括 '(',),'{','}','[',] 的字符串 s,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
分析 :很经典的堆栈问题,主要是判断下标 top 是否为 0。
bool isValid (char * s) {
char stack [10001 ];
int top=0 ;
( i= ; s[i]!= ; i++) {
c=s[i];
(c == || c == || c == ) {
[++top] = c;
} {
(top== ){ ;}
topChar = [top];
((c == && topChar != ) || (c == && topChar != ) || (c == && topChar != )) {
;
}
top--;
}
}
(top!= ){ ;}
;
}
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如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
for
int
0
'\0'
char
if
'('
'{'
'['
stack
else
if
0
return
false
char
stack
if
')'
'('
'}'
'{'
']'
'['
return
false
if
0
return
false
return
true
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.爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
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.二叉树的中序遍历 给定一个二叉树的根节点 root,返回 它的 中序 遍历 。
分析 :中序是'左根右',另外还有先序的'根左右'以及后序的'左右根';root 在哪就是什么序,然后左右;这次的话用递归就好办不少了,写代码的时候注意指针操作最好加个括号。
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.对称二叉树 给你一个二叉树的根节点 root,检查它是否轴对称。
两个都为空,对称
只有一个为空,不对称
值不同,不对称
递归检查:左的左 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.二叉树的最大深度 给定一个二叉树 root,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
分析 :如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为 max(l,r)+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.买卖股票的最佳时机 给定一个数组 prices,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0。
分析 :每天的最大获利 = 今天 - 前面 n 天的最小值;最大获利 = max(每天最大获利)。
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.只出现一次的数字 给你一个 非空 整数数组 nums,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
分析 :刚上来就想到哈希表做法,但官方答案用 异或 来做更好一些。
int singleNumber (int * nums, int numsSize) {
int result = 0 ;
for (int i = 0 ; i < numsSize; i++) {
result ^= nums[i];
}
return result;
}
141.环形链表 给你一个链表的头节点 head,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
如果链表中存在环 ,则返回 true。否则,返回 false。
分析 :使用快慢指针,如果有环,快的一定能追上慢的。
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.相交链表 给你两个单链表的头节点 headA 和 headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null。
分析 :最开始想固定 A,让 B 轮询,时间复杂度 O(m×n),不优雅;后来用 双指针 (两个指针都走 m+n 步,必然在交点或终点相遇)。
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.多数元素 给定一个大小为 n 的数组 nums,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
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.翻转链表 给你单链表的头节点 head,请你反转链表,并返回反转后的链表。
分析 :很基础的问题,一般直接修改原链表,还可以生成新链表方式(n 次 malloc,不推荐)。
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.反转二叉树 给你一棵二叉树的根节点 root,翻转这棵二叉树,并返回其根节点。
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.回文链表 给你一个单链表的头节点 head,请你判断该链表是否为回文链表。如果是,返回 true;否则,返回 false。
分析 :第一直觉是生成一个反转链表然后逐个比对;在长度不大的情况下也可以直接转成数组。
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;
}
bool isPalindrome (struct ListNode* head) {
if (head == NULL || head->next == NULL ) return true ;
int arr[100001 ];
int n = 0 ;
struct ListNode * cur = head;
while (cur) {
arr[n++] = cur->val;
cur = cur->next;
}
int left = 0 , right = n - 1 ;
while (left < right) {
if (arr[left] != arr[right]) return false ;
left++;
right--;
}
return true ;
}
283.移动零 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意,必须在不复制数组的情况下原地对数组进行操作。
分析 :记录元素之前有多少个零就行了,直接和前面第一个零交换位置就好。
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.比特位计数 给你一个整数 n,对于 0 <= i <= n 中的每个 i,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
分析 :这道题的关键在于怎样去找一个数对应的二进制,最优解应该是位运算(Brian Kernighan 算法)。
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.找到所有数组中消失的数字 给你一个含 n 个整数的数组 nums,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。
分析 :第一时间用哈希表暴力解出来了;官方答案是拿数组本身当作哈希,效率更高。
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.汉明距离 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y,计算并返回它们之间的汉明距离。
分析 :通过 x^y,不同比特位变成 1,然后求 1 的个数,可以用 Brian Kernighan 算法。
int hammingDistance (int x, int y) {
unsigned int xor = x ^ y;
int count = 0 ;
while (xor) {
xor &= xor - 1 ;
count++;
}
return count;
}
543.二叉树的直径 给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root。
两节点之间路径的 长度 由它们之间边数表示。
分析 :首先想到的是前面做的二叉树最大深度题,左深度 + 右深度,但是需要注意,直径并不是百分百过根节点 的,每个节点都可能是最长直径的转折点,需要 遍历所有节点 。
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.合并二叉树 给你两棵二叉树:root1 和 root2。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
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;
}