簡単 0件解決済み 正答率0%

コイン投げの連続

コイン投げの記録から、表の最長連続、裏の最長連続、連続の個数を求めます。

このチャレンジで学べること

  • 列をできるだけ長い連続に分割する
  • 値ごとに最長の連続を記録する
  • 連続の個数を数える

問題

原文(英語)を表示

確率の実験で、コインを何度も投げて結果を H(表)と T(裏)の文字列として記録しています。ここでいう「連続」とは、同じ結果が続くできるだけ長いかたまりのことで、HHTHHH には HH、T、HHH の3つの連続があります。ランダムな記録の中の最長連続が意外と長いことに生徒はよく驚くので、実験ではそれを測っています。

coin_toss_streaks(tosses) を実装してください。

入力

tosses: 結果を順に並べたもの。H と T だけからなります。

出力

表の最長連続の長さ、裏の最長連続の長さ(一度も出なければ0)、連続の総数を [longest_heads, longest_tails, streaks] として返してください。

制約

0 ≤ tosses の長さ ≤ 100,000

例

例 1
入力:
tosses = "HHTHHH"

期待される出力:
expected = [3, 1, 3]
入力:
std::string tosses = "HHTHHH";

期待される出力:
std::vector<long long> expected = {3, 1, 3};
入力:
string tosses = "HHTHHH";

期待される出力:
long[] expected = new long[] {3, 1, 3};

解説

連続は HH、T、HHH なので、表の最長連続は3、裏の最長連続は1で、連続は3つです。

例 2
入力:
tosses = "TTTT"

期待される出力:
expected = [0, 4, 1]
入力:
std::string tosses = "TTTT";

期待される出力:
std::vector<long long> expected = {0, 4, 1};
入力:
string tosses = "TTTT";

期待される出力:
long[] expected = new long[] {0, 4, 1};

解説

表は一度も出ないので最長連続は0です。裏の連続が長さ4で1つあるので [0, 4, 1] です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

新しい連続は、添字0と、直前の結果と異なる位置で始まります。

ヒント 2

表と裏それぞれについて、最長の長さを1つずつ記録しましょう。

ヒント 3

空文字列には連続が1つもありません。

目安の計算量

時間 O(n)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。