问题描述

给定两个等长字符串A和B，它们所含的字符个数及种类完全一样，问最少需要对A执行多少次交换字符才能使得A变成B？

分析

因为这个问题数据规模很小，只包含6种字符、A和B的长度都不超过20，所以暴力+适当剪枝的思路就能够通过。

首先对于A[i]==B[i]的部分，完全不需要做任何处理；

其次，对于A[i]!=B[i]的部分，显然需要找A[j]来跟A[i]进行交换，A[j]满足A[j]==B[i]。在这个过程中，如果A[i]==B[j]，那自然是“意外之喜”，“一箭双雕”，“一石二鸟”。可以很自信的想：如果能够一箭双雕，必然是最优策略。但是，如果没有“一箭双雕”，那就只能逐个尝试寻找最优的 j 了。假设就选择了j，交换完后得到新的字符串A'，可以递归调用求solve(A’，B)。

在这个递归过程中，因为B是不变的，这个函数只要A确定，返回值就定下来了。所以可以用备忘录方法（记忆化搜索）来加速递归。

站在更宏观的角度考虑这个问题，把每个A字符串当做结点，每一次swap操作会形成新的结点并添加一条边，以上递归的过程相当于深度优先搜索。如果改写成广度优先搜索，运行效率必定能够提高。

站在更宏观的角度考虑这个问题，这是一个很艰难的图论问题。问题等价于寻找有向图的边的一个覆盖，使得每一个子集都是环，要使环数最大。这个问题似乎是个NP问题。

但是贪心的方式足以通过此题。

贪心法则如下：

选择每个顶点的最小环构成一个最小环集合，对此集合执行去重操作。

如果环集合中存在结点数为1的环，必然选择之。

如果环集合中存在结点数为2的环，必然选择之。

否则，执行以下步骤。

对于这个环集合，统计图中边的使用次数。

对每个环，求它边的平均使用次数作为这个环的value。

优先消去value最小的环

这个问题等价于：

给定一个可以包含重复元素的数组，最少需要执行多少次swap操作，才能使数组变得有序。

C++递归写法

class Solution {public:    unordered_map
    
      mp;    int kSimilarity(string A, string B) {        if(A

pos; while(j

Java非递归写法

class Solution {    public int kSimilarity(String A, String B) {        if (A.equals(B)) return 0;        Set
    
      vis= new HashSet<>();        Queue
     
       q= new LinkedList<>();        q.add(A);        vis.add(A);        int res=0;        while(!q.isEmpty()){            res++;            for (int sz=q.size(); sz>0; sz--){                String s= q.poll();                int i=0;                while (s.charAt(i)==B.charAt(i)) i++;                for (int j=i+1; j

Java贪心法

import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.*;import java.util.stream.Collectors;class Solution {/** * 构图，构完图之后，两个字符串就可以丢掉了 */int[][] buildGraph(char[] a, char[] b) {    TreeMap
    
      ma = new TreeMap<>();    for (char i : a) {        if (!ma.containsKey(i)) {            ma.put(i, ma.size());        }    }    for (char j : b) {        if (!ma.containsKey(j)) {            ma.put(j, ma.size());        }    }    int g[][] = new int[ma.size()][ma.size()];    for (int i = 0; i < a.length; i++) {        int from = ma.get(b[i]), to = ma.get(a[i]);        g[from][to] += 1;    }    return g;}/** * 计算结点node的出度 */int outEdge(int node, int[][] g) {    return Arrays.stream(g[node]).sum();}int[][] copyGraph(int[][] g) {    int[][] a = new int[g.length][g.length];    for (int i = 0; i < g.length; i++) {        for (int j = 0; j < g.length; j++) {            a[i][j] = g[i][j];        }    }    return a;}/** * 寻找node结点所在的最小环 */List
     
      
       > findMinRingOf(int node, int[][] g) {    g = copyGraph(g);    List
       
        
         > rings = new LinkedList<>();    while (outEdge(node, g) > 0) {        int[] prev = new int[g.length];//记录最小环的路径        Arrays.fill(prev, -1);        Queue
         
           q = new LinkedList<>(); q.add(node); out: while (!q.isEmpty()) { Integer i = q.poll(); for (int j = 0; j < g[i].length; j++) { if (g[i][j] > 0) { if (prev[j] != -1) continue;//已经访问过了就不再访问了 prev[j] = i; q.add(j);//准备扩展j结点 if (j == node) {//找到了 break out; } } } } ArrayList
          
            a = new ArrayList<>(g.length); a.add(node); int now = node; while (true) { int next = prev[now]; if (next == node) break; a.add(next); now = next; } //翻转数组 for (int i = 0; i < a.size() >> 1; i++) { int temp = a.get(i); a.set(i, a.get(a.size() - 1 - i)); a.set(a.size() - 1 - i, temp); } if (rings.isEmpty() || rings.get(0).size() == a.size()) { rings.add(a); } else { break; } removeRing(a, g); } return rings;}/** * 用完一个环之后，把环删除 */void removeRing(List
           
             ring, int[][] g) { for (int i = 0; i < ring.size(); i++) { g[ring.get(i)][(ring.get((i + 1) % ring.size()))]--; }}/** * 贪心寻找图中最优环 */List
            
              findMinRing(int[][] g) { List
             
              
               > rings = new LinkedList<>();//全部环构成的集合 for (int i = 0; i < g.length; i++) { if (outEdge(i, g) > 0) { List
               
                
                 > r = findMinRingOf(i, g); rings.addAll(r); } } //去重 Set
                 
                   had = new TreeSet<>(); LinkedList
                  
                   
                    > uniqRings = new LinkedList<>(); for (List
                    
                      ring : rings) { String k = ring.stream().sorted().map(x -> x + "").collect(Collectors.joining(",")); if (!had.contains(k)) { had.add(k); uniqRings.add(ring); } } rings = uniqRings; //统计每条边的使用次数 double[][] use = new double[g.length][g.length]; for (List
                     
                       ring : rings) { for (int j = 0; j < ring.size(); j++) { use[ring.get(j)][ring.get((j + 1) % ring.size())]++; } } rings.sort(Comparator.comparing(x -> { if (x.size() == 1) return -1.0;//优先级最高 if (x.size() == 2) return 0.0;//优先级次高 double s = 0; for (int i = 0; i < x.size(); i++) { s += use[x.get(i)][x.get((i + 1) % x.size())]; } s /= x.size(); return s; })); if (rings.size() == 0) return null; return rings.get(0);}public int kSimilarity(String A, String B) { char[] a = A.toCharArray(), b = B.toCharArray(); int[][] g = buildGraph(a, b); int N = a.length; while (true) { List
                      
                        ring = findMinRing(g); if (ring == null) break; N--; removeRing(ring, g); } return N;}public static void main(String[] args) { try { Scanner cin = new Scanner(new FileInputStream("in.txt")); System.out.println(new Solution().kSimilarity(cin.next(), cin.next())); } catch (FileNotFoundException e) { e.printStackTrace(); }}}

转载地址：http://wdyca.baihongyu.com/

你可能感兴趣的文章