242. 有效的字母异位词
题目说明中有提示：小写字母，这种一般想到用一个长度26的数组去做点什么事情
注意用collections里Counter的写法
import collections
Counter(targe_str)
用counter的话很简单，但是体现不出什么思想
def isAnagram(self, s: str, t: str) -> bool:
arr = [0]*26
for c in s:
arr[97-ord(c)] += 1
for c in t:
arr[97-ord(c)] -= 1
for x in arr:
if x != 0:
return False
return True
相似题目 266
给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串
思路：奇数字符数量为0或者1
def canBe(s):
arr = [0]*26
odd = 0
for c in s:
arr[97-ord(c)] += 1
for num in arr:
if num & 1 == 1:
odd += 1
return odd in (0,1)
相似题目
49. 字母异位词分组
这里用defaultdict方便输出结果
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
from collections import defaultdict
dic = defaultdict(list)
for s in strs:
key = ''.join(sorted(list(s)))
dic[key] += s.split(',')
return list(dic.values())
相似题目
438. 找到字符串中所有字母异位词
这也是个有趣的题目，人们在日常打字中常容易打出重复字符，这个程序可以判断是否是有效重复，哈哈
925. 长按键入
你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
def isLongPressedName(self, name: str, typed: str) -> bool:
l1,l2=len(name),len(typed)
p1=p2= 0 #双指针
while p1<l1 and p2<l2:
if name[p1]==typed[p2]:
c=name[p1]
cl1,cl2=p1,p2
while cl1<l1 and name[cl1]==c:
cl1+=1
while cl2<l2 and typed[cl2]==c:
cl2+= 1
if cl2-p2<cl1-p1:
return False
else:
p1,p2=cl1,cl2
else:
return False
if p1<l1 or p2<l2: #判断是否还有一个串有值
return False
return True
重点：
第一次没有写出来的几个点：
- while cl1<l1 and name[cl1]==c: 中的cl1<l1 定义的递增变量一定要注意判断是否越界，属于程序基本功
- 最后判断是否还有一个串有值，这个是业务逻辑上考虑不周密
百度面试遇到的：求子串重复数目
def getCount(s,substr):
ans = 0
p1 = p2 = 0
while(p1 < len(s)):
if p2<len(substr) and s[p1]==substr[p2]: #第一次写的时候没有写p2<len(str) 导致当len(substr)==1的时候判断substr[p2]会越界
if p2 == len(substr)-1:
ans += 1
p2 = 0
p1 += 1
p2 += 1
else:
p2 = 0
if s[p1]!=substr[p2]:
p1 += 1
return ans
1464 直接用sorted , 当然自己还是要会写快排
无论如何，第一次成功做出树类型的题目还是很开心，加油加油，继续继续
1002. 查找常用字符
给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
输入：["bella","label","roller"]
输出：["e","l","l"]
输入：["cool","lock","cook"]
输出：["c","o"]
提示：
1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] 是小写字母
def commonChars(self, A: List[str]) -> List[str]:
if not A: return []
if len(A) == 1: return list(A)
ans, c =[], Counter(A[0])
for i in range(1,len(A)):
c = Counter(A[i]) & c #精华
for k in c:
ans.extend([k]*c[k])
return ans
知识点：counter的牛逼用法
763. 划分字母区间
做出来了但是复杂度是N^2 需要优化
def partitionLabels(self, S: str) -> List[int]:
if not S: return [0]
if len(S)==1: return [1]
dic,ans={},[]
for c in S:
if c in dic:
index = dic[c]
tmp = ''.join(ans[index:])+c #这里是debug出来第一次忘记加当前字符
ans = ans[:index]
ans.append(tmp)
for c1 in tmp:#这里也是debug出来，要把改片区所有字符对应的下标改掉
dic[c1] = index
else:
dic[c] = (len(ans))
ans.append(c)
return [len(s) for s in ans]
官方的思路更加正点，第一次遍历记住每个字符的最右端
第二次遍历根据这个左右端分段就行 贪心算法
class Solution:
def partitionLabels(self, S: str) -> List[int]:
last = [0] * 26
for i, ch in enumerate(S):
last[ord(ch) - ord("a")] = i
partition = list()
start = end = 0
for i, ch in enumerate(S):
end = max(end, last[ord(ch) - ord("a")])
if i == end:
partition.append(end - start + 1)
start = end + 1
return partition
76. 最小覆盖子串
def minWindow(self, s: str, t: str) -> str:
ls,lt=len(s),len(t)
if(ls==lt): return s if s==t else ""
elif(ls<lt): return ""
else:
left,right=-10**9,10**9
low,high=0,0
tmp=t
while(high<ls):
if(s[high] in tmp):
tmp=tmp.replace(s[high],"")
if(not tmp):
if(high-low)<(right-left):
left,right=low,high
tmp=t
high+=1
return s[left:right+1]
这里把自己困住的主要原因是不知道怎么去判断滑动窗口包含了T中所有的元素，这个时候要想到计数counter，那么自然也就可以想到字典了，于是滑动窗口+字典的组合出炉了
def minWindow(self, s: str, t: str) -> str:
ls,lt=len(s),len(t)
if(ls<lt): return ""
else:
low,high,num,mlen,start=0,0,0,ls+1,0 #num表示滑动窗口中出现t中字符的个数,mlen表示最小子串长度,start起始位置
windic,tdic={},dict(Counter(t)) #滑动窗口字典和待查找字符串字典
while(high<ls):
highCount=windic.get(s[high],0) #抽取出来之后速度是有明显提升的
if(highCount<tdic.get(s[high],0)):#待查找字符出现，+1
num+=1
windic[s[high]]=highCount+1 #字符频次+1
high+=1 #注意是每次先和待查找字典对比后再+1
while(num==lt): #表示滑动窗口包含了t中所有字符,开始移动左边界
lowCount=windic.get(s[low],0);#抽取出来之后速度是有明显提升的
if((high-low)<mlen): #移动左边界的过程中记录最小子串
mlen,start=high-low,low
if(lowCount==tdic.get(s[low],0)):#待查找字符出现，频次-1
num-=1
windic[s[low]]=lowCount-1 #字符频次-1
low+=1
return "" if mlen==ls+1 else s[start:start+mlen]
1. 43. 字符串相乘
def multiply(self, num1: str, num2: str) -> str:
if(num1=="0" or num2=="0"): return "0"
else:
ans=0
l1,l2=len(num1),len(num2)
for i in range(l1):
for j in range(l2):
a = int(num1[i])*pow(10,l1-1-i)
b = int(num2[j])*pow(10,l2-1-j)
ans += (a*b)
return str(ans)
submit successfully but the time is 334ms , not that fast
a = int(num1[i])pow(10,l1-1-i) can be moved to the outer loop , 100ms decreased
you can find return str(int(num1)int(num2)) only cost 40 ms what's the purpose of the problem?
3. 剑指 Offer 67. 把字符串转换成整数
4. 剑指 Offer 20. 表示数值的字符串
这个有点难，虽然理性分析了良久，但是最终还是有漏掉的case，可以看下最后一次的面条代码
def isNumber(self, s: str) -> bool:
pool='+-.e0123456789'
num_pool=pool[4:]
s = s.lower().strip()
if(len(s)==1 and num_pool.find(s[0])==-1):return False
dic = {}
epos, dotpos, addpos, negpos = -1,-1,-1,-1
for i in range(len(s)):
dic[s[i]] = dic.get(s[i],0) + 1
if pool.find(s[i]) == -1: return False
if(dic.get('.',0) > 1 or dic.get('e',0) > 1 or dic.get('+',0) > 1): return False
if(s[i] == '.'): dotpos = i
if(s[i] == 'e'): epos = i
if(s[i] == '+'): addpos = i
if(s[i] == '-'): negpos = i
if(addpos!=-1 and addpos!=0): return False #正号必须在第一位
if(epos!=-1 and dotpos!=-1 and epos-dotpos<2): return False #e至少要在.后两位
if(epos==0 or epos==len(s)-1): return False #e不能出现在首尾
#判断.前后数字的逻辑
if(dotpos==len(s)-1 and num_pool.find(s[dotpos-1])==-1): return False
if(dotpos==0 and num_pool.find(s[1])==-1): return False
if(dotpos!=-1 and dotpos!=len(s)-1 and dotpos!=0):
if(num_pool.find(s[dotpos+1])==-1): return False #.后面一定是数字 前面可以是小数点和数字
if(negpos!=-1):
if(negpos==0 or s[negpos-1]=='e'): return True #负号判断应该放在最后
else: return False
return True
疯了有没有。。。。只能看答案了，有限状态机！
同时学习了python中枚举的用法和dic中包含dic的巧妙使用
Python 优先状态机题解
a = Enum('status',['status1','status2'])
a.status1
a.status2
