d*****v 发帖数: 72 | 1 发个第一轮电面的面经,为第二轮攒rp了
两道题
打印一个数的所有乘数组合,从大到小,不要有重复
merge interval |
f*******w 发帖数: 1243 | |
w*****5 发帖数: 75 | 3 lz能详细说说merge interval这个吗?我看之前的面经给的是add interval和
getTotalLength,和merge interval还是有点区别的。比如那个面试官不让sort。 |
l*****a 发帖数: 14598 | 4 不让sort就是insert interval了
【在 w*****5 的大作中提到】 : lz能详细说说merge interval这个吗?我看之前的面经给的是add interval和 : getTotalLength,和merge interval还是有点区别的。比如那个面试官不让sort。
|
l*****a 发帖数: 14598 | 5 24=2*2*2*3
=2*3*4
=2*12
=3*8
=4*6
【在 f*******w 的大作中提到】 : 第一题没看懂。什么叫乘数组合?
|
f*******w 发帖数: 1243 | |
l*****a 发帖数: 14598 | 7 我写的是从小到大
【在 f*******w 的大作中提到】 : 所以是因式分解?那什么叫从大到小,按个数排序?
|
r*******e 发帖数: 971 | 8 你第一轮面完之后过了多久有第二轮啊?
【在 d*****v 的大作中提到】 : 发个第一轮电面的面经,为第二轮攒rp了 : 两道题 : 打印一个数的所有乘数组合,从大到小,不要有重复 : merge interval
|
d********w 发帖数: 363 | 9 这第一题是我出的,不好意思,让你费心
【在 d*****v 的大作中提到】 : 发个第一轮电面的面经,为第二轮攒rp了 : 两道题 : 打印一个数的所有乘数组合,从大到小,不要有重复 : merge interval
|
r*******e 发帖数: 971 | 10 这道题的标准解法是啥?从平方向下递归么?
【在 d********w 的大作中提到】 : 这第一题是我出的,不好意思,让你费心
|
|
|
x********k 发帖数: 256 | 11 是要求factor降序,要求第一个factor从大到小么?如果是你这个倒过来也不对啊。
应该12*2排第一个?
然后8*3,6*4这样。
【在 l*****a 的大作中提到】 : 24=2*2*2*3 : =2*3*4 : =2*12 : =3*8 : =4*6
|
c********6 发帖数: 33 | 12 List> factorCombination(int n) {
List> result = new ArrayList>();
dfs(n, 2, result, new ArrayList());
return result;
}
void dfs(int n, int start, List> result, List sub
) {
if(n == 1) {
result.add(new ArrayList(sub));
return;
}
for(int i = start; i <= n; i++) {
if(n % i != 0) continue;
if(i == n && sub.isEmpty()) continue;
sub.add(i);
dfs(n / i, i, result, sub);
sub.remove(sub.size() - 1);
}
}
求指点,这样的代码能过么?
【在 d********w 的大作中提到】 : 这第一题是我出的,不好意思,让你费心
|
l********g 发帖数: 372 | |
r*******e 发帖数: 971 | 14 方法不错啊。
sub
【在 c********6 的大作中提到】 : List> factorCombination(int n) { : List> result = new ArrayList>(); : dfs(n, 2, result, new ArrayList()); : return result; : } : void dfs(int n, int start, List> result, List sub : ) { : if(n == 1) { : result.add(new ArrayList(sub)); : return;
|
r*******e 发帖数: 971 | 15 我改了一下,这要不过不了也没办法了,不用recursion实在麻烦。
public List> getFactorCombination(int n) {
List> result = new ArrayList<>();
getFactorCombinationHelper(n, n/2, result, new ArrayList());
return result;
}
private void getFactorCombinationHelper(int n, int start, List
> result, List sub) {
if(n==1) {
result.add(new ArrayList(sub));
return;
}
for(int i = start; i >= 2; i--) {
if(n % i != 0) continue;
sub.add(i);
getFactorCombinationHelper(n / i, i, result, sub);
sub.remove(sub.size() - 1);
}
}
sub
【在 c********6 的大作中提到】 : List> factorCombination(int n) { : List> result = new ArrayList>(); : dfs(n, 2, result, new ArrayList()); : return result; : } : void dfs(int n, int start, List> result, List sub : ) { : if(n == 1) { : result.add(new ArrayList(sub)); : return;
|
d*****v 发帖数: 72 | 16 发个第一轮电面的面经,为第二轮攒rp了
两道题
打印一个数的所有乘数组合,从大到小,不要有重复
merge interval |
f*******w 发帖数: 1243 | |
w*****5 发帖数: 75 | 18 lz能详细说说merge interval这个吗?我看之前的面经给的是add interval和
getTotalLength,和merge interval还是有点区别的。比如那个面试官不让sort。 |
l*****a 发帖数: 14598 | 19 不让sort就是insert interval了
【在 w*****5 的大作中提到】 : lz能详细说说merge interval这个吗?我看之前的面经给的是add interval和 : getTotalLength,和merge interval还是有点区别的。比如那个面试官不让sort。
|
l*****a 发帖数: 14598 | 20 24=2*2*2*3
=2*3*4
=2*12
=3*8
=4*6
【在 f*******w 的大作中提到】 : 第一题没看懂。什么叫乘数组合?
|
|
|
f*******w 发帖数: 1243 | 21 所以是因式分解?那什么叫从大到小,按个数排序? |
l*****a 发帖数: 14598 | 22 我写的是从小到大
【在 f*******w 的大作中提到】 : 所以是因式分解?那什么叫从大到小,按个数排序?
|
r*******e 发帖数: 971 | 23 你第一轮面完之后过了多久有第二轮啊?
【在 d*****v 的大作中提到】 : 发个第一轮电面的面经,为第二轮攒rp了 : 两道题 : 打印一个数的所有乘数组合,从大到小,不要有重复 : merge interval
|
d********w 发帖数: 363 | 24 这第一题是我出的,不好意思,让你费心
【在 d*****v 的大作中提到】 : 发个第一轮电面的面经,为第二轮攒rp了 : 两道题 : 打印一个数的所有乘数组合,从大到小,不要有重复 : merge interval
|
r*******e 发帖数: 971 | 25 这道题的标准解法是啥?从平方向下递归么?
【在 d********w 的大作中提到】 : 这第一题是我出的,不好意思,让你费心
|
x********k 发帖数: 256 | 26 是要求factor降序,要求第一个factor从大到小么?如果是你这个倒过来也不对啊。
应该12*2排第一个?
然后8*3,6*4这样。
【在 l*****a 的大作中提到】 : 24=2*2*2*3 : =2*3*4 : =2*12 : =3*8 : =4*6
|
c********6 发帖数: 33 | 27 List> factorCombination(int n) {
List> result = new ArrayList>();
dfs(n, 2, result, new ArrayList());
return result;
}
void dfs(int n, int start, List> result, List sub
) {
if(n == 1) {
result.add(new ArrayList(sub));
return;
}
for(int i = start; i <= n; i++) {
if(n % i != 0) continue;
if(i == n && sub.isEmpty()) continue;
sub.add(i);
dfs(n / i, i, result, sub);
sub.remove(sub.size() - 1);
}
}
求指点,这样的代码能过么?
【在 d********w 的大作中提到】 : 这第一题是我出的,不好意思,让你费心
|
l********g 发帖数: 372 | |
r*******e 发帖数: 971 | 29 方法不错啊。
sub
【在 c********6 的大作中提到】 : List> factorCombination(int n) { : List> result = new ArrayList>(); : dfs(n, 2, result, new ArrayList()); : return result; : } : void dfs(int n, int start, List> result, List sub : ) { : if(n == 1) { : result.add(new ArrayList(sub)); : return;
|
r*******e 发帖数: 971 | 30 我改了一下,这要不过不了也没办法了,不用recursion实在麻烦。
public List> getFactorCombination(int n) {
List> result = new ArrayList<>();
getFactorCombinationHelper(n, n/2, result, new ArrayList());
return result;
}
private void getFactorCombinationHelper(int n, int start, List
> result, List sub) {
if(n==1) {
result.add(new ArrayList(sub));
return;
}
for(int i = start; i >= 2; i--) {
if(n % i != 0) continue;
sub.add(i);
getFactorCombinationHelper(n / i, i, result, sub);
sub.remove(sub.size() - 1);
}
}
sub
【在 c********6 的大作中提到】 : List> factorCombination(int n) { : List> result = new ArrayList>(); : dfs(n, 2, result, new ArrayList()); : return result; : } : void dfs(int n, int start, List> result, List sub : ) { : if(n == 1) { : result.add(new ArrayList(sub)); : return;
|
|
|
r******j 发帖数: 92 | 31 这种解法的复杂度如何计算呢?
));
Integer>
【在 r*******e 的大作中提到】 : 我改了一下,这要不过不了也没办法了,不用recursion实在麻烦。 : public List> getFactorCombination(int n) { : List> result = new ArrayList<>(); : getFactorCombinationHelper(n, n/2, result, new ArrayList()); : return result; : } : private void getFactorCombinationHelper(int n, int start, List : > result, List sub) { : if(n==1) { : result.add(new ArrayList(sub));
|
r*******e 发帖数: 971 | 32 没法算,考虑最坏情况与最好情况。最坏情况我得想想,最好不用想大家都知道了。
【在 r******j 的大作中提到】 : 这种解法的复杂度如何计算呢? : : )); : Integer>
|
g********r 发帖数: 89 | 33 mark
【在 d*****v 的大作中提到】 : 发个第一轮电面的面经,为第二轮攒rp了 : 两道题 : 打印一个数的所有乘数组合,从大到小,不要有重复 : merge interval
|
g********r 发帖数: 89 | 34 recursive基本上就是这样了,不过既factorization是降序,这句话可以optimize一下
getFactorCombinationHelper(n / i, i, result, sub);
--》
getFactorCombinationHelper(n / i, min(n/i, i), result, sub);
));
Integer>
【在 r*******e 的大作中提到】 : 我改了一下,这要不过不了也没办法了,不用recursion实在麻烦。 : public List> getFactorCombination(int n) { : List> result = new ArrayList<>(); : getFactorCombinationHelper(n, n/2, result, new ArrayList()); : return result; : } : private void getFactorCombinationHelper(int n, int start, List : > result, List sub) { : if(n==1) { : result.add(new ArrayList(sub));
|
g********r 发帖数: 89 | 35 大牛是不是漏了个6*2*2?
【在 l*****a 的大作中提到】 : 24=2*2*2*3 : =2*3*4 : =2*12 : =3*8 : =4*6
|
l********s 发帖数: 358 | |
j**********3 发帖数: 3211 | |
r*******e 发帖数: 971 | 38 善
【在 g********r 的大作中提到】 : recursive基本上就是这样了,不过既factorization是降序,这句话可以optimize一下 : getFactorCombinationHelper(n / i, i, result, sub); : --》 : getFactorCombinationHelper(n / i, min(n/i, i), result, sub); : : )); : Integer>
|
h***s 发帖数: 45 | 39 比较经典,和小李的Combination Sum是一类题,也可以变化出乘数不能重复的。
));
Integer>
【在 r*******e 的大作中提到】 : 我改了一下,这要不过不了也没办法了,不用recursion实在麻烦。 : public List> getFactorCombination(int n) { : List> result = new ArrayList<>(); : getFactorCombinationHelper(n, n/2, result, new ArrayList()); : return result; : } : private void getFactorCombinationHelper(int n, int start, List : > result, List sub) { : if(n==1) { : result.add(new ArrayList(sub));
|
w*******s 发帖数: 96 | 40 import java.util.ArrayList;
import java.util.List;
public class FactorTest {
List> getFactor(int n) {
List> result = new ArrayList<>();
List path = new ArrayList<>();
dfs(n, n / 2, path, result);
return result;
}
private void dfs(int n, int start, List path, List
>> result) {
if (n == 1) {
result.add(new ArrayList(path));
return;
}
for (int i = start; i > 1; i--) {
if (n % i != 0) {
continue;
}
path.add(i);
dfs(n / i, Math.min(n / i, i), path, result);
path.remove(path.size() - 1);
}
}
} |
|
|
w*****t 发帖数: 485 | 41 除第一个值,后面的都需要分解到因子吗?
比如24 = 6 * 4 还是 6 * 2 * 2 ?
24分解:
24 * 1
12 * 2
8 * 3
6 * 2 * 2 (or 6 * 4)
4 * 3 * 2
3 * 2 * 2 * 2
另外谁能写个非递归的出来? |
f**********t 发帖数: 1001 | 42 // 打印一个数的所有乘数组合,从大到小,不要有重复
void allMultiply(unsigned n, unsigned mn = 2) {
static vector factors;
for (unsigned i = mn; i <= n / 2; ++i) {
if (n % i == 0) {
factors.push_back(i);
allMultiply(n / i, i);
factors.pop_back();
}
}
if (!factors.empty() && n >= mn) {
factors.push_back(n);
for_each(factors.begin(), factors.end(), [](unsigned x) {
cout << x << ' ';
});
factors.pop_back();
cout << endl;
} |
t******5 发帖数: 30 | |