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

时间：2014-01-17 00:19:44 阅读：391 评论：0 收藏：0 [点我收藏+]

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 }

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

原文：http://www.cnblogs.com/WhyEngine/p/3522309.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)