刀大师面经题时间间隔

nexttomexxd

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 nexttomexxd 于 2022-2-19 16:28 编辑

input 是两个 string,e.g. “mon 11:00 am”,“mon 11:15 am”,返回 a list of strings[“11100”,“111105”,“111110”,“111115”],第一个 digit 是 day,mon -> 1,tue -> 2,
后面是四位时间,24 小时制,每两个时间中间间隔五分钟。需要 validate input,如果
invalid,返回空。
input 可能有 12 小时制,也可能有 24 小时制(没有 am,pm)。时间可能有 leading
zeros,可能不在范围内。开始时间不保证早于结束时间。如果 input 时间不是 5 的倍数,
要四舍五入到最近的点

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
from typing import List
class Time:
days_to_num = {'mon': 0, 'tue': 1, 'wed': 2, 'thur':3, 'fri': 4, 'sat': 5, 'sun': 6}
nums_to_day = {v: k for k, v in days_to_num.items()}
def __init__(self, timec: List[int]):
self.timec = timec
@classmethod
def from_s(cls, s: str):
timec = cls.parse_time(s)
return cls(timec)
def __add__(self, m: int) -> List[int]:
day, hh, mm, tf = self.timec
mm_r = (mm + m) // 60
mm_m = (mm + m) % 60
hh_r = (hh + mm_r) // 24
hh_m = (hh + mm_r) % 24
day_r = (day + hh_r) // 7
day_m = (day + hh_r) % 7
day, hh, mm, tf = day_m, hh_m, mm_m, tf
return Time([day, hh, mm, tf])
def __eq__(self, other) -> bool:
return self.timec == other.timec
def __gt__(self, other) -> bool:
gt = all(i >= j for i, j in zip(self.timec[:-1], other.timec[:-1]))
g = any(i > j for i, j in zip(self.timec[:-1], other.timec[:-1]))
return gt and g
def __ge__(self, other) -> bool:
return self.__gt__(other) or self.__eq__(other)
@classmethod
def parse_time(cls, s: str) -> List[int]:
splits = s.split()
day = splits[0].lower()
hh, mm = map(int, splits[1].split(':'))
if len(splits) == 2:
return [cls.days_to_num[day], hh, mm, 1]
if len(splits) == 3:
am_pm = splits[2]
if am_pm.lower() == 'am' or hh == '12':
return [Time.days_to_num[day], hh, mm, 0]
else:
return [Time.days_to_num[day], hh + 12, mm, 0]
return 1
def __str__(self) -> str:
day, hh, mm, tf = self.timec
if tf == 0:
if hh >= 12:
if hh > 12:
hh = hh % 12
return f"{Time.nums_to_day[day]} {hh//10}{hh%10}:{mm//10}{mm%10} pm"
return f"{Time.nums_to_day[day]} {hh//10}{hh%10}:{mm//10}{mm%10} am"
return f"{Time.nums_to_day[day]} {hh//10}{hh%10}:{mm//10}{mm%10}"
def get_time_interval(s1: Time, s2: Time) -> List[str]:
s1 = Time.from_s(s1)
s2 = Time.from_s(s2)
if s1.timec[2] % 10 < 5:
s1.timec[2] = s1.timec[2] - s1.timec[2] % 4
if s1.timec[2] % 10 > 5:
s1 = s1.add(10-(s1.timec[2] % 10))
if s1 > s2: return list()
stop = False
result = list()
while not stop:
if s1.timec[2] % 5 == 0:
result.append(str(s1))
s1 = s1+1
if s2 > s1:
stop = True
return result
print(get_time_interval("mon 10:00 am", "mon 11:00 am"))
print(get_time_interval("mon 10:00 pm", "tue 01:00 am"))
print(get_time_interval("mon 10:00 pm", "mon 10:00 pm"))
print(get_time_interval("mon 10:00", "tue 00:00"))
print(get_time_interval("mon 10:00", "mon 00:00"))

复制代码

补充内容 (2022-02-22 02:40 +8:00):
汇总刀大师面经python手撕解法，求加米

nexttomexxd

1. Given array of pick up and delivery options, make sure that the array is valid.
Example 1:
Input: ['P1', 'D1']
Output: True
Explanation: P1 comes before D1
Example 2:
Input: ['P2', 'D1', 'P1', 'D2']
Output: False
Explanation: D1 comes before P1, but it should come after.
Note to future solver: Make sure you cover case like P11 and P99 etc. where number followed
by P and D is in double digits.
My thoughts: Was able to solve this, got stuck at the P11 test case, they hide the test cases
from you, so it's difficult to know/ think of all edge cases. Was able to produce working output.

from typing import List, Tuple
def all_valid(n: int) -> List[str]:
result = list()
visited = [0] * n
def dfs(path, i):
if len(path) == 2*n:
result.append(path.copy())
return
# pick i
if i < n:
path.append('P' + str(i))
dfs(path, i+1)
# or deli one
path.pop(-1)
for j in range(n):
if visited[j] == 0:
path.append(f"D{j}")
visited[j] = 1
dfs(path, i)
visited[j] = 0
path.pop(-1)
dfs([], 0)
return result
print(all_valid(2))

复制代码

nexttomexxd

