关于OA回顾
这个系列旨在记录参加过的一些日本互联网公司的OA原题。考虑到私密性等问题，文中只会记录题目的内容而不会指明该题来自于哪一家公司。
题目概述
现有一个数组nums由非负整数构成。求该数组中各位数字互不重复的最大两数之和。若不存在各位数字互不重复的两数，则返回-1。
限制条件：
2 <= nums.length <= 2 * 10 ^ 50 <= nums[i] <= 10 ^ 9
例:
1
2
3
4
5
6
7
8
Input: nums = [53, 1, 36, 103, 53, 5]
Output: 108
Input: nums = [9, 19, 29, 99]
Output: -1
Input: nums = [15, 0, 105]
Output: 15
思路 & 代码实现
解法一：位运算 + Brute Force
暴力枚举数组中所有的两数组合，判断其各位数字是否互不重复，并更新最大的两数之和。
为了获取一个数中包含的数字，并实现高效的比较运算，可以使用集合:
1
2
3
4
5
6
7
8
9
def getDigits(num):
if not num:
return set([0])
digits = set()
while num:
digit = num % 10
digits.add(digit)
num //= 10
return digits
或者使用一个二进制数字用于表示数字0 ~ 9的存在性。例如103，它包含了0、1、3这三个数字，那么在对应的二进制数字中，从最低位开始的第0、1、3位用1表示存在，也即1011。
1
2
3
4
5
6
7
8
9
def getDigits(num):
if not num:
return 1
digits = 0
while num:
digit = num % 10
digits |= (1 << digit)
num //= 10
return digits
接着这个利用位运算的思路，我们可以用按位与运算这个非常简便的方式判断它们所包含的数字是否互不重复。例如103和5，它们用上述方式转换后得到的二进制表示分别为001011、100000，按位与后结果为0，说明没有重复数字。如果得到的数大于0，说明两数中至少有一位均为1，也就是出现了重复数字。
那么，暴力枚举的完整代码实现为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(nums):
def getDigits(num):
if not num:
return 1
digits = 0
while num:
digit = num % 10
digits |= (1 << digit)
num //= 10
return digits
ans = -1
for i, num1 in enumerate(nums[:-1]):
for num2 in nums[i+1:]:
if getDigits(num1) & getDigits(num2):
continue
else:
ans = max(ans, num1 + num2)
return ans
Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$
或者稍作优化，为了避免每次比较都重新计算一遍二进制表示，可以事先利用一个哈希表存储。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(nums):
def getDigits(num):
if not num:
return 1
digits = 0
while num:
digit = num % 10
digits |= (1 << digit)
num //= 10
return digits
ans = -1
num_digits = list(map(getDigits, nums))
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if num_digits[i] & num_digits[j]:
continue
else:
ans = max(ans, nums[i] + nums[j])
return ans
Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$
考虑到测试用例中数组的长度会达到10的五次方，这个时间复杂度不太能接受。
解法二：位运算 + 哈希表 + 贪心
其实使用二进制数表示一个数中包含的数字已经是一个非常好的思路了，它直达了该问题的本质，即：所需要比较的并不是数组中的数，而是转化后的二进制数。因为核心要求为两两包含的数字互不重复，那么无论这两个数多大，它们所能包含的数字最多也就0 ~ 9这10种，无非 $2 ^ {10} = 1024$ 种形式。用二进制表示的话，范围在0 ~ 1111111111（0 ~ 1023）之间。
这样只需要建立一个key为0 ~ 1023的哈希表，就能涵盖所有可能的数字表示。并且，由于题目要求最大的两数之和，因此对应key只需要贪心地保存最大的那一个数即可。
代码实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solution(nums):
def getDigits(num):
if not num:
return 1
digits = 0
while num:
digit = num % 10
digits |= (1 << digit)
num //= 10
return digits
num_digits = {}
ans = -1
for num in nums:
digits = getDigits(num)
if digits not in num_digits:
num_digits[digits] = num
else:
num_digits[digits] = max(num_digits[digits], num)
for k1, v1 in num_digits.items():
for k2, v2 in num_digits.items():
if k1 & k2:
continue
else:
ans = max(ans, v1 + v2)
return ans
Time complexity: $O(n + k ^ 2)$
Space complexity: $O(k)$
$k$ 为num_digits的长度，最大值为1024。
