s*n
2 楼
for number of cards from 1 to 为。, do
for each collection of cards,
if cards number < n,
foreach the rest card c of this collection,
sum = c + sum(collection)
if sum < n, add c union collection into a new collection,
if sum = n, print c union collection,
end foreach
remove the collection from the collection of the collection
end foreach
end for
【在 P*******b 的大作中提到】
: 从一副牌中选n张,使其和为。
: 打印所有结果。
: 要求不能用递归。
: 谁给讲讲思路吧。谢谢
for each collection of cards,
if cards number < n,
foreach the rest card c of this collection,
sum = c + sum(collection)
if sum < n, add c union collection into a new collection,
if sum = n, print c union collection,
end foreach
remove the collection from the collection of the collection
end foreach
end for
【在 P*******b 的大作中提到】
: 从一副牌中选n张,使其和为。
: 打印所有结果。
: 要求不能用递归。
: 谁给讲讲思路吧。谢谢
P*b
3 楼
谢谢回复。再问一下。这里for each collection of cards, 这些collection这么造出
来的?
【在 s*****n 的大作中提到】
: for number of cards from 1 to 为。, do
: for each collection of cards,
: if cards number < n,
: foreach the rest card c of this collection,
: sum = c + sum(collection)
: if sum < n, add c union collection into a new collection,
: if sum = n, print c union collection,
: end foreach
: remove the collection from the collection of the collection
: end foreach
来的?
【在 s*****n 的大作中提到】
: for number of cards from 1 to 为。, do
: for each collection of cards,
: if cards number < n,
: foreach the rest card c of this collection,
: sum = c + sum(collection)
: if sum < n, add c union collection into a new collection,
: if sum = n, print c union collection,
: end foreach
: remove the collection from the collection of the collection
: end foreach
P*l
8 楼
这是那个“数组里两个数和为给定值”问题的扩展版。
觉得枚举每个组合就挺好。比如,52张牌选三张的组合是
1, 1, 1
1, 1, 2
1, 1, 3
。。。
1, 1, 13
1, 2, 2
1, 2, 3
。。。
11, 13, 13
12, 12, 12
12, 12, 13
12, 13, 13
13, 13, 13
如果要选4张牌,使其和为28,就可以通过前三张算出第四张,然后检查是否符合要求。
代码:
http://code.google.com/p/sureinterview/source/browse/test/test1/CombinationTest.java#120
public void testNumComb2() {
// list all combinations of c(7,3)
int suit = 4;
int rank = 13;
int takeN = 3; //4-1=3。
int totalNum = 28;
List numList = new ArrayList();
for (int i = 1; i <= rank; i++) {
for (int j = 0; j < suit; j++) {
numList.add(i);
}
}
Combination comb = new CombinationImpl(numList,
takeN);
for (List cb : comb) {
// System.out.println(StringUtils.join(cb.toArray(), ", "));
int sum = 0;
for (Integer num : cb) {
sum += num;
}
int lastNum = totalNum - sum;
int tk1 = cb.get(takeN - 1);
//检查是否符合要求
if (lastNum <= rank && (lastNum > tk1 || //
((takeN < suit || tk1 == cb.get(takeN - suit)) &&
lastNum == tk1))) {
System.out.print(StringUtils.join(cb.toArray(), ", "));
System.out.println(", " + lastNum);
}
}
}
枚举带重复的组合的代码:
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/CombinationImpl.java#158
看看有问题没有?
觉得枚举每个组合就挺好。比如,52张牌选三张的组合是
1, 1, 1
1, 1, 2
1, 1, 3
。。。
1, 1, 13
1, 2, 2
1, 2, 3
。。。
11, 13, 13
12, 12, 12
12, 12, 13
12, 13, 13
13, 13, 13
如果要选4张牌,使其和为28,就可以通过前三张算出第四张,然后检查是否符合要求。
代码:
http://code.google.com/p/sureinterview/source/browse/test/test1/CombinationTest.java#120
public void testNumComb2() {
// list all combinations of c(7,3)
int suit = 4;
int rank = 13;
int takeN = 3; //4-1=3。
int totalNum = 28;
List
for (int i = 1; i <= rank; i++) {
for (int j = 0; j < suit; j++) {
numList.add(i);
}
}
Combination
takeN);
for (List
// System.out.println(StringUtils.join(cb.toArray(), ", "));
int sum = 0;
for (Integer num : cb) {
sum += num;
}
int lastNum = totalNum - sum;
int tk1 = cb.get(takeN - 1);
//检查是否符合要求
if (lastNum <= rank && (lastNum > tk1 || //
((takeN < suit || tk1 == cb.get(takeN - suit)) &&
lastNum == tk1))) {
System.out.print(StringUtils.join(cb.toArray(), ", "));
System.out.println(", " + lastNum);
}
}
}
枚举带重复的组合的代码:
http://code.google.com/p/sureinterview/source/browse/src/lib/combination/CombinationImpl.java#158
看看有问题没有?
相关阅读
Rocket Fuel一题请问这个statement是不是意味着辞职不需要14天notice? (转载)拜早年,祝大家码到成功申请了Post-Completion OPT,假如拿不到学位怎么办?onsite面试对loafer, oxford有这么讲究不?关于推荐人的问题找工作压力大啊关于找工作的经验教训full stack马工算个几把毛,还不是被你们嘲笑的臭教书的管着 (转载)fireeye 招人, senior level〔招聘〕Data Migration Analyst 和 BI Report Developer (转载)求问Facebook最近招人情况?能否再发一次email询问?薪水的讨价还价Amazon intern大概多久出结果google hardware 面试应该怎么准备?求指教。accounting找工作谁能预测下今年H1B形势?打算quit晚年PHD,找工作