0254._Factor_Combinations.md

254. Factor Combinations

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/factor-combinations/description/

内容描述

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.

Note:

You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Example 1:

Input: 1
Output: []
Example 2:

Input: 37
Output:[]
Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]
Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

就每次遍历到sqrt(n)就够了，再往后面过去其实重复了, beats 62.6%

class Solution(object):
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        from math import sqrt
        if n < 4:
            return []
        res = []
        for i in range(2, int(sqrt(n))+1):
            if n % i == 0 and i <= n / i:
                res.append([i]+[n/i])
                for j in self.getFactors(n/i):
                    if j and i <= j[0]:
                        res.append([i]+j)
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

想着用一下memorization会更快一点，果然beats 100%

class Solution(object):
    cache = {}
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        from math import sqrt
        if n < 4:
            return []
        if n in self.cache:
            return self.cache[n]
        else:
            res = []
            for i in range(2, int(sqrt(n))+1):
                if n % i == 0 and i <= n / i:
                    res.append([i]+[n/i])
                    for j in self.getFactors(n/i):
                        if j and i <= j[0]:
                            res.append([i]+j)
            self.cache[n] = res
        return res

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******

换个思路，每次都先直接append一个最大到res中，然后递归部分只增加一个更大的factor，但其实这种也不是很快，只beats 62.61，跟思路1一样一样的。

一直觉得这种类似递归的算法看code最能理解了，我就不多说了，打球去了！

class Solution(object):
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        def helper(n, prev):
            # for each recursive part, at least append a larger factor
            start = 2 if not prev else prev[-1] 
            for i in range(start, int(pow(n, 0.5))+1):
                if n % i == 0:
                    helper(n/i, prev+[i])
            if prev: # drectly append the cur largest factor
                self.res.append(prev+[n])
            
        self.res = []
        helper(n, [])
        return self.res