记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

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]=valuedef get(self, key):""":type key: int:rtype: int"""return self.l[key] if self.l[key]!="" else -1def 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 = 0cnt = {}initial.sort()mem = {}for i in range(n):if i in mem:continuecur = {}l = [i]num = 1mem[i]=1cur[i]=1while l:tmp = []for node in l:for j,v in enumerate(graph[node]):if v==0 or j==node or j in mem:continuemem[j]=1cur[j]=1num+=1tmp.append(j)l=tmpfor node in cur:cnt[node] = numnet[node] = netnumnetnum+=1cur={}for node in initial:nodenet = net[node]cur[nodenet] = cur.get(nodenet,0)+1ans = initial[0]maxnum = 0for node in initial:if cur[net[node]]==1 and cnt[node]>maxnum:maxnum = cnt[node]ans = nodereturn 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=-1mincount= 99999if not initial:return 0initial.sort()def bfs(pos):query = initial[:]query.remove(pos)visit = {x:0 for x in range(N)}visit[pos]=1ret = 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]=1ret+=1return retfor i in initial:ans = bfs(i)if ans<mincount:mincount = ansres = ireturn 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]-=1if s[num]==0:del s[num]else:ans.append(num)s[num*2] = s.get(2*num,0)+1return 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 -1mem = {}def dfs(i,j):if (i,j)in mem:return mem[(i,j)]if j<0:return 0ans = (dfs(i,j-1)+dist[j]+speed-1)//speed*speedif i:ans = min(ans,dfs(i-1,j-1)+dist[j])mem[(i,j)]=ansreturn ansfor 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)returnfor i in range(loc,len(candidates)):c = candidates[i]tmp = l[:]if c>v:returntmp.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):returnif k==0 and v==0:ret.append(now)for i in range(len(l)):c = l[i]if c>v:returndfs(v-c,k-1,l[i+1:],now+[c])dfs(n,k,l,[])return ret

---