题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=reswhile 1:node_list=[]flag=1q=pfor i in range(k):if q.next==None:flag=0breakelse:q=q.nextnode_list.append(q)last_node=q.nextif flag:for i in range(k):p.next=node_list[k-i-1]p=p.nextp.next=last_nodeelse:breakreturn res.next题30（困难）：
分析：
说实话，我第一反应是找所有words的位置来减少时间复杂度，结果来一个
最后迫不得已暴力求解了
python代码：
import re
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 1else:return 0for 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=0if tmp_list!=[]:a2=tmp_list.pop()else:a2=0next=a1+a2+2tmp_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 Falseseen.add(num)return Truefor i in range(9):if not isValidUnit(board[i]):return Falsefor j in range(9):column = [board[i][j] for i in range(9)]if not isValidUnit(column):return Falsefor 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 Falsereturn Truedef run(n):for i in range(n,81):x = i // 9y = i % 9if board[x][y]!='.':continuefor j in range(1,10):board[x][y]=str(j)if Conflict(board) and run(i+1):return Trueboard[x][y]='.'return Falsereturn Truerun(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题65（困难）：
分析：
不得不说，这个有效数字判定规则很诡异，不过难度真不配困难
python代码：
class Solution:def isNumber(self, s: str) -> bool:s_stack=[]dot_flag=0sign_flag=0e_flag=0for i in s:#如果为数字if i in ('0','1','2','3','4','5','6','7','8','9'):if dot_flag==1:dot_flag=0if e_flag==1:e_flag=0if sign_flag==1:sign_flag=0s_stack.append(i)#如果为.elif i=='.':if s_stack==[] or s_stack==['+'] or s_stack==['-']:dot_flag=1if '.' in s_stack:return Falseif ('e' in s_stack) or ('E' in s_stack):return Falses_stack.append('.')#如果为+-elif i=='+' or i=='-':#如果不是空或者前面不是e就0if s_stack==[]:sign_flag=1s_stack.append(i)elif s_stack[-1]=='e' or s_stack[-1]=='E':s_stack.append(i)else:return False#如果为e或者Eelif i=='e' or i=='E':print(s_stack)e_flag=1if 'e' in s_stack or 'E' in s_stack:return Falseif s_stack==[] or s_stack==['+'] or s_stack==['-']:return Falseif s_stack==['.'] or s_stack==['+','.'] or s_stack==['-','.']:return Falses_stack.append(i)else:return Falseif dot_flag==1:return Falseif e_flag==1:return Falseif sign_flag==1:return Falsereturn True题68（困难）：
分析：
感觉这题也不配困难啊，思路清晰点都随便做
python代码：
class Solution:def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:res=[]tmp_line=[]now_len=0#遍历一遍，确定每一行塞哪些单词for index,value in enumerate(words):#首先判断是否可以塞下这个单词#now_len+=单词长度+1if now_len+len(value)<=maxWidth:#如果可以塞下这个单词，那么直接塞进去now_len+=len(value)+1tmp_line.append(value)else:#如果塞不下kg_num=maxWidth-now_len+1i=0while kg_num>0:#从第一个的后面加空格tmp_line[i]+=' 'kg_num-=1i+=1if i>=len(tmp_line)-1:i=0line=' '.join(tmp_line)res.append(line)tmp_line=[value]now_len=len(value)+1#如果是最后一个单词if index==len(words)-1:line=' '.join(tmp_line)+' '*(maxWidth-now_len+1)res.append(line)return res题76（困难）：
分析：
这道题其实不难，但是是我做最久的了，我居然去用res去接所有可能得值，然后再求长度导致空间暴力，我还以为是我queue的问题。。。
最后用暴力求解解的，使用双指针，移动前后指针，后指针用来找齐所有的t值，前指针用来压缩为最短值
python代码：
class Solution:def minWindow(self, s: str, t: str) -> str:#思路就是双指针，应该start一个end#加上一个map用于记录各个需要多少个，need_len用与判断还缺否if len(s)<len(t):return ''res=''need={}need_len=len(t)for c in t:need[c]=need.get(c,0)+1start,end=0,0flag=1#用于判断应该移动start还是end,1为移动end，0为移动startwhile end<len(s):while flag== 1 and end<len(s):#移动endif s[end] in need:#如果需要这个if need[s[end]]>=1:need_len-=1need[s[end]]-=1if need_len==0:flag=0#说明不需要了end+=1else:end+=1continuewhile flag == 0 and start<end:if s[start] in need:need[s[start]]+=1if need[s[start]]>0:if res=='':res=s[start:end]else:res=s[start:end] if len(res)>len(s[start:end]) else resneed_len+=1flag=1start+=1else:start+=1continuereturn res
