- 题目:给定一个有小写字母组成的字符串,重组这个字符串,使相同字符之间的间隔至少为d。
Input:{a,b,b}, distance=2
output:{b,a,b}。
-
个人认为这道题目很有难度。初看时不知如何下手。结合文章中给出的算法,具体算法如下:主体的算法思想是“贪心算法”。出现次数最多的字符被选中放入新字符串的优先级最高,如果这个字符不能被选中(因为距离的限制,比如上次选择了字符a,这次选择如果仍然a出现次数最多,但是却不能选a,因为如果要求距离为2,再次选择a,造成两个a相邻,那距离就为1了),那么我们选择下一个优先级最高的字符(并且这个字符的出现也要满足距离的要求,如果不满足,就接着选下一个优先级高的字符,以此类推;如果没有满足条件的字符,就说明出现了错误。比如给定字符aaaaa,要求重组字符距离为2,显然不存在这样的重组字符,返回error)。为了提高算法的效率,使用一些数组来存储信息。
-
下面给出代码:
1 #include<iostream>
2 #include<cassert>
3
4 using namespace std;
5
6 int find_max(int freq[], bool excep[]) {
7 int max_i = -1;
8 int max = -1;
9 //找到出现次数最多的字母
10 //max记录出现次数最多的字母出现的次数
11 //max_i记录哪个字母出现次数最多
12 for (char c = 'a'; c <= 'z'; c++) {
13 if (!excep[c] && freq[c] > 0 && freq[c] > max) {
14 max = freq[c];
15 max_i = c;
16 }
17 }
18 return max_i;
19 }
20
21 void create(char* str, int d, char ans[]) {
22 int n = strlen(str);
23 int freq[256] = {0}; //记录每个字母出现次数
24 for (int i = 0; i < n; i++)
25 freq[str[i]]++;
26
27 int used[256] = {0};
28 for (int i = 0; i < n; i++) {
29 bool excep[256] = {false};
30 bool done = false;
31 while (!done) {
32 int j = find_max(freq, excep);
33 if (j == -1) {
34 cout << "Error!\n";
35 return;
36 }
37 excep[j] = true;
38 if (used[j] <= 0) {
39 ans[i] = j;
40 freq[j]--;
41 used[j] = d;
42 done = true;
43 }
44 }
45 for (int i = 0; i < 256; i++)
46 used[i]--;
47 }
48 ans[n] = '\0';
49 }
50 int main()
51 {
52 char* str="bbaaaccdd";
53 //char* str="aaaaaaadd";
54 int dis=3;
55 char ans[20];
56 create(str,dis,ans);
57 cout<<ans<<endl;
58 return 0;
59 }
输出为:abcadbacd
- 代码分析:
几个数组的作用:freq[256]:记录每个字母出现的次数,初始为0;used[256]:记录每个字母距离再次被选中的长度,例如,如果这次选择了字符a,就将used['a']设置为3,每次选择一个字符后,就将used数组中的每个数据减1,知道used['a']小于等于0,说明a再次出现在新数组中时就可以满足距离的要求;excep[256],每选中一个新字符就将这个字符的execp[]设置为true,for循环开始处将其置为false。
第6行,函数find_max返回出现次数最多的字符。
第28行,外层for循环每次选择一个字符加入到新字符串ans中。
第31行,while循环,选择一个合适的字符加入新的字符串。
第33行,如果没有合适的字符即j==-1说明输入的字符不满足条件,返回error。
第37行,将execp[]设置为true,即下次再选择时不再选择这个字符。
第38行,如果used[]<=0,即满足条件说明,将选择的字符加入ans中,字符出现次数减一,used设为d,done变为true,退出while循环。如果不满足,while重新执行,选择新的字符。
第45行,每次while执行完,即在ans中新加入了一个字符,那么所有字符的used计数减一。
- 总结:这道题技巧性很强,我是写不出这样的代码的,以后努力加油吧!!!
参考文章:
http://www.leetcode.com/2010/05/here-is-another-google-phone-interview.html
原文链接: https://www.cnblogs.com/ZJUKasuosuo/archive/2012/08/12/2634765.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/59035
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!