s***g
发帖数: 1250 | 1 printFactors(int n)
input:32
output:
1 * 32
2 * 16
2 * 2 * 8
2 * 2 * 2 * 4
2 * 2 * 2 * 2 * 2
2 * 4 * 4
4 * 8
没有思路啊。
只能想到先找出所有的factor。 大牛们能给点思路吗？谢谢 | l*****a
发帖数: 14598 | 2 List> func(int n) {
List> result= new ArrayList>();
List cur=new ArrayList<>();
get(n,2,cur,result);
return result;
}
public get(int target,int start,List cur,List> result
) {
if(target==1) {
result.add(new ArrayList(cur));
return;
}
for(int i=start;i<=target/2;i++) {
if(target%i==0) {
cur.add(i);
get(target/i,i,cur,result);
cur.remove(cur.size()-1);
}
}
}
注意，没考虑第一个1*32,你单独写进去好了
【在 s***g 的大作中提到】
: printFactors(int n)
: input:32
: output:
: 1 * 32
: 2 * 16
: 2 * 2 * 8
: 2 * 2 * 2 * 4
: 2 * 2 * 2 * 2 * 2
: 2 * 4 * 4
: 4 * 8
| s***g
发帖数: 1250 | 3 非常敢谢，我消化一下
result
【在 l*****a 的大作中提到】
: List> func(int n) {
: List> result= new ArrayList>();
: List cur=new ArrayList<>();
: get(n,2,cur,result);
: return result;
: }
: public get(int target,int start,List cur,List> result
: ) {
: if(target==1) {
: result.add(new ArrayList(cur));
| p*****p
发帖数: 379 | 4 需要memorization，不然复杂度似乎是O(n!)级的（不是很确定这个怎么算）
result
【在 l*****a 的大作中提到】
: List> func(int n) {
: List> result= new ArrayList>();
: List cur=new ArrayList<>();
: get(n,2,cur,result);
: return result;
: }
: public get(int target,int start,List cur,List> result
: ) {
: if(target==1) {
: result.add(new ArrayList(cur));
| r****7
发帖数: 2282 | 5 递归就行了啊
【在 s***g 的大作中提到】
: printFactors(int n)
: input:32
: output:
: 1 * 32
: 2 * 16
: 2 * 2 * 8
: 2 * 2 * 2 * 4
: 2 * 2 * 2 * 2 * 2
: 2 * 4 * 4
: 4 * 8
| r****7
发帖数: 2282 | 6 这个。。。没考虑到的东西略多啊
result
【在 l*****a 的大作中提到】
: List> func(int n) {
: List> result= new ArrayList>();
: List cur=new ArrayList<>();
: get(n,2,cur,result);
: return result;
: }
: public get(int target,int start,List cur,List> result
: ) {
: if(target==1) {
: result.add(new ArrayList(cur));
| h**d
发帖数: 630 | 7 第一个32打不出来 后面的16 等等也会打不出来 因为循环到target/2就停了
result
【在 l*****a 的大作中提到】
: List> func(int n) {
: List> result= new ArrayList>();
: List cur=new ArrayList<>();
: get(n,2,cur,result);
: return result;
: }
: public get(int target,int start,List cur,List> result
: ) {
: if(target==1) {
: result.add(new ArrayList(cur));
| p**p
发帖数: 742 | 8 暴力递归解法：
public List> printFactors(int n) {
List> result = new ArrayList>();
if(n <= 0) {
return result;
}
List trace = new ArrayList();
printFactorsHelper(n, trace, result);
return result;
}
private void printFactorsHelper(int n, List trace, List
Integer>> result) {
List list = new ArrayList(trace);
if(list.isEmpty()) {
list.add(1);
}
list.add(n);
result.add(list);
for(int i = trace.isEmpty() ? 2 : trace.get(trace.size()-1); i <= n/
i; i++) {
if(n % i == 0) {
trace.add(i);
printFactorsHelper(n/i, trace, result);
trace.remove(trace.size()-1);
}
}
} | h**d
发帖数: 630 | 9 c++的
void findfactor(int n, int target,int start, vector > &result,
vector &group)
{
if(target == 1)
{
if(group.size()==1)
{
group.insert(group.begin(),1);
}
result.push_back(group);
return;
}
for(int i= start;i<=target;i++)
{
if(target%i==0)
{
group.push_back(i);
findfactor(n, target/i, i, result, group);
group.pop_back();
}
}
}
【在 s***g 的大作中提到】
: printFactors(int n)
: input:32
: output:
: 1 * 32
: 2 * 16
: 2 * 2 * 8
: 2 * 2 * 2 * 4
: 2 * 2 * 2 * 2 * 2
: 2 * 4 * 4
: 4 * 8
| f*********0
发帖数: 17 | 10 函数参数有了target还要n干嘛？
另外这应该是指数级复杂度的吧？
void recur(int n, int m, vector > &results, vector &result)
{
//if (m > n) return;
if (n == 1) {
results.push_back(result);
return;
}
for (int i = m; i <= n; ++i) {
if (n%i == 0) {
result.push_back(i);
recur(n/i, i, results, result);
result.pop_back();
}
}
}
vector > printFactors(int n) {
vector > results = {{1,32}};
recur(n, 2, results, result);
return results;
}
【在 h**d 的大作中提到】
: c++的
: void findfactor(int n, int target,int start, vector > &result,
: vector &group)
: {
: if(target == 1)
: {
: if(group.size()==1)
: {
: group.insert(group.begin(),1);
: }
| l*****a
发帖数: 14598 | 11 en,那个/2画蛇添足了，拿掉就好
【在 h**d 的大作中提到】
: 第一个32打不出来 后面的16 等等也会打不出来 因为循环到target/2就停了
:
: result
|
|
