LeetCode笔记：Weekly Contest 263
LeetCode笔记：Weekly Contest 263
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题只要按照题意按照来做就行了，这里就不对实现多做赘述了。
2. 代码实现
给出python代码实现如下：
class Solution:
def areNumbersAscending(self, s: str) -> bool:
tokens = s.split()
pre = -1
for w in tokens:
if re.match("^\d+$", w):
x = int(w)
if x <= pre:
return False
pre = x
return True提交代码评测得到：耗时32ms，占用内存14.6MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题同样没啥好多说的，感觉就是按照题目意思实现就行了。
2. 代码实现
给出python代码实现如下：
class Bank:
def __init__(self, balance: List[int]):
self.balance = balance
self.n = len(self.balance)
def transfer(self, account1: int, account2: int, money: int) -> bool:
if account1 > self.n or account2 > self.n:
return False
if self.balance[account1-1] < money:
return False
self.balance[account1-1] -= money
self.balance[account2-1] += money
return True
def deposit(self, account: int, money: int) -> bool:
if account > self.n:
return False
self.balance[account-1] += money
return True
def withdraw(self, account: int, money: int) -> bool:
if account > self.n or self.balance[account-1] < money:
return False
self.balance[account-1] -= money
return True提交代码评测得到：耗时236ms，占用内存40.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的关键点在于说是或操作，因此事实上能够获得的最大值就是所有数的按位或操作的结果。
此时，我们事实上只需要实现求出可以达到的最大值，然后使用深度优先搜索看一下是否能够达到即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def countMaxOrSubsets(self, nums: List[int]) -> int:
n = len(nums)
tgt = 0
for x in nums:
tgt = x | tgt
res = 0
def dfs(idx, his):
nonlocal res
if his == tgt:
res += 2**(n-idx)
# print(res, n, his)
return
if idx >= n:
return
dfs(idx+1, his)
dfs(idx+1, his | nums[idx])
return
dfs(0, 0)
return res提交代码评测得到：耗时156ms，占用内存15.1MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题思路其实很简单，就是一个深度优先搜索，问题在于说由于可以允许路线上进行回撤，因此，如何对搜索路径进行剪枝成了一个巨大的问题。
这里，我们采用的方法是通过时间进行剪枝。显然，如果第一次到达了终点，此时目的地上只要经过两步行进就可以重新达到终点，此时能够间隔的时间也就是两次行进最多相差的时间，记作 δ t \delta t δt。
此时，对于任意一个节点，如果某条路线达到某一个节点的时间距离能够到大概位置的最短时间大于 δ t \delta t δt，那么这条路径必然不会是第二段时间的路径。
综上，我们就可以进行大幅的剪枝，然后得到我们最终的答案。
2. 代码实现
给出我们的python代码实现如下：
class Solution:
def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
delta = 0
for _ in range(2):
delta += time
delta = delta if (delta// change) % 2 else (delta // change + 1) * change
max_delta = change-1 + delta
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
costs = []
visited = [math.inf for _ in range(n+1)]
visited[1] = 0
s = [(0, 1, 0)]
while s:
t, u, pre = heapq.heappop(s)
arrive_time = t + time
next_time = arrive_time if (arrive_time // change) % 2 == 0 else (arrive_time // change + 1) * change
for v in graph[u]:
if v == n:
if costs == []:
costs.append(arrive_time)
elif arrive_time != costs[0]:
return arrive_time
if v == pre or next_time >= visited[v] + max_delta:
continue
heapq.heappush(s, (next_time, v, u))
visited[v] = min(visited[v], arrive_time)
t = costs[0]
t = t if (t // change) % 2 == 0 else (t // change + 1) * change
t = t + time
t = t if (t // change) % 2 == 0 else (t // change + 1) * change
return t + time提交代码评测得到：耗时2492ms，占用内存27.1MB。