近幾天使用的進(jìn)階python語(yǔ)法
- zip(*)將列轉(zhuǎn)換為行窿撬，是二維數(shù)組轉(zhuǎn)換為[(),(),()]形式。
- set()增加元素使用add
- 列表由值找索引叙凡，使用index(value)
- 二分查找劈伴，bisect類有bisect_left和bisect_right函數(shù)（object，target）握爷，返回的是idx
- python3的duque隊(duì)列模塊是雙向隊(duì)列跛璧，其中append和pop均在右側(cè)進(jìn)行，appendleft和popleft()在左側(cè)進(jìn)行新啼。
對(duì)于連續(xù)子序列的和問(wèn)題追城，可以考慮前綴和+哈希優(yōu)化（對(duì)于哈希的查找是O（1），而非O(N)）
重點(diǎn)：使用哈希前將h[i]-h[j-1]==k轉(zhuǎn)換為h[j-1]==h[i]-k即查找h[i]-k出現(xiàn)的次數(shù)燥撞，即相當(dāng)于查找了h[j-1]座柱，其個(gè)數(shù)即哈希值
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k迷帜，你需要找到該數(shù)組中和為 k 的連續(xù)的子數(shù)組的個(gè)數(shù)。
示例 1 :
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況色洞。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
pre=0
dict_={0:1}
ans=0
for i in nums:
pre+=i
ans+=dict_.get(pre-k,0)
dict_[pre]=dict_.get(pre,0)+1
print(dict_)
return ans
'''
#前后指針
left,right=0,0
ans=0
cnt=0
while right<len(nums):
if cnt+nums[right]<k:
cnt+=nums[right]
right+=1
elif cnt+nums[right]==k:
cnt+=nums[right]
ans+=1
cnt-=nums[left]
left+=1
right+=1
else:
cnt-=nums[left]
if left==right:
right+=1
left+=1
return ans
'''
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有戏锹。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處火诸。
自我感覺(jué)使用了O(1)的內(nèi)存和O(N)的時(shí)間復(fù)雜度
給你一個(gè)整數(shù)數(shù)組 nums 锦针，判斷這個(gè)數(shù)組中是否存在長(zhǎng)度為 3 的遞增子序列。
如果存在這樣的三元組下標(biāo) (i, j, k) 且滿足 i < j < k 置蜀，使得 nums[i] < nums[j] < nums[k] 奈搜，返回 true ；否則盯荤，返回 false 馋吗。
輸入：nums = [1,2,3,4,5]
輸出：true
解釋：任何 i < j < k 的三元組都滿足題意
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/increasing-triplet-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)廷雅，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處耗美。
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
if len(nums)<3:
return False
#last_min_left,last_min_right,min_left,min_right=0,0,0,0
flag=False#記錄有沒(méi)有找到right
min_left,min_right=nums[0],nums[1]
if min_right>min_left:
flag=True
elif min_right<min_left:
min_left,min_right=min_right,min_left
for i in nums[2:]:
#print(min_left,min_right,flag)
if min_left>i:
min_left=i
elif i>min_left and not flag:
min_right=i
flag=True
elif flag and min_left<i<min_right:
min_right=i
elif flag and i>min_right:
return True
return False
注意在python中set是哈希表
字符串 S 由小寫(xiě)字母組成。我們要把這個(gè)字符串劃分為盡可能多的片段航缀，同一字母最多出現(xiàn)在一個(gè)片段中商架。返回一個(gè)表示每個(gè)字符串片段的長(zhǎng)度的列表。
示例：
輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"芥玉。
每個(gè)字母最多出現(xiàn)在一個(gè)片段中蛇摸。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯(cuò)誤的，因?yàn)閯澐值钠螖?shù)較少灿巧。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-labels
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有赶袄。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處抠藕。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
#O(N^2)的復(fù)雜度不知道能不能過(guò)
hash_set=set()
def first_end_idx(c:str,s):
#st,ed=-1,len(s)
st=s.find(c)
ed=len(s)-s[::-1].find(c)-1
'''
if c=='a':
print(st,ed)
'''
return st,ed
ans=[]
sta,end=-1,-1
for i in s:
if i not in hash_set:
hash_set.add(i)
else:
continue
a,b=first_end_idx(i,s)
if sta==-1:
sta,end=a,b
elif a<end and b>end:
end=b
elif a>=end:
ans.append(end-sta+1)
sta,end=a,b
ans.append(end-sta+1)
return ans
給定一種規(guī)律 pattern 和一個(gè)字符串 str 饿肺，判斷 str 是否遵循相同的規(guī)律。
這里的 遵循 指完全匹配盾似，例如敬辣， pattern 里的每個(gè)字母和字符串 str 中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(yīng)規(guī)律。
示例1:
輸入: pattern = "abba", str = "dog cat cat dog"
輸出: true
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-pattern
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有零院。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)溉跃，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
word_to_chr={}
s_list=s.split(' ')
#pa_list=list(pattern)
if len(s_list)!=len(pattern):
return False
for i in range(len(s_list)):
if s_list[i] not in word_to_chr:
if pattern[i] not in word_to_chr.values():
word_to_chr[s_list[i]]=pattern[i]
else:
#print('hi')
return False
else:
if word_to_chr[s_list[i]]==pattern[i]:
pass
else:
return False
return True
自作聰明導(dǎo)致做錯(cuò)
很多時(shí)候自作聰明并不是比最終答案做出的努力少告抄，而是努力方向沒(méi)加以驗(yàn)證撰茎，做了錯(cuò)誤的努力
給你一個(gè)整數(shù) n ，求恰由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的 二叉搜索樹(shù) 有多少種打洼？返回滿足題意的二叉搜索樹(shù)的種數(shù)龄糊。
image.png
class Solution:
def __init__(self):
self.dict_={}
self.dict_[1]=1
self.dict_[2]=2
self.dict_[3]=5
self.dict_[0]=1
#動(dòng)態(tài)規(guī)劃or搜索
def numTrees(self, n: int) -> int:
#
if n==1:
return 1
elif n==2:
return 2
elif n==3:
return 5
else:
ans=0
if n in self.dict_:
return self.dict_[n]
for i in range(n):
'''
if n%2==1 and i==n//2:
continue
'''
ans+=self.numTrees(i)*self.numTrees(n-i-1)
#print(ans)
self.dict_[n]=ans
return ans
實(shí)屬惡心人了逆粹，屬于是
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if sum(candidates)<target:
return []
n=len(candidates)
isvisited=[False]*n
ans=[]
hash_set=set()
def dfs(sum_,i,per):
if sum_>target:
return
if sum_==target:
t=tuple(sorted(per))
if t not in hash_set:
hash_set.add(t)
ans.append([i for i in t])
return
for j in range(i,n):
if not isvisited[j]:
isvisited[j]=True
per.append(candidates[j])
dfs(sum_+candidates[j],j,per)
per.pop()
isvisited[j]=False
dfs(0,0,[])
return ans
