力扣困难题汇总
题4（困难）：
思路：
找两数组中位数，这个看起来简单，顺手反应就是数第(m+n)/2个，这个难在要求时间复杂度为log(m+n)，所以不能这样搞，我的思路是：每次切割长度为较小长度的一半，然后比较哪个对中位数没有影响就切哪个
python代码
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:med=Nonewhile 1:if len(nums1) == 0:med2 = nums2[(len(nums2)) // 2] if len(nums2) % 2 == 1 else (nums2[len(nums2) // 2 - 1] + nums2[len(nums2) // 2]) / 2med = med2breakif len(nums2) == 0:med1 = nums1[(len(nums1)) // 2] if len(nums1) % 2 == 1 else (nums1[len(nums1) // 2 - 1] + nums1[len(nums1) // 2]) / 2med = med1breakif (len(nums1) + len(nums2) <= 2):med = ((nums1[0] if len(nums1) > 0 else 0) + (nums2[0] if len(nums2) > 0 else 0)) / (len(nums1) + len(nums2))breakcutlen=len(nums1)//2 if len(nums1)<=len(nums2) else len(nums2)//2if(cutlen<1):cutlen=1if nums1[cutlen-1]<nums2[cutlen-1]:nums1=nums1[cutlen:]else:nums2=nums2[cutlen:]if len(nums1)!=0 and (len(nums2)==0 or nums1[len(nums1)-cutlen]>nums2[len(nums2)-cutlen]) :nums1=nums1[:len(nums1)-cutlen]else:nums2=nums2[:len(nums2)-cutlen]return med题10（困难）：
思路：
我只能说我不是理解正则，毕竟爬虫我都不管啥，直接.*？,导致我理解错了题意思，我当时以为*是可以匹配任意了，然后写一晚上都没成功，看评论才理解意思，其实理解了写起来就清晰了，采用的方法是递归，时间比较消耗，所以要预处理一下，不然超时
python代码：
class Solution:def isMatch(self, s: str, p: str) -> bool:if p=='':return s==''if s=='':if len(p)!=2 and p[1]!='*':return Falseif len(p)==2 and p[1]=='*':return Truei=0#预处理，while 1:if p[i]=='*':if i+2<len(p) and p[i+2]=='*':if p[i-1]==p[i+1]:p=p[:i+1]+p[i+3:]i+=1if i>=len(p):breaks_p=0p_p=0while 1:if s_p>=len(s) and p_p>=len(p):return Trueif p_p>=len(p):return Falseif p_p+1<=len(p)-1 and p[p_p+1]=='*':for i in range(s_p,len(s)):if s[i]!=p[p_p] and p[p_p]!='.':breakelse:if self.isMatch(s[i:],p[p_p]+p[p_p+2:]):return Truep_p+=2else:if s_p>=len(s):return Falseif p[p_p]==s[s_p] or p[p_p]=='.':p_p+=1s_p+=1else:return False写得很气，所以赶工，注释都没有，再看的话又烦，感觉屎山一样，做的最久的一次，写了3个版本的代码
23题（困难）：
分析：
真不配这个难度，因为这个直接暴力求解都行，和第一个（21题）没区别，python没有指针，初始化感觉挺麻烦，你看了我代码就发现，我的head第一个往往都是空，返回head.next，因为我不想浪费空间重新拿创建，所以我更倾向于用它给的空间，这样看起来说实话有点别扭。但是第一个的赋值要在我们弄或者建立索引单独弄也别扭，以后再补上c++的吧
python代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = nextclass Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:p=ListNode()res=pif len(lists)==0:return Nonewhile 1:k=0for i in range(len(lists)):if lists[k]==None:k=iif lists[i] and lists[i].val<lists[k].val:k=iif lists[k]==None:breakprint(k)p.next=lists[k]p=p.nextlists[k]=lists[k].nextreturn res.next if res.next else None题25（困难）：
分析：
有意思，但是难度不配困难。思路其实挺清晰，我们知道链表时候插入数据但是不适合查找数据，本题因为要交换k个数据就说明一定要查找数据，因为你不知道要找第几个，而是要传入k，这个时候肯定要寻求数组的帮助，我们定义一个长度为k的数组，每次拿k个，这样我们要哪个就方便了
python代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
res=ListNode(0,head)
p=res
while 1:
node_list=[]
flag=1
q=p
for i in range(k):
if q.next==None:
flag=0
break
else:
q=q.next
node_list.append(q)
last_node=q.next
if flag:
for i in range(k):
p.next=node_list[k-i-1]
p=p.next
p.next=last_node
else:
break
return res.next
题30（困难）：
分析：
说实话，我第一反应是找所有words的位置来减少时间复杂度，结果来一个
最后迫不得已暴力求解了
python代码：
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
word_len=len(words)
word_size=len(words[0])
if word_len*word_size>len(s) or word_len==0:
return []
res=[]
def in_word(word,words):
w1=[word[word_size*i:word_size*(i+1)] for i in range(word_len)]
w1.sort()
w2=sorted(words)
if w1==w2:
return 1
else:
return 0
for i in range(len(s)-word_size*word_len+1):
word=s[i:i+word_size*word_len]
if in_word(word,words):
res.append(i)
return res
题32（困难）：
分析：
其实就是遍历一遍，我的思路就是每一项为前两项的和+2，且将前两项去了
python代码：
class Solution:
def longestValidParentheses(self, s: str) -> int:
tmp_list=[]
s_stack=[]
for i in s:
if i=="(":
s_stack.append(i)
tmp_list.append(0)
else:
if len(s_stack)!=0 and s_stack[-1]=='(':
s_stack.pop()
if tmp_list!=[]:
a1=tmp_list.pop()
else:
a1=0
if tmp_list!=[]:
a2=tmp_list.pop()
else:
a2=0
next=a1+a2+2
tmp_list.append(next)
else:
tmp_list.append(0)
return max(tmp_list) if tmp_list!= [] else 0
题37（困难）：
python代码：
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def Conflict(board):
def isValidUnit(unit):
# 检查一个行、列或宫格是否有效
seen = set()
for num in unit:
if num != '.':
if num in seen:
return False
seen.add(num)
return True
for i in range(9):
if not isValidUnit(board[i]):
return False
for j in range(9):
column = [board[i][j] for i in range(9)]
if not isValidUnit(column):
return False
for i in range(0, 9, 3):
for j in range(0, 9, 3):
square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
if not isValidUnit(square):
return False
return True
def run(n):
for i in range(n,81):
x = i // 9
y = i % 9
if board[x][y]!='.':
continue
for j in range(1,10):
board[x][y]=str(j)
if Conflict(board) and run(i+1):
return True
board[x][y]='.'
return False
return True
run(0)
题41（困难）：
分析：
这题我开始没什么思路,记录第一个逼我看评论的，后面看评论的方法，真解，借助一个数组，将nums对应数字放对应位置，然后如果下标和数字不同就返回
python代码（基础版）:
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n_list=[-1 for i in range(len(nums))]#根据提示O(2n)==O(n),我们知道了一定要循环两次，于是就有放回位置上去for i in range(len(nums)):if nums[i]>0 and nums[i]<=len(nums):n_list[nums[i]-1]=nums[i]for i in range(len(n_list)):if n_list[i]==-1:return i+1return len(nums)+1python代码（进阶）：
class Solution:def firstMissingPositive(self, nums: List[int]) -> int:n_len=len(nums)#不能用额外空间，那就改变它的值，且时间复杂度为O(n)，#首先使用双指针法，将等于len和小于0的值去了或者放到另一边left=0right=len(nums)-1flag=1while left<=right:while left<=right:if nums[left]>n_len or nums[left]<=0:breakleft+=1while left<=right:if nums[right]<=n_len and nums[right]>0:breakright-=1if left>right:breakelse:nums[left],nums[right]=nums[right],-1#另一边的空间就随便我们使用了，通过left来知道有多少个，将数字根据下标排好n=0while n<left:if nums[n]>n_len or nums[n]<=0:n+=1continueif nums[n]!=n+1:#如果不相同，则放到相同的地方if nums[n]!=nums[nums[n]-1]:#保证换回来的数字不重复，不然就卡住了,顺便排除相同的tmp=nums[n]nums[n]=nums[nums[n]-1]nums[tmp-1]=tmpn-=1n+=1#遍历找相同的for i in range(n_len):if nums[i]!=i+1:return i+1return n_len+1题42（困难）：
分析：
我一开始是数格子，从最后一行数，但是超时了，只能寻找其他方法，然后想到双指针法，我们可以移动更小的一遍，因为这样对整体才有影响嘛，之前求最大盛水量也是这样，
#双指针，先找左右局部极大值 #移动更小的指针， #如果移动遇到小于其高度的点，面积加上h_left_max-h_left #如果大于，则h_left_max=h_left,a再和右比较，
python代码：
class Solution:def trap(self, height: List[int]) -> int:#双指针，先找左右局部极大值w_res=0left=0right=len(height)-1#左右找峰值n=0while left<right:if height[left]<height[left+1]:left+=1else:breakwhile left<right:if height[right]<height[right-1]:right-=1else:breakh_left_max=height[left]h_right_max=height[right]#移动更小的指针，#如果移动遇到小于其高度的点，面积加上h_left_max-h_left#如果大于，则h_left_max=h_left,a再和右比较，while left<right:if height[left]<height[right]:while left<right:left+=1if h_left_max<height[left]:h_left_max=height[left]breakw_res+=(h_left_max-height[left])else:while left<right:right-=1if h_right_max<height[right]:h_right_max=height[right]breakw_res+=(h_right_max-height[right])return w_res题44（困难）：
分析
又是正则匹配，这个肯定第一反应是递归，但是发现一个问题，上一次我递归超时，这个递归作为指数阶的方法，肯定超时，所以只能迭代方法，作为和递归一起的就是借助动态数组，实时根据前一个的状态来推测当前状态
python代码：
class Solution:def isMatch(self, s: str, p: str) -> bool:# dp[i][j] 表示s的前i个字符和p的前j个字符是否匹配dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]# 初始化dp数组，空字符串匹配dp[0][0] = True# 初始化第一行，处理模式p中以*开头的匹配情况for j in range(1, len(p) + 1):if p[j - 1] == '*':dp[0][j] = dp[0][j - 1]# 填充dp数组for i in range(1, len(s) + 1):for j in range(1, len(p) + 1):if p[j - 1] == '*':# '*'可以匹配空字符串，也可以匹配任意长度的字符串dp[i][j] = dp[i][j - 1] or dp[i - 1][j]elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:# '?'匹配任意单个字符，或者当前字符相等dp[i][j] = dp[i - 1][j - 1]return dp[len(s)][len(p)]题60（困难）：
分析：
这道题第一反应是暴力递归求排列再取值，其实没必要这样，主要是它要取第k个，我们想象1,2,3来说
如果k在【1,2】那么第一个数就是1，如果k在【3，4】就是2……
这个时候来判断第二个数字，有n-1种情况，每种情况之间间隔（n-2）！个，思路就来了
python代码：
class Solution:def getPermutation(self, n: int, k: int) -> str:if k==Solution.get_n_factorial(n):return ''.join(str(i) for i in range(n,0,-1))n_list=[Solution.get_n_factorial(i) for i in range(n-1,0,-1)]res=''num=0leave=k#num剩余取值nums=[str(i) for i in range(n,0,-1)]for index,value in enumerate(n_list):num=math.ceil(leave/value)leave=leave%valueres+=str(nums[len(nums)-num])nums.remove(str(nums[len(nums)-num]))if leave==0:res=res+''.join(nums)breakreturn res@staticmethoddef get_n_factorial(n):res=1for i in range(1,n+1):res*=ireturn res