字符串&数组


17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        map={'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
        if not digits: return []
        ans=[""]
        for i in digits:
            ans=[pre+suf for pre in ans for suf in map[i]]
        return ans

696.计数二进制子串

给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        temp=[1]
        ans=0
        for i in range(1,len(s)):
            if s[i]==s[i-1]:
                temp[-1]+=1
            else:
                temp.append(1)
        for i in range(len(temp)-1):
            ans+=min(temp[i],temp[i+1])
        return ans

# 计算相邻数的频数
# 看着有些抽象

605.种花问题

假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

给定一个花坛(表示为一个数组包含01,其中0表示没种植花,1表示种植了花),和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花?能则返回True,不能则返回False

class Solution:
    def canPlaceFlowers(self, f: List[int], n: int) -> bool:
        f=[0]+f+[0,1]
        ans,cnt=0,0
        for i in f:
            if i==0: cnt+=1
            else: 
                ans+=(cnt-1)//2
                cnt=0
        #print(ans,n)
        return ans>=n

# 数组,两端加值便于解题。

75.颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 012 分别表示红色、白色和蓝色。

#荷兰国旗问题,快速排序基础
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        i,l,r=0,0,len(nums)-1
        while i<=r:
            if nums[i]==0:
                nums[i],nums[l]=nums[l],nums[i]
                l+=1
                i+=1
            elif nums[i]==2:
                nums[i],nums[r]=nums[r],nums[i]
                r-=1
            else: i+=1

74.搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows,cols=len(matrix),len(matrix[0])
        l,r=0,rows*cols-1
        while l<=r:
            mid=(l+r)//2
            x,y=mid//cols,mid%cols
            if matrix[x][y]==target: return True
            elif matrix[x][y]>target: r=mid-1
            else: l=mid+1
        return False

#原地二分查找

852.山脉数组的峰顶索引

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l, r = 0, len(arr)-1
        while l<r:
            mid = (l+r)//2
            if arr[mid] > arr[mid+1]:
                r = mid
            else:
                l = mid + 1
        return l

#二分的变式

kmp算法

kmp是一个效率非常高的字符串匹配算法。
有问题如下:

#求b在a中出现次数
a = "ababacababadababadadda"
b = "ababad"

kmp可以将暴力法的O(m*n)降低为O(m+n)

过程:
1. 计算temp数组
temp数组可理解为一组b中相同前后缀的标记(不能为本身长度)

b = "ababad"
对第一位'a',没有相同前后缀,temp[0] = 0
对第二位'ab'temp[1] = 0
对第三位’aba'temp[2] = 1
以此类推,temp= [0,0,1,2,3,0]

def cal_temp(b):
    #K是一个对相同前后缀的标记
    temp,k=[0],0
    #从索引1处开始遍历
    for i in range(1,len(b)):
        while k>0 and b[i]!=b[k]:
            k=temp[k-1]
        if b[i]==b[k]:
            k+=1
        temp.append(k)
    return temp

分析一下代码:

  • i=1时,’ab’,b[1]!=b[0],temp.append(0)
  • i=2时,’aba’,b[2]==b[0],temp.append(1)
  • i=3时,’abab’,b[3]==b[1],temp.append(2)
  • i=4时,’ababa’,b[4]==b[2],temp.append(3)
  • i=5时,’ababad’,temp=[0,0,1,2,3]
    b[5]!=b[3],k=temp[3-1]=1
    b[5]!=b[1],k=temp[1-1]=0
    temp.append(0)

发现比较难理解的是那个回溯的地方:k=temp[k-1]
没事,把i=5的情况再分析一下:

i=5时,’ababad’,temp=[0,0,1,2,3],k=3

aba and aba can match,k=3
a and a can match,k=(aba的匹配数1,即temp[k-1])
more explain: aba can see as a and a,the first a can match the fourth a

2. kmp
打完上面的怪,就可以直接写kmp了

def kmp(a,b):
    temp=cal_temp(b)
    ans,k=0,0
    for i in range(len(a)):
        while k>0 and a[i]!=b[k]:
            k=temp[k-1]
        if a[i]==b[k]:
            k+=1
        if k==len(b):
            ans+=1
            k=temp[k-1]
    return ans

#小结:利用已匹配的信息,迈出比较大的步子。

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录