2

我正在解决这个问题,我的解决方案似乎适用于我可以想象尝试的所有案例,并且在 3 秒的时间限制内完成,但是当我在线提交时它仍然超过 3 秒。我认为一定有一种情况导致这个while循环无限期地进行:

while (!equals(availableChars, testChars)){
        next = getNextAlphaString(high, next, availableChars, it);      
        fillCharSet(next, testChars);       
    }

但我已经测试了我的功能,但我无法弄清楚它是什么......希望你们能看到一些东西。以下是辅助函数:

bool equals(multiset<char>& availableChars, multiset<char>& test){  
    multiset<char>::iterator it;
    for (it = availableChars.begin(); it != availableChars.end(); it++){
        if ((int)availableChars.count(*it) != (int)test.count(*it)) return false;
    }
    return true;
}

*

string getNextAlphaString(char& high, string next, multiset<char>& availableChars, multiset<char>::iterator& it){   
for (int i=next.size()-1; i>=0; i--){

    if (next[i] != high){
        it = availableChars.find(next[i]); 
        while(*it == next[i]){
            it++;           
            if (it == availableChars.end()){it = availableChars.begin(); break;}
        }
        next[i] = *it;
        break;}
    else{
        it = availableChars.begin();
        next[i] = *it;
    }       
}
return next;
}

*

void fillCharSet(string in, multiset<char>& chars){
    chars.clear();
    for (int i=0; i<in.size(); i++){chars.insert(in[i]);}
}
4

2 回答 2

1

这是一篇使用 GDB 检测无限循环的文章:

http://www.unknownroad.com/rtfm/gdbtut/gdbinfloop.html

希望这可以帮助您解决问题。

于 2012-06-22T00:30:10.697 回答
0

好吧……我来回答我自己的问题。我用 next_permutation 重写了它,它变得更加简单和高效。我仍然没有用其他解决方案解决实际的循环问题,但现在我不需要了。谢谢大家的提示:)

于 2012-06-23T00:29:07.943 回答