Question

我想请所有我的编程伙伴只谈“效率” 。我目前正在解决在面试中可以问到的问题,我遇到了一个著名的string 的变相。下面我所写的代码可能是编程史上最常用的代码,但是,我不知道它是什么状态,因为我还没有检查任何解决方案。

长长的故事是,下面我所编的短程序会是一个合适的解决方案吗?或者它能更有效率。问是因为如果有一天我出现,我想确定我是否实施了解决这一问题的最佳方法之一。

#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}

Answer 1

我通过使用 std::map 找到解决方案。不要认为 效率低;

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}
int main(int argc, const char * argv[])
{
    string str="aabb";
    int limit=fac(str.size());
    int mod=str.size();
    std::map<string,bool>T;
    vector<string>permutations;
    for(int i=0;i<limit;i++){
        if(T[str]==0){
            permutations.push_back(str);
            T[str]=1;
        }
        swap(str[i%mod],str[(i+1)%mod]);
    }
    for(int i=0;i<permutations.size();i++)
        cout<<permutations[i]<<endl;
    return 0;
}

Answer 2

不处理字符串中重复的字母, 例如 "aaaabbb" 。

Answer 3

您可以使用循环 :

#include <iostream>
#include <tchar.h>
#include <string>

using namespace std;

void swap(char &first, char &second) {
    char tmp = first;
    first = second;
    second = tmp;
}

void enumPermutations(string &p, int m)
{
    if (m == p.size() - 1)
        cout << p << endl;
    else
        for (int j = m; j < p.size(); j++) {
            swap(p[j], p[m]);
            enumPermutations(p, m+1);
            swap(p[j], p[m]);
        }
}

int _tmain(int argc, _TCHAR* argv[])
{
    string str = "abcd";
    enumPermutations(str, 0);
    getchar();
    return 0;
}

(在视觉工作室编写和测试)。

Answer 4

您问题的答案是“ 强势” 。您不应担心任何拟议解决方案的效率, 直到您知道它有效。而这个无效。

下文说明了这一事实。

ben-tillys-macbook-pro:ton btilly$ cat foo.cc
#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}
ben-tillys-macbook-pro:ton btilly$ g++ foo.cc
ben-tillys-macbook-pro:ton btilly$ ./a.out | wc
      24      24     120
ben-tillys-macbook-pro:ton btilly$ ./a.out | sort -u | wc
      12      12      60
ben-tillys-macbook-pro:ton btilly$ ./a.out | grep bdc
ben-tillys-macbook-pro:ton btilly$

友情链接