基础知识的回顾不再写到这里面了，会写一些算法算法的解答或者读一些相关书籍的笔记。
今天做了一道算法题，来自微软必应·英雄会第三届在线编程大赛：几个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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h> struct LNode
{
int data; // 该结点在字符串中的位置
int num; // 该结点之后的组合有多少种
struct LNode *next; // 下一个结点
}LNode, *LinkedList; // 单链表的初始化
LinkedList LinkedListInit()
{// 建立一个空的单链表
LNode *L = (LNode*)malloc(sizeof(LNode));
if(L == NULL)
{
exit();
}
L->next = NULL;
L->data = ;
L->num = ;
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 = ,
end = ,
first = ,
i = ,
gLen = ; if(dataLen < )
{
return ;
} // 初始化链表
LinkedList bData = LinkedListInit(),
iData = LinkedListInit(),
nData = LinkedListInit(),
gData = LinkedListInit(); for (; i < dataLen; i++)
{
if(first && s[i] == 'b')
{
start = i;
first = ;
}
else if(s[i] == 'g')
{
end = i;
}
} // 根据字符串插入链表数据
for (i = start; i <= end ; i++)
{
switch(s[i])
{
case 'b':
bData = LinkedListInsert(bData, i, );
break;
case 'i':
iData = LinkedListInsert(iData, i, );
break;
case 'n':
nData = LinkedListInsert(nData, i, );
break;
case 'g':
gLen++;
gData = LinkedListInsert(gData, i, );
break;
default:
return ;
}
}
LinkedList p = gData->next;
i = ;
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(, ) + );
} int main()
{
printf("%d",howmany("Test"));
}