D***r 发帖数: 7511 | 1 电话面试遇到一道题
给两个整数M,N, 求抛N次硬币有M个head的所有输出
比如2, 3
输出是HHT, HTH, THH | z*******o 发帖数: 4773 | | d******b 发帖数: 73 | 3 S(h, t) =
"H" + S(h - 1, t - 1) union "T" + S(h, t - 1) if (h < t)
"HH...H" (h times) if (h = t)
empty if (h > t) | T******e 发帖数: 157 | | d******b 发帖数: 73 | 5 shut up and show me the code
using namespace std;
vector S(int h, int t) {
vector result;
if (h == 0) {
string s;
for (int i = 0; i < t; i++) s += "T";
result.push_back(s);
} else if (h == t) {
string s;
for (int i = 0; i < h; i++) s += "H";
result.push_back(s);
} else if (h < t){
for (string s : S(h - 1, t - 1))
result.push_back("H" + s);
for (string s : S(h, t - 1))
result.push_back("T" + s);
}
return result;
}
int main() {
for(string s : S(2, 5))
cout << s << endl;
} | n******n 发帖数: 12088 | 6 求长度为n的0/1串里有m个1。
【在 D***r 的大作中提到】 : 电话面试遇到一道题 : 给两个整数M,N, 求抛N次硬币有M个head的所有输出 : 比如2, 3 : 输出是HHT, HTH, THH
| t*********r 发帖数: 387 | | y******s 发帖数: 92 | 8 难道不是 Cn(m) = n!/(m!*(n-m)!) ?
【在 D***r 的大作中提到】 : 电话面试遇到一道题 : 给两个整数M,N, 求抛N次硬币有M个head的所有输出 : 比如2, 3 : 输出是HHT, HTH, THH
| s******x 发帖数: 417 | 9 static ArrayList HeadTail(int m, int n)
{
ArrayList result = new ArrayList<>();
makeheadtail(result, new StringBuilder(), m, n-m);
return result;
}
private static void makeheadtail(ArrayList result, StringBuilder
sb, int head, int tail)
{
if((head == 0) && (tail == 0))
{
String temp = sb.toString();
result.add(temp);
return;
}
if(head == 0)
{
sb.append("T");
makeheadtail(result, sb, head, tail -1);
sb.deleteCharAt(sb.length()-1);
}
else if(tail == 0)
{
sb.append("H");
makeheadtail(result, sb, head-1, tail);
sb.deleteCharAt(sb.length()-1);
}
else
{
sb.append("T");
makeheadtail(result, sb, head, tail-1);
sb.deleteCharAt(sb.length()-1);
sb.append("H");
makeheadtail(result, sb, head-1, tail);
sb.deleteCharAt(sb.length()-1);
}
} | t****i 发帖数: 88 | 10 用java大概写了一下, recursion的思路,
void getCoinSequence(ArrayList result, String currSeq, int N, int M,
int numHeadsInCurrSeq) {
//invalid input
if(M > N) {
return null;
}
//end cases with no chance to get M heads
if(N-currSeq.length() < M - numHeadsInCurrSeq || numHeadsInCurrSeq > M)
{
return;
}
if (currSeq.length() == N && numHeadsInCurrSeq == M) {
result.add(currSeq)
return;
}
getCoinSequence(result, currSeq+"T", N, M, numHeadsInCurrSeq);
getCoinSequence(result, currSeq+"H", N, M, numHeadsInCurrSeq + 1);
}
调用的话,就是getCoinSequence( result, "", N, M, 0) | s*******7 发帖数: 6 | |
|