|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
2/21 838. 推多米诺
广搜BFS
使用l,r两个集合记录当前向左向右倾倒的位置
每一个向左的位置-1 如果位置上的骨牌状态为.则暂时标记可以倾倒
向右的一样
判断向左向右倾倒的位置是否有重复 如果有重复
这个位置将不会倾倒 去除这些位置
将可以倾倒的位置标记后 下一轮重新操作
def pushDominoes(dominoes):
"""
:type dominoes: str
:rtype: str
"""
dmn = list(dominoes)
l,r = set(),set()
for loc,c in enumerate(dmn):
if c=="R":
r.add(loc)
elif c=="L":
l.add(loc)
n = len(dominoes)
while l or r:
tmpl,tmpr = set(),set()
for loc in l:
tmp = loc-1
if tmp>=0 and dmn[tmp]==".":
tmpl.add(tmp)
for loc in r:
tmp = loc+1
if tmp<n and dmn[tmp]==".":
tmpr.add(tmp)
same = tmpl&tmpr
tmpl -= same
tmpr -= same
for loc in tmpl:
dmn[loc]="L"
for loc in tmpr:
dmn[loc]="R"
l = tmpl
r = tmpr
return "".join(dmn)
2/22 1994. 好子集的数目
判断每个数是否可以由不同的质数相乘 如果不行 直接排除
数值在30以内 质数已知2,3,5,7,11,13,17,19,23,29
统计每一个数出现的个数 如果一个数包含了多个相同的质数因子
则这个数必定不能在好子集内 为无用数4,8,9,12,16,18,20,24,25,27,28
对于一个好子集 加入若干个1 同样是好子集 所以不考虑1
如果1的个数是n 则最后结果为ans*(2^n)
统计每个数包含的质数因子
因为一共只有十个质数 使用十位二进制来标记几个质数已被使用 tag
遍历每一个有用数 可以选择加入或者不加入子集中 usenum表示已经加入子集的数
如果加入子集 需要判断当前有用数包含的质数是否已经被使用
如果遍历完所有 统计每个数出现的次数 将次数相乘即为这个子集可能的概率
最后与1的个数相乘即为最终结果
def numberOfGoodSubsets(nums):
"""
:type nums: List[int]
:rtype: int
"""
MOD = 10**9+7
useless = set([4,8,9,12,16,18,20,24,25,27,28])
primes=[2,3,5,7,11,13,17,19,23,29]
from collections import defaultdict
nummap = {}
for num in nums:
if num in useless:
continue
nummap[num] = nummap.get(num,0)+1
valueToprime = defaultdict(int)
for loc,prime in enumerate(primes):
for num in nummap.keys():
if num%prime==0:
valueToprime[num] |= (1<<loc)
li = list(valueToprime.keys())
global ans
ans = 0
def check(loc,usenum,tag):
global ans
if loc>=len(li):
if len(usenum)>0:
cur = 1
for num in usenum:
cur *= nummap[num]
ans =(ans+cur)%MOD
return
num = li[loc]
tmp = []
tmp.extend(usenum)
check(loc+1,tmp,tag)
primes = valueToprime[num]
if tag&primes==0:
tmp = []
tmp.extend(usenum)
tmp.append(num)
check(loc+1,tmp,tag|primes)
check(0,[],0)
if nummap.get(1,0)>0:
numone = (2**nummap[1])%MOD
ans = (ans*numone)%MOD
return ans
2/23 917. 仅仅反转字母
ischar判断字符是否是字母
双指针l,r找到是字母的位置 交换
def reverseOnlyLetters(s):
"""
:type s: str
:rtype: str
"""
def isChar(c):
return "a"<=c<="z" or "A"<=c<="Z"
li = list(s)
l,r = 0,len(li)-1
while l<r:
while l<len(li) and not isChar(li[l]):
l+=1
while r>=0 and not isChar(li[r]):
r-=1
if l<r:
li[l],li[r]=li[r],li[l]
l+=1
r-=1
return "".join(li)
2/24 1706. 球会落何处
模拟小球运动
小球从上至下运动 行数依次增加 col记录当前小球所在列
如果是1 则向右边移动 col+1
如果是-1 则向左边移动 col-1
此时如果碰到左右两侧 则卡住
或者此时的格子状态与之前不同遇到V型 同样卡住
tag判断小球是否顺利通过
最后记录小球的结果
def findBall(grid):
"""
:type grid: List[List[int]]
:rtype: List[int]
"""
m,n = len(grid),len(grid[0])
ans = [-1]*n
for j in range(n):
col = j
tag = True
for i in range(m):
mv = grid[i][col]
col +=mv
if col<0 or col>=n or grid[i][col]!=mv:
tag = False
break
if tag:
ans[j]=col
return ans
2/25 537. 复数乘法
(a+bi)*(c+di) = (ac-bd)+(ad+bc)i
def complexNumberMultiply(num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
l = num1.split("+")
a = int(l[0])
b = int(l[1][:-1])
l = num2.split("+")
c = int(l[0])
d = int(l[1][:-1])
x = a*c-b*d
y = a*d+b*c
ans = "%d+%di"%(x,y)
return ans
2/26 2016. 增量元素之间的最大差值
1.差分数组
问题转换为最大子序列和
2.从头遍历记录当前为止最小值 将当前值与最小值相减得到结果
def maximumDifference(nums):
"""
:type nums: List[int]
:rtype: int
"""
diff = []
for i in range(len(nums)-1):
diff.append(nums[i+1]-nums[i])
ans = 0
cur = 0
for i in range(len(diff)):
cur += diff[i]
ans = max(ans,cur)
if cur<0:
cur = 0
return -1 if ans ==0 else ans
def maximumDifference2(nums):
"""
:type nums: List[int]
:rtype: int
"""
minv = nums[0]
ans = 0
for i in range(1,len(nums)):
ans = max(ans,nums[i]-minv)
minv = min(nums[i],minv)
return -1 if ans ==0 else ans
2/27
|