|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
8/16 526. Beautiful Arrangement 优美的排列
回溯
store存储位置i可以放置的数 包括i的因数 以及i的倍数<=n
s记录当前可用的数字
每一个位置遍历所有可放置的数 是否可用 可用则继续下一个位置
def countArrangement(n):
"""
:type n: int
:rtype: int
"""
def factors(num):
ret = []
for i in range(1,num//2+1):
if num%i==0:
ret.append(i)
return ret
store = {}
for i in range(1,n+1):
num = factors(i)
tmp = i
while tmp<=n:
num.append(tmp)
tmp+=i
store[i] = num
s = set(list(range(1,n+1)))
def find(loc):
if loc==n+1:
return 1
l = store[loc]
ans = 0
for num in l:
if num in s:
s.remove(num)
ans += find(loc+1)
s.add(num)
return ans
return find(1)
8/17 551. Student Attendance Record I 学生出勤记录 I
numA 记录缺勤次数
conL 记录连续迟到天数
def checkRecord(s):
"""
:type s: str
:rtype: bool
"""
numA = 0
conL = 0
for c in s:
if c=="L":
conL +=1
if conL>2:
return False
else:
conL = 0
if c=="A":
numA +=1
if numA==2:
return False
return True
8/18 552. Student Attendance Record II 学生出勤记录 II
1.num 当前天数
numa 缺勤天数
prel 连续迟到天数
mem记录已考虑状况
递归太深 失败
2.状态转移 dp
缺勤最多只能1次
所以可以分为a,p 分别代表缺勤一次 未缺勤
连续迟到最多可以2次 所以分为0,1,2 代表连续迟到天数
所以一共有六种状态a0,a1,a2,p0,p1,p2
p0可以由p0,p1,p2 +P转变
p1只能由p0 +L转变
p2只能由p1 +L转变
a0可以由p0,p1,p2 +A 或者a0,a1,a2 +P转变
a1只能由a0 +L转变
a2只能由a1 +L转变
循环n次将六种状态累加得到答案
def checkRecord(n):
"""
:type n: int
:rtype: int
"""
MOD=10**9+7
mem = {}
def find(num,numa,prel):
if (num,numa,prel) in mem:
return mem[(num,numa,prel)]
ans = 0
if num==n:
mem[(num,numa,prel)] = 1
return 1
if numa<1:
ans += find(num+1,numa+1,0)%MOD
if prel<2:
ans += find(num+1,numa,prel+1)%MOD
ans += find(num+1,numa,0)%MOD
ans = ans%MOD
mem[(num,numa,prel)] = ans
return ans
return find(0,0,0)
def checkRecord2(n):
"""
:type n: int
:rtype: int
"""
MOD=10**9+7
p0,p1,p2 = 1,0,0
a0,a1,a2 = 0,0,0
for i in range(n):
t0,t1,t2 = p0,p1,p2
p0,p1,p2 = (p0+p1+p2)%MOD,p0,p1
a0,a1,a2 = (a0+a1+a2+t0+t1+t2)%MOD,a0,a1
ans = (p0+p1+p2+a0+a1+a2)%MOD
return ans
8/19 345. Reverse Vowels of a String 反转字符串中的元音字母
前后双指针 遇到元音字母停下 两处交换
def reverseVowels(s):
"""
:type s: str
:rtype: str
"""
vowel=set(list("aoeiuAOEIU"))
i,j=0,len(s)-1
l = list(s)
while i<j:
while l[i] not in vowel:
i+=1
if i==j:
return ''.join(l)
while l[j] not in vowel:
j-=1
if i==j:
return ''.join(l)
l[i],l[j]=l[j],l[i]
i+=1
j-=1
return ''.join(l)
8/20 541. Reverse String II 反转字符串 II
l,r代表需要反正的字符段左右
l需要小于s的长度 r为l+k-1和长度n-1之间的较小值
下一个l为之前r+k+1
def reverseStr(s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
n = len(s)
ls= list(s)
l = 0
while l<n:
r = min(l+k-1,n-1)
tmp = r
while l<r:
ls[l],ls[r]=ls[r],ls[l]
l+=1
r-=1
l = tmp+k+1
return ''.join(ls)
8/21 443. String Compression 压缩字符串
pre记录前一个字符 num记录前一个字符个数
如果字符变换 则将pre加入答案
如果num>1 则将num变为list的字符串加入
def compress(chars):
"""
:type chars: List[str]
:rtype: int
"""
pre = ""
num = 0
ans = []
for c in chars:
if pre=="":
pre = c
num = 1
elif pre ==c:
num+=1
else:
ans.append(pre)
if num>1:
numl = list(str(num))
ans.extend(numl)
pre = c
num = 1
ans.append(pre)
if num>1:
numl = list(str(num))
ans.extend(numl)
ret = len(ans)
chars[:ret] = ans[:]
return ret
8/22 789. Escape The Ghosts 逃脱阻碍者
只要有一个阻碍者在我之前到达目的地 那么必定无法成功逃脱
def escapeGhosts(ghosts, target):
"""
:type ghosts: List[List[int]]
:type target: List[int]
:rtype: bool
"""
num = abs(target[0])+abs(target[1])
for x,y in ghosts:
tmp = abs(x-target[0])+abs(y-target[1])
if tmp<=num:
return False
return True
|