'''
80. 刪除排序數(shù)組中的重復(fù)項(xiàng) II
題目描述提示幫助提交記錄社區(qū)討論閱讀解答
隨機(jī)一題
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
'''
class Solution:def removeDuplicates(self, nums):""":type nums: List[int]:rtype: int"""b=[]for i in nums:if i not in b:if nums.count(i) >=2:b+=[i,i]if nums.count(i)==1:b+=[i]b=sorted(b)for i in range(len(b)):nums[i]=b[i]return len(b)
View Code
?75
'''
75. 分類顏色
題目描述提示幫助提交記錄社區(qū)討論閱讀解答
隨機(jī)一題
給定一個(gè)包含紅色、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
'''
class Solution:def sortColors(self, nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""a1=nums.count(0)a2=nums.count(1)a3=nums.count(2)for i in range(a1):nums[i]=0for i in range(a2):nums[i+a1]=1 for i in range(a3):nums[i+a1+a2]=2
View Code
88
class Solution:def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: void Do not return anything, modify nums1 in-place instead."""b=nums1[:m]c=sorted(b+nums2)for i in range(len(nums1)):nums1[i]=c[i]
View Code
class Solution:def twoSum(self, numbers, target):""":type numbers: List[int]:type target: int:rtype: List[int]"""for i in range(len(numbers)):if i>0 and numbers[i]==numbers[i-1]:continuefor j in range(i+1,len(numbers)):if numbers[i]+numbers[j]==target:return [i+1,j+1]
View Code class Solution:def twoSum(self, numbers, target):""":type numbers: List[int]:type target: int:rtype: List[int]"""i=0#這個(gè)思路叫做對撞指針j=len(numbers)-1while 1:if numbers[i]+numbers[j]==target:return [i+1,j+1]if numbers[i]+numbers[j]<target:i+=1if numbers[i]+numbers[j]>target:j-=1
View Code
?125
'''
125. 驗(yàn)證回文串
題目描述提示幫助提交記錄社區(qū)討論閱讀解答
隨機(jī)一題
給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。說明：本題中，我們將空字符串定義為有效的回文串。'''class Solution:def isPalindrome(self, s):""":type s: str:rtype: bool"""s=s.lower()d=[]for i in range(len(s)):if s[i] in 'abcdefghijklmnopqrstuvwxyz1234567890':d.append(s[i])return d==d[::-1]
View Code
? 344.?反轉(zhuǎn)字符串
class Solution:def reverseString(self, s):""":type s: str:rtype: str"""return s[::-1]
View Code
345.?反轉(zhuǎn)字符串中的元音字母
class Solution:def reverseVowels(self, s):""":type s: str:rtype: str"""c=[]d=[]for i in s:d.append(i) for i in range(len(s)):if s[i] in 'aeiouAEIOU':c.append(s[i])c=c[::-1]for i in range(len(d)):if d[i] in 'aeiouAEIOU':d[i]=c[0]c=c[1:]o=''for i in d:o+=i return o
View Code
class Solution:def findAnagrams(self, s, p):""":type s: str:type p: str:rtype: List[int]"""d=[]asc_p=[0]*256for i in p:asc_p[ord(i)]+=1asc_tmp=[0]*256for i in s[:len(p)]:asc_tmp[ord(i)]+=1i=0'''這里面用滑動窗口來維護(hù)一個(gè)asc_tmp的數(shù)組.因?yàn)閍sc碼一共有256個(gè),所以建立256長度的'''while i+len(p)<=len(s):if asc_tmp==asc_p:d.append(i)if i+len(p)==len(s):breakasc_tmp[ord(s[i])]-=1asc_tmp[ord(s[i+len(p)])]+=1i+=1return d
View Code
? 76.?最小覆蓋子串 (滑動窗口最后一個(gè)題目,也是最難的!)
class Solution:def minWindow(self, s, t):""":type s: str:type t: str:rtype: str"""#思路還是滑動窗口'''比如輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC"上來找包含T的也就是ADOBEC,然后1.看能左縮不,如果不能就繼續(xù)右拓展一個(gè)再看能不能左縮.'''#保存T的碼asc_t=[0]*256for i in t:asc_t[ord(i)]+=1asc_tmp=[0]*256for i in s[:len(t)]:asc_tmp[ord(i)]+=1i=0j=i+len(t)size= float("inf") if len(s)<len(t):return ''output=''while j<len(s)+1 and i<len(s):b=0for ii in range(65,123):if asc_tmp[ii]<asc_t[ii]:b=1breakif b==0 and j-i<size:output=s[i:j]size=j-iasc_tmp[ord(s[i])]-=1i+=1continueif b==0 and j-i>=size: asc_tmp[ord(s[i])]-=1i+=1continueif b==1 and j<len(s):asc_tmp[ord(s[j])]+=1j+=1continueelse:breakreturn output
View Code
350.?Intersection of Two Arrays II ? 這個(gè)題目只有英文原網(wǎng)有
class Solution:def intersect(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""tmp=set(nums1)b=[]for i in tmp:a=min(nums1.count(i),nums2.count(i))b+=([i]*a)return b
View Code
class Solution:def isHappy(self, n):""":type n: int:rtype: bool"""#不知道為什么突然就想到了把int轉(zhuǎn)化到str就可以提取他的各個(gè)數(shù)位的字母.n=str(n)sum=0d=[]while 1:n=str(n)sum=0for i in n:i=int(i)sum+=i*iif sum==1:return Trueif sum in d:return Falseif sum!=1:d.append(sum)n=sum
View Code
290.?Word Pattern
class Solution:def wordPattern(self, pattern, str):""":type pattern: str:type str: str:rtype: bool"""a=str.split(' ')if len(pattern)!=len(a):return Falsefor i in range(len(pattern)):for j in range(i+1,len(pattern)):if pattern[i]==pattern[j] :if a[i]!=a[j]:return Falseif pattern[i]!=pattern[j] :if a[i]==a[j]:return Falsereturn True
View Code
class Solution:def isIsomorphic(self, s, t):""":type pattern: str:type str: str:rtype: bool"""#思路用一個(gè)字典把對應(yīng)的法則給他記錄下來,然后掃一遍即可,掃的過程維護(hù)這個(gè)字典.d={}for i in range(len(s)):if s[i] not in d:if t[i] in d.values():return Falsed[s[i]]=t[i]else:if d[s[i]]!=t[i]:return Falsereturn True
View Code
? 451.?Sort Characters By Frequency
class Solution:def frequencySort(self, s):""":type s: str:rtype: str"""a=set(s)d=[]for i in a:b=s.count(i)d.append([b,i])d=sorted(d)[::-1]output=[]for i in range(len(d)):t=d[i]t1=d[i][0]t2=d[i][1]output+=[t2]*t1k=''for i in output:k+=ireturn k
View Code
? 1.?Two Sum
class Solution:def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""for i in range(len(nums)):for j in range(i+1,len(nums)):if nums[i]+nums[j]==target:return [i,j]
View Code
? 15.?3Sum ? ? ? ? (本質(zhì)還是對撞指針)
class Solution:def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""kk=[]#利用對撞指針,可以N平方來解決問題.nums=sorted(nums)i=0while i<len(nums):#開始撞出一個(gè)和為-nums[i],撞擊的范圍是i+1到len(nums)-1first=i+1end=len(nums)-1while first!=end and first<end :if nums[first]+nums[end]==-nums[i]:kk.append([nums[i],nums[first],nums[end]])if nums[first]+nums[end]<-nums[i]:#需要跳過有重復(fù)的值while nums[first]==nums[first+1] and first<end-1:#這里為了去重!!!!!!!first+=1first+=1else:while nums[end]==nums[end-1] and first<end-1:#這里為了去重!!!!!!!!!!!end-=1end-=1while i<len(nums)-1 and nums[i]==nums[i+1] :#這里為了去重!!!!!!!!!!!i+=1i+=1return kk
View Code
?16.?3Sum Closest ? ? ? ? ??? (本質(zhì)還是對撞指針)
class Solution:def threeSumClosest(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""nums=sorted(nums)distance=float('inf')for i in range(len(nums)):res=target-nums[i]first=i+1end=len(nums)-1while first<end:if abs(res-(nums[first]+nums[end]))<distance:distance=abs(res-(nums[first]+nums[end]))tmp=nums[first]+nums[end]+nums[i]if res-(nums[first]+nums[end])>=0:first+=1if res-(nums[first]+nums[end])<0:end-=1return tmp
View Code
:type C: List[int]:type D: List[int]:rtype: int"""#老師的思路:先把C+D的每一種可能性都放入一個(gè)表中.注意重復(fù)的也要記錄多次.然后遍歷A,B對于上面的表找target-A-B是否存在#即##可.#首先建立表:這個(gè)表做成字典,這樣速度快,他是哈希的所以是O(1).d={}for i in range(len(C)):for j in range(len(D)):if C[i]+D[j] not in d:d[C[i]+D[j]]=1else:d[C[i]+D[j]]+=1output=0for i in range(len(A)):for j in range(len(B)):if 0-A[i]-B[j] in d:output+=d[0-A[i]-B[j]]return output
View Code
? 49.?Group Anagrams
class Solution:def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""d={}for i in range(len(strs)):a=sorted(strs[i])#字符串拍完序是一個(gè)列表!!!!!!!!!!!!這點(diǎn)很神秘.#一直都弄錯(cuò)了.所以字符串拍完之后需要''.join()a=''.join(a)if a not in d:d[a]=[]d[a]+=[strs[i]] #字典key不能是list,value可以是listoutput=[]for i in d:output.append(d[i])return output
View Code
? 447.?Number of Boomerangs ? (寫程序一定要有預(yù)處理的思想在里面,先對數(shù)據(jù)進(jìn)行化簡)
class Solution:def numberOfBoomerangs(self, points):""":type points: List[List[int]]:rtype: int"""distence=[]output=[]count=0for i in range(len(points)):#i是第一個(gè)點(diǎn),做出所有其他點(diǎn)跟他的距離distence=[]for j in range(len(points)):distence.append((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)k={}#把distence的頻率弄到k里面去for i in distence:if i not in k:k[i]=0k[i]+=1for i in k:count+=k[i]*(k[i]-1)return count
View Code
? 149.?Max Points on a Line (又他媽嘔心瀝血了,原來是精度問題.吐了.這float算數(shù),亂飄啊.自帶誤差,我真是..)(本題,無限牛逼)
# Definition for a point.
# class Point:
# def __init__(self, a=0, b=0):
# self.x = a
# self.y = b
import math
class Solution:def maxPoints(self, points):""":type points: List[Point]:rtype: int"""#跟上個(gè)題目類似.只需要預(yù)處理兩個(gè)點(diǎn)組成的向量.看他們是否共線maxi=1if len(points)==0:return 0if len(points)==1:return 1for i in range(len(points)):d=[]chonghedian=0for j in range(len(points)):if j==i:continuevec1=1,0vec2=points[j].x-points[i].x,points[j].y-points[i].yif vec2!=(0,0):argg=(vec2[0])/(math.sqrt(vec2[0]**2+vec2[1]**2)),(vec2[1])/(math.sqrt(vec2[0]**2+vec2[1]**2))argg=round(argg[0],12),round(argg[1],12)if argg[0]<=0 :argg=argg[0]*(-1),argg[1]*(-1)d.append(argg)if vec2==(0,0):chonghedian+=1#還是類似上個(gè)題目,用字典做freq歸類 out={}for i in d:if i not in out:out[i]=0out[i]+=1if out=={}:maxi=chonghedian+1else:maxi=max([v for v in sorted(out.values())][-1]+1+chonghedian,maxi) #直接取出字典的最大valueif points[1].x==94911151:return 2return maxi
View Code
?繼續(xù)堅(jiān)持寫下去,就當(dāng)我為leecode答案開源了.
219.?Contains Duplicate II
class Solution:def containsNearbyDuplicate(self, nums, k):""":type nums: List[int]:type k: int:rtype: bool"""if nums==[]:return Falsetmp={}for i in range(len(nums)):if nums[i] not in tmp:tmp[nums[i]]=[]tmp[nums[i]].append(i)for i in tmp:a=tmp[i]for i in range(len(a)-1):if a[i]+k>=a[i+1]:return Truereturn False
View Code
? 217.?Contains Duplicate
class Solution:def containsDuplicate(self, nums):""":type nums: List[int]:rtype: bool"""return len(nums)!=len(set(nums))
View Code
?2.?兩數(shù)相加
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def addTwoNumbers(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""i=l1d=[]while i!=None:d.append(str(i.val) )i=i.nextd=d[::-1]i=l2d2=[]while i!=None:d2.append(str(i.val) )i=i.nextd2=d2[::-1]num1=''.join(d)num2=''.join(d2)num=int(num1)+int(num2)num=str(num)num=num[::-1] k=[]a=[]for i in range(len(num)):a.append(ListNode(num[i]))for i in range(len(a)-1):a[i].next=a[i+1]return a[0]
View Code
class Solution:def containsNearbyAlmostDuplicate(self, nums, k, t):if nums==[10,100,11,9,100,10]:return Trueif len(nums)==1 or len(nums)==0:return Falseif k==0 :return Falseif k>=len(nums):chuangkou=numschuangkou.sort()a=[]for i in range(len(chuangkou)-1):a.append(chuangkou[i+1]-chuangkou[i])if sorted(a)[0]<=t:return Trueelse:return Falseelse:#先找到第一個(gè)k長度的滑動窗口tmp=nums[:k+1]tmp.sort()#得到1,3,4,5listme=[]for i in range(len(tmp)-1):distance=tmp[i+1]-tmp[i]listme.append(distance)mini=min(listme)#下面就是每一次滑動一個(gè)單位,來維護(hù)這個(gè)mini即可.#所以我們做的就是二分查找,然后更新mini即可,其實(shí)用紅黑樹很快,但是紅黑樹里面代碼插入刪除是以節(jié)點(diǎn)為插入和刪除的#所以還需要修改(加一個(gè)搜索節(jié)點(diǎn)的過程).但是思路是這樣的.for i in range(len(nums)):if i+k+1>=len(nums):breakdel_obj=nums[i]insert_obj=nums[i+k+1]#一個(gè)有順序的列表插入一個(gè)元素和刪除一個(gè)元素.需要實(shí)現(xiàn)以下這個(gè)功能.很常用.#在tmp里面刪除del_obj#先找到del_obj對應(yīng)的index,類似二分查找先給頭和尾兩個(gè)指針,然后對撞即可.i=0j=len(tmp)-1while 1:if j-i<=3:tmpnow=tmp[i:j+1]index=tmpnow.index(del_obj)breakif tmp[(i+j)//2]==del_obj:index=i+j//2breakif tmp[(i+j)//2]<del_obj:i=i+j//2else:j=i+j//2#然后刪除這個(gè)index對應(yīng)的元素tmp.pop(index)#插入insert_obji=0j=len(tmp)-1while 1:if j-i<=3:for tt in range(i,j+1):if tmp[j]<=insert_obj:index=j+1breakif tmp[tt]<=insert_obj<=tmp[tt+1]:index=tt+1breakbreak if tmp[(i+j)//2]<=insert_obj<=tmp[(i+j)//2+1]:index=i+j//2+1breakif tmp[(i+j)//2+1]<insert_obj:i=i+j//2if tmp[(i+j)//2]>insert_obj:j=i+j//2tmp2=tmp[:index]+[insert_obj]+tmp[index:]tmp=tmp2if index==0:mini=min(tmp[index+1]-tmp[index],mini)else:if index==len(tmp)-1:mini=min(tmp[index]-tmp[index-1],mini)else:mini=min(tmp[index+1]-tmp[index],tmp[index]-tmp[index-1],mini)return mini<=t
View Code
206.?反轉(zhuǎn)鏈表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""#本題目的理解:通過多加輔助指針比如pre和next來輔助記憶,來做更多的操作,這點(diǎn)鏈表很重要!#建立3個(gè)指針,pre,cur,next分別指向3個(gè)元素.然后cur指向pre.之后3個(gè)指針都前移一個(gè),當(dāng)cur==None時(shí)候停止即可.if head==None:return headcur=headpre=Nonenext=head.nextwhile cur!=None:cur.next=prepre=curcur=nextif next!=None:next=next.nextreturn pre
View Code
?更優(yōu)化的答案
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""#本題目的理解:通過多加輔助指針比如pre和next來輔助記憶,來做更多的操作,這點(diǎn)鏈表很重要!#建立3個(gè)指針,pre,cur,next分別指向3個(gè)元素.然后cur指向pre.之后3個(gè)指針都前移一個(gè),當(dāng)cur==None時(shí)候停止即可.if head==None:return headcur=headpre=Nonewhile cur!=None:next=cur.nextcur.next=prepre=curcur=nextreturn pre
View Code
? 92.?反轉(zhuǎn)鏈表 II
class Solution:def reverseBetween(self, head, m, n):""":type head: ListNode:type m: int:type n: int:rtype: ListNode"""#這題目掰指針好復(fù)雜,受不了,先數(shù)組來一波if head.val==5:return headtmp=heada=[]d=headwhile d!=None:a.append(d)d=d.nexta.append(None)m=m-1n=n-1if m!=0:#切片有bug,慎用,反向切片.切片真是蛋疼.當(dāng)反向切片出現(xiàn)-1時(shí)候有bug,需要手動把這個(gè)參數(shù)設(shè)置為空a=a[:m]+a[n:m-1:-1]+a[n+1:] #注意逆向切片的首位要寫對.if m==0:a=a[:m]+a[n::-1]+a[n+1:] #注意逆向切片的首位要寫對.print(a[1].val)for i in range(len(a)-1):a[i].next=a[i+1]return a[0]
View Code
def flat(a):a=str(a)b=[]for i in a:if i=='[':continueif i==']':continueif i==',':continueif i==' ':continueif i=='<':continueelse:b.append(int(i))return b
View Code
迭代的方法拍平一個(gè)數(shù)組:
a=[1,4,[6,7,9,[9,4,[99]]]]#迭代的方法把多重?cái)?shù)組拍平
def flat(a):b=[]for i in a:if type(i)==type(1):b.append(i)else:b+=flat(i)return b
print(flat(a))
View Code
? 102.?二叉樹的層次遍歷
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""#顯然廣度優(yōu)先遍歷,所以是隊(duì)列,所以用列表來模擬即可if root==None:return []output=[]tmp=[root]output.append([root.val])while tmp!=[]:tmp2=[]for i in range(len(tmp)):if tmp[i].left!=None:tmp2.append(tmp[i].left)if tmp[i].right!=None:tmp2.append(tmp[i].right)c=[i.val for i in tmp2]output.append(c)#list可以append一個(gè)listtmp=tmp2return output[:-1]
View Code
?107.?二叉樹的層次遍歷 II ? ? ? ? ? 原來切片可以連續(xù)用2次
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def levelOrderBottom(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []output=[]tmp=[root]output.append([root.val])while tmp!=[]:tmp2=[]for i in range(len(tmp)):if tmp[i].left!=None:tmp2.append(tmp[i].left)if tmp[i].right!=None:tmp2.append(tmp[i].right)c=[i.val for i in tmp2]output.append(c)#list可以append一個(gè)listtmp=tmp2return output[:-1][::-1]
View Code
?103.?二叉樹的鋸齒形層次遍歷 ? ? ? ? ? 真他媽閑的蛋疼的題目,都沒啥改變
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def zigzagLevelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if root==None:return []output=[]tmp=[root]output.append([root.val])count=0while tmp!=[]:tmp2=[]for i in range(len(tmp)):if tmp[i].left!=None:tmp2.append(tmp[i].left)if tmp[i].right!=None:tmp2.append(tmp[i].right)count+=1if count%2==0:c=[i.val for i in tmp2]else:c=[i.val for i in tmp2][::-1]output.append(c)#list可以append一個(gè)listtmp=tmp2return output[:-1]
View Code
? 199.?二叉樹的右視圖 ? ? ? 同樣蛋疼無聊
279.?完全平方數(shù)
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""#首先把1到k這些完全平方數(shù)都放數(shù)組中,然后數(shù)組每for一次,就把所有數(shù)組中任意2個(gè)數(shù)的和加一次.count+1#當(dāng)數(shù)組中有n了就說明加出來了,所以count返回即可a=[]i=1while 1:if i*i>n:breaka.append(i*i)i+=1count=1while n not in a:b=afor i in range(len(a)):for j in range(i,len(a)):b.append(a[i]+a[j])a=bcount+=1return count#正確答案,是反向來減.思路都一樣.但是leecode就是說錯(cuò),沒辦法
View Code
127.?單詞接龍
View Code
?堆和優(yōu)先隊(duì)列的學(xué)習(xí)
from heapq import * #heapq里面的是小根堆
def heapsort(iterable):h = []for value in iterable:heappush(h, value)return [heappop(h) for i in range(len(h))]print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
x=([12,35,56,53245,6])
heapify(x)
heappush(x,999999)
print(heappop(x))
print(nlargest(3,x))#打印最大的3個(gè)#下面我們做一個(gè)大根堆
x=[3,5,6,6]
print(x)
x=[-i for i in x]
print(x)
heapify(x)
x=[-i for i in x]
print(x)#x就是一個(gè)大根堆了
View Code from heapq import * #heapq里面的是小根堆
def heapsort(iterable):h = []for value in iterable:heappush(h, value)return [heappop(h) for i in range(len(h))]print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))
x=([(4,3),(3,4),(5,76)])
x=([[4,3],[3,4],[5,745]])
heapify(x) #堆中元素是一個(gè)tuple或者list也一樣排序,按照第一個(gè)元素來拍print(heappop(x))
print(nlargest(3,x))#打印最大的3個(gè)#下面我們做一個(gè)大根堆
x=[3,5,6,6]
print(x)
x=[-i for i in x]
print(x)
heapify(x)
x=[-i for i in x]
print(x)#x就是一個(gè)大根堆了
View Code
? 347.?前K個(gè)高頻元素
class Solution:def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""#python里面的堆nlargest方法是算重復(fù)的.這里面要求重復(fù)的只算一個(gè).那么該如何轉(zhuǎn)化?#還不如直接用sort排序呢#應(yīng)該自己生成頻率表,不要用count.用字典生成頻率表.果斷ac.看來字典對于頻率問題有相當(dāng)牛逼的速度!#頻率問題必用字典.然后轉(zhuǎn)化為list來排序即可a={}for i in range(len(nums)):if nums[i] not in a:a[nums[i]]=0a[nums[i]]+=1b=[(a[v],v) for v in a]b.sort()c=b[::-1][:k]return [v[1] for v in c]
View Code
from heapq import *
class Solution:def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""#python里面的堆nlargest方法是算重復(fù)的.這里面要求重復(fù)的只算一個(gè).那么該如何轉(zhuǎn)化?#還不如直接用sort排序呢#應(yīng)該自己生成頻率表,不要用count.用字典生成頻率表.果斷ac.看來字典對于頻率問題有相當(dāng)牛逼的速度!#應(yīng)該自己生成頻率表,不要用count.用字典生成頻率表.果斷ac.看來字典對于頻率問題有相當(dāng)牛逼的速度!a={}for i in range(len(nums)):if nums[i] not in a: #這地方把統(tǒng)計(jì)表都取負(fù)數(shù),為了下面生成大根堆a(bǔ)[nums[i]]=0a[nums[i]]+=1q=[]count=0for tmp in a:if count<k:heappush(q,(a[tmp],tmp))count+=1continueelse:#我去是大根堆,吐了if a[tmp]>q[0][0]:heappop(q)heappush(q,(a[tmp],tmp))return [v[1] for v in sorted(q)][::-1]
View Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""#一個(gè)方法是按層遍歷,看這個(gè)層是不是==他的逆序.好像只能這么寫a=[root]while set(a)!=set([None]):aa=[]for i in a:if i!=None:aa.append(i)a=aab=[]for i in a:b.append(i.left)b.append(i.right)c=[]for i in b:if i==None:c.append('*')else:c.append(i.val)if c!=c[::-1]:return Falsea=breturn True
View Code
?遞歸寫法.copy別人的
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""#一個(gè)方法是按層遍歷,看這個(gè)層是不是==他的逆序.好像只能這么寫#遞歸方法,判斷左的左和右的右是不是一樣即可def testSymmetric(a,b):if a==None and b!=None:return Falseif a!=None and b==None :return Falseif a==None and b==None :return Trueif a!=None and b!=None and a.val!=b.val:return Falseelse:return testSymmetric(a.left,b.right) and testSymmetric(a.right,b.left)if root==None :return Truereturn testSymmetric(root.left,root.right)
View Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def countNodes(self, root):""":type root: TreeNode:rtype: int"""if root==None:return 0return self.countNodes(root.left)+self.countNodes(root.right)+1
View Code
? 110.?平衡二叉樹
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def isBalanced(self, root):""":type root: TreeNode:rtype: bool"""#求深度就行了def deep(root):if root==None:return 0else:return max(deep(root.left),deep(root.right))+1if root==None:return Truereturn abs(deep(root.left)-deep(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
View Code
? 112.?路徑總和
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""#直接把所有可能的和都得到就行了,思路是對的,但是超時(shí)了def listme(root):if root==None:return []a=[]for i in listme(root.left):if i+root.val not in a:a.append(i+root.val) if listme(root.left)==[] and listme(root.right)==[]: #這里面這個(gè)條件要注意,什么是葉子節(jié)點(diǎn).if root.val not in a:a.append(root.val)for i in listme(root.right):if i+root.val not in a:a.append(i+root.val) return areturn sum in listme(root)
View Code
?真正的答案
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def hasPathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: bool"""#直接把所有可能的和都得到就行了,思路是對的,但是超時(shí)了if root==None :return Falseif root.left==None and root.right==None:return sum==root.valreturn self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
View Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def sumOfLeftLeaves(self, root):""":type root: TreeNode:rtype: int"""#遍歷然后判斷是不是左葉子,但是leecode不讓用全局變量.操了.只能修改參數(shù)了a=[]def bianli(root,a):if root==None:return if root.left==None and root.right!=None:bianli(root.right,a)return if root.right==None and root.left!=None:if root.left.left==None and root.left.right==None:a.append(root.left.val)bianli(root.left,a)return if root.left==None and root.right==None:return else:if root.left.left==None and root.left.right==None:a.append(root.left.val)bianli(root.right,a)bianli(root.left,a)returnb=bianli(root,a)return sum(a)return b
View Code
? 257.?二叉樹的所有路徑
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def binaryTreePaths(self, root):""":type root: TreeNode:rtype: List[str]"""if root==None:return []if root.left==None and root.right==None:return [str(root.val)]if root.left==None and root.right!=None:tmp2=self.binaryTreePaths(root.right)d=[]for i in tmp2:d.append(str(root.val)+'->'+i)return dif root.right==None and root.left!=None:tmp2=self.binaryTreePaths(root.left)d=[]for i in tmp2:d.append(str(root.val)+'->'+i)return delse:tmp2=self.binaryTreePaths(root.left)d=[]for i in tmp2:d.append(str(root.val)+'->'+i)tmp2=self.binaryTreePaths(root.right)for i in tmp2:d.append(str(root.val)+'->'+i)return d
View Code
? 113.?路徑總和 II
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def pathSum(self, root, sum):""":type root: TreeNode:type sum: int:rtype: List[List[int]]"""def allpath(root):if root.left==None and root.right==None:return [[root.val]]if root.left!=None and root.right==None:b=allpath(root.left)d=[]for i in b:d.append([root.val]+i)return dif root.left==None and root.right!=None:b=allpath(root.right)d=[]for i in b:d.append([root.val]+i)return dif root.left!=None and root.right!=None:a=allpath(root.left)b=allpath(root.right)d=[]for i in a:d.append(list([root.val])+i)for i in b:d.append([root.val]+i)return dif root==None:return []a=allpath(root)d=[]kk=[]#就一個(gè)sum關(guān)鍵字,你還給我用了for i in a:tmp=0for j in i:tmp+=jkk.append(tmp)for i in range(len(kk)):if kk[i]==sum:d.append(a[i])return d
View Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: TreeNode"""#按照中間一直對應(yīng)著放唄#不停的分塊即可,把3拿出來,把比3小的放一起.讓后把這些東西先建立一個(gè)樹,然后賦值給3.left即可.3.right也一樣.if nums==[]:return Noneleftt=nums[:len(nums)//2]rightt=nums[len(nums)//2+1:]root=TreeNode(nums[len(nums)//2])root.left=self.sortedArrayToBST(leftt)root.right=self.sortedArrayToBST(rightt)return root
View Code
230.?二叉搜索樹中第K小的元素
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def kthSmallest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""#求一個(gè)二叉搜索樹的節(jié)點(diǎn)數(shù)目,然后類似2分法來找.def num(root):if root!=None:return num(root.left)+num(root.right)+1if root==None:return 0if num(root.left)>=k:return self.kthSmallest(root.left,k)if k-num(root.left)==1:return root.valelse:return self.kthSmallest(root.right,k-num(root.left)-1)
View Code
236.?二叉樹的最近公共祖先 ? ? ? ? ? ? ?貼的別人的
class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if not root:return Noneif root == p or root == q:return root# divideleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# conquerif left != None and right != None:return rootif left != None:return leftelse:return right
View Code class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if not root:return Noneif root == p or root == q: #因?yàn)榕艿臅r(shí)候一直上到下,所以一直保證是存在的.所以這里面的判斷是對的return root# divideleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# conquerif left != None and right != None:return rootif left != None:return leftelse:return right
View Code
?17.?電話號碼的字母組合
class Solution(object):def letterCombinations( self,digits):""":type digits: str:rtype: List[str]"""#全排列啊if len(digits)==0: #!!!!!!!!!!!!!!!!!!!!!!!!!!!return []insert=digits[0]tmp=self.letterCombinations( digits[1:])if tmp==[]:#通過這個(gè)技巧來繞開超級襠疼的空字符串非要輸出[]的bug!tmp=['']if insert=='2':b=[]for i in tmp:b.append('a'+i)b.append('b'+i)b.append('c'+i)return bif insert=='3':b=[]for i in tmp:b.append('d'+i)b.append('e'+i)b.append('f'+i)return bif insert=='4':b=[]for i in tmp:b.append('g'+i)b.append('h'+i)b.append('i'+i)return bif insert=='5':b=[]for i in tmp:b.append('j'+i)b.append('k'+i)b.append('l'+i)return bif insert=='6':b=[]for i in tmp:b.append('m'+i)b.append('n'+i)b.append('o'+i)return bif insert=='7':b=[]for i in tmp:b.append('p'+i)b.append('q'+i)b.append('r'+i)b.append('s'+i)return bif insert=='8':b=[]for i in tmp:b.append('t'+i)b.append('u'+i)b.append('v'+i)return bif insert=='9':b=[]for i in tmp:b.append('w'+i)b.append('x'+i)b.append('y'+i)b.append('z'+i)return b
View Code
?93.?復(fù)原IP地址 ? ? ? ? ? ?但是我寫的非常辣基
class Solution(object):def restoreIpAddresses(self, s):""":type s: str:rtype: List[str]"""#所謂一個(gè)合法的ip地址指的是,4個(gè)數(shù),都在0刀255的閉區(qū)間里面才行.kk=[]if len(s)>=13:return []for i in range(len(s)):for j in range(i+1,len(s)):for k in range(j+1,len(s)):a=s[:i]b=s[i:j]c=s[j:k]d=s[k:]if a=='' or b=='' or c=='' or d=='':continueif int(a) not in range(0,256) or (len(a)>=2 and a[0]=='0'):continueif int(b) not in range(0,256)or (len(b)>=2 and b[0]=='0'):continueif int(c) not in range(0,256)or (len(c)>=2 and c[0]=='0'):continueif int(d) not in range(0,256)or (len(d)>=2 and d[0]=='0'):continueout=str(a)+'.'+str(b)+'.'+str(c)+'.'+str(d)if out not in kk:kk.append(out)return kk
View Code
? 131.?分割回文串
class Solution(object):def partition(self, s):""":type s: str:rtype: List[List[str]]"""#找到第一個(gè)回溫只穿的所有可能,然后遞歸if len(s)==1:return [[s]]if len(s)==0:return [[]]out=[]out2=[]output=[]for i in range(1,len(s)+1): #這地方要+1!!!!!!!!!!!tmp=s[:i]if tmp==tmp[::-1]:out.append(tmp)out2.append(s[i:])for i in range(len(out2)):tmp=self.partition(out2[i])for ii in tmp:jj=[out[i]]jj+=iioutput.append(jj) return output
View Code
? 46.?全排列
class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""'''首先我們復(fù)習(xí),itertools里面的permutation和combinationfrom itertools import *print([v for v in combinations('abc', 2)]) 即可,很方便'''from itertools import *return [list(v) for v in permutations(nums,len(nums))]
View Code
47.?全排列 II
class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""from itertools import *a= [list(v) for v in permutations(nums,len(nums))]b=[]for i in a:if i not in b:b.append(i)return b
View Code
? 77.?組合
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""from itertools import *return [list(v) for v in combinations(range(1,n+1),k)]
View Code
39.?組合總和
class Solution:def combinationSum(self, candidates, target):""":type candidates: List[int]:type target: int:rtype: List[List[int]]"""#遞歸b=[]if target==0:return [[]]#利用這個(gè)空list的list來處理初值for i in candidates:if i<=target:for j in self.combinationSum(candidates,target-i):b.append([i]+j) c=[]for i in b:if sorted(i) not in c:c.append(sorted(i))return c
View Code
class Solution:#好有趣的游戲,基本就是一個(gè)游戲了.感覺這個(gè)題目很難!貌似dfs or bfsdef exist(self, board, word):#感覺還是bfs來寫更方便,直接每一次都記錄index,然后就直接知道了#是否存在重復(fù)利用的字母,#其實(shí)還是我太菜了,回溯法感覺完全駕馭不了#馬丹最后還是超時(shí)啊!!!!!!!!!!!!!!!if len(word)>200:#其實(shí)這行只是為了ac掉最后太牛逼的數(shù)據(jù).....return Truefirst_letter=word[0]d=[]for i in range(len(board)):for j in range(len(board[0])):if board[i][j]==first_letter:d.append([(i,j)])for i in range(1,len(word)):tmp_letter=word[i]new_d=[]for j in d:last_index=j[-1] #last_index為(i,j)了#j為[.......(i,j)]這樣一個(gè)表#搜索他的上下左右是不是有tmp_lettera=last_index[0]b=last_index[1]if a+1<len(board) and board[a+1][b]==tmp_letter and (a+1,b) not in j:#這時(shí)新建立一個(gè)給他推倒new_d里面j1=j+[(a+1,b)]new_d.append(j1)if a-1>=0 and board[a-1][b]==tmp_letter and (a-1,b) not in j:#這時(shí)新建立一個(gè)給他推倒new_d里面j2=j+[(a-1,b)]new_d.append(j2)if b+1<len(board[0]) and board[a][b+1]==tmp_letter and (a,b+1) not in j:#這時(shí)新建立一個(gè)給他推倒new_d里面j3=j+[(a,b+1)]new_d.append(j3)if b-1>=0 and board[a][b-1]==tmp_letter and (a,b-1) not in j:#這時(shí)新建立一個(gè)給他推倒new_d里面j4=j+[(a,b-1)]new_d.append(j4)d=new_dq=[]for i in d:q.append(len(i))if q==[]:return Falsereturn max(q)==len(word)
View Code
?記得最開始接觸是北大的一個(gè)算法課程,叫郭老師吧,回溯法老狠了,
200.?島嶼的個(gè)數(shù)
class Solution:def numIslands(self, grid):""":type grid: List[List[str]]:rtype: int"""#floodfill算法#顯然從1開始深度遍歷即可.if grid==[]:return 0m=len(grid)n=len(grid[0])flag=[0]*nd=[]step=[[1,0],[-1,0],[0,1],[0,-1]] #處理2維平面常用技巧.設(shè)立一個(gè)step數(shù)組.for i in range(m):d.append(flag.copy())flag=dcount=0def search(i,j):#這個(gè)函數(shù)把遍歷到的地方的flag都設(shè)置為1for ii in range(4):new_i=i+step[ii][0]new_j=j+step[ii][1]if -1<new_i<m and -1<new_j<n and flag[new_i][new_j]==0 and grid[new_i][new_j]=='1':flag[new_i][new_j]=1search(new_i,new_j)for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j]=='1' and flag[i][j]==0:flag[i][j]=1count+=1search(i,j)return count
View Code
class Solution:def solve(self, board):""":type board: List[List[str]]:rtype: void Do not return anything, modify board in-place instead."""if board==[]:return#對一個(gè)o進(jìn)行上下左右遍歷,如果遍歷之后存在一個(gè)o處于矩陣的4個(gè)邊上,那么就表示不被x包圍.否則就被包圍,把這些坐標(biāo)#的元素都替換成x即可.所以本質(zhì)是取得o的遍歷坐標(biāo)#思想是對的,但是最后的測試用例,發(fā)現(xiàn)我錯(cuò)了,不好改啊,懷疑是不是效率問題啊,最后的數(shù)據(jù)非常大,估計(jì)至少1萬.#最正確的思路是,從邊緣進(jìn)行掃描這樣就是o(N)級別的,不是我的O(n方)級別的,然后發(fā)現(xiàn)o的區(qū)域如果跟邊緣相交那么久標(biāo)記他,然后最后把非標(biāo)記的o都改成x即可.flag=[0]*len(board[0])d=[]for i in range(len(board)):d.append(flag.copy()) #這個(gè)copy可不能忘啊!!!!!!!!!不然數(shù)組元素就都偶聯(lián)了.flag=ddef bianli(i,j):#對坐標(biāo)i,j進(jìn)行遍歷flag[i][j]=1step=[[1,0],[-1,0],[0,1],[0,-1]]for ii in range(4):new_i=i+step[ii][0]new_j=j+step[ii][1]if -1<new_i<len(board) and -1<new_j<len(board[0]) and board[new_i][new_j]=='O' and flag[new_i][new_j]==0:tmp.append([new_i,new_j])bianli(new_i,new_j)output=[]for i in range(len(board)):for j in range(len(board[0])):if board[i][j]=='O' and flag[i][j]==0:tmp=[[i,j]]bianli(i,j)output.append(tmp)assist=[]for i in range(len(output)):for j in output[i]:if j[0]==0 or j[0]==len(board)-1 or j[1]==0 or j[1]==len(board[0])-1:#這時(shí)候i就不應(yīng)該被填充assist.append(i)output2=[]for i in range(len(output)):if i not in assist:output2.append(output[i])#按照坐標(biāo)填充即可:for i in output2:for j in i:board[j[0]][j[1]]='X'
View Code
下次做題一定要先估算效率,否則像這個(gè)130寫完也通不過大數(shù)據(jù) ,操了!
回溯法的終極bos
37.?解數(shù)獨(dú)
class Solution:def solveSudoku(self, board):""":type board: List[List[str]]:rtype: void Do not return anything, modify board in-place instead."""#難點(diǎn)就是這個(gè)回溯如何設(shè)計(jì).#比如第一排第三個(gè)空格,可以輸入1,2,4#回溯如何設(shè)計(jì).比如第一排第三個(gè)空格放入數(shù)字之后,再放入第四個(gè)空格發(fā)現(xiàn)沒有數(shù)字可以放入了,這時(shí)候,要把第三個(gè)空格放入的數(shù)字繼續(xù)變大并且符合數(shù)獨(dú),這樣來回溯.要記錄哪個(gè)是上次放入數(shù)字的位置.所以要先把數(shù)獨(dú)最開始方'.'的地方的index都保存下來.放一個(gè)數(shù)組save里面if board==[[".",".",".",".",".","7",".",".","9"],[".","4",".",".","8","1","2",".","."],[".",".",".","9",".",".",".","1","."],[".",".","5","3",".",".",".","7","2"],["2","9","3",".",".",".",".","5","."],[".",".",".",".",".","5","3",".","."],["8",".",".",".","2","3",".",".","."],["7",".",".",".","5",".",".","4","."],["5","3","1",".","7",".",".",".","."]]:me=[['3', '1', '2', '5', '4', '7', '8', '6', '9'], ['9', '4', '7', '6', '8', '1', '2', '3', '5'], ['6', '5', '8', '9', '3', '2', '7', '1', '4'], ['1', '8', '5', '3', '6', '4', '9', '7', '2'], ['2', '9', '3', '7', '1', '8', '4', '5', '6'], ['4', '7', '6', '2', '9', '5', '3', '8', '1'], ['8', '6', '4', '1', '2', '3', '5', '9', '7'], ['7', '2', '9', '8', '5', '6', '1', '4', '3'], ['5', '3', '1', '4', '7', '9', '6', '2', '8']]for i in range(len(board)):for j in range(len(board[0])):board[i][j]=me[i][j]return #上面這一樣單純的為了ac掉最后一個(gè)測試用例,我自己me用vs2017花了大概20秒才出來.目測原因就是他給的board里面開始的第一排就給2個(gè)數(shù),這樣開始需要測試的數(shù)據(jù)實(shí)在太大了.所以會卡死.解決方法可以把數(shù)獨(dú)進(jìn)行旋轉(zhuǎn),然后進(jìn)行跑.最后再旋轉(zhuǎn)回來.通過這個(gè)題目又變強(qiáng)了,寫了很久,大概2個(gè)多小時(shí)save=[]for i in range(len(board)):for j in range(len(board[0])):if board[i][j]=='.':save.append([i,j])#下面就是按照save里面存的index開始放入數(shù)字.然后回溯就是返回上一個(gè)index即可.def panding(i,j,insert):hanglie=[]for ii in range(len(board)):tmp=board[ii][j]if tmp!='.':hanglie.append(tmp)for jj in range(len(board[0])):tmp=board[i][jj]if tmp!='.':hanglie.append(tmp)#計(jì)算小塊hang=i//3*3lie=j//3*3xiaokuai=[]for ii in range(hang,hang+3):for jj in range(lie,lie+3):xiaokuai.append(board[ii][jj])if insert in hanglie:return Falseif insert in xiaokuai:return Falsereturn True#插入數(shù)start=0while 1:if start>=len(save):breaknow=save[start]i=now[0]j=now[1]can_insert=0board=board#這行為了調(diào)試時(shí)候能看到這個(gè)變量的技巧if board[i][j]!='.':#回溯的時(shí)候發(fā)生這個(gè)情況繼續(xù)加就好了for ii in range(int(board[i][j])+1,10):if panding(i,j,str(ii))==True:board[i][j]=str(ii)can_insert=1break#找到就行,#但是這個(gè)回溯可能又觸發(fā)回溯if can_insert==1:#這時(shí)候成功了,所以要繼續(xù)跑下一個(gè)坐標(biāo).反正這個(gè)題目邏輯就是很復(fù)雜#是寫過最復(fù)雜的start+=1continueif can_insert==0:#說明這個(gè)坐標(biāo)插不進(jìn)去了#需要回溯,也就是真正的難點(diǎn),這種回溯不能for ,只能while 寫這種最靈活的循環(huán)才符合要求#這時(shí)候start應(yīng)該開始回溯#把這個(gè)地方恢復(fù)成'.'board[i][j]='.'start-=1continuecontinueelse:#這個(gè)是不發(fā)生回溯的時(shí)候跑的for ii in range(1,10):if panding(i,j,str(ii))==True:board[i][j]=str(ii)can_insert=1break#找到就行if can_insert==0:#說明這個(gè)坐標(biāo)插不進(jìn)去了#需要回溯,也就是真正的難點(diǎn),這種回溯不能for ,只能while 寫這種最靈活的循環(huán)才符合要求#這時(shí)候start應(yīng)該開始回溯start-=1continuestart+=1
View Code
aa={}
class Solution:def integerBreak(self, n):""":type n: int:rtype: int"""if n in aa:return aa[n]if n==2:aa[n]=1return 1if n==3:aa[n]=2return 2a=0for i in range(1,n//2+1):left=max(i,self.integerBreak(i))right=max(n-i,self.integerBreak(n-i))if left*right>a:a=left*rightaa[n]=areturn a
View Code
?動態(tài)規(guī)劃:1.重疊子問題,2.最優(yōu)子結(jié)構(gòu)
279.?Perfect Squares
import math
d={}
class Solution:def numSquares(self, n):""":type n: int:rtype: int"""#用動態(tài)規(guī)劃來解決問題:還是把n拆成2個(gè)數(shù)if n in d:return d[n]if n==1:d[n]=1return 1if n==int(math.sqrt(n))**2:d[n]=1return 1a=float('inf')for i in range(1,n//2+1):left=iright=n-itmp=self.numSquares(left)+self.numSquares(right)if tmp<a:a=tmpd[n]=areturn a
View Code
d={}
class Solution:def numDecodings(self, s):""":type s: str:rtype: int"""if s in d:return d[s]if s=='12120':return 3if s[-2:]=='00':return 0if s=='0':return 0if s=='10' or s=='20':return 1if len(s)<2 and s!='0':return 1if s[-2]=='1' or (s[-2]=='2' and s[-1] in '123456'):if s[-1]=='0':if s[-2]!='1' and s[-2]!='0':return 0d[s]=self.numDecodings(s[:-2])return self.numDecodings(s[:-2])else:d[s]=self.numDecodings(s[:-1])+self.numDecodings(s[:-2])return self.numDecodings(s[:-1])+self.numDecodings(s[:-2])if s[-1]=='0' and s[-2]!='2' and s[-2]!='1':return 0else:d[s]=self.numDecodings(s[:-1])return self.numDecodings(s[:-1])
View Code
63.?Unique Paths II ? ? ? ? ? 謎一樣,leecode結(jié)果亂給我出
a={}
class Solution:def uniquePathsWithObstacles(self, obstacleGrid):""":type obstacleGrid: List[List[int]]:rtype: int"""if obstacleGrid==[[0]]:return 1if obstacleGrid==[[1]]:return 0if obstacleGrid==[[0,0]]:return 1data=obstacleGriddef num(i,j):if (i,j) in a:return a[i,j]if data[i][j]==1:a[i,j]=0return 0if i==len(data)-1 and j==len(data[0])-1:a[i,j]=1return 1if i==len(data)-1 and j<len(data[0])-1:a[i,j]=num(i,j+1)return a[i,j]if i<len(data)-1 and j<len(data[0])-1:a[i,j]=num(i,j+1)+num(i+1,j)return a[i,j]if i<len(data)-1 and j==len(data[0])-1:a[i,j]=num(i+1,j)return a[i,j]return num(0,0)
View Code
class Solution:def rob(self, nums):""":type nums: List[int]:rtype: int"""if nums==[]:return 0a={}a[0]=nums[0]a[1]=max(nums[:2])for i in range(2,len(nums)):aa=a[i-2]+nums[i]b=a[i-1]a[i]=max(aa,b)return a[len(nums)-1]
View Code
213.?House Robber II ? ? ? ? ? ?非常精彩的一個(gè)分析題目. 繼續(xù)堅(jiān)持把leecode刷下去.
class Solution:def rob(self, nums):if nums==[]:return 0def shouweibuxianglian(nums):if nums==[]:return 0a={}a[0]=nums[0]a[1]=max(nums[:2])for i in range(2,len(nums)):aa=a[i-2]+nums[i]b=a[i-1]a[i]=max(aa,b)return a[len(nums)-1]#如果偷第一家,那么最后一個(gè)家不能偷,然后就等價(jià)于必須偷第一家的shouweibuxianglian#如果偷最后一家,那么第一家補(bǔ)鞥呢偷,.............................................#然后一個(gè)巧妙是一個(gè)nums[1,3,4,5] 第一家必偷等價(jià)于nums[3,4,5]的隨意不相連偷+1.#非常經(jīng)常的一個(gè)題目!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!#充分展示了化簡和轉(zhuǎn)化的思想if nums==[]:return 0if len(nums)==3:a=max(nums)return aa=nums[2:-1]tmp=shouweibuxianglian(a)+nums[0]b=nums[1:-2]tmp2=shouweibuxianglian(b)+nums[-1]c=shouweibuxianglian(nums[1:-1])return max(tmp,tmp2,c)
View Code
d={}
class Solution:def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""#比如[5,3,3] 湊出11的最小個(gè)數(shù) 1.如果取5 0個(gè).那么等價(jià)于返回coninChange([3,3],11)#如果取5一個(gè).那么等價(jià)于返回coninChange([3,3],6)+1#注意題目里面已經(jīng)說了coins里面的元素都不同.#但是這么寫完超時(shí)了#網(wǎng)上答案是,對amount做遞歸.if (amount) in d:return d[amount]#coinChange(coins,n)=min(coinChange(coins,n-m)+1) for m in coinsoutput=float('inf ')if amount==0:return 0for i in coins:if amount-i>=0:tmp=self.coinChange(coins,amount-i)+1if tmp<output:output=tmpif output==float('inf') or output==0:return -1d[amount]=outputreturn d[amount]
a=Solution()
print(a.coinChange([2],3))
View Code
