[转帖]微软必应·英雄会第三届在线编程大赛:几个bing?_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3389 | 回复: 0   主题: [转帖]微软必应·英雄会第三届在线编程大赛:几个bing?        下一篇 
yang.liu
注册用户
等级:少校
经验:1182
发帖:77
精华:1
注册:2014-1-3
状态:离线
发送短消息息给yang.liu 加好友    发送短消息息给yang.liu 发消息
发表于: IP:您无权察看 2014-1-7 9:10:45 | [全部帖] [楼主帖] 楼主

微软必应·英雄会第三届在线编程大赛:几个bing?



分类:
编程挑战2014-01-03

首先吐槽一下CSDN的这个编程比赛,什么情况啊。

第一届,第二届,加上这次的第三届,代码统统提价之后都是“编译和测试中,请稍后...”

不要说我是算法的问题,我本机往极限数据测试也不会超过0.1秒的。

难不成这个提交也是有窍门的?

好了,废话不多说,上题:

题目详情:

本届大赛由微软必应词典冠名,必应词典(http://cn.bing.com/dict/?form=BDVSP4&mkt=zh-CN&setlang=ZH)是微软推出的新一代英语学习引擎,里面收录了很多我们常见的单词。但现实生活中,我们也经常能看到一些毫无规则的字符串,导致词典无法正常收录,不过,我们是否可以从无规则的字符串中提取出正规的单词呢?

例如有一个字符串"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取余数之后的结果。

答题说明:

main函数可不用完成。

简单的解析:

如果单纯的用递归遍历的话,那么复杂度就是O2。这样肯定是不符合要求的。

我想这题肯定存在O1的方式来解决。

想了想,一个一个字符的往后推算,最后遇到g就加和的话,应该可以完成。

于是写了写代码,个人感觉没有错,如果各位发现什么问题,欢迎指出。

大体上的思路就是:

遇到i时,只记录b的数目和i原有的数目。

遇到n时,只记录i的数目和n原有的数目。

遇到g时,只记录n的数目和num原有的数目。

最后统计出来的结果应该就是总数量。

代码:

[java]view plaincopyprint?

  1. publicclass Test4 { 
  2.       staticchar[] ch; 
  3.       staticint index=0; 
  4.       staticint b_num=0; 
  5.       staticint i_num=0; 
  6.       staticint n_num=0; 
  7.       staticint num=0; 
  8.       
  9.       publicstaticvoid main(String[] args) { 
  10.             
  11.             System.out.println(getNum("iinbinbinginng")); 
  12.       } 
  13.       
  14.       publicstaticint getNum(String str){ 
  15.             ch=str.toCharArray(); 
  16.             for (int i = 0; i < ch.length; i++) { 
  17.                   switch (ch[i]) { 
  18.                         case'b': 
  19.                         b_num++; 
  20.                         break; 
  21.                         case'i': 
  22.                         i_num+=b_num; 
  23.                         break; 
  24.                         case'n': 
  25.                         n_num+=i_num; 
  26.                         break; 
  27.                         case'g': 
  28.                         num+=n_num; 
  29.                         break; 
  30.                         default: 
  31.                         break; 
  32.                   } 
  33.             } 
  34.             return num%(10^9+7); 
  35.       } 




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论