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取余数之后的结果。

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

第一版代码:

 #include <stdio.h>

 #include <iostream>

 #include <string>

 #include <cstring>

 #include <cstdio>

 #define BING_MAX 1000000007

 int Bing(const char* szBing)

 {

     if (!szBing || !szBing[])

     {

         return ;

     }

     int len = (int)strlen(szBing);

     int* listPosB = (int*)malloc(len*sizeof(int));

     int* listPosI = (int*)malloc(len*sizeof(int));

     int* listPosN = (int*)malloc(len*sizeof(int));

     int* listPosG = (int*)malloc(len*sizeof(int));

     memset(listPosB, , len*sizeof(int));

     memset(listPosI, , len*sizeof(int));

     memset(listPosN, , len*sizeof(int));

     memset(listPosG, , len*sizeof(int));

     int numB = ;

     int numI = ;

     int numN = ;

     int numG = ;

     for (int i = ; i < len; i++)

     {

         switch (szBing[i])

         {

         case 'B':

         case 'b':

             listPosB[numB] = i;

             numB++;

             break;

         case 'I':

         case 'i':

             listPosI[numI] = i;

             numI++;

             break;

         case 'N':

         case 'n':

             listPosN[numN] = i;

             numN++;

             break;

         case 'G':

         case 'g':

             listPosG[numG] = i;

             numG++;

             break;

         }

     }

     int count = ;

     int startB;

     int startI;

     int startN;

     int startG;

     for (int b = ; b < numB; b++)

     {

         startB = listPosB[b];

         for (int i = ; i < numI; i++)

         {

             startI = listPosI[i];

             if (startI < startB)

             {

                 continue;

             }

             for (int n = ; n < numN; n++)

             {

                 startN = listPosN[n];

                 if (startN < startI)

                 {

                     continue;

                 }

                 for (int g = ; g < numG; g++)

                 {

                     startG = listPosG[g];

                     if (startG < startN)

                     {

                         continue;

                     }

                     count++;

                     if (count > BING_MAX)

                     {

                         count -= BING_MAX;

                     }

                 }

             }

         }

     }

     free(listPosB);

     free(listPosI);

     free(listPosN);

     free(listPosG);

     return count;

 }

