Leetcode【789、1017】

问题描述：【Math】789. Escape The Ghosts

解题思路：

这道题是在二维平面上有一个人从原点出发，每次移动一个单位（东南西北）到目标坐标 target，平面上还有一些鬼 ghosts 每次也移动一个单位到目标坐标。如果人比所有鬼先到目标坐标，则表示逃离鬼，返回 True，否则返回 False。

这道题很简单，可以发现，无论是人还是鬼，到达目标坐标 target 都需要移动 abs(x - target[0]) + abs(y - target[1]) 步，其中 (x, y) 为人或者鬼的初始坐标。因此，只需要遍历一次 ghosts 数组，找到移动最少步数的鬼，然后和人的移动步数做对比。如果人的步数小于鬼的最少步数，返回 True；否则返回 False。时间复杂度为 O(N)，空间复杂度为 O(1)。

Python3 实现：

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

问题描述：【Math】1017. Convert to Base -2

解题思路：

这道题是给一个正整数 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)。

Python3 实现：

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]  # 所有余数反转就是结果