给定任意字符串，计算一共能组合成多少个单词bing

CSDN编程挑战里的题目

例如有一个字符串"iinbinbing"，截取不同位置的字符‘b’、‘i’、‘n’、‘g’组合成单词"bing"。
若从1开始计数的话，则‘b’ ‘i’ ‘n’ ‘g’这4个字母出现的位置分别为(4,5,6,10) (4,5,9,10),
(4,8,9,10)和(7,8,9,10)，故总共可以组合成4个单词”bing“。
问题是：现给定任意字符串，只包含小写‘b’ ‘i’ ‘n’ ‘g’这4种字母，请问一共能组合成多少个单词bing?

字符串长度不超过10000，由于结果可能比较大，请输出对10^9 + 7取余数之后的结果。

这个问题写个四重循环就可以.只是效率方面还有待优化.

第一版代码:

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string>
  4 
  5 #include <cstring>
  6 #include <cstdio>
  7 
  8 #define BING_MAX 1000000007
  9 
 10 int Bing(const char* szBing)
 11 {
 12     if (!szBing || !szBing[0])
 13     {
 14         return 0;
 15     }
 16 
 17     int len = (int)strlen(szBing);
 18     int* listPosB = (int*)malloc(len*sizeof(int));
 19     int* listPosI = (int*)malloc(len*sizeof(int));
 20     int* listPosN = (int*)malloc(len*sizeof(int));
 21     int* listPosG = (int*)malloc(len*sizeof(int));
 22     memset(listPosB, 0, len*sizeof(int));
 23     memset(listPosI, 0, len*sizeof(int));
 24     memset(listPosN, 0, len*sizeof(int));
 25     memset(listPosG, 0, len*sizeof(int));
 26     int numB = 0;
 27     int numI = 0;
 28     int numN = 0;
 29     int numG = 0;
 30 
 31     for (int i = 0; i < len; i++)
 32     {
 33         switch (szBing[i])
 34         {
 35         case 'B':
 36         case 'b':
 37             listPosB[numB] = i;
 38             numB++;
 39             break;
 40         case 'I':
 41         case 'i':
 42             listPosI[numI] = i;
 43             numI++;
 44             break;
 45         case 'N':
 46         case 'n':
 47             listPosN[numN] = i;
 48             numN++;
 49             break;
 50         case 'G':
 51         case 'g':
 52             listPosG[numG] = i;
 53             numG++;
 54             break;
 55         }
 56     }
 57 
 58     int count = 0;
 59 
 60     int startB;
 61     int startI;
 62     int startN;
 63     int startG;
 64     for (int b = 0; b < numB; b++)
 65     {
 66         startB = listPosB[b];
 67 
 68         for (int i = 0; i < numI; i++)
 69         {
 70             startI = listPosI[i];
 71             if (startI < startB)
 72             {
 73                 continue;
 74             }
 75 
 76             for (int n = 0; n < numN; n++)
 77             {
 78                 startN = listPosN[n];
 79                 if (startN < startI)
 80                 {
 81                     continue;
 82                 }
 83 
 84                 for (int g = 0; g < numG; g++)
 85                 {
 86                     startG = listPosG[g];
 87                     if (startG < startN)
 88                     {
 89                         continue;
 90                     }
 91 
 92                     count++;
 93                     if (count > BING_MAX)
 94                     {
 95                         count -= BING_MAX;
 96                     }
 97                 }
 98             }
 99         }
100     }
101 
102     free(listPosB);
103     free(listPosI);
104     free(listPosN);
105     free(listPosG);
106 
107     return count;
108 }

 优化后的代码:

  1 #include <cstring>
  2 #include <cstdio>
  3 
  4 #define BING_MAX 1000000007
  5 
  6 struct U2 
  7 {
  8     short pos;
  9     short next;
 10 };
 11 
 12 int Bing(const char* szBing)
 13 {
 14     if (!szBing || !szBing[0])
 15     {
 16         return 0;
 17     }
 18 
 19     int len = (int)strlen(szBing);
 20     U2* listPosB = (U2*)malloc(len*sizeof(U2));
 21     U2* listPosI = (U2*)malloc(len*sizeof(U2));
 22     U2* listPosN = (U2*)malloc(len*sizeof(U2));
 23     U2* listPosG = (U2*)malloc(len*sizeof(U2));
 24     memset(listPosB, 0, len*sizeof(int));
 25     memset(listPosI, 0, len*sizeof(int));
 26     memset(listPosN, 0, len*sizeof(int));
 27     memset(listPosG, 0, len*sizeof(int));
 28     int numB = 0;
 29     int numI = 0;
 30     int numN = 0;
 31     int numG = 0;
 32 
 33     for (int i = 0; i < len; i++)
 34     {
 35         switch (szBing[i])
 36         {
 37         case 'B':
 38         case 'b':
 39             listPosB[numB].pos = (short)i;
 40             numB++;
 41             break;
 42         case 'I':
 43         case 'i':
 44             listPosI[numI].pos = (short)i;
 45             numI++;
 46             break;
 47         case 'N':
 48         case 'n':
 49             listPosN[numN].pos = (short)i;
 50             numN++;
 51             break;
 52         case 'G':
 53         case 'g':
 54             listPosG[numG].pos = (short)i;
 55             numG++;
 56             break;
 57         }
 58     }
 59 
 60     for (int i = 0; i < numB; i++)
 61     {
 62         for (int j = 0; j < numI; j++)
 63         {
 64             if (listPosB[i].pos < listPosI[j].pos)
 65             {
 66                 listPosB[i].next = j;
 67                 break;
 68             }
 69         }
 70     }
 71 
 72     for (int i = 0; i < numI; i++)
 73     {
 74         for (int j = 0; j < numN; j++)
 75         {
 76             if (listPosI[i].pos < listPosN[j].pos)
 77             {
 78                 listPosI[i].next = j;
 79                 break;
 80             }
 81         }
 82     }
 83 
 84     for (int i = 0; i < numN; i++)
 85     {
 86         for (int j = 0; j < numG; j++)
 87         {
 88             if (listPosN[i].pos < listPosG[j].pos)
 89             {
 90                 listPosN[i].next = j;
 91                 break;
 92             }
 93         }
 94     }
 95 
 96     int count = 0;
 97     for (int b = 0; b < numB; b++)
 98     {
 99         for (int i = listPosB[b].next; i < numI; i++)
100         {
101             for (int n = listPosI[i].next; n < numN; n++)
102             {
103                 for (int g = listPosN[n].next; g < numG; g++)
104                 {
105                     count++;
106                     if (count > BING_MAX)
107                     {
108                         count -= BING_MAX;
109                     }
110                 }
111             }
112         }
113     }
114 
115     /*
116     short startB;
117     short startI;
118     short startN;
119     short startG;
120     for (int b = 0; b < numB; b++)
121     {
122         startB = listPosB[b].pos;
123 
124         for (int i = 0; i < numI; i++)
125         {
126             startI = listPosI[i].pos;
127             if (startI < startB)
128             {
129                 continue;
130             }
131 
132             for (int n = 0; n < numN; n++)
133             {
134                 startN = listPosN[n].pos;
135                 if (startN < startI)
136                 {
137                     continue;
138                 }
139 
140                 for (int g = 0; g < numG; g++)
141                 {
142                     startG = listPosG[g].pos;
143                     if (startG < startN)
144                     {
145                         continue;
146                     }
147 
148                     count++;
149                     if (count > BING_MAX)
150                     {
151                         count -= BING_MAX;
152                     }
153                 }
154             }
155         }
156     }
157     */
158 
159     free(listPosB);
160     free(listPosI);
161     free(listPosN);
162     free(listPosG);
163 
164     return count;
165 }

 第三版优化,还是运行时间超过3s,我是真没辙了.

  1 #include <cstring>
  2 #include <cstdio>
  3 #include <assert.h>
  4 
  5 #define BING_MAX 1000000007
  6 
  7 struct U2 
  8 {
  9     short pos;
 10     short next;
 11 };
 12 
 13 int Bing(const char* szBing, int len)
 14 {
 15     if (!szBing || !szBing[0])
 16     {
 17         return 0;
 18     }
 19 
 20     U2* listPosB = (U2*)malloc(len*sizeof(U2));
 21     U2* listPosI = (U2*)malloc(len*sizeof(U2));
 22     U2* listPosN = (U2*)malloc(len*sizeof(U2));
 23     U2* listPosG = (U2*)malloc(len*sizeof(U2));
 24     memset(listPosB, 0, len*sizeof(int));
 25     memset(listPosI, 0, len*sizeof(int));
 26     memset(listPosN, 0, len*sizeof(int));
 27     memset(listPosG, 0, len*sizeof(int));
 28     int numB = 0;
 29     int numI = 0;
 30     int numN = 0;
 31     int numG = 0;
 32 
 33     for (int i = 0; i < len; i++)
 34     {
 35         if (szBing[i] == 'b')
 36         {
 37             listPosB[numB].pos = (short)i;
 38             numB++;
 39         }
 40         else if  (szBing[i] == 'i')
 41         {
 42             listPosI[numI].pos = (short)i;
 43             numI++;
 44         }
 45         else if  (szBing[i] == 'n')
 46         {
 47             listPosN[numN].pos = (short)i;
 48             numN++;
 49         }
 50         else
 51         {
 52             listPosG[numG].pos = (short)i;
 53             numG++;
 54         }
 55     }
 56 
 57     int t = 0;
 58     for (int i = 0; i < numB; i++)
 59     {
 60         for (int j = t; j < numI; j++)
 61         {
 62             if (listPosB[i].pos < listPosI[j].pos)
 63             {
 64                 listPosB[i].next = t = j;
 65                 break;
 66             }
 67         }
 68     }
 69 
 70     t = 0;
 71     for (int i = 0; i < numI; i++)
 72     {
 73         for (int j = t; j < numN; j++)
 74         {
 75             if (listPosI[i].pos < listPosN[j].pos)
 76             {
 77                 listPosI[i].next = t = j;
 78                 break;
 79             }
 80         }
 81     }
 82 
 83     t = 0;
 84     for (int i = 0; i < numN; i++)
 85     {
 86         for (int j = t; j < numG; j++)
 87         {
 88             if (listPosN[i].pos < listPosG[j].pos)
 89             {
 90                 listPosN[i].next = t = j;
 91                 break;
 92             }
 93         }
 94     }
 95 
 96     int count = 0;
 97     for (int b = 0; b < numB; b++)
 98     {
 99         for (int i = listPosB[b].next; i < numI; i++)
100         {
101             for (int n = listPosI[i].next; n < numN; n++)
102             {
103                 count += numG - listPosN[n].next;
104             }
105         }
106 
107         if (count > BING_MAX)
108         {
109             count -= BING_MAX;
110         }
111     }
112 
113     free(listPosB);
114     free(listPosI);
115     free(listPosN);
116     free(listPosG);
117 
118     return count;
119 }

