1.数据结构-字符串问题

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