【MEDIUM】Factor Combinations

发布于: 2019-03-10 17:33
阅读: 39
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/factor-combinations/

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:

  • Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  • 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]
]

分析过程

  • 输入:一个正整数 value
  • 输出:这个正整数的所有因数组合,不包括 1 和自己
  • 思路:可以用普通递归的方法,或者回溯法。
    • 从 2 开始遍历找因数,然后递归找到 value / factor 的所有组合,然后把 factor 插在第一个即可。这里要去掉重复的情况,见注释。
    • 回溯法,见注释。

解决方法

普通方法:

class Solution {
    func getFactors(_ n: Int) -> [[Int]] {
        // 循环时从2到根号value循环,小于4的结果直接排除
        let sqrtValue = Int(sqrtf(Float(n)))
        guard sqrtValue >= 2 else {
            return []
        }
        var result = [[Int]]()
        for f in 2...sqrtValue {
            // f是因数
            guard n % f == 0 else {
                continue
            }
            // 先把f和value/f这种情况放入结果
            result.append([f, n / f])
            // 对value/f递归,得到所有组合情况
            let r = getFactors(n / f)
            // 处理其他情况
            for var v in r {
                // 题目要求因数重小到大,因此f只能插在最前面
                // 还可以过滤掉一些仅仅是顺序不同的重复的情况
                guard f <= v[0] else {
                    continue
                }
                v.insert(f, at: 0)
                result.append(v)
            }
        }
        return result
    }
}

回溯法:

class Solution {
    
    func _getFactors(value: Int, factor: Int, tmp: inout [Int], result: inout [[Int]]) {
        guard value > 1 else {
            // 递归的结束条件,除到1为止
            // 这里大于1是为了过滤掉自己本身作为唯一因数这种情况
            if tmp.count > 1 {
                // 除到1以后,tmp里就是一种结果,放入result
                result.append(tmp)
            }
            return
        }
        guard value >= factor else {
            return
        }
        for f in factor...value {
            // f是因数
            guard value % f == 0 else {
                continue
            }
            // 把因数放入
            tmp.append(f)
            // 然后对value/f递归
            _getFactors(value: value / f, factor: f, tmp: &tmp, result: &result)
            // 递归结束以后,当前因数的情况就结束了
            // 弹出当前因数,继续下一次循环
            tmp.removeLast()
        }
        
    }
    
    func getFactors(_ n: Int) -> [[Int]] {
        if n < 4 {
            return []
        }
        var result = [[Int]]()
        // 用于回溯的临时空间
        var tmp = [Int]()
        
        _getFactors(value: n, factor: 2, tmp: &tmp, result: &result)
        
        return result
    }
}

Thanks for reading.

All the best wishes for you! 💕