Hot100 代码随想录：最长回文子串、合并有序数组与合并链表

Java刷题笔记0923最长回文子串、合并有序数组与合并链表学习日期09 月 23 日关键词中心扩展、双指针、虚拟头节点、排序算法本篇包含三道题分别练习字符串中心扩展、数组尾部双指针和链表虚拟头节点并在最后复习常用排序算法。一、最长回文子串题目链接LeetCode 5. 最长回文子串回文字符串从左向右和从右向左读取相同奇数长度aba 偶数长度abba1. 方法一枚举子串并判断枚举子串的左右边界再使用双指针判断是否为回文。classSolution{publicStringlongestPalindrome(Strings){intmaxLength0;intstart0;for(inti0;is.length();i){for(intji;js.length();j){if(isPalindrome(s,i,j)j-i1maxLength){maxLengthj-i1;starti;}}}returns.substring(start,startmaxLength);}privatebooleanisPalindrome(Strings,intleft,intright){while(leftright){if(s.charAt(left)!s.charAt(right)){returnfalse;}left;right--;}returntrue;}}复杂度子串数量为O(n²)每次判断回文最坏为O(n)总时间复杂度为O(n³)空间复杂度为O(1)。该方法适合建立基本思路但字符串稍长时效率较低。2. 方法二中心扩展回文串一定围绕中心对称。以每个位置为中心向两侧扩展并分别处理奇数回文中心(i, i) 偶数回文中心(i, i 1)classSolution{publicStringlongestPalindrome(Strings){intstart0;intmaxLength0;for(inti0;is.length();i){intoddLengthexpand(s,i,i);intevenLengthexpand(s,i,i1);intlengthMath.max(oddLength,evenLength);if(lengthmaxLength){maxLengthlength;starti-(length-1)/2;}}returns.substring(start,startmaxLength);}privateintexpand(Strings,intleft,intright){while(left0rights.length()s.charAt(left)s.charAt(right)){left--;right;}returnright-left-1;}}为什么长度是right-left-1循环停止时left和right已经分别多走了一步所以真正的回文区间是[left 1, right - 1]长度为(right - 1) - (left 1) 1 right - left - 1复杂度时间复杂度O(n²)空间复杂度O(1)。3. 方法补充这道题还可以使用动态规划时间O(n²)空间O(n²)Manacher算法时间O(n)但实现和理解成本更高。面试和常规刷题中中心扩展通常在代码复杂度和运行效率之间取得了较好的平衡。二、合并两个有序数组题目链接LeetCode 88. 合并两个有序数组nums1的长度为mn前m个位置保存有效元素后面预留空间用于合并nums2。1. 方法一从尾部开始的三指针这不是“边插边排”更准确的名称是逆向双指针合并。如果从数组头部填充可能覆盖nums1中尚未比较的元素从尾部开始则不会产生覆盖问题。classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){intp1m-1;intp2n-1;intwritemn-1;while(p20){if(p10nums1[p1]nums2[p2]){nums1[write--]nums1[p1--];}else{nums1[write--]nums2[p2--];}}}}为什么只需要判断while(p20)如果nums2先处理完nums1剩余元素本来就在正确位置如果nums1先处理完继续把nums2剩余元素写入nums1即可。复杂度时间复杂度O(mn)空间复杂度O(1)。2. 方法二先复制再排序classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){for(inti0;in;i){nums1[mi]nums2[i];}Arrays.sort(nums1);}}复杂度复制O(n)排序O((mn)log(mn))总时间复杂度O((mn)log(mn))。代码更短但没有利用两个数组原本已经有序的条件。三、合并两个有序链表题目链接LeetCode 21. 合并两个有序链表1. 虚拟头节点如果直接构造结果链表需要单独处理“第一个节点是谁”。使用虚拟头节点dummy后每一次追加节点都可以使用相同逻辑。classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummynewListNode(-1);ListNodetaildummy;while(list1!nulllist2!null){if(list1.vallist2.val){tail.nextlist1;list1list1.next;}else{tail.nextlist2;list2list2.next;}tailtail.next;}tail.next(list1!null)?list1:list2;returndummy.next;}}这里要区分两个指针dummy始终保存结果链表虚拟头部的位置 tail不断向后移动指向结果链表的最后一个节点原代码中ListNodedummynewListNode();ListNoderesnewListNode();resdummy;第二次创建的节点会立即被覆盖没有实际作用。直接写成ListNodedummynewListNode(-1);ListNodetaildummy;即可。复杂度时间复杂度O(mn)空间复杂度O(1)复用了原链表节点。四、数组合并与链表合并的共同思想两道合并题都利用了输入已经有序这一条件比较两个候选元素 ↓ 选择更合适的一个放入结果 ↓ 移动对应指针区别在于场景主要问题解决方法数组合并从头写会覆盖有效元素从尾部向前写链表合并第一个结果节点需要特殊处理使用虚拟头节点五、常用排序算法复习1. 冒泡排序相邻元素两两比较把较大的元素逐轮移动到末尾。publicstaticvoidbubbleSort(int[]nums){for(intendnums.length-1;end0;end--){booleanswappedfalse;for(inti0;iend;i){if(nums[i]nums[i1]){inttempnums[i];nums[i]nums[i1];nums[i1]temp;swappedtrue;}}if(!swapped){break;}}}平均时间复杂度O(n²)最好时间复杂度优化后为O(n)空间复杂度O(1)稳定排序。2. 选择排序每轮从未排序区域中选出最小元素放到当前起始位置。publicstaticvoidselectionSort(int[]nums){for(inti0;inums.length-1;i){intminIndexi;for(intji1;jnums.length;j){if(nums[j]nums[minIndex]){minIndexj;}}inttempnums[i];nums[i]nums[minIndex];nums[minIndex]temp;}}时间复杂度O(n²)空间复杂度O(1)通常不稳定。3. 快速排序选择一个基准值将较小元素放在左侧、较大元素放在右侧然后递归处理两部分。publicstaticvoidquickSort(int[]nums,intleft,intright){if(leftright){return;}intpivotIndexpartition(nums,left,right);quickSort(nums,left,pivotIndex-1);quickSort(nums,pivotIndex1,right);}privatestaticintpartition(int[]nums,intleft,intright){intpivotnums[right];intsmallerleft;for(intileft;iright;i){if(nums[i]pivot){inttempnums[i];nums[i]nums[smaller];nums[smaller]temp;smaller;}}inttempnums[smaller];nums[smaller]nums[right];nums[right]temp;returnsmaller;}平均时间复杂度O(n log n)最坏时间复杂度O(n²)递归栈平均为O(log n)通常不稳定。实际使用时可通过随机选择基准值降低持续遇到最坏情况的风险。4. 桶排序桶排序先按数值范围把元素分配到多个桶中每个桶内部排序后再依次合并。原数据 ↓ 按范围分桶 桶009 桶11019 桶22029 ↓ 桶内排序并合并 有序结果桶排序适合数据分布比较均匀能够合理划分数值范围额外空间可以接受。在分布较均匀、桶数量设计合理时平均性能可以接近O(n)但如果所有元素都进入同一个桶性能会退化为桶内排序算法的复杂度。5. 排序对比排序算法平均时间最坏时间额外空间稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)平均O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定桶排序依赖数据分布依赖桶内排序O(nk)取决于实现“稳定”指的是两个值相等的元素经过排序后原有的相对顺序是否保持不变。六、复盘今天的三道题分别对应三个值得复用的模板回文字符串 → 枚举中心并向两侧扩展 合并有序数组 → 从尾部写入避免覆盖 合并有序链表 → dummy固定头部tail负责移动做题时应该优先利用题目提供的条件。例如“两个数组已经有序”意味着不需要重新完整排序“结果直接写入nums1”意味着需要思考如何避免覆盖原有数据。