|
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
12/19 1971. 寻找图中是否存在路径
way[i]记录节点i可以走到的所有节点数
广搜查找是否能够从source到destination
def validPath(n, edges, source, destination):
"""
:type n: int
:type edges: List[List[int]]
:type source: int
:type destination: int
:rtype: bool
"""
if source==destination:
return True
from collections import defaultdict
way = defaultdict(list)
for x,y in edges:
way[x].append(y)
way[y].append(x)
l = [source]
mem = set()
while l:
tmp = []
for node in l:
if node in mem:
continue
mem.add(node)
for nt in way[node]:
if nt == destination:
return True
if nt not in mem:
tmp.append(nt)
l = tmp
return False
12/20 1760. 袋子里最少数目的球
二分判断 每个袋子里最多为x时需要的操作次数
如果num<=x 则不需要
x<num<=2x 则需要1次 以此类推
如果此时操作次数op<=maxOperations 则可以将x减小
def minimumSize(nums, maxOperations):
"""
:type nums: List[int]
:type maxOperations: int
:rtype: int
"""
l,r = 1,max(nums)
ans = 0
while l<=r:
x = (l+r)//2
ops = sum((num-1)//x for num in nums)
if ops<=maxOperations:
ans = x
r = x-1
else:
l = x+1
return ans
12/21 1753. 移除石子的最大得分
假设a<=b<=c
如果a+b<=c 那么答案就是a+b个
如果a+b>c
首先取b,c 使得a与b相等
接着依次取a,c;b,c 取完c 此时得到c分
再取a,b 得到a-(c-(b-a))//2分
def maximumScore(a, b, c):
"""
:type a: int
:type b: int
:type c: int
:rtype: int
"""
l = [a,b,c]
l.sort()
a,b,c = l[0],l[1],l[2]
if a+b<=c:
return a+b
return c+a-(c-(b-a)+1)//2
12/22 1799. N 次操作后的最大分数和
gcd辗转相除获得最大公约数
g[i][j]用来存储nums[i],nums[j]的最大公约数
一共有n个数 用一个长度为n的二进制表示 数组状态
将使用的位置设置为1 一共有2^n-1种状态
一个合理的状态必定是拥有偶数个1
从小到大遍历所有状态
def maxScore(nums):
"""
:type nums: List[int]
:rtype: int
"""
def gcd(a,b):
if b==0:
return a
return gcd(b,a%b)
def getone(a):
ans = 0
while a:
ans += a&1
a>>=1
return ans
n = len(nums)
g = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(i+1,n):
g[i][j] = gcd(nums[i],nums[j])
f = [0]*(1<<n)
for k in range(1<<n):
cnt = getone(k)
if cnt%2==0:
for i in range(n):
if k>>i &1:
for j in range(i+1,n):
if k>>j & 1:
f[k] = max(f[k],f[k^(1<<i)^(1<<j)]+g[i][j]*(cnt//2))
return f[-1]
12/23 2011. 执行操作后的变量值
遍历 检查第2位可以判断是加还是减
def finalValueAfterOperations(operations):
"""
:type operations: List[str]
:rtype: int
"""
ans = 0
for op in operations:
if op[1]=="+":
ans+=1
else:
ans-=1
return ans
12/24 1754. 构造字典序最大的合并字符串
对于word1[i] word1[j]
如果word1[i:]>word1[j:] 则将word1[i]先放入
def largestMerge(word1, word2):
"""
:type word1: str
:type word2: str
:rtype: str
"""
l=[]
n,m=len(word1),len(word2)
i,j=0,0
while i<n or j<m:
if i<n and word1[i:]>word2[j:]:
l.append(word1[i])
i+=1
else:
l.append(word2[j])
j+=1
return ''.join(l)
12/25 1739. 放置盒子
对第i层 可以增加i个
盒子上限为1+（1+2)+(1+2+3)+…+i(i+2)/2 = i(i+1)(i+2)/6
基础之上在增加j个
def minimumBoxes(n):
"""
:type n: int
:rtype: int
"""
cur = i = j = 1
while n>cur:
n -= cur
i += 1
cur += i
cur = 1
while n>cur:
n -= cur
j += 1
cur += 1
return (i-1)*i//2 + j
|