记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
11/7 816. 模糊坐标11/8 1684. 统计一致字符串的数目11/9 764. 最大加号标志11/10 864. 获取所有钥匙的最短路径11/11 1704. 判断字符串的两半是否相似11/12 790. 多米诺和托米诺平铺11/13 791. 自定义字符串排序
11/7 816. 模糊坐标
check用来解析s可以添加小数点后 形成多少种情况
遍历位置i 寻找i左侧部分left 右侧right 可以构成的情况
分别组合
def ambiguousCoordinates(s): """ :type s: str :rtype: List[str] """ def check(s): res = [] if s[0]!='0' or s=='0': res.append(s) for loc in range(1,len(s)): if loc!=1 and s[0]=='0' or s[-1]=='0': continue res.append(s[:loc]+'.'+s[loc:]) return res l = s[1:-1] ans = [] for i in range(1,len(l)): left = check(l[:i]) if len(left)==0: continue right = check(l[i:]) if len(right)==0: continue for x in left: for y in right: ans.append('('+x+', '+y+')') return ans11/8 1684. 统计一致字符串的数目
检验每个word
def countConsistentStrings(allowed, words): """ :type allowed: str :type words: List[str] :rtype: int """ s = set(list(allowed)) def check(w): for c in w: if c not in s: return False return True ans = 0 for w in words: if check(w): ans +=1 return ans11/9 764. 最大加号标志
对于位置[i,j] 它可以得到最大的加号长度 为他到四边的距离最小值 min(i+1,j+1,n-i,n-j)
遍历所有的为0的位置 更新其位置上下左右距离dis
def orderOfLargestPlusSign(n, mines): """ :type n: int :type mines: List[List[int]] :rtype: int """ grid = [[0]*n for _ in range(n)] for i in range(n): for j in range(n): grid[i][j] = min(i+1,n-i,j+1,n-j) for x,y in mines: grid[x][y] = 0 dis = 1 while x-dis>=0 or x+dis<n or y-dis>=0 or y+dis<n: if x-dis>=0: grid[x-dis][y] = min(grid[x-dis][y],dis) if x+dis<n: grid[x+dis][y] = min(grid[x+dis][y],dis) if y-dis>=0: grid[x][y-dis] = min(grid[x][y-dis],dis) if y+dis<n: grid[x][y+dis] = min(grid[x][y+dis],dis) dis+=1 return max([max(l) for l in grid])11/10 864. 获取所有钥匙的最短路径
广搜
(i,j,mask)代表当前状态 i,j为当前位置
mask为当前已经有的钥匙状态 mask为k长度的二进制 如果某一个钥匙拿到 则该位置设置为1
寻找mask = 2*k-1时最短路径
dis记录(i,j,mask)状态需要的最小步数
遇到钥匙 更新mask状态
遇到锁 判断是否有对应的钥匙
def shortestPathAllKeys(grid): """ :type grid: List[str] :rtype: int """ steps = [(-1,0),(0,-1),(1,0),(0,1)] m,n = len(grid),len(grid[0]) keyid = {} sx,sy = 0,0 for i in range(m): for j in range(n): if grid[i][j]=="@": sx,sy=i,j elif grid[i][j].islower(): if grid[i][j] not in keyid: idx = len(keyid) keyid[grid[i][j]]=idx l = [(sx,sy,0)] dis = {} dis[(sx,sy,0)] = 0 while l: tmp = [] for x,y,mask in l: for dx,dy in steps: nx,ny = x+dx,y+dy if 0<=nx<m and 0<=ny<n and grid[nx][ny]!="#": if grid[nx][ny]=="." or grid[nx][ny]=="@": if (nx,ny,mask) not in dis: dis[(nx,ny,mask)] = dis[(x,y,mask)]+1 tmp.append((nx,ny,mask)) elif grid[nx,ny].islower(): idx = keyid[grid[nx][ny]] if (nx,ny,mask|(1<<idx)) not in dis: dis[(nx,ny,mask|(1<<idx))]= dis[(x,y,mask)]+1 if mask|(1<<idx) ==2**len(keyid)-1: return dis[(nx,ny,mask|(1<<idx))] tmp.append((nx,ny,mask|(1<<idx))) else: idx = keyid[grid[nx][ny].lower()] if mask&(1<<idx) and (nx,ny,mask) not in dis: dis[(nx,ny,mask)] = dis[(x,y,mask)]+1 tmp.append((nx,ny,mask)) l = tmp return -111/11 1704. 判断字符串的两半是否相似
判断前一半元音和后一半元音数目是否相同
def halvesAreAlike(s): """ :type s: str :rtype: bool """ n = len(s) dic = set(['a','e','i','o','u','A','E','I','O','U']) diff = 0 loc = 0 while loc<n//2: if s[loc] in dic: diff +=1 if s[loc+n//2] in dic: diff -=1 loc+=1 return diff==011/12 790. 多米诺和托米诺平铺
dp
假设dp[i][x]为第i列状态 0一个没有铺 1上方格子被铺 2下方格子被铺 3两个格子都被铺
dp[i][0] = dp[i-1][3]
dp[i][1] = dp[i-1][0]+dp[i-1][2]
dp[i][2] = dp[i-1][0]+dp[i-1][1]
dp[i][3] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]
def numTilings(n): """ :type n: int :rtype: int """ MOD=10**9+7 dp = [[0]*4 for _ in range(n+1)] dp[0][3]=1 for i in range(1,n+1): dp[i][0] = dp[i-1][3] dp[i][1] = (dp[i-1][0]+dp[i-1][2])%MOD dp[i][2] = (dp[i-1][0]+dp[i-1][1])%MOD dp[i][3] = (dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3])%MOD return dp[n][3]11/13 791. 自定义字符串排序
统计s中出现的个字母出现的次数
依次遍历order每个字母c 如果c在s中出现 则将出现次数个c加入答案中
最后将没有出现的字母加入
def customSortString(order, s): """ :type order: str :type s: str :rtype: str """ dic = {} for c in s: dic[c] = dic.get(c,0)+1 ans = [] for c in order: if c in dic: ans.extend([c]*dic[c]) dic[c]=0 for c in dic.keys(): if dic[c]>0: ans.extend([c]*dic[c]) return "".join(ans)