基础知识的回顾不再写到这里面了，会写一些算法算法的解答或者读一些相关书籍的笔记。
今天做了一道算法题，来自微软必应·英雄会第三届在线编程大赛：几个bing?
做出来了。。。但不知道为啥执行测试用例失败，也许不对吧，求大神帮这看一下，有兴趣的可以去做做，
本届大赛由微软必应词典冠名，(Bing Dictionary)是微软推出的新一代英语学习引擎，里面收录了很多我们常见的单词。但现实生活中，我们也经常能看到一些毫无规则的字符串，导致词典无法正常收录，不过，我们是否可以从无规则的字符串中提取出正规的单词呢？
例如有一个字符串"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取余数之后的结果。
思路
先找到第一个b和最后一个g，锁定字符串。
然后遍历一边从第一个b到最后一个g的字符串片段，分别将其放到4个链表里，链表结构体如下：
struct LNode{ int data; // 该结点在字符串中的位置 int num; // 该结点之后的组合有多少种 struct LNode *next; // 下一个结点}LNode, *LinkedList; 其中的num可能比较难以理解，我举个例子，若字符串为"binbignngg"，则最后一个g的num为1，倒数第二个为2，即在取到相应的g时，g及其后的字符串组合的可能性为几。倒数第一个n的话，它的num为2，代表的是ng组合的可能。倒数第一个i的num为4，即ing组合的可能性。依次往前推即可。
#include#include #include #include struct LNode{ int data; // 该结点在字符串中的位置 int num; // 该结点之后的组合有多少种 struct LNode *next; // 下一个结点}LNode, *LinkedList;// 单链表的初始化LinkedList LinkedListInit(){ // 建立一个空的单链表 LNode *L = (LNode*)malloc(sizeof(LNode)); if(L == NULL) { exit(0); } L->next = NULL; L->data = 0; L->num = 0; return L;}LinkedList LinkedListInsert(LinkedList L, int data, int num){ // 用头插法插入结点 LNode *p = (LNode *)malloc(sizeof(LNode)); p->data = data; p->num = num; p->next = L->next; L->next = p; return L;}LinkedList getNum(LinkedList UL, LinkedList DL){ // 由后往前推出个数 LinkedList up = UL, uq = UL->next, dp = DL, dq = DL->next, last = NULL; while(dq) { while(uq && dq->data < uq->data) { up = uq; if(up == last) { break; } uq = uq->next; } last = up; dq->num = up->num + dp->num; // 前一个字母顺序的个数和该字母顺序的前一个个数 dp = dq; dq = dq->next; } printf("\n"); return DL;}int howmany (char* s){ int dataLen = strlen(s), start = 0, end = 0, first = 1, i = 0, gLen = 0; if(dataLen < 4) { return 0; } // 初始化链表 LinkedList bData = LinkedListInit(), iData = LinkedListInit(), nData = LinkedListInit(), gData = LinkedListInit(); for (; i < dataLen; i++) { if(first && s[i] == 'b') { start = i; first = 0; } else if(s[i] == 'g') { end = i; } } // 根据字符串插入链表数据 for (i = start; i <= end ; i++) { switch(s[i]) { case 'b': bData = LinkedListInsert(bData, i, 0); break; case 'i': iData = LinkedListInsert(iData, i, 0); break; case 'n': nData = LinkedListInsert(nData, i, 0); break; case 'g': gLen++; gData = LinkedListInsert(gData, i, 0); break; default: return 0; } } LinkedList p = gData->next; i = 1; while(p) { p->num = i; i++; p = p->next; } nData = getNum(gData, nData); iData = getNum(nData, iData); bData = getNum(iData, bData); LinkedList lastB = bData->next; while(lastB->next) { lastB = lastB->next; } int result = lastB->num; return (int)result%(int)(pow(10, 9) + 7);}int main(){ printf("%d",howmany("Test"));}