这道题是在二维平面上有一个人从原点出发,每次移动一个单位(东南西北)到目标坐标 target,平面上还有一些鬼 ghosts 每次也移动一个单位到目标坐标。如果人比所有鬼先到目标坐标,则表示逃离鬼,返回 True,否则返回 False。
这道题很简单,可以发现,无论是人还是鬼,到达目标坐标 target 都需要移动 abs(x - target[0]) + abs(y - target[1])
步,其中 (x, y) 为人或者鬼的初始坐标。因此,只需要遍历一次 ghosts 数组,找到移动最少步数的鬼,然后和人的移动步数做对比。如果人的步数小于鬼的最少步数,返回 True;否则返回 False。时间复杂度为 O(N),空间复杂度为 O(1)。
class Solution:
def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
ghosts_min = float("inf") # 鬼离目标坐标走的最少步数
for ghost in ghosts:
ghosts_min = min(ghosts_min, abs(ghost[0]-target[0]) + abs(ghost[1]-target[1]))
if abs(target[0]) + abs(target[1]) < ghosts_min: # 人走的步数小于鬼的最少步数
return True
else:
return False
这道题是给一个正整数 N,返回由若干 "0" 和 "1" 组成的字符串,该字符串为 N 的负二进制(base -2)表示。
我们已经知道将十进制数转化为二进制数的做法:将数不断除以 2,然后记录余数,最后将余数反转。如果对于转为负二进制采用同样的思路,余数会出现负数(-1),怎么办?
对于 a / b = c ... d
,有 a = b * c + d
;转化为负二进制,需要保证余数是正数并且是最小的那个,那么可以假设 a / (-b) = c ... d
,那么 a = (-b) * c + d
;如果 d >= 0
(对于这道题只有 0 这种可能),则不用管,继续执行除以 -b 操作;如果 d < 0
(对于这道题只有 -1 这种可能),可以将上式变为 a = (-b) * (c + 1) + (d + b)
,这时 d + b
是正数(d + b
只有 1 这种可能),而且 b + d
肯定是最小的那个正数(d 只加了一次 b),然后继续执行除以 -b 操作。当 N 为 0 时,我们将每次记录的余数进行反转,就是答案。
因为每次都执行除以 -2 操作,则时间复杂度为 O(logN)。
class Solution:
def baseNeg2(self, N: int) -> str:
if N == 0:
return "0"
ans = ""
while N != 0:
N, mod = divmod(N, -2)
if mod < 0: # 余数为-1,则商加1,余数加除数的绝对值
N, mod = N + 1, mod + 2
ans += str(mod)
return ans[::-1] # 所有余数反转就是结果