日本Yahoo算法笔试题目分享_level_1

Question

问题

用英文单词来组合成一句话，文章中只包含英文字母(a-z,A-z)，半角空格，和句末的半角英文句号（.）
要求组合成的英文文章的平均单词长度最长。

平均单词长度解释 例如：This is a dog. 包含This, is, a, dog 四个单词，则该句话的平均单词长度为（4 + 2 + 1 + 3）/4 = 2.5

其中，组成一句话的单词可以从{}中选择，例如：
当输入为s, s={That,This} is a {cat,dog,bear}.的时候，可以组合成一下6句话：
- This is a cat.
- This is a dog.
- This is a bear.
- That is a cat.
- That is a dog.
- That is a bear
这个时候，求出以上组合中平均单词长度最大的值。

Input

s

• s长度少于100，并且一定包含至少一个英文单词。
• s由（a-z,A-Z）,半角空格( ), 大括号({,})以及半角逗号(,)组成，并且句末一定有半角句号(.)存在且半角句号只在句末出现。
• 半角空格不会连续出现两次。
• 半角空格不会在开头出现，且空格后面不会直接出现半角句号(.)
• {}一定按顺序成对出现，且{}内只有英文单词和半角逗号存在。
• 末尾换行符号为\n

Output

输出单词平均长度最大值，绝对误差小数点后6位数

解答例子

Sample One

Input

This is a dog.

Output

2.5

Sample Two

Input

{This,That} is a {dog,cat,bear}.

Output

2.75

Sample Three

Input

{a,aa,aaaaaa} bbbbb {c,ddddd,eee}.

Output

5.333333

结果小数点后超过六位时，保留至小数点后6位小数。

Sample Four

Input

A.

Output

1

s仅为一个单词时。

Answer 1

看来题目太过简单，不值得大咖回答。主要考察的应该也就是字符串操作，正则表达吧，那我就把我当时php实现的答案分享一下，求交流指正。

php<?php

$s = "{This,That} is a {cat,dog,bear}.";
// 将输入内容拆分为数组
$arr = preg_split('/\s|{|}|\./',$s);    

$words_count = 0;       // 单词计数
$words_sum_length = 0;  // 所有单词总长度

foreach($arr as $value) {
    if($value) {
        $cur_word_length = 0;
        $words_count++;
        $inside_value = explode(',', $value);
        foreach($inside_value as $cur_word) {
            $cur_word_length = strlen($cur_word) > $cur_word_length ? strlen($cur_word) : $cur_word_length;
        }
        $words_sum_length += $cur_word_length;
    }
}

$avg_length = round($words_sum_length/$words_count,6);

echo $avg_length;