找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6003|回复: 2
收起左侧

[米群网刷题小分队] LeetCode - Factor Combinations 会员题

[复制链接]

14

主题

0

精华

52

积分

资深会员

Rank: 2

积分
52
发表于 8-22-2015 06:53 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

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 【i】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 【i】n is always positive.
  • Factors should be greater than 1 and less than 【i】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]]

思路:
这题就是不停的DFS, 直到 n == 1. 有个判断条件 if (item.size() > 1)  是为了防止答案是自己本身n, 按照题意, 这是不允许的.
可能有人会立刻想, 那为什麽不在for回圈终止条件就设置 i < n, 这样的话, 当用 n / i进入下一个DFS时, 会漏掉答案, 例如:
n = 4, [2 2] 是一个答案, for回圈终止条件必须设置i = n, 才不会漏掉第2个2.

时间复杂度, 个人觉得是O(n*log(n)), 一开始觉得是O(n!), 但後来想想好像没那麽大. 我的想法是,
最一开始的for回圈是n, 但是一旦进入了下一个DFS, 每次最差都是 n / i在减小, 这边就是log(n), 所以总共是O(n*log(n)), 有错还请指正.


  1. public List<List<Integer>> getFactors(int n) {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> item = new ArrayList<>();
  4.         
  5.     if (n <= 3) {
  6.         return res;
  7.     }
  8.         
  9.     helper(2, n, item, res);
  10.     return res;
  11.     }
  12.    
  13.     private void helper(int start, int n, List<Integer> item, List<List<Integer>> res) {
  14.     if (n == 1) {
  15.         if (item.size() > 1) {
  16.             res.add(new ArrayList<Integer>(item));
  17.         }
  18.         return;
  19.     }
  20.         
  21.     for (int i = start; i <= n; i++) {
  22.         if (n % i == 0) {
  23.             item.add(i);
  24.             helper(i, n / i, item, res);
  25.             item.remove(item.size() - 1);
  26.         }
  27.     }
  28.     }
复制代码


14

主题

0

精华

52

积分

资深会员

Rank: 2

积分
52
 楼主| 发表于 8-22-2015 07:30 AM | 显示全部楼层
题目格式没弄好 重贴如下

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.
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]
]
回复 支持 反对

使用道具 举报

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 9-15-2015 10:20 AM | 显示全部楼层
好像你的代码当输入为32时,输出的结果顺序和例子中的不一样
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表