文章目录一、数组1.数组循环左移408考研10年42题2.搜索旋转数组 面试题3.169.多数元素4.191.1的个数二、链表1.876.链表的中间结点2.141.环形链表3.206.反转链表、LCR 024.反转链表4.21.合并两个有序链表5.61.旋转链表 【待做Linux01】三、递归1.509.斐波那契数列四、排序1.912.排序数组五、二叉树1.104.二叉树的最大深度2.98.验证二叉搜索树六、查找1.寻找旋转排序数组中的最小值 待做Linux022.275.H指数 二分查找七、STL容器1.LRU缓存2.单词接龙Leetcode①锻炼写代码的基本能力②锻炼算法能力一、数组1.数组循环左移408考研10年42题思路Reverse()函数#define_CRT_SECURE_NO_WARNINGS#includestdio.hvoidprint_array(intarr[],intn){for(inti0;in;i){printf(%d ,arr[i]);}printf(\n);}voidreverse(intarr[],intleft,intright){while(leftright){inttemparr[left];arr[left]arr[right];arr[right]temp;left;right--;}}voidrotateLeft(intarr[],intn,intk){kk%n;if(k0)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){intcount0;structListNode*currenthead;while(current!NULL){currentcurrent-next;count;}intmidcount/2;currenthead;for(inti0;imid;i){currentcurrent-next;}returncurrent;}思路2快慢指针 (效率高)structListNode*middleNode(structListNode*head){structListNode*fasthead;structListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}returnslow;}完整代码#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includestdlib.h#includestdbool.htypedefstructnode{intdata;structnode*next;}Node;Node*node_create(void){returncalloc(1,sizeof(Node));}voidnode_destroy(Node*head){Node*curhead;while(cur!NULL){Node*nextcur-next;free(cur);curnext;}}//头插法voidadd_before_head(Node**head,intvalue){Node*new_nodemalloc(sizeof(Node));new_node-datavalue;new_node-next*head;*headnew_node;}//1.求链表中间结点两次遍历intmiddleElement(Node*list){//Node* list是指向链表头节点的指针intcount0;Node*currentlist;while(current!NULL){currentcurrent-next;count;}intmidcount/2;currentlist;for(inti0;imid;i){currentcurrent-next;}returncurrent-data;}voidprint_list(Node*head){while(head!NULL){printf(%d ,head-data);headhead-next;}printf(\n);}intmain(void){//Node* head node_create();Node*headNULL;//不要头结点add_before_head(head,1);add_before_head(head,2);add_before_head(head,3);add_before_head(head,4);print_list(head);intmidmiddleElement(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*fasthead;structListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){//快慢指针相遇说明有环returntrue;}}returnfalse;}完整代码#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includestdlib.h#includestdbool.htypedefstructnode{intdata;structnode*next;}Node;//头插法voidadd_before_head(Node**head,intvalue){Node*new_nodemalloc(sizeof(Node));new_node-datavalue;new_node-next*head;*headnew_node;}//1.求链表中间结点快慢指针intmiddleElement_2(Node*list){Node*fastlist;Node*slowlist;while(fastfast-next){fastfast-next-next;slowslow-next;}returnslow-data;}voidprint_list(Node*head){while(head!NULL){printf(%d ,head-data);headhead-next;}printf(\n);}intmain(void){//直接在栈上创建链表Node node8{8,NULL};Node node6{6,node8};Node node4{4,node6};Node node2{2,node4};print_list(node2);intmidmiddleElement_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*currenthead;structListNode*previousNULL;while(current!NULL){structListNode*nextcurrent-next;//next声明为current后一个current-nextprevious;//头插法反转previouscurrent;//prev后移currentnext;//curr后移}returnprevious;//新的头节点}思路2递归时间复杂度O(n)空间复杂度O(n)递归调用栈深度为nstructListNode*reverseList(structListNode*head){//1.递归出口(边界条件)if(headNULL||head-nextNULL){returnhead;}//2.递归公式structListNode*restreverseList(head-next);//问题规模由n减为n-1//反转第一个结点,假设后n-1个结点已经反转head-next-nexthead;head-nextNULL;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*taildummyNode;//判空:处理空链表的情况if(list1NULL)returnlist2;if(list2NULL)returnlist1;while(list1!NULLlist2!NULL){if(list1-vallist2-val){tail-nextlist1;taillist1;list1list1-next;}else{tail-nextlist2;taillist2;list2list2-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(n0||n1){returnn;}returnfib(n-1)fib(n-2);}思路2动态规划动态规划Dynamic ProgrammingDP是一种算法设计方法用于解决那些可以被分解成重叠子问题的复杂问题。这种方法通过将问题拆分成更小、更简单的子问题来解决每个子问题只解决一次并将其结果存储起来以便在解决其他子问题时可以直接使用这些结果从而避免了重复计算。动态规划通常用于优化问题比如求最大值或最小值例如寻找最短路径、最长公共子序列、背包问题等。这种方法特别适用于那些子问题重叠和最优子结构性质的问题它可以显著减少计算量提高效率。intfib(intn){if(n0||n1)returnn;intsum0,n10,n21;//0,1,1,2,3,5,8,13,21,34,55,89for(inti2;in;i){sumn1n2;n1n2;n2sum;}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; * }; */intdeep0;voidPreOrder(structTreeNode*root,inth){if(rootNULL)return;if(hdeep)deeph;PreOrder(root-left,h1);PreOrder(root-right,h1);}//递归后序遍历 函数返回值 (自底向上传递信息)intmaxDepth(structTreeNode*root){deep0;PreOrder(root,1);//初始深度为1returndeep;}思路2递归后序遍历 函数返回值 (自底向上传递信息)intmaxDepth(structTreeNode*root){if(rootNULL)return0;intlmaxDepth(root-left);intrmaxDepth(root-right);returnlr?l1:r1;}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; * }; */#includelimits.hlonglongcur_minLLONG_MIN;//未遍历过结点的最小值bool isBSTtrue;voidinOrder(structTreeNode*root){//边界条件if(rootNULL)return;//递归公式inOrder(root-left);if(root-valcur_min){isBSTfalse;return;//已经false了,可以直接返回}else{cur_minroot-val;}inOrder(root-right);}boolisValidBST(structTreeNode*root){cur_minLLONG_MIN;isBSTtrue;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){intleft0,rightn-1;//闭区间while(leftright){intmidleft(right-left1);if(citations[mid]n-mid){//至少n-mid篇被引用了c[mid]次rightmid-1;//H指数应该更小,向左走}else{leftmid1;//H指数应该更小,向右走}}returnn-left;}2.花生题解1//数组,有序:想到二分查找inthIndex(int*citations,intn){intleft0,rightn-1;//闭区间while(leftright){intmidleft(right-left1);if(citations[mid]n-mid){//至少n-mid篇被引用了c[mid]次rightmid-1;//H指数应该更小,向左走}elseif(citations[mid]n-mid){leftmid1;//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/