第四版代码:

  1 #include <cstring>
  2 #include <cstdio>
  3 
  4 #define BING_MAX 1000000007
  5 
  6 struct U2 
  7 {
  8     int pos;
  9     int count;
 10 };
 11 
 12 int Bing(const char* szBing, int len)
 13 {
 14     if (!szBing || !szBing[0])
 15     {
 16         return 0;
 17     }
 18 
 19     U2* listPosB = (U2*)malloc(len*sizeof(U2));
 20     U2* listPosI = (U2*)malloc(len*sizeof(U2));
 21     U2* listPosN = (U2*)malloc(len*sizeof(U2));
 22     U2* listPosG = (U2*)malloc(len*sizeof(U2));
 23     memset(listPosB, 0, len*sizeof(int));
 24     memset(listPosI, 0, len*sizeof(int));
 25     memset(listPosN, 0, len*sizeof(int));
 26     memset(listPosG, 0, len*sizeof(int));
 27     int numB = 0;
 28     int numI = 0;
 29     int numN = 0;
 30     int numG = 0;
 31 
 32     for (int i = 0; i < len; i++)
 33     {
 34         if (szBing[i] == 'b')
 35         {
 36             listPosB[numB].pos = i;
 37             numB++;
 38         }
 39         else if  (szBing[i] == 'i')
 40         {
 41             listPosI[numI].pos = i;
 42             numI++;
 43         }
 44         else if  (szBing[i] == 'n')
 45         {
 46             listPosN[numN].pos = i;
 47             numN++;
 48         }
 49         else if  (szBing[i] == 'g')
 50         {
 51             listPosG[numG].pos = i;
 52             numG++;
 53         }
 54     }
 55 
 56     int b = 0;
 57     int i = 0;
 58     int n = 0;
 59     int g = 0;
 60     int t;
 61 
 62     // 每个N之后有多少个G的选择
 63     for (n = 0; n < numN; n++)
 64     {
 65         while (listPosG[g].pos < listPosN[n].pos && g < numG)
 66         {
 67             g++;
 68         }
 69         listPosN[n].count = numG - g;
 70     }
 71 
 72     // 每个I之后有多少个NG的选择
 73     n = 0;
 74     for (i = 0; i < numI; i++)
 75     {
 76         while (listPosN[n].pos < listPosI[i].pos && n < numN)
 77         {
 78             n++;
 79         }
 80         listPosI[i].count = 0;
 81         for (t = n; t < numN; t++)
 82         {
 83             listPosI[i].count += listPosN[t].count;
 84         }
 85     }
 86 
 87     // 每个B之后有多少个ING的选择
 88     i = 0;
 89     int count = 0;
 90     for (int b = 0; b < numB; b++)
 91     {
 92         while (listPosI[i].pos < listPosB[b].pos && i < numI)
 93         {
 94             i++;
 95         }
 96         listPosB[b].count = 0;
 97         for (t = i; t < numI; t++)
 98         {
 99             listPosB[b].count += listPosI[t].count;
100         }
101 
102         count += listPosB[b].count;
103         if (count > BING_MAX)
104         {
105             count -= BING_MAX;
106         }
107     }
108 
109     free(listPosB);
110     free(listPosI);
111     free(listPosN);
112     free(listPosG);
113 
114     return count;
115 }

 终于想到正确答案了,原来我一开始就误入歧途了,最早的代码算法复杂度是O(n^4),我将其优化到O(n^2),然后又优化到O(n*log(n)),而最终代码的复杂度是O(n).

 1 #define BING_MAX 1000000007
 2 
 3 int Bing(const char* szBing)
 4 {
 5     int numB = 0;
 6     int numI = 0;
 7     int numN = 0;
 8     int numG = 0;
 9     int pos = 0;
10     while (szBing[pos])
11     {
12         if (szBing[pos] == 'b')
13         {
14             numB++;
15         }
16         else if (szBing[pos] == 'i')
17         {
18             numI += numB;
19         }
20         else if (szBing[pos] == 'n')
21         {
22             numN += numI;
23         }
24         else if (szBing[pos] == 'g')
25         {
26             numG += numN;
27             if (numG > BING_MAX)
28             {
29                 numG -= BING_MAX;
30             }
31         }
32         pos++;
33     }
34 
35     return numG;
36 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/WhyEngine/p/3522309.html