优化后的代码:

 #include <cstring>

 #include <cstdio>

 #define BING_MAX 1000000007

 struct U2

 {

     short pos;

     short next;

 };

 int Bing(const char* szBing)

 {

     if (!szBing || !szBing[])

     {

         return ;

     }

     int len = (int)strlen(szBing);

     U2* listPosB = (U2*)malloc(len*sizeof(U2));

     U2* listPosI = (U2*)malloc(len*sizeof(U2));

     U2* listPosN = (U2*)malloc(len*sizeof(U2));

     U2* listPosG = (U2*)malloc(len*sizeof(U2));

     memset(listPosB, , len*sizeof(int));

     memset(listPosI, , len*sizeof(int));

     memset(listPosN, , len*sizeof(int));

     memset(listPosG, , len*sizeof(int));

     int numB = ;

     int numI = ;

     int numN = ;

     int numG = ;

     for (int i = ; i < len; i++)

     {

         switch (szBing[i])

         {

         case 'B':

         case 'b':

             listPosB[numB].pos = (short)i;

             numB++;

             break;

         case 'I':

         case 'i':

             listPosI[numI].pos = (short)i;

             numI++;

             break;

         case 'N':

         case 'n':

             listPosN[numN].pos = (short)i;

             numN++;

             break;

         case 'G':

         case 'g':

             listPosG[numG].pos = (short)i;

             numG++;

             break;

         }

     }

     for (int i = ; i < numB; i++)

     {

         for (int j = ; j < numI; j++)

         {

             if (listPosB[i].pos < listPosI[j].pos)

             {

                 listPosB[i].next = j;

                 break;

             }

         }

     }

     for (int i = ; i < numI; i++)

     {

         for (int j = ; j < numN; j++)

         {

             if (listPosI[i].pos < listPosN[j].pos)

             {

                 listPosI[i].next = j;

                 break;

             }

         }

     }

     for (int i = ; i < numN; i++)

     {

         for (int j = ; j < numG; j++)

         {

             if (listPosN[i].pos < listPosG[j].pos)

             {

                 listPosN[i].next = j;

                 break;

             }

         }

     }

     int count = ;

     for (int b = ; b < numB; b++)

     {

         for (int i = listPosB[b].next; i < numI; i++)

         {

             for (int n = listPosI[i].next; n < numN; n++)

             {

                 for (int g = listPosN[n].next; g < numG; g++)

                 {

                     count++;

                     if (count > BING_MAX)

                     {

                         count -= BING_MAX;

                     }

                 }

             }

         }

     }

     /*

     short startB;

     short startI;

     short startN;

     short startG;

     for (int b = 0; b < numB; b++)

     {

         startB = listPosB[b].pos;

         for (int i = 0; i < numI; i++)

         {

             startI = listPosI[i].pos;

             if (startI < startB)

             {

                 continue;

             }

             for (int n = 0; n < numN; n++)

             {

                 startN = listPosN[n].pos;

                 if (startN < startI)

                 {

                     continue;

                 }

                 for (int g = 0; g < numG; g++)

                 {

                     startG = listPosG[g].pos;

                     if (startG < startN)

                     {

                         continue;

                     }

                     count++;

                     if (count > BING_MAX)

                     {

                         count -= BING_MAX;

                     }

                 }

             }

         }

     }

     */

     free(listPosB);

     free(listPosI);

     free(listPosN);

     free(listPosG);

     return count;

 }

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

 #include <cstring>

 #include <cstdio>

 #include <assert.h>

 #define BING_MAX 1000000007

 struct U2

 {

     short pos;

     short next;

 };

 int Bing(const char* szBing, int len)

 {

     if (!szBing || !szBing[])

     {

         return ;

     }

     U2* listPosB = (U2*)malloc(len*sizeof(U2));

     U2* listPosI = (U2*)malloc(len*sizeof(U2));

     U2* listPosN = (U2*)malloc(len*sizeof(U2));

     U2* listPosG = (U2*)malloc(len*sizeof(U2));

     memset(listPosB, , len*sizeof(int));

     memset(listPosI, , len*sizeof(int));

     memset(listPosN, , len*sizeof(int));

     memset(listPosG, , len*sizeof(int));

     int numB = ;

     int numI = ;

     int numN = ;

     int numG = ;

     for (int i = ; i < len; i++)

     {

         if (szBing[i] == 'b')

         {

             listPosB[numB].pos = (short)i;

             numB++;

         }

         else if  (szBing[i] == 'i')

         {

             listPosI[numI].pos = (short)i;

             numI++;

         }

         else if  (szBing[i] == 'n')

         {

             listPosN[numN].pos = (short)i;

             numN++;

         }

         else

         {

             listPosG[numG].pos = (short)i;

             numG++;

         }

     }

     int t = ;

     for (int i = ; i < numB; i++)

     {

         for (int j = t; j < numI; j++)

         {

             if (listPosB[i].pos < listPosI[j].pos)

             {

                 listPosB[i].next = t = j;

                 break;

             }

         }

     }

     t = ;

     for (int i = ; i < numI; i++)

     {

         for (int j = t; j < numN; j++)

         {

             if (listPosI[i].pos < listPosN[j].pos)

             {

                 listPosI[i].next = t = j;

                 break;

             }

         }

     }

     t = ;

     for (int i = ; i < numN; i++)

     {

         for (int j = t; j < numG; j++)

         {

             if (listPosN[i].pos < listPosG[j].pos)

             {

                 listPosN[i].next = t = j;

                 break;

             }

         }

     }

     int count = ;

     for (int b = ; b < numB; b++)

     {

         for (int i = listPosB[b].next; i < numI; i++)

         {

             for (int n = listPosI[i].next; n < numN; n++)

             {

                 count += numG - listPosN[n].next;

             }

         }

         if (count > BING_MAX)

         {

             count -= BING_MAX;

         }

     }

     free(listPosB);

     free(listPosI);

     free(listPosN);

     free(listPosG);

     return count;

 }

