【leetcode HOT100 一句话题解】困难题(持续更新中)

HOT100 按照难度降序排列4.寻找两个正序数组的中位数寻找两个正序数组的第k kk大如果A AA数组划分成a [ 1 x ] a[1x]a[1x]a [ x 1 n ] a[x1n]a[x1n]那么B BB数组划分为b [ 1 k − x ] b[1k-x]b[1k−x]b [ k − x 1 m ] b[k-x1m]b[k−x1m]数组有序只要保证m a x ( a [ x ] b [ k − x ] ) m i n ( a [ x 1 ] b [ k − x 1 ] ) max(a[x]b[k-x]) min(a[x1]b[k-x1])max(a[x]b[k−x])min(a[x1]b[k−x1])二分最大的x xxs.t.a [ x ] ≤ b [ k − x 1 ] a[x] \leq b[k-x1]a[x]≤b[k−x1]即可。本题边界条件比较复杂。classSolution{public:doublefindMedianSortedArrays(vectorintnums1,vectorintnums2){intmstatic_castint(nums1.size());intnstatic_castint(nums2.size());inttotalmn;intktotal/2;// l 表示 nums1 左半部分最后一个元素的下标// 因此 l 可以为 -1表示 nums1 左边不取元素intlmax(-1,k-n-1);intrmin(m-1,k-1);while(lr){// 上中位数配合 l mid避免死循环intmidl(r-l1)/2;// mid 一定处于合法数组下标范围if(nums1[mid]nums2[k-mid-1]){lmid;}else{rmid-1;}}// nums1 左边取 i 个nums2 左边取 j 个intil1;intjk-i;longlongnums1Lefti0?LLONG_MIN:nums1[i-1];longlongnums1Rightim?LLONG_MAX:nums1[i];longlongnums2Leftj0?LLONG_MIN:nums2[j-1];longlongnums2Rightjn?LLONG_MAX:nums2[j];longlongrightMinmin(nums1Right,nums2Right);if(total%21){returnstatic_castdouble(rightMin);}longlongleftMaxmax(nums1Left,nums2Left);return(static_castdouble(leftMax)static_castdouble(rightMin))/2.0;}};10. 正则表达式匹配设布尔数组f[i][j]表示字符串p的前i位与字符串s的前j位能否匹配动态规划分情况讨论即可。需要注意的是 * 可以匹配0个/1个/多个字符。classSolution{public:boolisMatch(string s,string p){boolf[21][21];intlenss.length();intlenpp.length();for(inti0;ilenp;i){for(intj0;jlens;j){f[i][j]0;}}f[0][0]1;for(inti1;ilenp;i){if(p[i-1]*)f[i][0]f[i-2][0]||f[i][0];for(intj1;jlens;j){if(p[i-1].){f[i][j]f[i-1][j-1];}elseif(p[i-1]*){f[i][j](f[i-1][j-1]||f[i][j-1])(p[i-2]s[j-1]||p[i-2].);// *为多个字符f[i][j]|f[i-2][j];//0个f[i][j]|f[i-1][j];//1个}else{f[i][j]f[i-1][j-1](p[i-1]s[j-1]);}}}returnf[lenp][lens];}};23. 合并 K 个升序链表依次归并即可/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*mergeLists(ListNode*A,ListNode*B){ListNode*CnewListNode();ListNode*C_tailC;while(AB){if(A-valB-val){C_tail-nextA;C_tailC_tail-next;AA-next;}else{C_tail-nextB;C_tailC_tail-next;BB-next;}}while(A){C_tail-nextA;C_tailC_tail-next;AA-next;}while(B){C_tail-nextB;C_tailC_tail-next;BB-next;}returnC-next;}ListNode*mergeKLists(vectorListNode*lists){ListNode*ansnullptr;for(inti0;ilists.size();i){ansmergeLists(ans,lists[i]);}returnans;}};