记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
6/12 1483. 树节点的第 K 个祖先6/13 2475. 数组中不等三元组的数目6/14 1375. 二进制字符串前缀一致的次数6/15 1177. 构建回文串检测6/16 1494. 并行课程 II6/17 2481. 分割圆的最少切割次数6/18 1254. 统计封闭岛屿的数目
6/12 1483. 树节点的第 K 个祖先
dp[i][j]表示节点i的第2^j个祖先 对于dp[i][j] 可以先得到2^(j-1)的祖先dp[i][j-1] 然后再找这个祖先的2^(j-1)祖先 及dp[dp[i][j-1]][j-1]
class TreeAncestor(object):
def __init__(self, n, parent):
"""
:type n: int
:type parent: List[int]
"""
self.dp = [[] for _ in range(n)]
for i in range(n):
self.dp[i].append(parent[i])
j=1
while True:
tag = True
for i in range(n):
v = -1
if self.dp[i][j-1]!=-1:
v = self.dp[self.dp[i][j-1]][j-1]
self.dp[i].append(v)
if v!=-1:
tag = False
if tag:
break
j+=1
def getKthAncestor(self, node, k):
"""
:type node: int
:type k: int
:rtype: int
"""
ans = node
pos = 0
while k and ans!=-1:
if pos>=len(self.dp[ans]):
return -1
if k&1:
ans = self.dp[ans][pos]
k = k>>1
pos+=1
return ans
6/13 2475. 数组中不等三元组的数目
统计每个整数出现次数
def unequalTriplets(nums):
"""
:type nums: List[int]
:rtype: int
"""
from collections import defaultdict
m = defaultdict(int)
for num in nums:
m[num]+=1
n = len(nums)
l = 0
ans = 0
for v in m.value():
ans += l*v*(n-l-v)
l+=v
return ans
6/14 1375. 二进制字符串前缀一致的次数
记录翻转最大位置 如果最大位置等于翻转次数 说明满足
def numTimesAllBlue(flips):
"""
:type flips: List[int]
:rtype: int
"""
ans,r = 0,0
for i,v in enumerate(flips):
r = max(r,v)
if r==i+1:
ans +=1
return ans
6/15 1177. 构建回文串检测
可以重新排列 所以最多一个字符出现奇数次可以构成回文串 用26位二进制来表示字符串每个字母的奇偶性 m用来存储前缀 getnum用来获取字符串中有多少个奇数次的字母
def canMakePaliQueries( s, queries):
"""
:type s: str
:type queries: List[List[int]]
:rtype: List[bool]
"""
def getnum(v):
num = 0
while v>0:
if v!=0:
v = v&(v-1)
num+=1
return num
n = len(s)
m = [0]*(n+1)
for i in range(n):
m[i+1] = m[i]^(1<<(ord(s[i])-ord('a')))
ans = []
for l,r,k in queries:
total = getnum(m[r+1]^m[l])
ans.append(total<=k*2+1)
return ans
6/16 1494. 并行课程 II
pre[x]用一个n位的二进制 来存储课程x的先修课 dp[i]表示上完i中课程最少需要的学期
def minNumberOfSemesters(n, relations, k):
"""
:type n: int
:type relations: List[List[int]]
:type k: int
:rtype: int
"""
if len(relations)==0:
return (n+k-1)//k
pre = [0]*n
for x,y in relations:
pre[y-1] |= 1<<(x-1)
u=(1< dp = [float("inf")]*(1< dp[0]=0 for i in range(1,1< c = u^i num = 0 for j,p in enumerate(pre): if i>>j&1 and p|c==c: num |=1< if num.bit_count() <=k: dp[i] =dp[i^num]+1 continue j=num while j: if j.bit_count()<=k: dp[i]=min(dp[i],dp[i^j]+1) j=(j-1)&num return dp[u] 6/17 2481. 分割圆的最少切割次数 n等分 最多n次切割 每个扇形角度为x=360/n 如果角度x为180因数 说明有两次切割能合并为一次 即n为偶数 def numberOfCuts(n): """ :type n: int :rtype: int """ if n==1: return 0 if n%2==0: return n//2 return n 6/18 1254. 统计封闭岛屿的数目 check遍历x,y相连的所有陆地 考虑过的将其标记为海水即可 边缘位置的陆地必定不满足条件 先将边缘全部考虑一遍 遍历内部未处理陆地 每次遇到一块陆地 +1 并将其相连陆地标记为海水 def closedIsland(grid): """ :type grid: List[List[int]] :rtype: int """ n,m=len(grid),len(grid[0]) step = [(1,0),(0,1),(-1,0),(0,-1)] def check(x,y): l = [(x,y)] while l: tmp=[] for i,j in l: for si,sj in step: ni,nj=i+si,j+sj if 0<=ni tmp.append((ni,nj)) grid[ni][nj]=1 l=tmp return for i in range(n): for j in [0,m-1]: if grid[i][j]==0: check(i,j) for j in range(m): for i in [0,n-1]: if grid[i][j]==0: check(i,j) ans = 0 for i in range(1,n-1): for j in range(1,m-1): if grid[i][j]==0: ans +=1 check(i,j) return ans 参考文章
您阅读本篇文章共花了：
发表评论