[LeetCode] 254. Factor Combinations 因子组合

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 254. Factor Combinations 因子组合,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

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.java

Note: python

  1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  2. You may assume that n is always positive.
  3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: app

[]

input: 37
output: less

[]

input: 12
output:函数

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:post

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

 

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

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.code

Note: htm

  1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  2. You may assume that n is always positive.
  3. Factors should be greater than 1 and less than n.

 

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

 写一个函数,给定一个整数n,返回全部可能的因子组合。

解法:递归。从2开始遍历到sqrt(n),能被n整除就进下一个递归,当start超过sqrt(n)时,start变成n,进下一个递归。

Java:

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(result, new ArrayList<Integer>(), n, 2);
        return result;
    }
 
    public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
        if (n <= 1) {
            if (item.size() > 1) {
                result.add(new ArrayList<Integer>(item));
            }
            return;
        }
        
        for (int i = start; i * i <= n; ++i) {
            if (n % i == 0) {
                item.add(i);
                helper(result, item, n/i, i);
                item.remove(item.size()-1);
            }
        }
        
        int i = n;
        item.add(i);
        helper(result, item, 1, i);
        item.remove(item.size()-1);
    }
}

Python: Time: O(nlogn) Space: O(logn)

class Solution:
    # @param {integer} n
    # @return {integer[][]}
    def getFactors(self, n):
        result = []
        factors = []
        self.getResult(n, result, factors)
        return result

    def getResult(self, n, result, factors):
        i = 2 if not factors else factors[-1]
        while i <= n / i:
            if n % i == 0:
                factors.append(i);
                factors.append(n / i);
                result.append(list(factors));
                factors.pop();
                self.getResult(n / i, result, factors);
                factors.pop()
            i += 1

C++:

// Time:  O(nlogn) = logn * n^(1/2) * n^(1/4) * ... * 1
// Space: O(logn)

// DFS solution.
class Solution {
    public:
        vector<vector<int>> getFactors(int n) {
            vector<vector<int>> result;
            vector<int> factors;
            getResult(n, &result, &factors);
            return result;
        }

        void getResult(const int n, vector<vector<int>> *result, vector<int> *factors) {
            for (int i = factors->empty() ? 2 : factors->back(); i <= n / i; ++i) {
                if (n % i == 0) {
                    factors->emplace_back(i);
                    factors->emplace_back(n / i);
                    result->emplace_back(*factors);
                    factors->pop_back();
                    getResult(n / i, result, factors);
                    factors->pop_back();
                }
            }
        }
    };

  

相似题目:

[LeetCode] 39. Combination Sum 组合之和

[LeetCode] 40. Combination Sum II 组合之和 II

[LeetCode] 216. Combination Sum III 组合之和 III

[LeetCode] 377. Combination Sum IV 组合之和 IV

 

All LeetCode Questions List 题目汇总