本文共 6839 字，大约阅读时间需要 22 分钟。
N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.
The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).
The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.
思路：
题意大致为：给你N对数，通过一系列swap之后，使得在每对数中，一个数为偶数，另一个数比它大1。求需要的swap的次数。
题目归类为graph，然而直接的解题方法比图的方法更容易想到：用队列的思想，如果队头的一对数满足要求，直接pop，否则找到一个合适的数对，与之swap(可能swap之后两对数都满足要求，也可能只有对头满足要求)，计数加一，再pop。代码如下：
class Solution {public: int minSwapsCouples(vector & row) { int count = 0; while(!row.empty()) { if(row[0]%2==0 && row[1]==row[0]+1 || row[1]%2==0 && row[0]==row[1]+1) { pop(row, 0); } else { if(row[0]%2 == 0) { int i; for(i = 0; i < row.size(); i++) if(row[i] == row[0]+1) break; swap(1, i, row); pop(row,0); count++; } else { int i; for(i = 0; i < row.size(); i++) if(row[i] == row[0]-1) break; swap(1, i, row); pop(row,0); count++; } } } return count; } void pop(vector & row, int p) { auto i = row.begin()+p; row.erase(i); row.erase(i); } void swap(int a, int b, vector & row) { int t = row[a]; row[a] = row[b]; row[b] = t; }}; 那么如何用图的思路来做呢？首先将原始的每个数对看做一个结点，如果两个数对通过交换能够使得其中的一个或者两个数对满足条件，结点之间连一条边，最终形成一个无向图。swap的次数即为边的个数减去环的个数。(环中的边数比处理环中的数对需要的次数多一)。
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.
For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".
Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.
思路：每个字符串作为一个结点，如果两个字符串是“相似”的，那么两个结点相连。题目也就是让我们求其中连通图的数量。常规的方法就是构建邻接表，DFS出所有连通图（效率比较低，beat 15），代码如下：
class Solution {public: int numSimilarGroups(vector & A) { map 另外，这一题可以使用并查集(或union-find)来解决问题。
并查集：
一种数据结构，将一个集合分为不相交的子集，在添加新的子集，合并现有子集，判断元素所在集合时时间复杂度接近常数级。常用于求连通子图和最小生成树的Kruskal算法。
操作：
makeSet: 初始化，给每个元素分配一个特定的id，以及一个指向自己的指针，表示每个元素都在一个大小为1的集合当中。
find： 查找某个元素的根元素。当两个元素拥有同样的根元素时，说明他们在同一个集合当中。为了使得时间复杂度接近常数级，在查找的过程中，可以更新指针指向根元素(代码中使用递归方法)，有人称其为路径压缩。
Union: 满足条件则合并两个子集。如果没有特殊要求，将一个集合的根指向另一个集合的根即可。也可根据秩或者集合的大小来指定。
所以对于这一题，我们建立一个并查集，子集的数量就是连通子图的数量，也就是需要的group的数量。效率得到提高(beat 75)
代码如下：
class Solution {public: int numSimilarGroups(vector & A) { int size = A.size(); vector next(size); makeSet(next); int s = size; for(int i = 0; i < s-1; i++) { for(int j = i+1; j < s; j++) { if(connect(A[i], A[j])) { unionSet(i, j, next, size); } } } return size; } bool connect(string& a, string& b) { int count = 0; for(int i = 0; i < a.length(); i++) if(a[i] != b[i]) count++; return count==2||count==0; } void makeSet(vector & next) { int j = 0; for(auto& i:next) i = j++; } void unionSet(int i, int j, vector & next, int& size) { int root_i = find(i, next), root_j = find(j, next); if(root_i != root_j) { next[root_i] = root_j; size--; } } int find(int i, vector & next) { if(i != next[i]) next[i] = find(next[i], next); return next[i]; }}; Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.
Given two anagrams A and B, return the smallest K for which A and B are K-similar.
思路：尝试使用贪心算法。策略为：替换只在不符合的字母之间进行，如果一次替换使得两个不符合的数同时符合，这个替换优先执行。然而，行不通，只通过了一半的测例。如"aabbccddee" "cdacbeebad"就无法通过。显然，某次替换会对之后的替换产生潜在影响。那……就用DFS把所有情况找出来，找出最小K的方案吧（暴力求解）。代码如下：
class Solution {private: int size; int new_size; int result;public: int kSimilarity(string A, string B) { this->size = A.length(); string a, b; for(int i = 0; i < this->size; i++) { if(A[i] != B[i]) { a.push_back(A[i]); b.push_back(B[i]); } } this->new_size = a.length(); if(this->new_size == 0) return 0; this->result = INT_MAX; DFS(a, b, 0, 0); return this->result; } void DFS(string a, string b, int p, int k) { if(p == this->new_size-1) { this->result = min(this->result, k); return; } if(a[p] == b[p]) { DFS(a, b, p+1, k); return; } for(int j = p+1; j < this->new_size; j++) { if(a[p] == b[j]) { swap(b[p], b[j]); DFS(a, b, p+1, k+1); swap(b[p], b[j]); } } } void swap(char& a, char& b) { char t = a; a = b; b = t; }}; 另外，还可以通过存储已经计算过的经过某些交换后的串的K值来避免重复计算，进而提高效率。
转载地址：http://eggab.baihongyu.com/