给一张 city 的地图和一个列表 locations,问从 locations 里的每个位置到 D 的最短步数,
地图中 X 为 blocked 的部分。locations 的长度远大于 D 的数量。
类似 leetcode 286
inputs:
char[][] city = {
// 0 1 2 3 4 5 6 7 8
{'X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'}, //0
{'X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'}, //1

{' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '}, //2
{' ', ' ', ' ', 'D', ' ', 'X', ' ', ' ', ' '}, //3
{' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'}, //4
{' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X'} //5
}
int[][] locations =
{
{200, 200},
{1, 4},
{0, 3},
{5, 6},
{5, 8}
}
outputs:
int[]
[-1, 2, 0, 8, -1]

def find_dis(mapping, locations, d):
c, r = len(mapping[0]), len(mapping)
results = [-2] * len(locations)
target = dict()
for i, (ir, ic) in enumerate(locations):
if (not 0 <= ir < r) or (not 0<= ic < c):
results[i] = -1
elif mapping[ir][ic] == 'X':
results[i] = -1
elif mapping[ir][ic] == 'D':
results[i] = 0
else:
target[(ir, ic)] = i
q = list()
dist = dict()
for i in range(len(d)):
q.append((d[i][0], d[i][1]))
dist[(d[i][0], d[i][1])] = 0
finished = False
while q and (not finished):
print(q)
print(dist)
print(results)
size = len(q)
for _ in range(size):
cur = q.pop(0)
if cur in target:
results[target[cur]] = dist[cur]
if all([i != -2 for i in results]):
finished = True
for n in get_neib(cur, r, c):
if (n not in dist) and (mapping[n[0]][n[1]] not in ('X', 'D')):
q.append(n)
dist[n] = dist[cur] + 1
return results
def get_neib(cur, R, C):
r, c = cur
dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (0 <= nr < R) and (0 <= nc < C):
yield (nr, nc)
mapping = [['X', 'D', '', ''],
['', 'X', '', 'D'],
['', '', '', 'X'],
['', 'X', 'D', 'X']]
locations = [[1, 0], [0, 3], [10, 9], [0, 1]]
d = [[0, 1], [1, 3], [3, 2]]
print(find_dis(mapping, locations, d))

复制代码

nexttomexxd

给一张 city 的地图和一个列表 locations,问从 locations 里的每个位置到 D 的最短步数,
地图中 X 为 blocked 的部分。locations 的长度远大于 D 的数量。
类似 leetcode 286
inputs:
char[][] city = {
// 0 1 2 3 4 5 6 7 8
{'X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'}, //0
{'X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'}, //1

{' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '}, //2
{' ', ' ', ' ', 'D', ' ', 'X', ' ', ' ', ' '}, //3
{' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'}, //4
{' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X'} //5
}
int[][] locations =
{
{200, 200},
{1, 4},
{0, 3},
{5, 6},
{5, 8}
}
outputs:
int[]
[-1, 2, 0, 8, -1]

def find_dis(mapping, locations, d):
c, r = len(mapping[0]), len(mapping)
results = [-2] * len(locations)
target = dict()
for i, (ir, ic) in enumerate(locations):
if (not 0 <= ir < r) or (not 0<= ic < c):
results[i] = -1
elif mapping[ir][ic] == 'X':
results[i] = -1
elif mapping[ir][ic] == 'D':
results[i] = 0
else:
target[(ir, ic)] = i
q = list()
dist = dict()
for i in range(len(d)):
q.append((d[i][0], d[i][1]))
dist[(d[i][0], d[i][1])] = 0
finished = False
while q and (not finished):
print(q)
print(dist)
print(results)
size = len(q)
for _ in range(size):
cur = q.pop(0)
if cur in target:
results[target[cur]] = dist[cur]
if all([i != -2 for i in results]):
finished = True
for n in get_neib(cur, r, c):
if (n not in dist) and (mapping[n[0]][n[1]] not in ('X', 'D')):
q.append(n)
dist[n] = dist[cur] + 1
return results
def get_neib(cur, R, C):
r, c = cur
dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (0 <= nr < R) and (0 <= nc < C):
yield (nr, nc)
mapping = [['X', 'D', '', ''],
['', 'X', '', 'D'],
['', '', '', 'X'],
['', 'X', 'D', 'X']]
locations = [[1, 0], [0, 3], [10, 9], [0, 1]]
d = [[0, 1], [1, 3], [3, 2]]
print(find_dis(mapping, locations, d))

复制代码

nexttomexxd

Given an integer matrix, find the length of the longest path that have same values. The matrix
has no boundary limits. (like, Google Maps - see edit for context)
From each cell, you can either move to two directions: horizontal or vertical. You may NOT
move diagonally or move outside of the boundary.
nums = [
[1,1],
[5,5],
[5,5]
]
Return 4 ( Four 5's).
Follow Up:

• follow up 是如果 matrix 是 no boundaries 怎么解

def find_longest(m):
def get_neib(r, c):
dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (0 <= nr < len(m)) and (0 <= nc < len(m[0])):
yield (nr, nc)
def dfs(r, c):
max_p = 0
for nr, nc in get_neib(r, c):
if (nr, nc) not in visited:
if m[r][c] == m[nr][nc]:
visited.add((nr , nc))
pathl = dfs(nr , nc)
max_p = max(pathl, max_p)
visited.remove((nr , nc))
return max_p + 1
result = 1
r, c = len(m), len(m[0])
visited = set()
for ir in range(r):
for ic in range(c):
visited.add((ir, ic))
result = max(result, dfs(ir, ic))
visited.remove((ir, ic))
return result
m = [[0,0,0,0,0],
[1,1,1,1,1],
[1,1,1,0,0]]
print(find_longest(m))

复制代码

[高频题] 刀大师面经题时间间隔

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块