0

我试图了解在 python 的 bisect 模块中使用 bisect 函数以及如何将它与元组一起使用。我已经看到它需要一个列表和一个值来找到放置值的索引。在我的情况下，该值是一个元组。这是来自 leetcode 981 https://leetcode.com/problems/time-based-key-value-store/。A 是一个元组列表，元组将包含 (int,string) 作为其数据。

class TimeMap(object):
def __init__(self):
    self.M = collections.defaultdict(list)

def set(self, key, value, timestamp):
    self.M[key].append((timestamp, value))

def get(self, key, timestamp):
    A = self.M.get(key, None)
    if A is None: return ""
    i = bisect.bisect(A, (timestamp, chr(127)))
    return A[i-1][1] if i else ""

我了解他们为解决问题而尝试做的事情。我只是想了解为什么使用 chr(127)。我尝试使用 None 但它给出了一个错误。我猜它总是会采用元组中的第一个 int 值，因为 chr(127) 总是不合格，因为 bisect 接受。但我无法找到正确的原因。IDLE 也将 chr(127) 显示为 \x7f 并发现它是一个非 ascii 字符。

4

2 回答 2

1

Python 逐个元素并从左到右比较元组。例如：

(1, 2) > (1, 1)是True

(1, 2) > (1, 2)是False

我猜，他们使用chr(127), 使元组中的第二项大于任何其他字符。

(1, chr(127)) > (1, 'z')是True

于 2021-03-08T09:17:45.680 回答
0

终于在 leetcode 论坛中找到了一些可以理解的解决方案。所有积分都归 leetcode 用户 https://leetcode.com/slvher/和https://leetcode.com/jcodem/

lower char 的 ascii 码范围是 [97, 122]，因此可以使用 chr(127) 来确保 bisect.bisect(A, (timestamp, chr(127))) 找到的索引满足条件：timestamp_prev <= 时间戳。其实这里也可以使用 chr(ascii_v)，其中 ascii_v 的范围是 [123, 127]。

于 2021-03-09T02:34:00.753 回答