Leetcode Hot 100 (C语言版) 1-21
博主搞嵌入式的，走底层纯C的，为了找实习/工作刷点题，平时AI coding习惯了，怕手撕代码写不出来，这里刷题顺便分享下思路，代码能跑就行，有什么问题欢迎指出，博主是新手入门；
这里按照难度排序依次进行。
在刷leetcode前建议可以先练一练牛客的算法入门，效果会更好。
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 0; }20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
分析：很经典的堆栈问题，主要是判断下标top是否为0
bool isValid(char* s) { char stack[10001]; int top=0; for(int i=0;s[i]!='\n'&&s[i]!='\0';i++) { char c=s[i]; if (c == '(' || c == '{' || c == '[') { stack[++top] = c; } else { if(top==0){return false;} char topChar = stack[top]; if ((c == ')' && topChar != '(') || (c == '}' && topChar != '{') || (c == ']' && topChar != '[')) { return false; } top--; } } if(top!=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; // f(n-2) int prev1 = 2; // f(n-1) int curr; for (int i = 3; i <= n; i++) { curr = prev1 + prev2; // f(n) = f(n-1) + f(n-2) prev2 = prev1; prev1 = curr; } return prev1; }94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
分析：中序是”左根右“，另外还有先序的”根左右“以及后序的”左右根“；root在哪就是什么序，然后左右；这次的话用递归就好办不少了，写代码的时候注意指针操作最好加个括号；
void inorder(struct TreeNode* root, int* tree, int* returnSize) { if(root == NULL) { return; // void函数直接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 ， 检查它是否轴对称。
分析：想明白递归思路，就稍微好写了
1. 两个都为空，对称 2. 只有一个为空，不对称 3. 值不同，不对称 4. 递归检查：左的左 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 ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
分析：这里leetcode官方给的解释很不错，
如果我们知道了左子树和右子树的最大深度 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 。
分析：（leetcode评论区）
每天的最大获利 = 今天 - 前面 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 ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
分析：刚上来就想到哈希表做法，但官方答案用异或来做更好一些
#define OFFSET 30000 // 偏移量，覆盖负数范围 #define SIZE 60001 int singleNumber(int* nums, int numsSize) { int hash[SIZE] = {0}; for(int i = 0; i < numsSize; i++) { int idx = nums[i] + OFFSET; // 负数变正数 hash[idx] ^= 1; // 0变1，1变0 } for(int i = 0; i < SIZE; i++) { if(hash[i] == 1) { return i - OFFSET; } } return 0; }int singleNumber(int* nums, int numsSize) { int result = 0; for(int i = 0; i < numsSize; i++) { result ^= nums[i]; // 成对的数会抵消，只剩单个的 } return result; }141.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 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轮询，然后A再往前走，这样的话时间复杂度是O(m×n)，而且一点也不优雅；后来看评论区用双指针（两个指针都走 m+n 步，必然在交点或终点相遇），走过你的来时路，只为与你相遇，还挺浪漫。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA = headA; while (curA != NULL) { struct ListNode *curB = headB; while (curB != NULL) { if (curA == curB) { return curA; } curB = curB->next; } curA = curA->next; } return 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.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
分析：这道题又想用哈希表，后来一看范围，觉得肯定不是最优解，看了看评论区，一命抵一命，人数最多的那个肯定活到最后，直接给程序写出来了
-10^9 <= nums[i] <= 10^91 <= n <= 5 * 10^4
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; // prev前移 curr = next; // curr前移 } return prev; // 新头节点 }struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newHead = NULL; // 新链表的头 while (head != NULL) { // 创建新节点，复制值 struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); newNode->val = head->val; // 头插法：新节点指向原来的新头 newNode->next = newHead; newHead = newNode; // 更新新头 head = head->next; // 遍历原链表（只读，不修改） } return newHead; // 全新的反转链表 }226.反转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
分析：经典递归做法；有趣的是，homebrew（一个很有名的苹果软件）的作者因为不能在白板上反转二叉树（就这道题）就被Google给拒了
struct TreeNode* invertTree(struct TreeNode* root) { // 1. 递归终止条件 if (root == NULL) { return NULL; } // 2. 递归翻转左右子树 struct TreeNode* left = invertTree(root->left); struct TreeNode* right = invertTree(root->right); // 3. 交换左右子树 root->left = right; root->right = left; return root; }234.回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
分析：第一直觉是生成一个反转链表然后逐个比对；
在长度不大的情况下也可以直接转成数组（时间n，空间n）
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; // 1. 快慢指针找中点（慢指针走到前半部分末尾） struct ListNode *slow = head, *fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } // 2. 反转后半部分 struct ListNode* secondHalfStart = reverseList(slow->next); // 3. 比较两部分 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; } // 4. 恢复链表（可选，良好习惯） 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; // 1. 链表转数组 struct ListNode* cur = head; while (cur) { arr[n++] = cur->val; cur = cur->next; } // 2. 双指针判断回文 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 n) { int count = 0; while (n > 0) { if (n % 2 == 1) { count++; } n = n / 2; } return count; } 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; }int countOnes(int x) { int ones = 0; while (x > 0) { x &= (x - 1); ones++; } return ones; }448.找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
分析：第一时间用哈希表暴力解出来了；官方答案是拿数组本身当作哈希，效率更高
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) { int hash[100001]={0}; int *arr=malloc(sizeof(int)*100000); int top=0; for(int i=0;i<numsSize;i++) { if(hash[nums[i]]==0) { hash[nums[i]]=1; } } for(int i=1;i<=numsSize;i++) { if(hash[i]==0) { arr[top]=i; top++; } } *returnSize=top; return arr; }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 算法；有趣的是，找到了一个GCC内置函数，得到了作弊方案
int hammingDistance(int x, int y) { unsigned int xor = x ^ y; int count = 0; while (xor) { xor &= xor - 1; count++; } return count; } int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); }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; }
