今天是元旦,开篇先祝福大家在新的一年心想事成,工作顺利,开心生活每一天【英雄会】微软题目:几个bing-LMLPHP

看到【英雄会】上出现了微软出的题目:几个bing,题目内容如下:

最初的想法:分别记录四个字符出现的位置编号,通过后者字符编号大于前者字符编号条件,循环遍历得到符合条件的次数,但该算法的时间复杂度O(n),实现绝对可以实现,但肯定行不通,改变策略。

分析:通过题面分析可知,是从字符串中取‘b’、‘i’、‘n’、‘g’四个字符进行排列组合,重新生成字符串”bing”的过程。但注意的是组合在一块的序列是有一定规律的,序号是逐渐递增的【(4,5,6,10) (4,5,9,10),(4,8,9,10)和(7,8,9,10)】,这就提供了一个先决条件:后者字符必须在前者字符存在的情况下进行计数和组合。算法复杂度为O(n).

做法:分别记录b、bi、bin、bing生成的排列次数,后者次数=前者基础次数+后者自身次数(例如:bi次数=b次数+bi自身次数)

以字符串"iinbinbing"为例,对字符串中字符进行遍历:

① 分别用四个计数器来记录组合

b

bi

bin

bing

0

0

0

0

② 当遍历’i’时,b的计数为0,在没有b存在的基础上,bing是不可能出现的

b

bi

bin

bing

0

0

0

0

③ 当遍历’i’时,b的计数为0,在没有b存在的基础上,bing是不可能出现的

b

bi

bin

bing

0

0

0

0

④ 当遍历’b’时,bing是以b开始的,则b计数为1:

b

bi

bin

bing

1

0

0

0

⑤ 当遍历’i’时,b的计数为1,在有b存在的基础上,bi是可以出现的,则bi计数为1(b计数+bi当前计数):

b

bi

bin

bing

1

1

0

0

⑥ 当遍历’n’时,i的计数为1,在有bi存在的基础上,bin是可以出现的,则bin计数为1(bi计数+bin计数):

b

bi

bin

bing

1

1

1

0

⑦ 当遍历’b’时,则b计数为2:

b

bi

bin

bing

2

1

1

0

⑧ 当遍历’i’时,b的计数为2,在有b存在的基础上,bi可能出现的次数为3(b计数+bi当前计数):

b

bi

bin

bing

2

3

1

0

⑨ 当遍历’n’时,i的计数为2,在有bi存在的基础上,bi可能出现的次数为4(bi计数+bin当前计数):

b

bi

bin

bing

2

3

4

0

⑩ 当遍历’g’时,在有bin存在的基础上,bing可能出现的次数为4(bin计数+bing当前计数):

b

bi

bin

bing

2

3

4

4

这样就得到了bing字符串的组合方式有4种了,代码实现如下:

using System;

public class Test
{
public static int howmany(string s)
{
int bCount = ;
int biCount = ;
int binCount = ;
int bingCount = ; for (int index = , length = s.Length; index < length; index++)
{
switch (s[index])
{
case 'b': bCount = ++bCount % ;
break;
case 'i': biCount = biCount % + bCount;
break;
case 'n': binCount = binCount % + biCount;
break;
case 'g': bingCount = bingCount % + binCount;
break;
}
}
return bingCount % ;
} //start 提示:自动阅卷起始唯一标识,请勿删除或增加。
public static void Main()
{
Console.WriteLine(howmany("iinbinbing "));
}
//end //提示:自动阅卷结束唯一标识,请勿删除或增加。
}
05-20 05:01
查看更多