LeetCode刷题

Leetcode：
①锻炼写代码的基本能力
②锻炼算法能力

一、数组

1.数组循环左移：408考研10年42题

思路：Reverse()函数

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>voidprint_array(intarr[],intn){for(inti=0;i<n;i++){printf("%d ",arr[i]);}printf("\n");}voidreverse(intarr[],intleft,intright){while(left<right){inttemp=arr[left];arr[left]=arr[right];arr[right]=temp;left++;right--;}}voidrotateLeft(intarr[],intn,intk){k=k%n;if(k==0)return;reverse(arr,0,k-1);reverse(arr,k,n-1);reverse(arr,0,n-1);}intmain(){intarr[10]={0,1,2,3,4,5,6,7,8,9};rotateLeft(arr,10,5);print_array(arr,10);return0;}

2.搜索旋转数组 （面试题）

链接：https://leetcode.cn/problems/search-rotate-array-lcci/description/

3.169.多数元素

4.191.1的个数

二、链表

1.876.链表的中间结点

链接：https://leetcode.cn/problems/middle-of-the-linked-list/

思路1：求链表中间结点：两次遍历

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*middleNode(structListNode*head){intcount=0;structListNode*current=head;while(current!=NULL){current=current->next;count++;}intmid=count/2;current=head;for(inti=0;i<mid;i++){current=current->next;}returncurrent;}

思路2：快慢指针 (效率高)

structListNode*middleNode(structListNode*head){structListNode*fast=head;structListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}returnslow;}

完整代码

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstructnode{intdata;structnode*next;}Node;Node*node_create(void){returncalloc(1,sizeof(Node));}voidnode_destroy(Node*head){Node*cur=head;while(cur!=NULL){Node*next=cur->next;free(cur);cur=next;}}//头插法voidadd_before_head(Node**head,intvalue){Node*new_node=malloc(sizeof(Node));new_node->data=value;new_node->next=*head;*head=new_node;}//1.求链表中间结点：两次遍历intmiddleElement(Node*list){//Node* list是指向链表头节点的指针intcount=0;Node*current=list;while(current!=NULL){current=current->next;count++;}intmid=count/2;current=list;for(inti=0;i<mid;i++){current=current->next;}returncurrent->data;}voidprint_list(Node*head){while(head!=NULL){printf("%d ",head->data);head=head->next;}printf("\n");}intmain(void){//Node* head = node_create();Node*head=NULL;//不要头结点add_before_head(&head,1);add_before_head(&head,2);add_before_head(&head,3);add_before_head(&head,4);print_list(head);intmid=middleElement(head);printf("mid = %d\n",mid);node_destroy(head);return0;}

2.141.环形链表

