主要内容
- 问题的分析与划归
- 排序算法映射,算法解析
- 不考虑重复字符串的实现代码
最近在传智论坛遇到一个算法的问题,想了一下,有一个我认为比较有趣的解法. 下面算 法或许不是最优的,但是可以参考一下.
问题:
=======================================================================
给定两个字符串,仅由小写字母组成,它们包含了相同字符。求把第一个字符串变
成第二个字符串的最小操作次数,且每次操作只能对第一个字符串中的某个字符移
动到此字符串中的开头。
例如给定两个字符串“abcd" "bcad" ,输出:2,因为需要操作2次才能把"abcd"变
成“bcad" ,方法是:abcd->cabd->bcad。
我开始用广度优先搜索做。可是比如abcdefg 和 gfedcba 递归下去就是7的7次方的
时间复杂度 然后再在变换位置的函数里循环 循环次数报表。
然后我用List记录 abcdefg出现的东东 把重复的去掉了,也就是7*6*5*4*3*2
但是每次判断list.contain()在内部貌似又要循环时间和上面差不多.
有没有比较好的解决方式.
========================================================================
这个问题比较有趣,这里我使用C#来完成,主要是考虑微软提供了许多数据结构 不用再重新实现数据结构和相关方法了.
问题分析
开始拿到这个问题,先分析一下需要做的事儿:就是将一个字符串,变成一个指 定的字符串. 抽象一下,将目标字符串看成一个有序集的结构,可以重新一个有序集.
再将原来的字符串看成一个等待排序的数据结构,就可以将问题简化为简单的排序算
法了. 即:指定序的排序问题.
举个例子:将字符串"abcd"变成"bcad".
那么字符集"bcad"构成一个有序集,可以得到映射表,如下:
{ ('b', 0), ('c', 1), ('a', 2), ('d', 3) }
因此需要排序的字符串就变成了一个数字集:{ 2, 0, 1, 3 }. 即
需要将这个数据集排序为 { 0, 1, 2, 3 },需要求最小的步骤. 因
此将问题转化为排序最小步骤问题.
另一方面,问题考虑了算法实现的要求,即每次只能将一个数据
取出,插入到开始的地方. 也就是说具体操作就是一个固定的函数:
将第i项插入到0项,原来前i-1项的数据依次后移一位. 故方法很简单:
1 // 注意到需要处理的是字符串,由于字符串是不可变的 2 // 这里考虑使用字符数组 3 public void jk_remove(char[] s, int index) { 4 char temp = s[index]; 5 for (int i = index - 1; i >= 0; i--) { 6 s[i + 1] = s[i]; 7 } 8 s[0] = temp; 9 }
那么这个函数调用几次,就表示操作了几次.
下面考虑另一个问题. 就是什么时候调用这个函数. 也就是如何操作才算是较优.
这个问题有点麻烦. 起初我打算从现成的算法中找一个. 不过现成的都不太友好. 想到
了使用"逆序"的方法.
所谓最少的步骤. 就是不要移动多余的步骤. 在前面已经提到,问题已经划归成排
序问题,下面姑且使用升序.
要将一个数字序列排序,又只能将数据往前放,那么最小的步骤就是每次移动一个
数据并且这个数据就是一个良序的,也就是说这个数字不会再次移动. 那么一个长度为
n的字符串,最多移动n-1次. 我想这个应该是最少的步骤了吧!!!
下面看看怎么移动会比较好.
首先考虑移动的特征就是每次移动数据都放在最开始的地方. 同时下一次移动开始
后这个已经被移动过的数据就会自动挤到后面去. 那么不再重复移动这个数据的办法就
是首先移动最大的数. 那么在移动剩下的最大数,就可以保证移动完成以后结果就是良
序的了.
那么什么样的数据需要移动呢?很简单逆序(注1)的. 举个例子:
延续前面的例子,数字2013. 第一个数字不需要考虑,第二个数字0与2构成一个逆
序,因此0是逆序数. 第三个数字1与2构成逆序,即1为逆序数. 那么首先移动较大的,
移动1得到1203. 由于数据排列发生变化,需要重新计算逆序. 因此得到0为逆序数,移
动0,得到结果0123.
这里就得到一个结论,就是判断逆序,移动最大的逆序数即可. 由此得到伪代码:
1 // 这里依旧使用升序排列 2 public void jk_sort(char[] s) { 3 char temp = '\0'; // 用来存放最大的逆序数 4 // 由于第一个数字不需要考虑逆序,因此从1开始循环 5 for(int i = 1; i < s.length; i++) { 6 for(int j = 0; j < i; j++) { 7 // 后一个数比前一个数小,那么构成逆序 8 if(s[i] < s[j]) { 9 // 判断记录最大的逆序数 10 if(temp == '\0' || temp < s[i]) { 11 temp = s[i]; 12 } 13 // 跳出循环,看下一个数是否为逆序 14 break; 15 } 16 } 17 } 18 // 移动逆序数 19 if(temp != '\0') { 20 jk_remove(s, temp); 21 // 如果存在逆序数就递归继续判断,否则离开函数排序完成 22 jk_sort( s ); 23 } 24 }
这里使用了递归,算法复杂度提升了,具体的优化可以以后再说. 那么有了这个思
路以后,就可以实现了.
代码实现
第一种情况,字符串中没有重复的字符
首先写一个类
1 public class JKSort { 2 3 }
提供静态方法,移动数据
1 private static void jk_remove(char[] s, int index) { 2 char temp = s[index]; 3 for (int i = index - 1; i >= 0; i--) { 4 s[i + 1] = s[i]; 5 } 6 s[0] = temp; 7 }
提供映射,可以考虑使用一个键值对
1 private Dictionary<char, int> dic; // 使用构造函数初始化 2 private JKSort(char[] chs) { 3 dic = new Dictionary<char, int>(); 4 for(int i = 0; i < chs.Length; i++) { 5 dic.Add(chs[i], i); 6 } 7 }
提供方法实现排序
1 private static void internal_jk_sort(char[] s, Dictionary<char, int> dic) { 2 int temp = -1; // 记录最大逆序数的索引 3 4 for(int i = 1; i < s.Length; i++) { 5 for(int j = 0; j < i; j++) { 6 7 if(dic[s[i]] < dic[s[j]]) { 8 9 if(temp == -1 || dic[s[temp]] < dic[s[i]]) { 10 temp = i; 11 } 12 13 break; 14 } 15 } 16 } 17 // 移动逆序数 18 if(temp != -1) { 19 jk_remove(s, temp); 20 // 如果存在逆序数就递归继续判断,否则离开函数排序完成 21 internal_jk_sort( s, dic ); 22 } 23 }
实现对外公开的方法
1 public static string JK_Sort(string str, string strObj) { 2 char[] chs = str.ToCharArray(); 3 char[] obj = strObj.ToCharArray(); 4 5 JKSort j = new JKSort(obj); 6 7 internal_jk_sort(chs, j.dic); 8 9 10 return new string(chs); 11 }
那么就完成了排序. 这里提供的算法没有实现优化,如想了解优化与带有重复字符
串的解决办法,请等待下文.
睡觉,2013年12月18日凌晨0时.
注1
逆序:在一个数字排列中,如果其中的两个数前面的一个比后面的一个大,那么就称
它们构成一个逆序. 相关逆序的结论与问题,可以参考《高等代数》或《线性代数》
的教材.