必会的10个经典算法题(附解析答案代码JavaCPython看这一篇就够)

奇迹暖暖

引言常见的数据结构与算法题目，涵盖了数组、链表、栈、队列、二叉树、哈希表、字符串、图、排序和查找等方面的考察点。每个题目都附带有LeetCode的链接，可以点击链接了解更多题目详情概述类型题目考察点难度LeetCode链接数组两数之和哈希表、查找简单LeetCode1链表合并两个有序链表链表操作、指针简单LeetCode21栈有效的括号栈、字符串处理简单LeetCode20队列循环队列设计队列、数组中等LeetCode622二叉树对称二叉树二叉树递归、对称性判断简单LeetCode101哈希表两个数组的交集II哈希表、数组简单LeetCode350字符串最长公共前缀字符串处理、前缀判断简单LeetCode14图克隆图图的遍历、深拷贝中等LeetCode133排序合并排序的数组归并排序、数组操作简单LeetCode88查找第K个数快速选择、二分查找中等LeetCode215两数之和（LeetCode1,Easy）标签：哈希表|数组题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1：输入：nums=[2,7,11,15],target=9输出：[0,1]解释：因为nums[0]+nums[1]==9，返回[0,1]。示例2：输入：nums=[3,2,4],target=6输出：[1,2]示例3：输入：nums=[3,3],target=6输出：[0,1]提示：2#includeint*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){int*result=(int*)malloc(2*sizeof(int));//分配保存结果的内存空间*returnSize=0;//初始化返回结果数组的大小为0，表示没有找到满足条件的元素对for(inti=0;iList[int]:result=[]#用于存储结果的列表n=len(nums)foriinrange(n):#外层循环遍历列表中的每个元素forjinrange(i+1,n):#内层循环遍历当前元素后面的每个元素ifnums[i]+nums[j]==target:#检查两个元素的和是否等于目标值result.append(i)#将符合条件的第一个元素的下标添加到结果列表中result.append(j)#将符合条件的第二个元素的下标添加到结果列表中returnresult#返回结果列表returnresult#如果没有找到满足条件的元素对，返回空列表12345678910111213'运行运行复杂度分析：时间复杂度分析：O(n^2)，其中n为数组nums的长度。这是由于代码使用了两层循环来遍历数组。外层循环将执行n次，而内层循环则将执行(n-1)次、(n-2)次、…、2次、1次，总的执行次数为n*(n-1)/2，即O(n^2)。空间复杂度分析：O(1)，即常数级别的空间复杂度。因为代码只使用了常数个额外变量来存储元素的下标和存储结果的数组。方式二：哈希表（推荐）思路注意到方法一的时间复杂度较高的原因是寻找target-x的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找target-x的时间复杂度降低到从O(N)降低到O(1)。这样我们创建一个哈希表，对于每一个x，我们首先查询哈希表中是否存在target-x，然后将x插入到哈希表中，即可保证不会让x和自己匹配。下图以[2,7,11,15]为例代码实现JAVA版本importjava.util.HashMap;classSolution{publicint[]twoSum(int[]nums,inttarget){//key为当前值，value为当前值的位置HashMapmap=newHashMap();for(inti=0;i#includeint*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){int*result=(int*)malloc(2*sizeof(int));*returnSize=0;//创建哈希表inthashtable[20001]={0};for(inti=0;i=-10000&complementList[int]:hashtable=defaultdict(int)#使用defaultdict来容纳哈希表foriinrange(len(nums)):complement=target-nums[i]#计算差值，即目标值与当前元素的差值ifcomplementinhashtable:return[hashtable[complement],i]#返回哈希表中保存的差值元素的下标和当前元素的下标hashtable[nums[i]]=i#将当前元素添加到哈希表中return[]#如果没有找到满足条件的元素对，返回空列表12345678910111213'运行运行复杂度分析：时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元素x，我们可以O(1)地寻找target-x。空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销。合并两个有序链表（LeetCode21,Easy）标签：哈希表|数组题目将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1：>输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]示例2：输入：l1=[],l2=[]输出：[]示例3：输入：l1=[],l2=[0]输出：[0]提示：两个链表的节点数目范围是[0,50]-100val=-1;//创建一个临时节点作为结果链表的头节点node->next=NULL;structListNode*cur=node;while(list1!=NULL&list2!=NULL){if(list1->valval){cur->next=list1;//将较小节点连接到结果链表list1=list1->next;//移动指针到下一个节点}else{cur->next=list2;list2=list2->next;}cur=cur->next;//移动当前节点指针到下一个节点}if(list1!=NULL){cur->next=list1;//将剩下的节点连接到结果链表}if(list2!=NULL){cur->next=list2;}structListNode*result=node->next;//指向结果链表的头节点free(node);//释放临时节点的内存returnresult;}1234567891011121314151617181920212223242526272829303132333435363738说明：在C语言中使用了头节点，并使用了指针操作来完成。在算法中，我们创建了一个临时节点作为结果链表的头节点。然后使用cur指针指向当前节点，通过遍历两个链表，比较节点的值，将较小节点连接到结果链表中，并将指针移向下一个节点。最后，将剩下的节点连接到结果链表的末尾。需要注意的是，最后返回的是结果链表的头节点，使用一个临时节点来保存结果链表的头节点可以简化操作。在末尾，我们释放了临时节点的内存，以防止内存泄漏。Python3版本#Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defmergeTwoLists(self,list1istNode,list2istNode)->ListNode:node=ListNode(-1)#创建临时节点作为结果链表的头节点cur=nodewhilelist1andlist2:iflist1.val#includestructListNode{intval;structListNode*next;};structListNode*mergeTwoLists(structListNode*l1,structListNode*l2){//如果l1为空，则直接返回l2作为合并后的链表if(l1==NULL){returnl2;}//如果l2为空，则直接返回l1作为合并后的链表elseif(l2==NULL){returnl1;}//如果l1的值小于l2的值elseif(l1->valval){//将l1的下一个节点与l2递归地合并l1->next=mergeTwoLists(l1->next,l2);returnl1;//返回合并后的链表头节点l1}//如果l2的值小于等于l1的值else{//将l2的下一个节点与l1递归地合并l2->next=mergeTwoLists(l1,l2->next);returnl2;//返回合并后的链表头节点l2}}123456789101112131415161718192021222324252627282930说明：在算法中，首先处理特殊情况：如果l1为空，则直接返回l2作为合并后的链表；如果l2为空，则直接返回l1作为合并后的链表。接下来，判断l1和l2的值的大小关系：如果l1的值小于l2的值，将l1的下一个节点与l2递归地合并，将合并结果作为l1的下一个节点，并返回l1作为合并后的链表头节点；如果l2的值小于等于l1的值，将l2的下一个节点与l1递归地合并，将合并结果作为l2的下一个节点，并返回l2作为合并后的链表头节点。最终，返回合并后的链表头节点。Python3版本#Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defmergeTwoLists(self,l1istNode,l2istNode)->ListNode:ifnotl1:#如果l1为空，则直接返回l2returnl2elifnotl2:#如果l2为空，则直接返回l1returnl1elifl1.valstack=newStack();//创建一个栈用于存储左括号字符for(inti=0;i#include#includeusingnamespacestd;boolisValid(strings){stackstk;//创建一个栈用于存储左括号字符for(charc:s){if(c=='('||c=='['||c=='{'){stk.push(c);//如果是左括号字符，将其压入栈中}else{if(stk.empty()){returnfalse;//如果栈为空，说明缺少左括号，返回false}chartop=stk.top();/*获取栈顶元素*/stk.pop();//弹出栈顶元素if(c==')'&top!='('){returnfalse;//如果当前字符是右括号且与栈顶元素不匹配，返回false}if(c==']'&top!='['){returnfalse;}if(c=='}'&top!='{'){returnfalse;}}}returnstk.empty();//最后判断栈是否为空，如果为空说明每个左括号都有匹配的右括号，则返回true，否则返回false}123456789101112131415161718192021222324252627282930说明：使用C++的标准库来实现栈，判断给定的字符串中的括号是否匹配。首先创建一个stack用于存储左括号字符。然后遍历字符串中的每个字符，如果是左括号字符，则将其压入栈中；如果是右括号字符，则与栈顶元素进行匹配。匹配成功则继续遍历，匹配失败则返回false。最后判断栈是否为空，如果为空则说明所有的括号都被匹配，返回true；否则，说明还有未匹配的括号，返回false。Python3版本classSolution:defisValid(self,s:str)->bool:stack=[]#创建一个栈用于存储左括号字符brackets={'(':')','[':']','{':'}'}forcharins:ifcharinbrackets.keys():#如果是左括号字符，将其压入栈中stack.append(char)elifcharinbrackets.values():#如果是右括号字符ifnotstack:#如果栈为空，说明缺少左括号，返回FalsereturnFalsetop=stack.pop()#弹出栈顶元素ifchar!=brackets[top]:#如果当前字符与栈顶元素不匹配，返回FalsereturnFalsereturnlen(stack)==0#判断栈是否为空，为空说明每个左括号都有匹配的右括号12345678910111213141516'运行运行说明：创建一个列表作为栈来判断给定的字符串中的括号是否匹配。首先定义了一个字典brackets，用来存储左括号和右括号的对应关系。然后遍历字符串中的每个字符，如果是左括号字符，则将其压入栈中；如果是右括号字符，则和栈顶元素进行匹配。匹配成功则继续遍历，匹配失败则返回False。最后判断栈是否为空，如果为空则说明所有的括号都被匹配，返回True；否则，说明还有未匹配的括号，返回False复杂度分析时间复杂度：O(n)，其中n是字符串s的长度。空间复杂度：O(n)，其中n为字符串的长度。在最坏情况下，所有的字符都是左括号，需要将其全部入栈，占用了O(n)的空间。这个算法具有线性时间复杂度和线性空间复杂度。循环队列设计（LeetCode622,Medium）标签：队列、数组题目设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作：MyCircularQueue(k):构造器，设置队列长度为k。Front:从队首获取元素。如果队列为空，返回-1。Rear:获取队尾元素。如果队列为空，返回-1。enQueue(value):向循环队列插入一个元素。如果成功插入则返回真。deQueue():从循环队列中删除一个元素。如果成功删除则返回真。isEmpty():检查循环队列是否为空。isFull():检查循环队列是否已满。示例：MyCircularQueuecircularQueue=newMyCircularQueue(3);//设置长度为3circularQueue.enQueue(1);//返回truecircularQueue.enQueue(2);//返回truecircularQueue.enQueue(3);//返回truecircularQueue.enQueue(4);//返回false，队列已满circularQueue.Rear();//返回3circularQueue.isFull();//返回truecircularQueue.deQueue();//返回truecircularQueue.enQueue(4);//返回truecircularQueue.Rear();//返回4提示：所有的值都在0至1000的范围内；操作数将在1至1000的范围内；请不要使用内置的队列库。原题：[LeetCode622](https://leetcode-cn.com/problems/design-circular-queue/)123456789101112131415161718192021222324252627282930313233思路及实现方式一：数组（不推荐）思路我们可以通过一个数组进行模拟，通过操作数组的索引构建一个虚拟的首尾相连的环。在循环队列结构中，设置一个队尾rear与队首front，且大小固定，结构如下图所示:在循环队列中，当队列为空，可知front=rear；而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，假设队列使用的数组有capacity个存储空间，则此时规定循环队列最多只能有capacity−1个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。根据以上可知，队列判空的条件是front=rear，而队列判满的条件是front=(rear+1)modcapacity。对于一个固定大小的数组，只要知道队尾rear与队首front，即可计算出队列当前的长度：(rear−front+capacity)modcapacity循环队列的属性如下:elements：一个固定大小的数组，用于保存循环队列的元素。capacity：循环队列的容量，即队列中最多可以容纳的元素数量。front：队列首元素对应的数组的索引。rear：队列尾元素对应的索引的下一个索引。循环队列的接口方法如下：MyCircularQueue(intk):初始化队列，同时base数组的空间初始化大小为k+1。front,rear全部初始化为0。enQueue(intvalue)：在队列的尾部插入一个元素，并同时将队尾的索引rear更新为(rear+1)modcapacity。deQueue()：从队首取出一个元素，并同时将队首的索引front更新为(front+1)modcapacity。Front()：返回队首的元素，需要检测队列是否为空。Rear()：返回队尾的元素，需要检测队列是否为空。isEmpty()：检测队列是否为空，根据之前的定义只需判断rear是否等于front。isFull()：检测队列是否已满，根据之前的定义只需判断front是否等于(rear+1)modcapacity。12345678代码实现Java版本classMyCircularQueue{privateintfront;//队头指针privateintrear;//队尾指针privateintcapacity;//队列容量privateint[]elements;//存储队列元素的数组publicMyCircularQueue(intk){capacity=k+1;//设置队列容量，需要额外留一个空位用于判断队满的条件elements=newint[capacity];//创建存储队列元素的数组rear=front=0;//初始化队头和队尾指针}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;//如果队列已满，无法入队，返回false}elements[rear]=value;//将元素放入队尾rear=(rear+1)%capacity;//队尾指针后移一位，通过取模实现循环returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;//如果队列为空，无法出队，返回false}front=(front+1)%capacity;//队头指针后移一位，通过取模实现循环returntrue;}publicintFront(){if(isEmpty()){return-1;//如果队列为空，返回-1}returnelements[front];//返回队头元素}publicintRear(){if(isEmpty()){return-1;//如果队列为空，返回-1}returnelements[(rear-1+capacity)%capacity];//返回队尾元素，通过(rear-1+capacity)%capacity实现循环}publicbooleanisEmpty(){returnrear==front;//队头指针等于队尾指针时，队列为空}publicbooleanisFull(){return(rear+1)%capacity==front;//队头指针的下一个位置等于队尾指针时，队列为满}}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152说明：代码实现了一个循环队列类MyCircularQueue，使用数组来存储队列的元素，并使用front和rear两个指针来指示队头和队尾的位置。在构造方法MyCircularQueue中，初始化capacity为k+1，由于要留出一个空位来判断队满的条件，因此数组的长度为capacity。在入队方法enQueue中，首先判断队列是否已满，如果已满则无法入队，返回false；否则将元素放入队尾，并将rear指针循环到下一个位置。在出队方法deQueue中，首先判断队列是否为空，如果为空则无法出队，返回false；否则将front指针循环到下一个位置。在Front方法中，如果队列为空则返回-1，否则返回front指针所指位置的元素。在Rear方法中，如果队列为空则返回-1，否则返回rear指针的前一个位置（通过(rear-1+capacity)%capacity来实现循环）。isEmpty方法用于判断队列是否为空，即判断rear与front是否相等。isFull方法用于判断队列是否已满，即判断(rear+1)%capacity是否等于front。这个代码中使用成员变量来存储队列的状态和数据，方法通过操作这些成员变量来实现对队列的操作。方法的返回值为布尔型，用于表示操作是否成功，而不是抛出异常来处理异常情况。C语言版本typedefstruct{intfront;//队头指针intrear;//队尾指针intcapacity;//队列容量int*elements;//存储队列元素的数组}MyCircularQueue;MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//分配队列结构体的内存空间obj->capacity=k+1;//设置队列容量，需要额外留一个空位用于判断队满的条件obj->front=obj->rear=0;//初始化队头和队尾指针为0obj->elements=(int*)malloc(sizeof(int)*obj->capacity);//创建存储队列元素的数组returnobj;}boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if((obj->rear+1)%obj->capacity==obj->front){returnfalse;//如果队列已满，无法入队，返回false}obj->elements[obj->rear]=value;//将元素放入队尾obj->rear=(obj->rear+1)%obj->capacity;//队尾指针后移一位，通过取模实现循环returntrue;}boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(obj->rear==obj->front){returnfalse;//如果队列为空，无法出队，返回false}obj->front=(obj->front+1)%obj->capacity;//队头指针后移一位，通过取模实现循环returntrue;}intmyCircularQueueFront(MyCircularQueue*obj){if(obj->rear==obj->front){return-1;//如果队列为空，返回-1}returnobj->elements[obj->front];//返回队头元素}intmyCircularQueueRear(MyCircularQueue*obj){if(obj->rear==obj->front){return-1;//如果队列为空，返回-1}returnobj->elements[(obj->rear-1+obj->capacity)%obj->capacity];//返回队尾元素，通过(rear-1+capacity)%capacity实现循环}boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj->rear==obj->front;//队头指针等于队尾指针时，队列为空}boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj->rear+1)%obj->capacity==obj->front;//队头指针的下一个位置等于队尾指针时，队列为满}voidmyCircularQueueFree(MyCircularQueue*obj){free(obj->elements);//释放存储队列元素的数组内存空间free(obj);//释放队列结构体内存空间}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859说明：使用结构体MyCircularQueue来存储队列的状态和数据。结构体中包括front和rear两个指针，capacity队列容量，以及存储队列元素的elements数组。Python3版本classMyCircularQueue:def__init__(self,k:int):self.front=self.rear=0#初始化队头和队尾指针self.elements=[0]*(k+1)#创建一个长度为k+1的数组来存储元素，留出一个空位作为判断队满的条件defenQueue(self,value:int)->bool:ifself.isFull():#如果队满，无法入队，返回FalsereturnFalseself.elements[self.rear]=value#将元素放入队尾self.rear=(self.rear+1)%len(self.elements)#队尾指针后移一位returnTruedefdeQueue(self)->bool:ifself.isEmpty():#如果队空，无法出队，返回FalsereturnFalseself.front=(self.front+1)%len(self.elements)#队头指针后移一位returnTruedefFront(self)->int:return-1ifself.isEmpty()elseself.elements[self.front]#如果队空，返回-1；否则返回队头元素defRear(self)->int:return-1ifself.isEmpty()elseself.elements[(self.rear-1)%len(self.elements)]#如果队空，返回-1；否则返回队尾元素defisEmpty(self)->bool:returnself.rear==self.front#队头指针等于队尾指针时，队列为空defisFull(self)->bool:return(self.rear+1)%len(self.elements)==self.front#队头指针的下一位等于队尾指针时，队列为满123456789101112131415161718192021222324252627282930'运行运行说明：代码实现了一个循环队列类MyCircularQueue，使用一个数组来存储队列元素，并用队头和队尾指针来指示队列的位置。在__init__方法中，初始化队头和队尾指针，并创建一个长度为k+1的数组来存储元素，其中k为传入的参数。在isFull方法中，通过判断队头指针的下一位是否等于队尾指针来判断队列是否为满。在isEmpty方法中，通过判断队头指针是否等于队尾指针来判断队列是否为空。enQueue方法实现元素的入队操作，先判断队列是否为满，如果为满则无法入队，返回False；否则将元素放入队尾，并将队尾指针后移一位。deQueue方法实现元素的出队操作，先判断队列是否为空，如果为空则无法出队，返回False；否则将队头指针后移一位。Front方法返回队列的队头元素，如果队列为空则返回-1。Rear方法返回队列的队尾元素，如果队列为空则返回-1。复杂度分析时间复杂度：初始化和每项操作的时间复杂度均为O(1)。空间复杂度：O(k)，其中k为给定的队列元素数目。方式二：链表（推荐）思路我们同样可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。循环队列的属性如下:head：链表的头节点，队列的头节点。tail：链表的尾节点，队列的尾节点。capacity：队列的容量，即队列可以存储的最大元素数量。size：队列当前的元素的数量。代码实现JavaclassMyCircularQueue{privateListNodehead;//队头节点privateListNodetail;//队尾节点privateintcapacity;//队列容量privateintsize;//当前队列的元素个数publicMyCircularQueue(intk){capacity=k;size=0;}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;//如果队列已满，无法入队，返回false}ListNodenode=newListNode(value);if(head==null){head=tail=node;//如果队列为空，设置头部和尾部节点为新节点}else{tail.next=node;//将新节点添加到尾部tail=node;//更新尾部节点}size++;//元素个数加1returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;//如果队列为空，无法出队，返回false}head=head.next;//将头部节点后移一位，实现出队操作size--;//元素个数减1returntrue;}publicintFront(){if(isEmpty()){return-1;//如果队列为空，返回-1}returnhead.val;//返回头部节点的值}publicintRear(){if(isEmpty()){return-1;//如果队列为空，返回-1}returntail.val;//返回尾部节点的值}publicbooleanisEmpty(){returnsize==0;//如果元素个数为0，队列为空}publicbooleanisFull(){returnsize==capacity;//如果元素个数等于队列容量，队列已满}}classListNode{intval;ListNodenext;publicListNode(intval){this.val=val;}}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566说明：MyCircularQueue类实现了一个循环队列，使用了链表来存储队列的元素。在构造方法MyCircularQueue中，初始化了队头节点head和队尾节点tail为null，队列的容量capacity为传入的参数k，当前队列元素个数size初始化为0。enQueue方法用于入队操作，首先判断队列是否已满，如果已满，则无法入队，返回false。创建一个新的节点node，如果队列为空，则将head和tail指针指向新节点；否则，将新节点添加到尾部，并更新tail指向新节点。元素个数size加1，并返回true表示入队成功。C语言typedefstruct{structListNode*head;//队头指针structListNode*tail;//队尾指针intcapacity;//队列容量intsize;//当前队列的元素个数}MyCircularQueue;MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建队列结构体并分配内存空间obj->capacity=k;//设置队列容量obj->size=0;//当前队列元素个数为0obj->head=obj->tail=NULL;//初始化队头和队尾指针为NULLreturnobj;}boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(obj->size>=obj->capacity){returnfalse;//如果队列已满，无法入队，返回false}structListNode*node=(structListNode*)malloc(sizeof(structListNode));//创建新节点并分配内存空间node->val=value;//设置节点的值node->next=NULL;//初始化节点的下一个指针为NULLif(!obj->head){obj->head=obj->tail=node;//如果队列为空，设置头部和尾部指针为新节点}else{obj->tail->next=node;//将新节点添加到尾部obj->tail=node;//更新尾部指针}obj->size++;//当前队列元素个数加1returntrue;}boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(obj->size==0){returnfalse;//如果队列为空，无法出队，返回false}structListNode*node=obj->head;//保存当前头部节点obj->head=obj->head->next;//头部指针后移一位，实现出队操作obj->size--;//当前队列元素个数减1free(node);//释放出队节点的内存returntrue;}intmyCircularQueueFront(MyCircularQueue*obj){if(obj->size==0){return-1;//如果队列为空，返回-1}returnobj->head->val;//返回头部节点的值}intmyCircularQueueRear(MyCircularQueue*obj){if(obj->size==0){return-1;//如果队列为空，返回-1}returnobj->tail->val;//返回尾部节点的值}boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj->size==0;//如果当前队列元素个数为0，队列为空}boolmyCircularQueueIsFull(MyCircularQueue*obj){returnobj->size==obj->capacity;//如果当前队列元素个数等于队列容量，队列已满}voidmyCircularQueueFree(MyCircularQueue*obj){for(structListNode*curr=obj->head;curr;){//遍历整个队列，从头部开始structListNode*node=curr;//保存当前节点curr=curr->next;//移动到下一个节点free(node);//释放当前节点的内存}free(obj);//释放队列结构体的内存}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374说明：使用了结构体来存储队列的状态和数据。在myCircularQueueCreate函数中，初始化了队列的容量capacity为传入的参数k，当前队列元素个数size为0，并将队头head和队尾tail指针初始化为NULL。Python3classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextclassMyCircularQueue:def__init__(self,k:int):self.head=self.tail=None#队头和队尾指针，用于指向队列的头部和尾部self.capacity=k#队列容量self.size=0#当前队列中的元素个数defenQueue(self,value:int)->bool:ifself.isFull():#如果队列已满，无法入队，返回FalsereturnFalsenode=ListNode(value)#创建一个新节点ifself.headisNone:#如果队列为空，设置头部和尾部指针为新节点self.head=nodeself.tail=nodeelse:self.tail.next=node#将新节点添加到尾部self.tail=node#更新尾部指针self.size+=1#元素个数加1returnTruedefdeQueue(self)->bool:ifself.isEmpty():#如果队列为空，无法出队，返回FalsereturnFalseself.head=self.head.next#将头部指针后移一位，实现出队操作self.size-=1#元素个数减1returnTruedefFront(self)->int:return-1ifself.isEmpty()elseself.head.val#如果队列为空，返回-1；否则返回头部节点的值defRear(self)->int:return-1ifself.isEmpty()elseself.tail.val#如果队列为空，返回-1；否则返回尾部节点的值defisEmpty(self)->bool:returnself.size==0#如果元素个数为0，队列为空defisFull(self)->bool:returnself.size==self.capacity#如果元素个数等于队列容量，队列已满12345678910111213141516171819202122232425262728293031323334353637383940414243'运行运行说明：使用链表来存储队列的元素。ListNode是节点结构体，用于表示队列中的每个节点。MyCircularQueue类的初始化方法__init__中，初始化队头和队尾指针为None，队列容量为k，当前队列的元素个数为0。enQueue方法用于入队操作，首先判断队列是否已满，如果已满则无法入队，返回False。创建一个新节点，如果队列为空，设置头部和尾部指针为新节点；否则，将新节点添加到队尾，并更新尾部指针。元素个数加1，并返回True表示入队成功。复杂度分析时间复杂度：初始化和每项操作的时间复杂度均为O(1)。空间复杂度：O(k)，其中k为给定的队列元素数目。数组VS链表方面数组链表存储方式连续的内存空间非连续的内存空间插入和删除操作O(n)O(1)随机访问O(1)O(n)内存效率较高（不需要额外指针空间）较低（需要额外指针空间）大小变化需要重新分配内存空间可以动态变化实现复杂性相对简单相对复杂对称二叉树（LeetCode101,Easy）标签：二叉树递归、对称性判断题目给你一个二叉树的根节点root，检查它是否轴对称。示例1：输入：root=[1,2,2,3,4,4,3]输出：true示例2：输入：root=[1,2,2,null,3,null,3]输出：false提示：树中节点数目在范围[1,1000]内-100/*structTreeNode{intval;structTreeNode*left;structTreeNode*right;};*/boolisMirror(structTreeNode*left,structTreeNode*right);boolisSymmetric(structTreeNode*root){if(root==NULL){returntrue;//如果根节点为NULL，即空树，视为对称二叉树，返回true}returnisMirror(root->left,root->right);//调用isMirror函数判断左子树和右子树是否对称}boolisMirror(structTreeNode*left,structTreeNode*right){if(left==NULL&right==NULL){returntrue;//如果左子树和右子树都为NULL，也视为对称，返回true}if(left==NULL||right==NULL){returnfalse;//如果左子树和右子树只有一个为NULL，视为不对称，返回false}return(left->val==right->val)&isMirror(left->left,right->right)&isMirror(left->right,right->left);//如果左子树和右子树的值相等，并且同时满足左子树的左子树和右子树的右子树对称，//以及左子树的右子树和右子树的左子树对称，则视为对称，返回true；否则，返回false}123456789101112131415161718192021222324252627282930Python3版本classSolution:defisSymmetric(self,root:TreeNode)->bool:ifrootisNone:returnTrue#如果根节点为空，返回True，空树被认为是对称的returnself.isMirror(root.left,root.right)defisMirror(self,left:TreeNode,right:TreeNode)->bool:ifleftisNoneandrightisNone:returnTrue#如果左子树和右子树都为空，认为是对称的ifleftisNoneorrightisNone:returnFalse#如果左子树和右子树只有一个为空，不对称returnleft.val==right.valandself.isMirror(left.left,right.right)andself.isMirror(left.right,right.left)#比较左子树的左子树和右子树的右子树，以及左子树的右子树和右子树的左子树，满足条件才认为是对称的#假设定义了TreeNode类，包含val、left和right属性classTreeNode:def__init__(self,val:int=0,left:TreeNode=None,right:TreeNode=None):self.val=valself.left=leftself.right=right12345678910111213141516171819202122232425说明：代码中使用了TreeNode类来定义树节点，包含val、left和right属性。其中val存储节点的值，left和right存储左子树和右子树的引用。复杂度分析时间复杂度：O(n)，其中n表示树的节点数。空间复杂度：O(n)，递归调用的栈空间最多为树的高度。方式二：队列（迭代）思路回想下递归的实现：当两个子树的根节点相等时，就比较:左子树的left和右子树的right，这个比较是用递归实现的。现在我们改用队列来实现，思路如下：首先从队列中拿出两个节点(left和right)比较：将left的left节点和right的right节点放入队列将left的right节点和right的left节点放入队列代码实现Java版本//leetcodesubmitregionbegin(Prohibitmodificationanddeletion)importjava.util.LinkedList;classSolution{publicbooleanisSymmetric(TreeNoderoot){if(root==null){returnfalse;//根节点为空，不算对称}if(root.left==null&root.right==null){returntrue;//左右子树都为空，算对称}LinkedListqueue=newLinkedList();//使用队列来保存待比较的节点queue.add(root.left);queue.add(root.right);while(queue.size()>0){TreeNodeleft=queue.removeFirst();TreeNoderight=queue.removeFirst();//只要两个节点都为空，继续循环；两者有一个为空，返回falseif(left==null&right==null){continue;}if(left==null||right==null){returnfalse;}//判断两个节点的值是否相等if(left.val!=right.val){returnfalse;}//将左节点的左子节点和右节点的右子节点放入队列queue.add(left.left);queue.add(right.right);//将左节点的右子节点和右节点的左子节点放入队列queue.add(left.right);queue.add(right.left);}returntrue;}}//leetcodesubmitregionend(Prohibitmodificationanddeletion)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647说明：这段代码使用迭代方法判断二叉树是否对称。在isSymmetric方法中，首先判断根节点是否为空，如果为空，返回false，表示不对称。然后，如果根节点的左右子树都为空，返回true，表示对称（只有一个元素的case）。接下来，创建一个队列queue，并将根节点的左子节点和右子节点加入队列。然后进入循环，每次从队列中取出两个节点进行比较。在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回false。将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回true，表示对称。这段代码使用了迭代方法，利用队列存储待比较的节点，逐层按顺序比较，避免了递归方法的额外栈空间开销。C语言版本//leetcodesubmitregionbegin(Prohibitmodificationanddeletion)#includestructTreeNode{intval;structTreeNode*left;structTreeNode*right;};boolisSymmetric(structTreeNode*root){if(root==NULL){returnfalse;//根节点为空，不算对称}structTreeNode*queue[10000];//使用队列来保存待比较的节点intfront=0,rear=0;queue[rear++]=root->left;queue[rear++]=root->right;while(rear!=front){structTreeNode*left=queue[front++];structTreeNode*right=queue[front++];//只要两个节点都为空，继续循环；两者有一个为空，返回falseif(left==NULL&right==NULL){continue;}if(left==NULL||right==NULL){returnfalse;}//判断两个节点的值是否相等if(left->val!=right->val){returnfalse;}//将左节点的左子节点和右节点的右子节点放入队列queue[rear++]=left->left;queue[rear++]=right->right;//将左节点的右子节点和右节点的左子节点放入队列queue[rear++]=left->right;queue[rear++]=right->left;}returntrue;}//leetcodesubmitregionend(Prohibitmodificationanddeletion)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950说明：这段代码使用C语言实现了迭代方法来判断二叉树是否对称。在isSymmetric函数中，首先判断根节点是否为空，如果为空，返回false，表示不对称。创建一个队列queue，使用数组来保存待比较的节点。使用front和rear变量分别表示队首和队尾的索引。将根节点的左子节点和右子节点依次加入队列queue。然后进入循环，每次从队列中取出两个节点进行比较。在比较过程中，只要两个节点均为空，继续循环；如果只有一个节点为空，返回false，表示不对称。然后，比较两个节点的值是否相等，如果不相等，返回false。将左节点的左子节点和右节点的右子节点放入队列，用于后续比较。同时，将左节点的右子节点和右节点的左子节点放入队列，也用于后续比较。当队列为空时，表示所有节点都已比较完毕，没有发现不对称的情况，返回true，表示对称。这段代码使用了迭代方法，利用数组队列方式存储待比较的节点，逐个按序比较，避免了递归方法的额外栈空间开销。Python3版本classSolution:defisSymmetric(self,root:TreeNode)->bool:ifrootisNone:returnFalse#根节点为空，不算对称queue=[]queue.append(root.left)queue.append(root.right)whilequeue:left=queue.pop(0)right=queue.pop(0)ifleftisNoneandrightisNone:continue#只要两个节点都为空，继续循环ifleftisNoneorrightisNone:returnFalse#两者有一个为空，返回False，不对称ifleft.val!=right.val:returnFalse#节点值不相等，不对称queue.append(left.left)#左节点的左子节点入队列queue.append(right.right)#右节点的右子节点入队列queue.append(left.right)#左节点的右子节点入队列queue.append(right.left)#右节点的左子节点入队列returnTrue#队列为空，所有节点比较完毕，对称1234567891011121314151617181920212223242526272829说明：（基础说明可查看java或者c的实现）在函数参数的类型注解中，使用了TreeNode类型来标注root参数的类型。使用了is运算符来判断节点是否为None。is运算符比较的是对象的身份标识，用于判断对象是否是同一个对象。这里用它来判断节点是否为None。使用了列表queue来实现队列的功能，通过append()方法将节点加入队列的尾部，通过pop(0)方法来从队列的头部取出节点。Python的列表可以很方便地实现队列的功能。复杂度分析时间复杂度：O(n)，其中n表示树的节点数。在最坏情况下，需要遍历树的所有节点。空间复杂度：O(n)，最坏情况下，队列中需要存储树的一层节点，所以空间复杂度与树的高度有关。在最坏情况下，树的高度为n/2，因此空间复杂度为O(n)。综合来看，这个算法的时间复杂度和空间复杂度都是O(n)，其中n表示树的节点数。算法的性能随着节点数的增加而线性增长。两个数组的交集II（LeetCode350,Easy）标签：哈希表、数组题目给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。示例1：输入：nums1=[1,2,2,1],nums2=[2,2]输出：[2,2]示例2:输入：nums1=[4,9,5],nums2=[9,4,9,8,4]输出：[4,9]提示：1numMap=newHashMap();Listres=newArrayList();//遍历nums1数组，将元素及其出现次数存储在哈希表中for(intnum:nums1){numMap.put(num,numMap.getOrDefault(num,0)+1);}//遍历nums2数组，检查每个元素是否在哈希表中出现//如果出现，将该元素添加到结果集中，并将哈希表中的对应出现次数减1for(intnum:nums2){if(numMap.containsKey(num)&numMap.get(num)>0){res.add(num);numMap.put(num,numMap.get(num)-1);}}//将结果集转换为数组输出int[]result=newint[res.size()];for(inti=0;i#include/***返回两个整数中的较小值*/intmin(inta,intb){returna0){res[resSize++]=nums2[i];numMap[nums2[i]]--;}}*returnSize=resSize;//将结果集的大小赋给返回值free(numMap);//释放动态分配的内存returnres;//返回结果集数组的指针}123456789101112131415161718192021222324252627282930313233说明：使用数组numMap来存储nums1数组中每个元素及其出现的次数，数组下标表示元素值。遍历nums2数组，对于每个元素nums2[i]，如果numMap[nums2[i]]大于0，则将nums2[i]添加到结果集res中，并将numMap[nums2[i]]减1。使用动态分配的数组res来存储交集结果，动态分配的内存大小为较小的数组大小min(nums1Size,nums2Size)。将结果集的大小resSize赋给returnSize，即将结果集的大小返回给调用函数。使用free()函数释放动态分配的内存。Python3版本classSolution:defintersect(self,nums1,nums2):#使用哈希表来存储nums1中每个元素及其出现的次数numMap={}fornuminnums1:numMap[num]=numMap.get(num,0)+1res=[]#遍历nums2数组，检查每个元素在哈希表中是否存在#如果存在且对应出现次数大于0，则加入结果集，并将对应出现次数减1fornuminnums2:ifnuminnumMapandnumMap[num]>0:res.append(num)numMap[num]-=1returnres12345678910111213141516'运行运行说明：使用字典numMap来存储nums1数组中每个元素及其出现的次数。遍历nums2数组，对于每个元素num，如果num在numMap中存在且对应出现次数大于0，则将num添加到结果集res中，并将numMap[num]减1。返回结果集res。复杂度分析时间复杂度：O(max(m,n))，其中m和n分别表示两个输入数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。空间复杂度：O(min(m,n))，表示两个输入数组中较小的那个数组的长度方式二：排序+双指针思路如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。首先对两个数组进行排序，然后使用两个指针遍历两个数组。初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。代码实现Java版本classSolution{publicint[]intersect(int[]nums1,int[]nums2){//对两个数组进行排序Arrays.sort(nums1);Arrays.sort(nums2);//获取两个数组的长度intlength1=nums1.length,length2=nums2.length;//创建结果数组，长度为两个数组中较小的长度int[]intersection=newint[Math.min(length1,length2)];//初始化指针和结果数组的索引intindex1=0,index2=0,index=0;//双指针法求交集while(index1nums2[index2]){index2++;//nums2的元素较小，移动nums2的指针}else{//相等，加入结果数组，同时移动两个指针和结果数组的索引intersection[index]=nums1[index1];index1++;index2++;index++;}}//返回交集结果数组，利用Arrays.copyOfRange()截取结果数组的有效部分returnArrays.copyOfRange(intersection,0,index);}}1234567891011121314151617181920212223242526272829303132333435说明：首先，对两个输入的数组nums1和nums2进行排序，这里使用了Arrays.sort()方法。时间复杂度为O(nlogn)，其中n分别表示两个数组的长度。初始化指针index1和index2分别指向数组nums1和nums2的起始位置，同时初始化结果数组的索引index为0。创建结果数组intersection，长度为两个数组长度较小的那个。使用双指针法进行比较：如果nums1[index1]小于nums2[index2]，说明nums1的元素较小，将index1向后移动。如果nums1[index1]大于nums2[index2]，说明nums2的元素较小，将index2向后移动。如果nums1[index1]等于nums2[index2]，说明找到了一个交集元素，将该元素加入结果数组intersection中，并将两个指针和结果数组的索引都向后移动。当有一个指针越界时，表示已经遍历完其中一个数组，此时得到的结果数组即为两个数组的交集。最后，利用Arrays.copyOfRange()方法截取结果数组intersection的有效部分（0到index-1），并返回新的数组作为输出。C语言版本#includeintcmp(constvoid*a,constvoid*b){return(*(int*)a-*(int*)b);}int*intersect(int*nums1,intnums1Size,int*nums2,intnums2Size,int*returnSize){//对两个数组进行排序qsort(nums1,nums1Size,sizeof(int),cmp);qsort(nums2,nums2Size,sizeof(int),cmp);//创建结果数组，长度为两个数组中较小的大小int*intersection=(int*)malloc(sizeof(int)*(nums1Sizenums2[index2]){index2++;//nums2的元素较小，移动nums2的指针}else{//相等，加入结果数组，同时移动两个指针和结果数组的索引intersection[index]=nums1[index1];index1++;index2++;index++;}}//返回交集结果数组的大小*returnSize=index;returnintersection;}1234567891011121314151617181920212223242526272829303132333435363738说明：使用qsort()函数对输入的两个数组nums1和nums2进行排序。这里使用了自定义的比较函数cmp()来指定排序规则。排序后，两个数组中的元素将按照从小到大的顺序排列。创建一个结果数组intersection，长度为两个数组中较小的那个。使用动态内存分配函数malloc()来分配存储交集结果所需的内存空间。初始化两个指针index1和index2，分别指向数组nums1和nums2的起始位置。同时，初始化结果数组的索引index为0。使用双指针法进行比较遍历：如果nums1[index1]小于nums2[index2]，说明nums1的元素较小，将index1向后移动。如果nums1[index1]大于nums2[index2]，说明nums2的元素较小，将index2向后移动。如果nums1[index1]等于nums2[index2]，说明找到了一个交集元素，将该元素加入结果数组intersection中，并将两个指针和结果数组的索引都向后移动。当有一个指针越界时，表示已经遍历完其中一个数组，此时得到的结果数组即为两个数组的交集。使用指针returnSize来记录交集结果数组的大小。返回交集结果数组intersection的指针。Python3版本classSolution:defintersect(self,nums1ist[int],nums2ist[int])->List[int]:#对两个数组进行排序nums1.sort()nums2.sort()#获取两个数组的长度length1,length2=len(nums1),len(nums2)#创建一个空列表来存储交集结果intersection=list()#初始化两个指针index1=index2=0#双指针法求交集whileindex1nums2[index2]:index2+=1else:#相等，加入结果列表，同时移动两个指针intersection.append(nums1[index1])index1+=1index2+=1#返回交集结果列表returnintersection123456789101112131415161718192021222324252627282930说明：对输入的两个数组nums1和nums2进行排序，这里使用了Python内置的sort()方法，能在原地排序。创建一个空列表intersection来存储交集结果。使用双指针法进行比较，分别初始化index1和index2为0，它们分别指向数组nums1和nums2的起始位置。遍历两个数组，比较当前指针位置上的元素大小。如果nums1[index1]小于nums2[index2]，则index1向右移动。如果nums1[index1]大于nums2[index2]，则index2向右移动。如果nums1[index1]等于nums2[index2]，则找到一个交集元素，加入结果列表intersection中，并同时移动两个指针。当有一个指针越界时，表示已经遍历完其中一个数组，那么结果列表intersection中存储的就是两个数组的交集。返回交集结果列表intersection。复杂度分析时间复杂度：O(mlogm+nlogn)，其中m和n分别是两个数组的长度。对两个数组进行排序的时间复杂度是O(mlogm+nlogn)，遍历两个数组的时间复杂度是O(m+n)，因此总时间复杂度是O(mlogm+nlogn)。空间复杂度：O(min(m,n))，其中m和n分别是两个数组的长度。为返回值创建一个数组intersection，其长度为较短的数组的长度。不过在C++中，我们可以直接创建一个vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为O(1)。最长公共前缀（LeetCode14,Easy）标签：字符串处理、前缀判断题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。示例1：输入：strs=["flower","flow","flight"]输出："fl"示例2：输入：strs=["dog","racecar","car"]输出：""解释：输入不存在公共前缀。提示：1#include#includechar*longestCommonPrefix(char**strs,intstrsSize){//如果字符串数组为空或者长度为0，则返回空字符串if(strs==NULL||strsSize==0)return"";//将第一个字符串作为初始的最长公共前缀char*prefix=strs[0];//遍历数组剩余的字符串，更新最长公共前缀for(inti=1;istr:#如果字符串数组为空，则返回空字符串ifnotstrs:return""#将数组的第一个字符串作为初始的最长公共前缀prefix,count=strs[0],len(strs)#遍历数组剩余的字符串，更新最长公共前缀foriinrange(1,count):prefix=self.lcp(prefix,strs[i])#如果最长公共前缀为空，则跳出循环ifnotprefix:breakreturnprefix#求取两个字符串的最长公共前缀deflcp(self,str1,str2):#获取两个字符串的最小长度length,index=min(len(str1),len(str2)),0#遍历两个字符串，找到最长公共前缀的结束索引whileindex#include//函数声明char*longestCommonPrefix(char**strs,intstrsSize);/**获取两个字符串的最长公共前缀*参数:str1-字符串1,str2-字符串2*返回值:最长公共前缀的指针*/char*commonPrefix(char*str1,char*str2);/**获取字符串数组中的最长公共前缀*参数:strs-字符串数组,strsSize-字符串数组的长度*返回值:最长公共前缀的指针*/char*longestCommonPrefix(char**strs,intstrsSize){//如果字符串数组为空或者长度为0，直接返回空字符串if(strs==NULL||strsSize==0){return"";}//将第一个字符串作为初始的最长公共前缀char*prefix=strs[0];//遍历剩余的字符串for(inti=1;istr:#定义递归函数，用于求取字符串数组中指定范围内的最长公共前缀deflcp(start,end):#如果范围中只有一个字符串，则直接返回该字符串作为最长公共前缀ifstart==end:returnstrs[start]#分治法，将范围划分为两部分，分别求取左右两部分的最长公共前缀mid=(start+end)//2lcpLeft,lcpRight=lcp(start,mid),lcp(mid+1,end)#找到左右两部分最长公共前缀的最小长度minLength=min(len(lcpLeft),len(lcpRight))#在最小长度范围内逐个字符比较foriinrange(minLength):iflcpLeft[i]!=lcpRight[i]:#遇到第一个不相等的字符，返回前缀部分returnlcpLeft[:i]#返回最小长度范围内的最长公共前缀returnlcpLeft[:minLength]#如果字符串数组为空，则返回空字符串return""ifnotstrselselcp(0,len(strs)-1)1234567891011121314151617181920212223242526说明：使用分治法，将指定范围划分为左右两部分，分别求取它们的最长公共前缀。计算中间索引mid。调用lcp()函数求取左半部分的最长公共前缀lcpLeft。调用lcp()函数求取右半部分的最长公共前缀lcpRight。找到左右两部分最长公共前缀的最小长度。在最小长度范围内逐个字符比较左右两部分的对应位置字符。如果遇到第一个不相等的字符，返回当前位置前的子串作为最长公共前缀。返回最小长度范围内的最长公共前缀。如果字符串数组为空，则返回空字符串。否则，调用lcp()函数，传入起始索引0和结束索引len(strs)-1，求取整个字符串数组的最长公共前缀。longestCommonPrefix()方法是主函数，用于启动递归过程并处理边界情况。lcp()函数是一个内部递归函数，用于求取字符串数组中指定范围内的最长公共前缀复杂度分析时间复杂度：O(mn)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。时间复杂度的递推式是T(n)=2⋅T(2n)+O(m)，通过计算可得T(n)=O(mn)。空间复杂度：O(mlogn)，其中m是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为logn，每层需要m的空间存储返回结果。方式四：二分查找显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用minLength表示字符串数组中的最短字符串的长度，则可以在[0,minLength]的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值mid，判断每个字符串的长度为mid的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于mid，如果不相同则最长公共前缀的长度一定小于mid，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。代码实现Java版本classSolution{publicStringlongestCommonPrefix(String[]strs){//如果字符串数组为空或长度为0，直接返回空字符串if(strs==null||strs.length==0){return"";}//获取字符串数组中最短字符串的长度intminLength=Integer.MAX_VALUE;for(Stringstr:strs){minLength=Math.min(minLength,str.length());}//使用二分查找的思路来查找最长公共前缀intlow=0,high=minLength;while(low=high时，二分查找结束，得到最长公共前缀的长度。返回最长公共前缀，使用strs[0].substring(0,low)来截取对应长度的前缀。isCommonPrefix()方法用于判断指定长度的前缀是否是字符串数组strs的公共前缀。获取第一个字符串的指定长度前缀str0。遍历剩余的字符串，逐个比较前缀中的字符。如果存在不相等的字符，说明不是公共前缀，返回false。如果所有字符串的前缀字符都相等，说明是公共前缀，返回true。C语言版本#include#include#include//函数声明char*longestCommonPrefix(char**strs,intstrsSize);intisCommonPrefix(char**strs,intstrsSize,intlen);/**intmain(){//测试数据char*strs[]={"flower","flow","flight"};intstrsSize=3;//调用函数并打印结果char*result=longestCommonPrefix(strs,strsSize);printf("LongestCommonPrefix:%s\n",result);return0;}**//**获取字符串数组中的最长公共前缀*参数:strs-字符串数组,strsSize-字符串数组的长度*返回值:最长公共前缀的指针*/char*longestCommonPrefix(char**strs,intstrsSize){//如果字符串数组为空或长度为0，直接返回空字符串if(strs==NULL||strsSize==0){return"";}//找出最短字符串的长度intminLength=INT_MAX;for(inti=0;i