Grind75第12天 | 67.二进制求和、937.最接近原点的k个点、295.数据流的中位数

67.二进制求和

题目链接：https://leetcode.com/problems/add-binary/

解法：

末尾对齐，从右到左，逐位相加，逢二进一。

使用一个变量?carry?表示上一个位置的进位，初始值为?0。

对于当前位置的两个数字x和y，加和后的carry = carry? + x + y，然后更新当前位置的数字为 carry % 2，下一步的carry = carry // 2 。把当前位置的数字添加到结果列表中。

对于较短的二进制数字符串，如果遍历到某位置时值为空了，那么就使用0来替代（补0）。

遍历结束，如果carry=1，那么添加1到结果列表中。

最后的结果需要进行翻转。

边界条件：无

时间复杂度：O(n)，n=max{∣a∣,∣b∣}

空间复杂度：O(1)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # 从字符串的末尾开始遍历
        idx1 = len(a) - 1
        idx2 = len(b) - 1
        # 用于进位
        carry = 0

        # 用于记录每个位置的值，最后要翻转
        res = []
        while idx1 >=0 or idx2 >= 0:

            # 获取当前的数字，如果为空则取0
            if idx1 < 0:
                x = 0
            else:
                x = ord(a[idx1]) - ord('0')
                idx1 -= 1

            if idx2 < 0:
                y = 0
            else:
                y = ord(b[idx2]) - ord('0')
                idx2 -= 1

            # 计算当前位置的值
            carry = carry + x + y
            res.append(str(carry % 2))
            carry = carry // 2
        
        if carry > 0:
            res.append('1')

        return ''.join(res)[::-1]

937.最接近原点的k个点

题目链接：https://leetcode.com/problems/k-closest-points-to-origin

解法：

这个题使用大根堆。

大根堆：将列表中的前k个元素加入到大根堆中。这个堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。堆顶（根节点）是这k个元素中最大的。所以大指的是顶点元素是堆中的最大值。

为啥使用大根堆而不是小根堆？因为从第k+1元素开始，判断是否小于顶点，如果小于，则弹出顶点，插入当前的元素，这样就保证一直维持k个最小的元素。

Python中的 heapq 模块提供的是小根堆功能，可以通过对元素取反来使用大根堆。

这个题主要的难点是heapq这个模块的使用语法：（1）元素是一个元素，value在前，key在后，根据value排序；（2）默认是小根堆，需要对value取反来实现大根堆。

这个题还有一种时间复杂度为O(n)的快排变形解法，这次先不管了。

边界条件：无

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # 对前k个元素初始化大根堆
        q = [(- x**2 - y**2, i) for i, (x, y) in enumerate(points[:k])]
        heapq.heapify(q)

        for i in range(k, len(points)):
            x, y = points[i]
            dist = - x**2 - y**2
            heapq.heappush(q, (dist, i))
            # push后别忘记pop
            heapq.heappop(q)

        res = [points[i] for _, i in q]
        return res

295.数据流的中位数

题目链接：https://leetcode.com/problems/find-median-from-data-stream

解法：

这道题还是比较有技巧性，但很优雅的感觉。

建立一个?小顶堆?A?和?大顶堆?B，各保存列表的一半元素，如果列表为奇数个，那么A中多保存一个元素。

A保存较大的一半，顶点是其中最小的；B保存较小的一半，顶点是其中最大的。那么如果列表为奇数个，中位数就是A的顶点；如果是偶数个，中位数就是A和B顶点的平均值。

添加元素时，比较有技巧性。

还需要注意的是，如果python实现，那么大根推是把数值取反，那么不仅插入时取反，在pop后加以使用时也要取反：（1）以上addNum的两种情况都需要把堆顶元素取反后再插入；（2）最后求中位数时，如果列表中有偶数个，那么取B顶点时也要取反，用于求平均。

参考题解：大顶推+小顶堆

边界条件：

时间复杂度：添加为O(logn)，查找为O(1)

空间复杂度：O(n)

class MedianFinder:

    def __init__(self):
        self.A = [] # 小顶堆，保存较大的一半
        self.B = [] # 大顶堆，保存较小的一半

    def addNum(self, num: int) -> None:
        # 不相等，则A中多了一个元素，那么需要加入B中
        # 先添加到A中，再把A的顶点推入B中
        if len(self.A) != len(self.B):
            heappush(self.A, num)
            heappush(self.B, -heappop(self.A))
        else:
            # B为大顶堆，所以添加时取反值
            heappush(self.B, -num)
            heappush(self.A, -heappop(self.B))

    def findMedian(self) -> float:
        if len(self.A) == len(self.B):
            # 注意是减去B的顶点，实际为加
            return (self.A[0] - self.B[0]) / 2
        else:
            return self.A[0]



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()