s*****n
发帖数: 994 | 1 输出一自然数所有不重复的因数分解
最后去重复的办法不算 | w*******e
发帖数: 285 | 2 从1到sqrt(n)扫描，能整除i就输出i和n/i？
【在 s*****n 的大作中提到】
: 输出一自然数所有不重复的因数分解
: 最后去重复的办法不算
| h*********o
发帖数: 230 | 3 应该这样吧。。。没啥想法。。
【在 w*******e 的大作中提到】
: 从1到sqrt(n)扫描，能整除i就输出i和n/i？
| l******6
发帖数: 340 | 4 void recurCompute(int curNum , int remain , int maxNum , vector &
curCombine , vector > & ret)
{
if(curNum > maxNum)
return;
recurCompute(curNum + 1 , remain , maxNum , curCombine , ret);
if(remain % curNum == 0)
{
remain = remain/curNum;
if(remain < curNum)
return;
curCombine.push_back(curNum);
curCombine.push_back(remain);
ret.push_back(curCombine);
curCombine.pop_back();
recurCompute(curNum , remain , maxNum , curCombine , ret);
curCombine.pop_back();
}
}
vector > getFactorCombination(int src)
{
assert(src > 0);
vector > ret;
int maxNum = sqrt(src);
vector curCombine;
ret.push_back(vector(1 , src));
recurCompute(2 , src , maxNum , curCombine , ret);
return ret;
} | s*****n
发帖数: 994 | 5 不是这个意思
12 =
1 12
2 6
2 2 3
3 4
【在 w*******e 的大作中提到】
: 从1到sqrt(n)扫描，能整除i就输出i和n/i？
| f*****e
发帖数: 2992 | 6 感觉有点繁琐的DP
original 1
add one 2
1 x 2
add another 2
2 x 2
1 x 4
add a 3
2 x 2 x 3
2 x 6
3 x 4
1 x 12
每加一个因子就乘以每个数组里的元素相乘，
say add f and we have [a1,...,an]
then add to the set
[a1,...,an, f]
[a1*f, ..., an]
[a1, a2*f, ..., an]
[a1, a2, ..., an * f]
有些boundary condition要考虑。
【在 s*****n 的大作中提到】
: 不是这个意思
: 12 =
: 1 12
: 2 6
: 2 2 3
: 3 4
| p*******2
发帖数: 50 | | s*****n
发帖数: 994 | 8 这题我感觉很难，是个国人大哥给的，感觉不想让pass... | w*******s
发帖数: 138 | 9 类似于整数分划，前面已经有人贴过code了，先做质因数分解再组合比直接枚举难写。
【在 s*****n 的大作中提到】
: 这题我感觉很难，是个国人大哥给的，感觉不想让pass...
| s*****n
发帖数: 994 | 10 怎么枚举？
我写的recursive就是无法去处duplication
【在 w*******s 的大作中提到】
: 类似于整数分划，前面已经有人贴过code了，先做质因数分解再组合比直接枚举难写。
| | | C*******n
发帖数: 24 | 11 标记个start，然后一步一步开始做
java code，貌似我童鞋也被考这个题了。
个人做了下，蛮有思路，耗时有点长，但是差不多能handle
不过真的算是个难的phone题啊，我这个小弱是这么觉得的。。。。
public void solution(int num){
int i = 1;
while(i * i <= num){
if(i == 1){
System.out.println(num + " * 1");
}else if( num % i == 0){
ArrayList> tmp = helper(num / i, i);
for (ArrayList r : tmp){
for ( Integer no : r){
System.out.print(no + " * ");
}
System.out.println(i);
}
}
i++;
}
}
public ArrayList> helper(int num,int start){
ArrayList> result = new ArrayList>
();
// add self value: num
ArrayList re = new ArrayList();
re.add(num);
result.add(re);
// if num == 1,2,3, final result, just return;
if (num == 1 || num == 2 || num == 3){
return result;
}
int handle = start;
while (handle * handle <= num){
if (num % handle == 0) {
ArrayList> tmp = helper(num / handle, handle);
for(ArrayList r : tmp){
re = new ArrayList(r);
re.add(handle);
result.add(re);
}
}
handle++;
}
return result;
} | w*******s
发帖数: 138 | 12 前面不是有人贴了代码么，可以参考一下
【在 s*****n 的大作中提到】
: 怎么枚举？
: 我写的recursive就是无法去处duplication
| s*****n
发帖数: 994 | 13 这个有问题吧？先抛开为啥第一个不是1-》1*2和2
就拿18来写
1*2
1*2*3
3*2
1*6
1*2*3*3
3*2*3
1*6*3
1*2*9
3*2*3
9*2
3*6
1*6*3
3*6
1*18
有很多duplication，而且1*anything除了1*18都不应该include
【在 f*****e 的大作中提到】
: 感觉有点繁琐的DP
: original 1
: add one 2
: 1 x 2
: add another 2
: 2 x 2
: 1 x 4
: add a 3
: 2 x 2 x 3
: 2 x 6
| b*********s
发帖数: 115 | 14 其实很短就可以写完
def fac(low, n):
if n == 1:
return [[]]
res = []
for i in xrange(low, n + 1):
if n % i == 0:
head = [i]
res += [head + tail for tail in fac(i, n / i)]
return res
def solve(n):
res = fac(2, n)
# 上面算出来的res最后一个是[n], 在开头插入1变成[1, n]
res[-1].insert(0, 1)
print res
测试:
input: 12 output: [[2, 2, 3], [2, 6], [3, 4], [1, 12]]
input: 100 output: [[2, 2, 5, 5], [2, 2, 25], [2, 5, 10], [2, 50], [4, 5, 5]
, [4, 25], [5, 20], [10, 10], [1, 100]]
input: 25 output: [[5, 5], [1, 25]] | s*****n
发帖数: 994 | 15 2 2 3 和 3 2 2 怎么避免重复打印的？
【在 b*********s 的大作中提到】
: 其实很短就可以写完
: def fac(low, n):
: if n == 1:
: return [[]]
: res = []
: for i in xrange(low, n + 1):
: if n % i == 0:
: head = [i]
: res += [head + tail for tail in fac(i, n / i)]
: return res
| b*********s
发帖数: 115 | 16
我的fac函数里面有个low，在加了3之后，后面加进来的就不能比3小
【在 s*****n 的大作中提到】
: 2 2 3 和 3 2 2 怎么避免重复打印的？
| k****r
发帖数: 807 | 17 楼主大牛拿到G和RF的offer了，能不能上个面经，造福大家啊？
下面是我的code，请指教：
void combinationMultiplyHelper(vector &num, int target, int start,
vector comb, vector> &res) {
if (target == 1) {
res.push_back(comb);
return;
}
for (int i = start; i < num.size(); i++) {
if (target >= num[i] && target % num[i] == 0) {
comb.push_back(num[i]);
combinationMultiplyHelper(num, target/num[i], i, comb, res);
comb.pop_back();
}
}
}
vector> combinationMultiply(int target) {
vector num;
for (int i = 2; i <= target/2; i++) num.push_back(i);
vector comb;
vector> res;
res.push_back({1, target});
combinationMultiplyHelper(num, target, 0, comb, res);
return res;
}
target = 60
res =
1 60
2 2 3 5
2 2 15
2 3 10
2 5 6
2 30
3 4 5
3 20
4 15
5 12
6 10 | f*****e
发帖数: 2992 | 18 class Solution {
public:
void recCompute(int s, int up, vector& vi, vector >& vv
i) {
if(s == 1){
vvi.push_back(vi);
return;
}
for(int i = up; i >= 2; --i){
if(s % i) continue;
else{
vi.push_back(i);
recCompute(s/i, i, vi, vvi);
vi.pop_back();
}
}
}
};
{
【在 k****r 的大作中提到】
: 楼主大牛拿到G和RF的offer了，能不能上个面经，造福大家啊？
: 下面是我的code，请指教：
: void combinationMultiplyHelper(vector &num, int target, int start,
: vector comb, vector> &res) {
: if (target == 1) {
: res.push_back(comb);
: return;
: }
: for (int i = start; i < num.size(); i++) {
: if (target >= num[i] && target % num[i] == 0) {
| c********p
发帖数: 1969 | | x*****0
发帖数: 452 | | f******s
发帖数: 25 | 21 我也遇到这道题了 高频题啊
就是输出non-decreasing的序列来避免重复。
还有一道设计题
点一个amazon.com上的一个link, 弹出一个网页显示商品的信息， 用户的信息，
review的信息。
问怎么设计这样一个系统 |
|
