记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 4/22 377. 组合总和 Ⅳ
- 4/23 1052. 爱生气的书店老板
- 4/24 2385. 感染二叉树需要的总时间
- 4/25 2739. 总行驶距离
- 4/26 1146. 快照数组
- 4/27 2639. 查询网格图中每一列的宽度
- 4/28 1017. 负二进制转换
4/22 377. 组合总和 Ⅳ
mem[x]记录数字x拥有的组合个数
def combinationSum4(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
mem={}
mem[0]=1
def check(num):
if num in mem:
return mem[num]
ans = 0
for v in nums:
if v<=num:
ans += check(num-v)
mem[num]=ans
return ans
return check(target)
4/23 1052. 爱生气的书店老板
先将不生气的都相加 并设置那时顾客为0
题目变为 顾客列表 连续X分钟达到最多
def maxSatisfied(customers, grumpy,minutes):
"""
:type customers: List[int]
:type grumpy: List[int]
:type X: int
:rtype: int
"""
ret = 0
left = 0
right = 0
for i in range(len(customers)):
if grumpy[i]==0:
ret += customers[i]
customers[i] = 0
tmp = ret
while right<len(customers):
tmp += customers[right]
if right-left+1>minutes:
tmp-=customers[left]
left+=1
right+=1
ret = max(ret,tmp)
return ret
4/24 2385. 感染二叉树需要的总时间
BFS将数转化为图
再根据图来搜索最远距离
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def amountOfTime1(root, start):
"""
:type root: Optional[TreeNode]
:type start: int
:rtype: int
"""
from collections import defaultdict
m = defaultdict(list)
l=[root]
while l:
tmp = []
for node in l:
if node.left:
m[node.val].append(node.left.val)
m[node.left.val].append(node.val)
tmp.append(node.left)
if node.right:
m[node.val].append(node.right.val)
m[node.right.val].append(node.val)
tmp.append(node.right)
l=tmp
l=[start]
ans = 0
mem = set()
while l:
tmp = []
for cur in l:
mem.add(cur)
for v in m[cur]:
if v not in mem:
tmp.append(v)
ans+=1
return ans-1
4/25 2739. 总行驶距离
主油箱的油 只要大于4l即可从副油箱取一升油 凑成5l
副油箱能够用掉的油为 min((mainTank-1)//4,additionalTank)
def distanceTraveled(mainTank, additionalTank):
"""
:type mainTank: int
:type additionalTank: int
:rtype: int
"""
return (mainTank+min((mainTank-1)//4,additionalTank))*10
4/26 1146. 快照数组
快照时无需记录整个数组
只要记录与前一份快照之间的修改
使用history[x]记录x位置元素的修改记录(snapid,value)
查询一个ind位置某个id的数据时
只要在history[ind]中二分找到快照编号小于id的最后一条修改记录值即可
class SnapshotArray(object):
def __init__(self, length):
"""
:type length: int
"""
from collections import defaultdict
self.curid = 0
self.history = defaultdict(list)
def set(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
self.history[index].append((self.curid,val))
def snap(self):
"""
:rtype: int
"""
self.curid +=1
return self.curid-1
def get(self, index, snap_id):
"""
:type index: int
:type snap_id: int
:rtype: int
"""
import bisect
j = bisect.bisect_left(self.history[index], (snap_id+1,))-1
return self.history[index][j][1] if j>=0 else 0
4/27 2639. 查询网格图中每一列的宽度
对每一列中的每个数进行判断其宽度
def findColumnWidth(grid):
"""
:type grid: List[List[int]]
:rtype: List[int]
"""
m,n = len(grid),len(grid[0])
ans = [0]*n
def check(num):
cur = 0
if num<=0:
cur = 1
num = -num
while num>0:
num = num//10
cur+=1
return cur
for j in range(n):
cur = 0
for i in range(m):
cur = max(cur,check(grid[i][j]))
ans[j]=cur
return ans
4/28 1017. 负二进制转换
先转换为正常二进制
对于奇数位 0,2,4,8 不会产生影响
对于偶数位 1,3,5 需要负二进制增加后一位相加实现
例如 2^3=8 需要(-2)4+(-2)3=16-8=8
def baseNeg2(n):
"""
:type n: int
:rtype: str
"""
if n==0:
return "0"
l = [0]*40
tmp = n
cur = 0
while tmp>0:
l[cur]=tmp%2
tmp//=2
cur+=1
cur = 0
while cur<35:
l[cur+1]+=l[cur]//2
l[cur] = l[cur]%2
if cur%2==0:
cur +=1
continue
if l[cur]==1:
l[cur+1]+=1
cur+=1
for i in range(29,-1,-1):
if l[i]==1:
cur = i
break
return "".join([str(l[loc]) for loc in range(cur,-1,-1)])
