找出第 K 个幸运数字

Submission

运行时间: 46 ms

内存: 15.9 MB

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        return bin(k + 1)[3:].replace("0", "4").replace("1", "7")

Explain

这个题解的思路基于一个有趣的观察：幸运数字序列（只包含数字4和7）可以看作是一个二进制序列的变体，其中二进制数的每个位被映射到4或7。具体来说，0被映射成4，1被映射成7。首先，计算出k+1的二进制表示，然后去掉前导的'0b'标志和最高位的1（因为二进制的起始位不用于生成幸运数字）。接下来，将剩余的二进制数中的0替换为4，1替换为7，得到第k个幸运数字。

时间复杂度: O(log(k))

空间复杂度: O(log(k))

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        # 将整数k+1转换为二进制字符串
        binary_representation = bin(k + 1)
        # 去掉二进制字符串前面的'0b'和最高位的'1'
        trimmed_binary = binary_representation[3:]
        # 将二进制字符串中的0替换为4, 1替换为7
        lucky_number = trimmed_binary.replace('0', '4').replace('1', '7')
        return lucky_number

Explore

在二进制计数中，一个数的最高位1代表该数的最大数位开始。例如，二进制的100是十进制的4，而011是3。在生成幸运数字序列时，我们实际上是从1开始生成（如二进制的1映射到4），因此我们想要从这个最大数位的1开始映射。然而，由于我们计算的是k+1的值，其二进制形式总是以1开头（因为它比k多1，保证了进位的存在），所以为了对应到正确的位置，我们需要去掉这个最高位的1。这样，剩余的二进制数才真正对应于从零开始的位置，确保了映射的正确性。

如果k为0，根据方法，我们首先计算k+1，即1。1的二进制表示是'0b1'。去掉'0b'和最高位的1后，剩下的是一个空字符串。按照题解中的逻辑，这会导致一个空的结果，而不是有效的幸运数字。因此，这种情况下方法不能正确工作。实际上，我们需要为这种特殊情况添加一个处理逻辑，例如直接返回'4'，因为0+1=1，对应的幸运数字应该是序列的第一个，即'4'。

在此算法中，将二进制的0和1映射到4和7是基于幸运数字只包含数字4和7的特性。我们可以将每个幸运数字看作是一个二进制数，其中每个二进制位（0或1）直接决定了在相应位置上是4还是7。例如，二进制的'0'对应'4'，'1'对应'7'。这种映射的好处是每增加一个数字，就相当于二进制数的一个进位，从而在幸运数字序列中生成下一个数字。这样，我们可以通过简单的二进制计数直接生成幸运数字序列，每个二进制数准确地映射到一个特定的幸运数字。

在编程时处理整数到二进制的转换和字符串操作，我们需要注意几个潜在的错误源和特殊情况：1. 确保在转换二进制字符串时去除'0b'前缀。2. 特别注意二进制表示是'0b1'的情况，这种情况下处理可能导致空字符串，需要特殊处理。3. 替换操作时，要确保所有的'0'和'1'都被正确替换，没有遗漏。4. 考虑边界值处理，如k非常大或为0的情况。通过仔细的错误检查，合理的边界条件测试和对特殊情况的处理，可以有效避免这些潜在的问题。