链接：https://leetcode.cn/problems/linked-list-cycle/
思路：快慢指针

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */boolhasCycle(structListNode*head){structListNode*fast=head;structListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){//快慢指针相遇，说明有环returntrue;}}returnfalse;}

完整代码

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<stdbool.h>typedefstructnode{intdata;structnode*next;}Node;//头插法voidadd_before_head(Node**head,intvalue){Node*new_node=malloc(sizeof(Node));new_node->data=value;new_node->next=*head;*head=new_node;}//1.求链表中间结点：快慢指针intmiddleElement_2(Node*list){Node*fast=list;Node*slow=list;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}returnslow->data;}voidprint_list(Node*head){while(head!=NULL){printf("%d ",head->data);head=head->next;}printf("\n");}intmain(void){//直接在栈上创建链表Node node8={8,NULL};Node node6={6,&node8};Node node4={4,&node6};Node node2={2,&node4};print_list(&node2);intmid=middleElement_2(&node2);printf("mid = %d\n",mid);return0;}

3.206.反转链表、LCR 024.反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/
链接：https://leetcode.cn/problems/UHnkqh/description/

思路1：迭代
头插法，三指针 (previous、current、next)

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*reverseList(structListNode*head){structListNode*current=head;structListNode*previous=NULL;while(current!=NULL){structListNode*next=current->next;//next声明为current后一个current->next=previous;//头插法反转previous=current;//prev后移current=next;//curr后移}returnprevious;//新的头节点}

思路2：递归
时间复杂度：O(n)
空间复杂度：O(n)，递归调用栈深度为n

structListNode*reverseList(structListNode*head){//1.递归出口(边界条件)if(head==NULL||head->next==NULL){returnhead;}//2.递归公式structListNode*rest=reverseList(head->next);//问题规模由n减为n-1//反转第一个结点,假设后n-1个结点已经反转head->next->next=head;head->next=NULL;returnrest;}

4.21.合并两个有序链表

链接：https://leetcode.cn/problems/merge-two-sorted-lists/
思路：栈上创建哑结点，尾插法

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){structListNodedummyNode={0,NULL};////在栈上创建哑结点,并初始化structListNode*tail=&dummyNode;//判空:处理空链表的情况if(list1==NULL)returnlist2;if(list2==NULL)returnlist1;while(list1!=NULL&&list2!=NULL){if(list1->val<list2->val){tail->next=list1;tail=list1;list1=list1->next;}else{tail->next=list2;tail=list2;list2=list2->next;}}//list1和list2有一个为空tail->next=(list1!=NULL)?list1:list2;//直接链接returndummyNode.next;}

5.61.旋转链表 【待做，Linux01】

链接：https://leetcode.cn/problems/rotate-list/description/

三、递归

1.509.斐波那契数列

链接：https://leetcode.cn/problems/fibonacci-number/

思路1：暴力递归

intfib(intn){if(n==0||n==1){returnn;}returnfib(n-1)+fib(n-2);}

思路2：动态规划

动态规划（Dynamic Programming，DP）是一种算法设计方法，用于解决那些可以被分解成重叠子问题的复杂问题。这种方法通过将问题拆分成更小、更简单的子问题来解决，每个子问题只解决一次，并将其结果存储起来，以便在解决其他子问题时可以直接使用这些结果，从而避免了重复计算。

动态规划通常用于优化问题，比如求最大值或最小值，例如寻找最短路径、最长公共子序列、背包问题等。这种方法特别适用于那些子问题重叠和最优子结构性质的问题，它可以显著减少计算量，提高效率。

intfib(intn){if(n==0||n==1)returnn;intsum=0,n1=0,n2=1;//0,1,1,2,3,5,8,13,21,34,55,89for(inti=2;i<=n;i++){sum=n1+n2;n1=n2;n2=sum;}returnsum;}

四、排序

1.912.排序数组

链接：https://leetcode.cn/problems/sort-an-array/description/

五、二叉树

1.104.二叉树的最大深度

链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/

思路1：递归先根遍历 +参数传递 + 全局变量(自顶向下传递信息)

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */intdeep=0;voidPreOrder(structTreeNode*root,inth){if(root==NULL)return;if(h>deep)deep=h;PreOrder(root->left,h+1);PreOrder(root->right,h+1);}//递归后序遍历 + 函数返回值 (自底向上传递信息)intmaxDepth(structTreeNode*root){deep=0;PreOrder(root,1);//初始深度为1returndeep;}

思路2：递归后序遍历 + 函数返回值 (自底向上传递信息)

intmaxDepth(structTreeNode*root){if(root==NULL)return0;intl=maxDepth(root->left);intr=maxDepth(root->right);returnl>r?l+1:r+1;}

2.98.验证二叉搜索树

链接：https://leetcode.cn/problems/validate-binary-search-tree/description/

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */#include<limits.h>longlongcur_min=LLONG_MIN;//未遍历过结点的最小值bool isBST=true;voidinOrder(structTreeNode*root){//边界条件if(root==NULL)return;//递归公式inOrder(root->left);if(root->val<=cur_min){isBST=false;return;//已经false了,可以直接返回}else{cur_min=root->val;}inOrder(root->right);}boolisValidBST(structTreeNode*root){cur_min=LLONG_MIN;isBST=true;inOrder(root);returnisBST;}

六、查找

1.寻找旋转排序数组中的最小值 （待做，Linux02）

链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/description/

思路：二分查找

2.275.H指数 （二分查找）

链接：https://leetcode.cn/problems/h-index-ii/description/

思路：
①H指数：至少有 h 篇论文分别被引用了至少 h 次
②第i篇论文被引用了citations[i]次，第mid篇论文被引用了citations[mid]次
③后一半的论文数量一共是n-mid篇，这n-mid篇的引用次数均 ≥ citations[mid]次
④答案一定是数组中的某个值，所以需要二分查找向左或向右移动区间

1.LeetCode官方题解：

//数组,有序:想到二分查找inthIndex(int*citations,intn){intleft=0,right=n-1;//闭区间while(left<=right){intmid=left+(right-left>>1);if(citations[mid]>=n-mid){//至少n-mid篇被引用了c[mid]次right=mid-1;//H指数应该更小,向左走}else{left=mid+1;//H指数应该更小,向右走}}returnn-left;}

2.花生题解1：

//数组,有序:想到二分查找inthIndex(int*citations,intn){intleft=0,right=n-1;//闭区间while(left<=right){intmid=left+(right-left>>1);if(citations[mid]>n-mid){//至少n-mid篇被引用了c[mid]次right=mid-1;//H指数应该更小,向左走}elseif(citations[mid]<n-mid){left=mid+1;//H指数应该更小,向右走}else{//相等，恰是H指数returnn-mid;}}// left > right//如果 left 在 [0, n-1]范围内，那么 citations[left] 就是第一个大于 n - left的元素//三种退出情况，都是 n-leftreturnn-left;}

3.花生题解2：

七、STL容器

1.LRU缓存

链接：https://leetcode-cn.com/problems/lru-cache/

2.单词接龙

链接：https://leetcode-cn.com/problems/word-ladder/