给出题目一的试题链接如下:
这一题依然还是翻译一下题目即可,基本不足要做什么额外的操作,不过在easy题目的范畴内这道题的逻辑多多少少算是复杂的了……
给出python代码实现如下:
class Solution:
def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: List[int], experience: List[int]) -> int:
exp, eng = 0, 0
for e, p in zip(energy, experience):
if initialEnergy <= e:
eng += e - initialEnergy + 1
initialEnergy = 1
else:
initialEnergy -= e
if initialExperience <= p:
exp += p - initialExperience + 1
initialExperience = p+1 + p
else:
initialExperience += p
return exp + eng
提交代码评测得到:耗时85ms,占用内存13.9MB。
给出题目二的试题链接如下:
这一题由于和原始数当中的顺序无关,因此我们只需要统计一下每一个数字出现的次数,然后成对取出后按照从大到小构成一个回文即可。
唯一需要注意的就是几个边界条件:
由此,我们即可得到最大的回文数字。
给出python代码实现如下:
class Solution:
def largestPalindromic(self, num: str) -> str:
cnt = Counter(num)
s = [0 for _ in range(10)]
unique = ""
for i in range(10):
s[i] = cnt[str(i)] // 2
if cnt[str(i)] % 2 == 1:
unique = str(i)
res = ""
for i in range(10):
if s[i] != 0:
res += str(i) * s[i]
if res.strip("0") != "":
res = res[::-1] + unique + res
elif unique != "":
res = unique
else:
res = "0"
return res
提交代码评测得到:耗时109ms,占用内存15.3MB。
给出题目三的试题链接如下:
这一题我的思路还是比较暴力的,就是先找出每一个元素的父节点,这样就能构成一个双向图。
然后就只需要使用一个dfs遍历就能够得到每一个节点关于start节点的距离了。
我们从中取出最大值就是我们的答案。
给出python代码实现如下:
class Solution:
def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
parents = {root: None}
u0 = None
def dfs(root):
nonlocal parents, u0
if root.val == start:
u0 = root
if root.left:
parents[root.left] = root
dfs(root.left)
if root.right:
parents[root.right] = root
dfs(root.right)
return
dfs(root)
dis = {u0: 0}
s = [u0]
res = 0
while s:
u = s.pop(0)
res = max(res, dis[u])
if u.left and u.left not in dis:
dis[u.left] = dis[u] + 1
s.append(u.left)
if u.right and u.right not in dis:
dis[u.right] = dis[u] + 1
s.append(u.right)
if parents[u] and parents[u] not in dis:
dis[parents[u]] = dis[u] + 1
s.append(parents[u])
return res
提交代码评测得到:耗时1214ms,占用内存144.2MB。
给出题目四的试题链接如下:
这题我傻逼了,居然没能自己搞定……
这题后来是参考了大佬的思路,发现异常简单,就是一个简单地堆排,因为k不会很大,所以只需要遍历一下几个最大的数就可以了。
给出python代码实现如下:
class Solution:
def kSum(self, nums: List[int], k: int) -> int:
pos = [x for x in nums if x >= 0]
_max = sum(pos) if len(pos) > 0 else 0
n = len(nums)
abn = sorted([abs(x) for x in nums])
s, q = 0, [(abn[0], 0)]
for i in range(k-1):
s, idx = heapq.heappop(q)
if idx + 1 < n:
heapq.heappush(q, (s - abn[idx] + abn[idx+1], idx+1))
heapq.heappush(q, (s + abn[idx+1], idx+1))
return _max - s
提交代码评测得到:耗时1075ms,占用内存29.4MB。