FreedomLy's blog.

【每周一坑】求乘积最大

字数统计: 739阅读时长: 3 min
2017/05/03 Share

本周题目:

设定一个长度为N的数字串,将其分为两部分,找出一个切分位置,是两部分的乘积值最大,并返回最大值

示例:

1
2
3
4
5
6
7
8
9
10
11
def product(num):
'''
>>>product(312)
62
>>>product(1234)
492
>>>product(12345)
6170
>>>product(123456)
74070
'''

思路

从头到尾遍历这个数字串,

  1. 先是按顺序截取长度为1的子串与剩余的子串相乘得到一个结果
  2. 然后还是按顺序截取长度为2的子串与剩余的子串相乘得到新的结果
  3. 以此类推…
    直到截取的长度为原来的数字串的长度(除了数字串本身)然后将这些结果进行比较,得到最大的并输出即可。

可以将每一步求出的值存入初始值为0的max_num中,每次求出的值都与max_num比较,若大于max_num,则更新它的值,这样可以保证得到最大的值,也即我们要求的最大值。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# coding: utf-8
def product(num):
i = 1
max_num = 0
while i != len(str(num)):
num1 = int(str(num)[:i])
num2 = int(str(num)[i:])
result = num1 * num2
# result = int(str(num)[:i]) * int(str(num)[i:])
if result > max_num:
max_num = result
i += 1
return max_num

# 测试
print(product(312))
print(product(1234))
print(product(12345))
print(product(123456))

输出结果

结果为:

62
492
6170
74070

结果与示例相符合

附加题

上述的题目感觉还是比较简单的,因此多了一个附加题:

输入的数字串可以重新打乱排列,比如输入123,打乱排列之后会有132,213,231,312,321等情况,其他条件不变,求最大值。

示例:

1
2
3
4
5
6
7
8
9
def product_2(num):
'''
>>>product_2(1234)
1312
>>>product_2(12345)
22412
>>>product_2(123456)
342002
'''

思路

可以打乱顺序,那么如何得到所有的可能数组串就是这个问题的关键了。可惜,我一开始并没有想到用什么方法,如果强行暴力求的话复杂度高不说,还可能求不全。于是我参考了别人的代码,发现了一个神奇的库:itertools
它属于Python标准库,今天用到的是permutations()这个函数:

permutations(p[,r]); 创建一个迭代器,返回iterable中所有长度为r的项目序列,如果省略了r,那么序列的长度与iterable中的项目数量相同
返回p中任意取r个元素做排列的元组的迭代器

例如:

permutations(‘ABCD’, 2)

返回的结果为:

AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD

有了这个函数,我们就可以完成附加题了

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# coding: utf-8
from itertools import permutations


def product_2(num):
i = 1
max_num = 0
for p in permutations(str(num)):
new_num = "".join(p) # 排列后返回的是一个元组,通过join()来重新生成数字串
# print(new_num)
result = product(new_num) # 就是上面的product()
if result > max_num:
max_num = result
return max_num


# 测试
print(product_2(1234))
print(product_2(12345))
print(product_2(123456))

输出结果

结果为:

1312
22412
342002

与示例一致

End~


CATALOG
  1. 1. 思路
  2. 2. Python实现
  3. 3. 输出结果
  4. 4. 附加题
  5. 5. 思路
  6. 6. Python实现
  7. 7. 输出结果