算法小题（一）

作者: kangomake | 来源:发表于2019-02-11 16:53 被阅读15次

算法小题（一）
算法小题篇
CSI讲义10:寻找峰值
小题
小题
小题
小题
小题
小题
小题

1.找出一个字符串中重复最多的字符且说出重复次数
2.冒泡法和快速排序
3.查找字符串2 在字符串1中出现的次数

//查找字符串2 在字符串1中出现的次数
    NSUInteger count = 0;
    NSString * string1 = @"123as21312312333123";
    NSString * string2 = @"123";
    
    if(string2.length >string1.length){
        return;
    }
    
    for(int i = 0;i<string1.length-string2.length +1;i++){
        if([[string1 substringWithRange:NSMakeRange(i, string2.length)] isEqualToString:string2]){
            count ++;
        }
   
    }
    
    NSLog(@"count-%lu",count);

4.如何用 GCD 同步若干个异步调用？
使用 Dispatch Group 追加 block 到 Global Group Queue，这些 block 如果全部执行完毕，就会执行 Main Dispatch Queue 中的结束处理的 block。

    dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
    dispatch_group_t group = dispatch_group_create();
    dispatch_group_async(group, queue, ^{
    });
    
    dispatch_group_async(group, queue, ^{
    });
    
    dispatch_group_async(group, queue, ^{
    });
    
    dispatch_group_notify(group, dispatch_get_main_queue(), ^{
        //ui更新
    });

5.# 求一个字符串中连续出现的次数最多的子串
求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的重复子串为abab。两个题目的解法有些类似，都用到了后缀数组这个数据结构。求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:
abababc
bababc
ababc
babc
abc
bc
c
可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。可以看出规律来，一个字符串s，如果第一次出现在后缀数组i的前面，那么如果它重复出现，下一次出现应该在第i+len(s)个后缀数组的前面。这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果。下面是代码：

1 #include <iostream>
 2 using namespace std;
 3 
 4 int con_sub(char *str, char **ret);
 5 
 6 int main()
 7 {
 8         char str[] = "abcabcabcabcabcabbbb";
 9         char *ret = NULL;
10         int time = con_sub(str, &ret);
11         printf("%s occuers %d times\n", ret, time);
12         return 0;
13 }
14 
15 int con_sub(char *str, char **ret)
16 {
17         int max_time = 0;//连续出现的最多次数
18         int ret_len = 0;//连续出现的字符串的长度
19         char *addr = NULL;//连续出现字符串的起始地址
20 
21         int len = strlen(str);
22         char **a = (char **)malloc(sizeof(char *)*len);
23         //生成后缀数组
24         for(int i=0; i<len; i++)
25                 a[i] = &str[i];
26 
27         //重复字符串的长度范围为1到(len+1)/2
28         for(int i=1; i<=(len+1)/2; i++)
29         {
30                 //当重复的字符串长度为i的时候，如果是连续出现的，那么第j和第j+i个后缀数组前面为重复的字符串
31                 for(int j=0; j+i<=len-1; j+=i)
32                 {
33                         int k = j;
34                         int temp_time = 1;
35                         while(k+i <= len-1 && strncmp(a[k], a[k+i], i) == 0)
36                         {
37                                 temp_time++;
38                                 k += i;
39                         }
40                         if(temp_time > max_time)
41                         {
42                                 max_time = temp_time;
43                                 ret_len = i;
44                                 addr = a[k];
45                         }
46                 }
47         }
48         *ret = new char[len+1];
49         strncpy(*ret, addr, ret_len);
50         return max_time;
51 }

注意：这里有一个小技巧，加入字符串中存在出现次数相同的子串，如何优先选择更长的字符串作为最终的结果？可以调整子串的长度为从大到小。