leetcode254 -- Factor Combinations (找到一个数的所有因式分解,不一定是最简单的)

leetcode254 -- Factor Combinations (找到一个数的所有因式分解,不一定是最简单的)

题目


找到一个数的所有因式分解,几个例子

input:1
output:[]

input: 37
output: []

input:12
output:
[
    [2,6],
    [2,2,3],
    [3,4]
]

这个题我是从之前的几个题中找到的思路,之前的递归的时候target是target-nums[i]而现在应该是target/nums[i]了,前提是只要能够除得进,而且可以有重复的,所以要从i开始,而不是从i+1递归。

代码如下


def main(n):

    def helper(candidates, target):
        res = []
        for i in range(len(candidates)):
            if candidates[i]>target:
                break
            if candidates[i]==target:
                res.append([candidates[i]])
                break
            if target%candidates[i]==0:
                temp = target/candidates[i]
                TT = helper(candidates[i:], temp)
                for x in TT:
                    x.insert(0, candidates[i])
                    res.append(x)

        return res

    ret = helper(range(2, n), n)

    return ret

if __name__ == '__main__':
    import sys
    print main(int(sys.argv[1]))
~                                                                                                                                                                                 
~                                                   

测试结果

qiuzhao john$ python factor_combination.py 1
[]
qiuzhao john$ python factor_combination.py 10
[[2, 5]]
qiuzhao john$ python factor_combination.py 100
[[2, 2, 5, 5], [2, 2, 25], [2, 5, 10], [2, 50], [4, 5, 5], [4, 25], [5, 20], [10, 10]]
qiuzhao john$ python factor_combination.py 8
[[2, 2, 2], [2, 4]]
qiuzhao john$ python factor_combination.py 32
[[2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 8], [2, 4, 4], [2, 16], [4, 8]]
qiuzhao john$ python factor_combination.py 35
[[5, 7]]
qiuzhao john$ python factor_combination.py 37
[]
qiuzhao john$ 


其实用下面这两种方法都是可以的

def helper(candidates, start, target, temp, res):
    if target <0:
        return
    if target ==1 :
        res.append(temp[:])
        return

    for i in range(start, len(candidates)):
        # recursive
        if target%candidates[i] ==0:
            temp.append(candidates[i])
            helper(candidates, i, target//candidates[i], temp, res)
            del(temp[-1])
def helper2(candidates, target):
    res = []
    for i in range(len(candidates)):
        if candidates[i]>target:
            break
        if target == candidates[i]:
            res.append([candidates[i]])
            break

        if target % candidates[i]==0:
            temp = helper2(candidates[i:], target//candidates[i])
            for a in temp:
                a.insert(0, candidates[i])
                res.append(a)
    return res

def main(n):

    res = []
    helper(list(range(2, n)), 0, n, [], res)
    print("res1", res)
    print("res2", helper2(list(range(2,n)), n))


主要是搞明白本质的思想,相加相乘都是可以出题的.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