#practiceLinkDiv { 表示: なし !重要; }数値の桁を含む文字列が与えられます。番号には、同じ連続数字が多数含まれる場合があります。課題は、数字の綴り方の数を数えるということです。
たとえば、8884441100 を考えてみると、単にトリプル 8、トリプル 4、ダブル 2、ダブル ゼロと綴ることができます。 double 8 8 4 double 4 2 2 double 0 と綴ることもできます。
例:
Input : num = 100 Output : 2 The number 100 has only 2 possibilities 1) one zero zero 2) one double zero. Input : num = 11112 Output: 8 1 1 1 1 2 11 1 1 2 1 1 11 2 1 11 1 2 11 11 2 1 111 2 111 1 2 1111 2 Input : num = 8884441100 Output: 64 Input : num = 12345 Output: 1 Input : num = 11111 Output: 16Recommended Practice 数字を綴ってください 試してみてください!
これは順列と組み合わせの単純な問題です。質問 11112 で与えられたテスト ケースの例を考えてみます。答えは 1111 の可能な部分文字列の数によって異なります。「1111」の可能な部分文字列の数は 2^3 = 8 です。これは、4 - 1 = 3 個の区切り文字 '|' の組み合わせの数であるためです。文字列の 2 つの文字の間 (文字列で表される数値の桁): '1|1|1|1'。組み合わせは特定の 1 を選択するかどうかに依存し、「2」の場合は 2^0 = 1 の可能性が 1 つだけあるため、「11112」の答えは 8*1 = 8 になります。
したがって、このアプローチは、文字列内の特定の連続する数字をカウントし、前の結果と 2^(count-1) を乗算することです。
C++// C++ program to count number of ways we // can spell a number #include
// Java program to count number of ways we // can spell a number import java.io.*; class GFG { // Function to calculate all possible // spells of a number with repeated digits // num --> string which is favourite number static long spellsCount(String num) { int n = num.length(); // final count of total possible spells long result = 1; // iterate through complete number for (int i = 0; i < n; i++) { // count contiguous frequency of // particular digit num[i] int count = 1; while (i < n - 1 && num.charAt(i + 1) == num.charAt(i)) { count++; i++; } // Compute 2^(count-1) and multiply // with result result = result * (long)Math.pow(2 count - 1); } return result; } public static void main(String[] args) { String num = '11112'; System.out.print(spellsCount(num)); } } // This code is contributed by Anant Agarwal.
# Python3 program to count number of # ways we can spell a number # Function to calculate all possible # spells of a number with repeated # digits num --> string which is # favourite number def spellsCount(num): n = len(num); # final count of total # possible spells result = 1; # iterate through complete # number i = 0; while(i<n): # count contiguous frequency # of particular digit num[i] count = 1; while (i < n - 1 and num[i + 1] == num[i]): count += 1; i += 1; # Compute 2^(count-1) and # multiply with result result = result * int(pow(2 count - 1)); i += 1; return result; # Driver Code num = '11112'; print(spellsCount(num)); # This code is contributed # by mits
// C# program to count number of ways we // can spell a number using System; class GFG { // Function to calculate all possible // spells of a number with repeated // digits num --> string which is // favourite number static long spellsCount(String num) { int n = num.Length; // final count of total possible // spells long result = 1; // iterate through complete number for (int i = 0; i < n; i++) { // count contiguous frequency of // particular digit num[i] int count = 1; while (i < n - 1 && num[i + 1] == num[i]) { count++; i++; } // Compute 2^(count-1) and multiply // with result result = result * (long)Math.Pow(2 count - 1); } return result; } // Driver code public static void Main() { String num = '11112'; Console.Write(spellsCount(num)); } } // This code is contributed by nitin mittal.
// PHP program to count // number of ways we // can spell a number // Function to calculate // all possible spells of // a number with repeated // digits num --> string // which is favourite number function spellsCount($num) { $n = strlen($num); // final count of total // possible spells $result = 1; // iterate through // complete number for ($i = 0; $i < $n; $i++) { // count contiguous frequency // of particular digit num[i] $count = 1; while ($i < $n - 1 && $num[$i + 1] == $num[$i]) { $count++; $i++; } // Compute 2^(count-1) and // multiply with result $result = $result * pow(2 $count - 1); } return $result; } // Driver Code $num = '11112'; echo spellsCount($num); // This code is contributed // by nitin mittal. ?> <script> // Javascript program to count number of // ways we can spell a number // Function to calculate all possible // spells of a number with repeated // digits num --> string which is // favourite number function spellsCount(num) { let n = num.length; // Final count of total possible // spells let result = 1; // Iterate through complete number for (let i = 0; i < n; i++) { // Count contiguous frequency of // particular digit num[i] let count = 1; while (i < n - 1 && num[i + 1] == num[i]) { count++; i++; } // Compute 2^(count-1) and multiply // with result result = result * Math.pow(2 count - 1); } return result; } // Driver code let num = '11112'; document.write(spellsCount(num)); // This code is contributed by code_hunt </script>
出力
8
時間計算量: O(n*log(n))
補助スペース: ○(1)
この問題を解決する別のアプローチがある場合は、共有してください。