第四版代码:

 #include <cstring>

 #include <cstdio>

 #define BING_MAX 1000000007

 struct U2

 {

     int pos;

     int count;

 };

 int Bing(const char* szBing, int len)

 {

     if (!szBing || !szBing[])

     {

         return ;

     }

     U2* listPosB = (U2*)malloc(len*sizeof(U2));

     U2* listPosI = (U2*)malloc(len*sizeof(U2));

     U2* listPosN = (U2*)malloc(len*sizeof(U2));

     U2* listPosG = (U2*)malloc(len*sizeof(U2));

     memset(listPosB, , len*sizeof(int));

     memset(listPosI, , len*sizeof(int));

     memset(listPosN, , len*sizeof(int));

     memset(listPosG, , len*sizeof(int));

     int numB = ;

     int numI = ;

     int numN = ;

     int numG = ;

     for (int i = ; i < len; i++)

     {

         if (szBing[i] == 'b')

         {

             listPosB[numB].pos = i;

             numB++;

         }

         else if  (szBing[i] == 'i')

         {

             listPosI[numI].pos = i;

             numI++;

         }

         else if  (szBing[i] == 'n')

         {

             listPosN[numN].pos = i;

             numN++;

         }

         else if  (szBing[i] == 'g')

         {

             listPosG[numG].pos = i;

             numG++;

         }

     }

     int b = ;

     int i = ;

     int n = ;

     int g = ;

     int t;

     // 每个N之后有多少个G的选择

     for (n = ; n < numN; n++)

     {

         while (listPosG[g].pos < listPosN[n].pos && g < numG)

         {

             g++;

         }

         listPosN[n].count = numG - g;

     }

     // 每个I之后有多少个NG的选择

     n = ;

     for (i = ; i < numI; i++)

     {

         while (listPosN[n].pos < listPosI[i].pos && n < numN)

         {

             n++;

         }

         listPosI[i].count = ;

         for (t = n; t < numN; t++)

         {

             listPosI[i].count += listPosN[t].count;

         }

     }

     // 每个B之后有多少个ING的选择

     i = ;

     int count = ;

     for (int b = ; b < numB; b++)

     {

         while (listPosI[i].pos < listPosB[b].pos && i < numI)

         {

             i++;

         }

         listPosB[b].count = ;

         for (t = i; t < numI; t++)

         {

             listPosB[b].count += listPosI[t].count;

         }

         count += listPosB[b].count;

         if (count > BING_MAX)

         {

             count -= BING_MAX;

         }

     }

     free(listPosB);

     free(listPosI);

     free(listPosN);

     free(listPosG);

     return count;

 }

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

 #define BING_MAX 1000000007

 int Bing(const char* szBing)

 {

     int numB = ;

     int numI = ;

     int numN = ;

     int numG = ;

     int pos = ;

     while (szBing[pos])

     {

         if (szBing[pos] == 'b')

         {

             numB++;

         }

         else if (szBing[pos] == 'i')

         {

             numI += numB;

         }

         else if (szBing[pos] == 'n')

         {

             numN += numI;

         }

         else if (szBing[pos] == 'g')

         {

             numG += numN;

             if (numG > BING_MAX)

             {

                 numG -= BING_MAX;

             }

         }

         pos++;

     }

     return numG;

 }

最新文章

  1. YourSQLDba版本升级总结
  2. Ionic开发实战
  3. 用Spring+Junit4.4进行测试(使用注解)
  4. Python 第三天 文件操作(2)
  5. wpf开发桌面软件记录
  6. jboss eap 6.2+ 版本中 加密datasource密码等敏感信息
  7. 【BZOJ1008】1008: [HNOI2008]越狱 简单组合数学+快速幂
  8. CSS--滚动条设置；
  9. Android：控件的隐藏显示
  10. C# config配置文件 自定义节点读取
  11. RESTful Web Services: A Tutorial--reference
  12. apache AH01630: client denied by server configuration错误解决方法
  13. 製程能力介紹(SPC introduction) ─ Cp之製程能力解釋
  14. WebLogic使用SSH架构部署遇到org.hibernate.hql.internal.ast.HqlTok
  15. 多元线性回归----Java简单实现
  16. 一个想法（续三）：一份IT技术联盟创业计划书，开启众筹创业征程
  17. Hyper-v 虚拟机安装win7
  18. html网页中加载js脚本 下载下来是乱码（文件编码格式）
  19. CTF---Web入门第十六题 天下武功唯快不破
  20. springboot Cacheable（redis），解决key乱码问题

热门文章

  1. react篇章-事件处理
  2. springboot+thymeleaf 模板中传递参数误报错误 红色波浪线
  3. Java反射机制demo（七）—反射机制与工厂模式
  4. CodeForces 140C New Year Snowmen（堆）
  5. java main class not found
  6. 【基础知识】winfrom窗体的属性
  7. [python 源码]整数对象的创建和维护
  8. BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流
  9. 命令神器：lsof 常用
  10. python mac环境搭建