微软几个bing 的golang代码

舞林 · · 4055 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目链接 http://hero.csdn.net/Question/Details?ID=215&ExamID=210

题目详情

本届大赛由微软必应词典冠名,必应词典(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取余数之后的结果。 最常想到的就是4个循环的解法,但是效率不高 代码如下

package main

import (
    "fmt"
    "math/rand"
    "time"
)

const (
    strlen int = 1000
)

func main() {
    rand.Seed(time.Now().Unix())
    bing := []string{"b", "i", "n", "g"}
    var strAll [strlen]string
    for i := 0; i < strlen; i++ {
        strAll[i] = fmt.Sprintf("%s", bing[rand.Intn(len(bing))])
    }
    //strAll := [strlen]string{"i", "i", "n", "b", "i", "n", "b", "i", "n", "g", "g"}
    fmt.Println(strAll)

    var (
        arr_b, arr_i, arr_n, arr_g []int
        count                      int64 = 0
    )

    for i := 0; i < strlen; i++ {
        if strAll[i] == "b" {
            arr_b = append(arr_b, i)
        } else if strAll[i] == "i" {
            arr_i = append(arr_i, i)
        } else if strAll[i] == "n" {
            arr_n = append(arr_n, i)
        } else if strAll[i] == "g" {
            arr_g = append(arr_g, i)
        }
    }
    //fmt.Println(arr_b, arr_i, arr_n, arr_g)

    for i := 0; i < len(arr_b); i++ {
        for j := 0; j < len(arr_i); j++ {
            for k := 0; k < len(arr_n); k++ {
                for h := 0; h < len(arr_g); h++ {
                    if arr_b[i] < arr_i[j] && arr_i[j] < arr_n[k] && arr_n[k] < arr_g[h] {
                        //fmt.Println(arr_b[i]+1, arr_i[j]+1, arr_n[k]+1, arr_g[h]+1)
                        count++
                    }
                }
            }
        }
    }
    fmt.Println(count % 1000000007)
}

1000个的时候就要3-5秒了,太慢

下面2个链接是别人的就讲解

http://www.cnblogs.com/muzihai1988/p/3500383.html

http://www.cnblogs.com/WhyEngine/p/3522309.html

声明:此文系舞林cuzn(www.wulinlw.org)原创稿件,转载请保留版权


有疑问加站长微信联系(非本文作者)

本文来自:舞林cuzn blog

感谢作者:舞林

查看原文:微软几个bing 的golang代码

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4055 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传