欧美激情校园春色,青青草青青碰,亚洲女人被黑人巨大的原因,东京热日韩无码,夜夜艹逼,99精品久久毛片A片,先锋影音一区二区三区,亚洲色婷婷在线播放

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 因子的組合，我們先來看題面：

https://leetcode-cn.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.

請實(shí)現(xiàn)一個(gè)函數(shù)，該函數(shù)接收一個(gè)整數(shù) n 并返回該整數(shù)所有的因子組合。

示例

注意：
你可以假定 n 為永遠(yuǎn)為正數(shù)。
因子必須大于 1 并且小于 n。

示例 1：
輸入: 1
輸出: []

示例 2：
輸入: 37
輸出: []

示例 3：
輸入: 12
輸出:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

示例 4:
輸入: 32
輸出:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

解題

可以采用遞歸。從2開始遍歷到sqrt(n)，能被n整除就進(jìn)下一個(gè)遞歸，當(dāng)start超過sqrt(n)時(shí)，start變成n，進(jìn)下一個(gè)遞歸。

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);
    }
}