algorithm - 给定一个数字列表，找到所需的最小交换次数，以便没有两个相邻元素相同

Question

这个问题是在谷歌现场采访中提出的。关联

我能够想出一个蛮力解决方案，我将枚举所有n!安排和所有有效安排，我将计算该安排所需的最小互换。

class Solution{
private:
    bool check(const string&str){
        return (adjacent_find(begin(str),end(str))==end(str));
    }
public:
    void minimumSwaps(string &str,int &ansSwaps,int swaps=0,int idx=0)
    {
        if(check(str)){
            ansSwaps=min(ansSwaps,swaps);
        }
        for(int i=idx;i<str.length();i++)
        {
            for(int j=i+1;j<str.length();j++)
            {
                swap(str[i],str[j]);
                minimumSwaps(str,ansSwaps,swaps+1,i+1);
                swap(str[i],str[j]);
            }
        }
    }
};

由于在采访中提出了这个问题，我假设这有一个更好的时间复杂度解决方案，以贪婪或图形相关概念的形式，但无法解决任何问题。

关于 codeforces 的讨论：https ://codeforces.com/blog/entry/53781

标签： algorithmdata-structures