近几天使用的进阶python语法
- zip(*)将列转换为行，是二维数组转换为[(),(),()]形式。
- set()增加元素使用add
- 列表由值找索引，使用index(value)
- 二分查找，bisect类有bisect_left和bisect_right函数（object，target），返回的是idx
- python3的duque队列模块是双向队列，其中append和pop均在右侧进行，appendleft和popleft()在左侧进行。
对于连续子序列的和问题，可以考虑前缀和+哈希优化（对于哈希的查找是O（1），而非O(N)）
重点：使用哈希前将h[i]-h[j-1]==k转换为h[j-1]==h[i]-k即查找h[i]-k出现的次数，即相当于查找了h[j-1]，其个数即哈希值
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 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
'''
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
自我感觉使用了O(1)的内存和O(N)的时间复杂度
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-triplet-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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#记录有没有找到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 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
#O(N^2)的复杂度不知道能不能过
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
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
自作聪明导致做错
很多时候自作聪明并不是比最终答案做出的努力少，而是努力方向没加以验证，做了错误的努力
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
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
#动态规划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
实属恶心人了，属于是
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
