难度: Medium
Submission
运行时间: 36 ms
内存: 16.2 MB
class Solution:
def findInteger(self, k: int, digit1: int, digit2: int) -> int:
if digit1 == digit2 == 0:
return -1
m = (1 << 31) - 1
if digit1 == digit2:
num = digit1
while num <= m:
if num > k and num % k == 0:
return num
num = 10 * num + digit1
return -1
if digit1 > digit2:
digit1, digit2 = digit2, digit1
q = deque([])
if digit1 != 0:
q.append(digit1)
q.append(digit2)
while True:
size = len(q)
for _ in range(size):
pre = q.popleft()
if pre > m:
return -1
if pre > k and pre % k == 0:
return pre
for digit in [digit1, digit2]:
num = pre * 10 + digit
q.append(num)
Explain
题解通过构造并检查整数来解决问题，整数由指定的两个数字digit1和digit2组成。首先，代码处理了特殊情况，当两个数字都为0时，返回-1，因为0不能被任何正数整除。接着，处理digit1和digit2相等的情况，从最小的数开始，逐步构造更大的数，直到找到一个大于k且能被k整除的数，或者超出32位整数的范围。如果digit1不等于digit2，代码首先确保digit1小于digit2以简化后续逻辑，然后使用广度优先搜索（BFS）策略从较小的数字开始，逐步构造可能的整数，并检查是否满足条件。通过队列来管理待检查的数字，对每个数字，尝试添加digit1和digit2作为新的最低位，从而构造新的数字，并检查是否满足条件。这个过程持续进行，直到找到合适的数字或确定无解。
时间复杂度: O(10^9) in the worst case scenario
空间复杂度: O(10^9) in the worst case scenario
class Solution:
def findInteger(self, k: int, digit1: int, digit2: int) -> int:
# 特殊情况：如果两个数字都为0，则无解
if digit1 == digit2 == 0:
return -1
# 32位整数的最大值
m = (1 << 31) - 1
# 如果两个数字相同
if digit1 == digit2:
num = digit1
while num <= m:
if num > k and num % k == 0:
return num
num = 10 * num + digit1
return -1
# 保证digit1是较小的数字
if digit1 > digit2:
digit1, digit2 = digit2, digit1
q = deque([])
# 初始化队列，避免以0开始的数字
if digit1 != 0:
q.append(digit1)
q.append(digit2)
# BFS搜索符合条件的数字
while True:
size = len(q)
for _ in range(size):
pre = q.popleft()
if pre > m:
return -1
if pre > k and pre % k == 0:
return pre
for digit in [digit1, digit2]:
num = pre * 10 + digit
q.append(num)
Explore
当两个数字都为0时，任何构造的数字都将只包含0（例如00, 000, 0000等），这些数字都是0。0不能被任何正数整除，因此不可能存在一个由两个0组成的正整数来满足能够被正整数k整除的条件。因此，这种情况下直接返回-1是因为继续搜索不会产生有效的结果。
当digit1和digit2相等时，任何可能的数字都会由相同的数字重复组成，如11, 111, 1111等。这种方法首先尝试最小的数，如单个数字，然后逐步增大，检查每个数字是否大于k并能被k整除。这种方法可能导致处理时间较长，但理论上，如果存在一个解，则最终可以找到，因为数字会不断增长直到找到一个符合条件的数或超出32位整数的范围。不存在找不到解的情况，除非所有可能的数字都已经超出32位整数的范围，这时返回-1。
确保digit1小于digit2可以简化算法的逻辑处理，因为这样可以始终从较小的数字开始构造新的数字。这有助于避免在数字构造过程中的重复和不必要的混乱。例如，在进行广度优先搜索（BFS）时，始终从较小的数字开始可以确保搜索路径是系统性的，逐渐增加数字的大小，并且能够更快地遍历所有可能的组合。这种做法提高了算法的效率和易于管理，尤其是在使用队列进行数字构造的过程中。