记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
4/15 706. 设计哈希映射
用数组代替
class MyHashMap(object):
def __init__(self):
self.l = [""]*(10**6+1)
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
self.l[key]=value
def get(self, key):
"""
:type key: int
:rtype: int
"""
return self.l[key] if self.l[key]!="" else -1
def remove(self, key):
"""
:type key: int
:rtype: None
"""
self.l[key]=""
4/16 924. 尽量减少恶意软件的传播
节点只有300个 枚举每一个连通网络中的节点个数
net[node]=x 记录节点node属于第x个网络
cnt[node]=num 记录节点node所属网络包含num个节点
将initial从小到大依次考虑
cur[net]记录当前net网络中恶意软件的数目
如果某一个网络中恶意软件数目超过1个
那么删除其中一个并不会对结果产生影响
只有当网络中有且仅有一个恶意软件时 删除它会减小感染数量
def minMalwareSpread(graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
n = len(graph)
net = {}
netnum = 0
cnt = {}
initial.sort()
mem = {}
for i in range(n):
if i in mem:
continue
cur = {}
l = [i]
num = 1
mem[i]=1
cur[i]=1
while l:
tmp = []
for node in l:
for j,v in enumerate(graph[node]):
if v==0 or j==node or j in mem:
continue
mem[j]=1
cur[j]=1
num+=1
tmp.append(j)
l=tmp
for node in cur:
cnt[node] = num
net[node] = netnum
netnum+=1
cur={}
for node in initial:
nodenet = net[node]
cur[nodenet] = cur.get(nodenet,0)+1
ans = initial[0]
maxnum = 0
for node in initial:
if cur[net[node]]==1 and cnt[node]>maxnum:
maxnum = cnt[node]
ans = node
return ans
4/17 928. 尽量减少恶意软件的传播 II
300个点 遍历每种情况
注意是从initial中去除一个 不是所有的点
直接遍历initial中所有点 使用bfs 计算每一种情况下的感染个数 取最小的位置
def minMalwareSpread(graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
N = len(graph)
link = {}
for i in range(N):
link[i] = [x for x in range(N) if graph[i][x]==1]
res=-1
mincount= 99999
if not initial:
return 0
initial.sort()
def bfs(pos):
query = initial[:]
query.remove(pos)
visit = {x:0 for x in range(N)}
visit[pos]=1
ret = len(query)
while query:
x = query.pop(0)
for next in link[x]:
if visit[next]==0 and graph[x][next]==1:
query.append(next)
visit[next]=1
ret+=1
return ret
for i in initial:
ans = bfs(i)
if ans<mincount:
mincount = ans
res = i
return res
4/18 2007. 从双倍数组中还原原数组
从小到大考虑
s中存放需要出现的双倍数值
如果当前num没有在s中 那么说明属于原数组
将双倍数值加入到s中
def findOriginalArray(changed):
"""
:type changed: List[int]
:rtype: List[int]
"""
n = len(changed)
if n%2==1:
return []
changed.sort()
s = {}
ans = []
for num in changed:
if s.get(num,0)>0:
s[num]-=1
if s[num]==0:
del s[num]
else:
ans.append(num)
s[num*2] = s.get(2*num,0)+1
return ans if len(ans)==n//2 else []
4/19 1883. 准时抵达会议现场的最小跳过休息次数
如果每次都跳过休息还是无法抵达 则说明不能到达
定义dfs(i,j) 最多跳i次情况下，从0到j的最小时间
分跳过和不跳过两个情况
如果不跳过则为前一个的最小时间加上当前需要时间 向上取整
如果跳过 为上一个位置最小时间加上当前时间
两种情况取最小值
def minSkips(dist, speed, hoursBefore):
"""
:type dist: List[int]
:type speed: int
:type hoursBefore: int
:rtype: int
"""
n=len(dist)
if sum(dist)>speed*hoursBefore:
return -1
mem = {}
def dfs(i,j):
if (i,j)in mem:
return mem[(i,j)]
if j<0:
return 0
ans = (dfs(i,j-1)+dist[j]+speed-1)//speed*speed
if i:
ans = min(ans,dfs(i-1,j-1)+dist[j])
mem[(i,j)]=ans
return ans
for i in range(n+1):
if dfs(i,n-2)+dist[-1]<=speed*hoursBefore:
return i
4/20 39. 组合总和
递归
按顺序排序 记录使用过的位置loc 防止继续取到前面的数造成重复
def combinationSum(candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = sorted(candidates)
ret = []
def dfs(v,loc,l):
if v==0:
ret.append(l)
return
for i in range(loc,len(candidates)):
c = candidates[i]
tmp = l[:]
if c>v:
return
tmp.append(c)
dfs(v-c,i,tmp)
dfs(target,0,[])
return ret
4/21 216. 组合总和 III
从小打大考虑
l记录当前可用数组
now记录当前已经选中的数
v为还需要的数值
k为需要挑选的数值个数
选中一个数c之后
接下来考虑k-1个数凑成v-c
def combinationSum3(k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
l = [i for i in range(1,10)]
ret =[]
def dfs(v,k,l,now):
if (k<=0 and v>0) or (k>0 and v<=0):
return
if k==0 and v==0:
ret.append(now)
for i in range(len(l)):
c = l[i]
if c>v:
return
dfs(v-c,k-1,l[i+1:],now+[c])
dfs(n,k,l,[])
return ret