由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道算法题(整数表示成乘积)
相关主题
Help, Algorithms questions计算组合数C(m,n)
除法有什么规律吗?整数除法
G家面经问一个facebook的电面题
每日一题之毛毛虫和叶子leecode上的divide two integers问题
T家在线测试面经,感觉好难啊leetcode: Divide Two Integers 怎么做?
[合集] 请教一道算法面试题Google onsite一题
只用加减实现整数除法,到底想考查什么?Divide Two Integers OJ和CCP150的做法
请问给一个整数,如何返回他的平方根?最近onsite的时候刚拿到一道面试题?
相关话题的讨论汇总
话题: remain话题: int话题: vector话题: factor话题: 乘积
进入JobHunting版参与讨论
1 (共1页)
m******a
发帖数: 84
1
问一道题,好像是L家的一题,将一个数N表示成一串整数的乘积,要求输出所有可能的
方式,并且去重,并由小到大排序,如N=24,则加过是 1*24, 2*2*2*3, 2*3*4, 3*8 .
.... 这个题就是先分解质因数,后面如何找到左右的由小到大的组合呢?
r****7
发帖数: 2282
2
这种题你要想的太细就没法做了
不用分解质因数,直接dfs,遇到能整除的把整除之后的结果继续递归,不过要排序去
重,所以要把当前的被除数带入到递归中,然后下一层递归的被除数要大于等于这个传
入的数

.

【在 m******a 的大作中提到】
: 问一道题,好像是L家的一题,将一个数N表示成一串整数的乘积,要求输出所有可能的
: 方式,并且去重,并由小到大排序,如N=24,则加过是 1*24, 2*2*2*3, 2*3*4, 3*8 .
: .... 这个题就是先分解质因数,后面如何找到左右的由小到大的组合呢?

m*****k
发帖数: 731
3
http://www.mitbbs.com/article_t/JobHunting/32803907.html
没有1*24吧
否者就该有1*2*2*2*3 吧
T******e
发帖数: 157
4
大概写一个试试,感觉1和数本身的情况要另外考虑
void divide(vector >& factors, vector& factor, int start,
int remain){
if (remain == 1) {
factors.push_back(factor);
return;
}
for (int i = start; i <= remain; i++) {
if (remain%i == 0) {
factor.push_back(i);
divide(factors, factor, i, remain/i);
factor.pop_back();
}
}
}
h**6
发帖数: 4160
5
想到分解质因数的都是数学竞赛后遗症。
1 (共1页)
进入JobHunting版参与讨论
相关主题
最近onsite的时候刚拿到一道面试题?T家在线测试面经,感觉好难啊
不用大整数如何计算组合数?[合集] 请教一道算法面试题
请教中文OJ一道题只用加减实现整数除法,到底想考查什么?
2000以内能被3 或者4 整除, 却不能被 5 整除的整数有多少个请问给一个整数,如何返回他的平方根?
Help, Algorithms questions计算组合数C(m,n)
除法有什么规律吗?整数除法
G家面经问一个facebook的电面题
每日一题之毛毛虫和叶子leecode上的divide two integers问题
相关话题的讨论汇总
话题: remain话题: int话题: vector话题: factor话题: 乘积