從給定序列中形成最小數 · GeeksForGeeks 中文系列教程

# 從給定序列中形成最小數 > 原文： [https://www.geeksforgeeks.org/form-minimum-number-from-given-sequence/](https://www.geeksforgeeks.org/form-minimum-number-from-given-sequence/) 給定一個僅包含`I`和`D`的模式。 `I`用于增加， `D`用于減少。設計一種算法以按照該模式打印最小數量。 1 到 9 的數字不能重復。 **示例**： ``` Input: D Output: 21 Input: I Output: 12 Input: DD Output: 321 Input: II Output: 123 Input: DIDI Output: 21435 Input: IIDDD Output: 126543 Input: DDIDDIID Output: 321654798 ``` 資料來源：[亞馬遜面試問題](https://www.geeksforgeeks.org/amazon-interview-experience-set-241-1-5-years-experience/) [](https://practice.geeksforgeeks.org/problem-page.php?pid=371) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。以下是一些重要的觀察由于數字不能重復，因此輸出中最多可以有 9 個數字。同樣，輸出中的位數比輸入中的字符數多一。請注意，輸入的第一個字符對應于輸出中的兩位數字。想法是遍歷輸入數組，并跟蹤到目前為止的最后打印數字和最大打印數字。以下是上述想法的實現。 ## C++ ```cpp // C++ program to print minimum number that can be formed // from a given sequence of Is and Ds #include <bits/stdc++.h> using namespace std; // Prints the minimum number that can be formed from // input sequence of I's and D's void PrintMinNumberForPattern(string arr) { ????// Initialize current_max (to make sure that ????// we don't use repeated character ????int curr_max = 0; ????// Initialize last_entry (Keeps track for ????// last printed digit) ????int last_entry = 0; ????int j; ????// Iterate over input array ????for (int i=0; i<arr.length(); i++) ????{ ????????// Initialize 'noOfNextD' to get count of ????????// next D's available ????????int noOfNextD = 0; ????????switch(arr[i]) ????????{ ????????case 'I': ????????????// If letter is 'I' ????????????// Calculate number of next consecutive D's ????????????// available ????????????j = i+1; ????????????while (arr[j] == 'D' && j < arr.length()) ????????????{ ????????????????noOfNextD++; ????????????????j++; ????????????} ????????????if (i==0) ????????????{ ????????????????curr_max = noOfNextD + 2; ????????????????// If 'I' is first letter, print incremented ????????????????// sequence from 1 ????????????????cout << " " << ++last_entry; ????????????????cout << " " << curr_max; ????????????????// Set max digit reached ????????????????last_entry = curr_max; ????????????} ????????????else ????????????{ ????????????????// If not first letter ????????????????// Get next digit to print ????????????????curr_max = curr_max + noOfNextD + 1; ????????????????// Print digit for I ????????????????last_entry = curr_max; ????????????????cout << " " << last_entry; ????????????} ????????????// For all next consecutive 'D' print? ????????????// decremented sequence ????????????for (int k=0; k<noOfNextD; k++) ????????????{ ????????????????cout << " " << --last_entry; ????????????????i++; ????????????} ????????????break; ????????// If letter is 'D' ????????case 'D': ????????????if (i == 0) ????????????{ ????????????????// If 'D' is first letter in sequence ????????????????// Find number of Next D's available ????????????????j = i+1; ????????????????while (arr[j] == 'D' && j < arr.length()) ????????????????{ ????????????????????noOfNextD++; ????????????????????j++; ????????????????} ????????????????// Calculate first digit to print based on? ????????????????// number of consecutive D's ????????????????curr_max = noOfNextD + 2; ????????????????// Print twice for the first time ????????????????cout << " " << curr_max << " " << curr_max - 1; ????????????????// Store last entry ????????????????last_entry = curr_max - 1; ????????????} ????????????else ????????????{ ????????????????// If current 'D' is not first letter ????????????????// Decrement last_entry ????????????????cout << " " << last_entry - 1; ????????????????last_entry--; ????????????} ????????????break; ????????} ????} ????cout << endl; } // Driver program to test above int main() { ????PrintMinNumberForPattern("IDID"); ????PrintMinNumberForPattern("I"); ????PrintMinNumberForPattern("DD"); ????PrintMinNumberForPattern("II"); ????PrintMinNumberForPattern("DIDI"); ????PrintMinNumberForPattern("IIDDD"); ????PrintMinNumberForPattern("DDIDDIID"); ????return 0; } ``` ## Java ```java // Java program to print minimum number that can be formed? // from a given sequence of Is and Ds? class GFG? { ????// Prints the minimum number that can be formed from? ????// input sequence of I's and D's? ????static void PrintMinNumberForPattern(String arr)? ????{ ????????// Initialize current_max (to make sure that? ????????// we don't use repeated character? ????????int curr_max = 0; ????????// Initialize last_entry (Keeps track for? ????????// last printed digit)? ????????int last_entry = 0; ????????int j; ????????// Iterate over input array? ????????for (int i = 0; i < arr.length(); i++)? ????????{ ????????????// Initialize 'noOfNextD' to get count of? ????????????// next D's available? ????????????int noOfNextD = 0; ????????????switch (arr.charAt(i)) ????????????{ ????????????????case 'I': ????????????????????// If letter is 'I'? ????????????????????// Calculate number of next consecutive D's? ????????????????????// available? ????????????????????j = i + 1; ????????????????????while (j < arr.length() && arr.charAt(j) == 'D')? ????????????????????{ ????????????????????????noOfNextD++; ????????????????????????j++; ????????????????????} ????????????????????if (i == 0)? ????????????????????{ ????????????????????????curr_max = noOfNextD + 2; ????????????????????????// If 'I' is first letter, print incremented? ????????????????????????// sequence from 1? ????????????????????????System.out.print(" " + ++last_entry); ????????????????????????System.out.print(" " + curr_max); ????????????????????????// Set max digit reached? ????????????????????????last_entry = curr_max; ????????????????????}? ????????????????????else? ????????????????????{ ????????????????????????// If not first letter? ????????????????????????// Get next digit to print? ????????????????????????curr_max = curr_max + noOfNextD + 1; ????????????????????????// Print digit for I? ????????????????????????last_entry = curr_max; ????????????????????????System.out.print(" " + last_entry); ????????????????????} ????????????????????// For all next consecutive 'D' print? ????????????????????// decremented sequence? ????????????????????for (int k = 0; k < noOfNextD; k++) ????????????????????{ ????????????????????????System.out.print(" " + --last_entry); ????????????????????????i++; ????????????????????} ????????????????????break; ????????????????// If letter is 'D'? ????????????????case 'D': ????????????????????if (i == 0) ????????????????????{ ????????????????????????// If 'D' is first letter in sequence? ????????????????????????// Find number of Next D's available? ????????????????????????j = i + 1; ????????????????????????while (j < arr.length()&&arr.charAt(j) == 'D')? ????????????????????????{ ????????????????????????????noOfNextD++; ????????????????????????????j++; ????????????????????????} ????????????????????????// Calculate first digit to print based on? ????????????????????????// number of consecutive D's? ????????????????????????curr_max = noOfNextD + 2; ????????????????????????// Print twice for the first time? ????????????????????????System.out.print(" " + curr_max + " " + (curr_max - 1)); ????????????????????????// Store last entry? ????????????????????????last_entry = curr_max - 1; ????????????????????}? ????????????????????else ????????????????????{ ????????????????????????// If current 'D' is not first letter? ????????????????????????// Decrement last_entry? ????????????????????????System.out.print(" " + (last_entry - 1)); ????????????????????????last_entry--; ????????????????????} ????????????????????break; ????????????} ????????} ????????System.out.println(); ????} ????// Driver code? ????public static void main(String[] args)? ????{ ????????PrintMinNumberForPattern("IDID"); ????????PrintMinNumberForPattern("I"); ????????PrintMinNumberForPattern("DD"); ????????PrintMinNumberForPattern("II"); ????????PrintMinNumberForPattern("DIDI"); ????????PrintMinNumberForPattern("IIDDD"); ????????PrintMinNumberForPattern("DDIDDIID"); ????} } // This code is contributed by Princi Singh ``` ## Python3 ```py # Python3 program to print minimum number that # can be formed from a given sequence of Is and Ds # Prints the minimum number that can be formed from # input sequence of I's and D's def PrintMinNumberForPattern(arr): ????# Initialize current_max (to make sure that ????# we don't use repeated character ????curr_max = 0 ????# Initialize last_entry (Keeps track for ????# last printed digit) ????last_entry = 0 ????i = 0 ????# Iterate over input array ????while i < len(arr): ????????# Initialize 'noOfNextD' to get count of ????????# next D's available ????????noOfNextD = 0 ????????if arr[i] == "I": ????????????# If letter is 'I' ????????????# Calculate number of next consecutive D's ????????????# available ????????????j = i + 1 ????????????while j < len(arr) and arr[j] == "D": ????????????????noOfNextD += 1 ????????????????j += 1 ????????????if i == 0: ????????????????curr_max = noOfNextD + 2 ????????????????last_entry += 1 ????????????????# If 'I' is first letter, print incremented ????????????????# sequence from 1 ????????????????print("", last_entry, end = "") ????????????????print("", curr_max, end = "") ????????????????# Set max digit reached ????????????????last_entry = curr_max ????????????else: ????????????????# If not first letter ????????????????# Get next digit to print ????????????????curr_max += noOfNextD + 1 ????????????????# Print digit for I ????????????????last_entry = curr_max ????????????????print("", last_entry, end = "") ????????????# For all next consecutive 'D' print ????????????# decremented sequence ????????????for k in range(noOfNextD): ????????????????last_entry -= 1 ????????????????print("", last_entry, end = "") ????????????????i += 1 ????????# If letter is 'D' ????????elif arr[i] == "D": ????????????if i == 0: ????????????????# If 'D' is first letter in sequence ????????????????# Find number of Next D's available ????????????????j = i + 1 ????????????????while j < len(arr) and arr[j] == "D": ????????????????????noOfNextD += 1 ????????????????????j += 1 ????????????????# Calculate first digit to print based on ????????????????# number of consecutive D's ????????????????curr_max = noOfNextD + 2 ????????????????# Print twice for the first time ????????????????print("", curr_max, curr_max - 1, end = "") ????????????????# Store last entry ????????????????last_entry = curr_max - 1 ????????????else: ????????????????# If current 'D' is not first letter ????????????????# Decrement last_entry ????????????????print("", last_entry - 1, end = "") ????????????????last_entry -= 1 ????????i += 1 ????print() # Driver code if __name__ == "__main__": ????PrintMinNumberForPattern("IDID") ????PrintMinNumberForPattern("I") ????PrintMinNumberForPattern("DD") ????PrintMinNumberForPattern("II") ????PrintMinNumberForPattern("DIDI") ????PrintMinNumberForPattern("IIDDD") ????PrintMinNumberForPattern("DDIDDIID") # This code is contributed by # sanjeev2552 ``` ## C# ```cs // C# program to print minimum number that can be formed? // from a given sequence of Is and Ds? using System; class GFG? { ????// Prints the minimum number that can be formed from? ????// input sequence of I's and D's? ????static void PrintMinNumberForPattern(String arr)? ????{ ????????// Initialize current_max (to make sure that? ????????// we don't use repeated character? ????????int curr_max = 0; ????????// Initialize last_entry (Keeps track for? ????????// last printed digit)? ????????int last_entry = 0; ????????int j; ????????// Iterate over input array? ????????for (int i = 0; i < arr.Length; i++)? ????????{ ????????????// Initialize 'noOfNextD' to get count of? ????????????// next D's available? ????????????int noOfNextD = 0; ????????????switch (arr[i]) ????????????{ ????????????????case 'I': ????????????????????// If letter is 'I'? ????????????????????// Calculate number of next consecutive D's? ????????????????????// available? ????????????????????j = i + 1; ????????????????????while (j < arr.Length && arr[j] == 'D')? ????????????????????{ ????????????????????????noOfNextD++; ????????????????????????j++; ????????????????????} ????????????????????if (i == 0)? ????????????????????{ ????????????????????????curr_max = noOfNextD + 2; ????????????????????????// If 'I' is first letter, print incremented? ????????????????????????// sequence from 1? ????????????????????????Console.Write(" " + ++last_entry); ????????????????????????Console.Write(" " + curr_max); ????????????????????????// Set max digit reached? ????????????????????????last_entry = curr_max; ????????????????????}? ????????????????????else ????????????????????{ ????????????????????????// If not first letter? ????????????????????????// Get next digit to print? ????????????????????????curr_max = curr_max + noOfNextD + 1; ????????????????????????// Print digit for I? ????????????????????????last_entry = curr_max; ????????????????????????Console.Write(" " + last_entry); ????????????????????} ????????????????????// For all next consecutive 'D' print? ????????????????????// decremented sequence? ????????????????????for (int k = 0; k < noOfNextD; k++) ????????????????????{ ????????????????????????Console.Write(" " + --last_entry); ????????????????????????i++; ????????????????????} ????????????????????break; ????????????????// If letter is 'D'? ????????????????case 'D': ????????????????????if (i == 0) ????????????????????{ ????????????????????????// If 'D' is first letter in sequence? ????????????????????????// Find number of Next D's available? ????????????????????????j = i + 1; ????????????????????????while (j < arr.Length&&arr[j] == 'D')? ????????????????????????{ ????????????????????????????noOfNextD++; ????????????????????????????j++; ????????????????????????} ????????????????????????// Calculate first digit to print based on? ????????????????????????// number of consecutive D's? ????????????????????????curr_max = noOfNextD + 2; ????????????????????????// Print twice for the first time? ????????????????????????Console.Write(" " + curr_max + " " + (curr_max - 1)); ????????????????????????// Store last entry? ????????????????????????last_entry = curr_max - 1; ????????????????????}? ????????????????????else ????????????????????{ ????????????????????????// If current 'D' is not first letter? ????????????????????????// Decrement last_entry? ????????????????????????Console.Write(" " + (last_entry - 1)); ????????????????????????last_entry--; ????????????????????} ????????????????????break; ????????????} ????????} ????????Console.WriteLine(); ????} ????// Driver code? ????public static void Main(String[] args)? ????{ ????????PrintMinNumberForPattern("IDID"); ????????PrintMinNumberForPattern("I"); ????????PrintMinNumberForPattern("DD"); ????????PrintMinNumberForPattern("II"); ????????PrintMinNumberForPattern("DIDI"); ????????PrintMinNumberForPattern("IIDDD"); ????????PrintMinNumberForPattern("DDIDDIID"); ????} } // This code is contributed by Princi Singh ``` ## PHP ```php <?php // PHP program to print minimum // number that can be formed // from a given sequence of? // Is and Ds // Prints the minimum number? // that can be formed from // input sequence of I's and D's function PrintMinNumberForPattern($arr) { ????// Initialize current_max? ????// (to make sure that ????// we don't use repeated? ????// character ????$curr_max = 0; ????// Initialize last_entry? ????// (Keeps track for ????// last printed digit) ????$last_entry = 0; ????$j; ????// Iterate over ????// input array ????for ($i = 0; $i < strlen($arr); $i++) ????{ ????????// Initialize 'noOfNextD' ????????// to get count of ????????// next D's available ????????$noOfNextD = 0; ????????switch($arr[$i]) ????????{ ????????case 'I': ????????????// If letter is 'I' ????????????// Calculate number of? ????????????// next consecutive D's ????????????// available ????????????$j = $i + 1; ????????????while ($arr[$j] == 'D' &&? ???????????????????$j < strlen($arr)) ????????????{ ????????????????$noOfNextD++; ????????????????$j++; ????????????} ????????????if ($i == 0) ????????????{ ????????????????$curr_max = $noOfNextD + 2; ????????????????// If 'I' is first letter,? ????????????????// print incremented ????????????????// sequence from 1 ????????????????echo " " , ++$last_entry; ????????????????echo " " , $curr_max; ????????????????// Set max? ????????????????// digit reached ????????????????$last_entry = $curr_max; ????????????} ????????????else ????????????{ ????????????????// If not first letter ????????????????// Get next digit ????????????????// to print ????????????????$curr_max = $curr_max +? ????????????????????????????$noOfNextD + 1; ????????????????// Print digit for I ????????????????$last_entry = $curr_max; ????????????????echo " " , $last_entry; ????????????} ????????????// For all next consecutive 'D'? ????????????// print decremented sequence ????????????for ($k = 0; $k < $noOfNextD; $k++) ????????????{ ????????????????echo " " , --$last_entry; ????????????????$i++; ????????????} ????????????break; ????????// If letter is 'D' ????????case 'D': ????????????if ($i == 0) ????????????{ ????????????????// If 'D' is first letter? ????????????????// in sequence. Find number ????????????????// of Next D's available ????????????????$j = $i+1; ????????????????while (($arr[$j] == 'D') &&? ???????????????????????($j < strlen($arr))) ????????????????{ ????????????????????$noOfNextD++; ????????????????????$j++; ????????????????} ????????????????// Calculate first digit? ????????????????// to print based on? ????????????????// number of consecutive D's ????????????????$curr_max = $noOfNextD + 2; ????????????????// Print twice for ????????????????// the first time ????????????????echo " " , $curr_max ,? ?????????????????????" " ,$curr_max - 1; ????????????????// Store last entry ????????????????$last_entry = $curr_max - 1; ????????????} ????????????else ????????????{ ????????????????// If current 'D'? ????????????????// is not first letter ????????????????// Decrement last_entry ????????????????echo " " , $last_entry - 1; ????????????????$last_entry--; ????????????} ????????????break; ????????} ????} echo "\n"; } // Driver Code PrintMinNumberForPattern("IDID"); PrintMinNumberForPattern("I"); PrintMinNumberForPattern("DD"); PrintMinNumberForPattern("II"); PrintMinNumberForPattern("DIDI"); PrintMinNumberForPattern("IIDDD"); PrintMinNumberForPattern("DDIDDIID"); // This code is contributed by aj_36 ?> ``` **輸出**： ``` 1 3 2 5 4 1 2 3 2 1 1 2 3 2 1 4 3 5 1 2 6 5 4 3 3 2 1 6 5 4 7 9 8 ``` Swapnil Trambake 建議此解決方案。 **替代解決方案**：讓我們觀察一下最小數量的一些事實： * 這些數字不能重復，因此輸出最多可以有 9 個數字。 * 為了在輸出的每個索引處形成一個最小數量，我們對可以放置在該索引上的最小數量感興趣。想法是遍歷整個輸入數組，跟蹤可放置在輸出的那個位置的最小數字（1-9）。當然，棘手的部分是在索引不是 0 的位置遇到`D`時發生的。在這種情況下，我們必須跟蹤`D`左側最接近的`I`，并在輸出向量中`I`和`D`之間的每個數字增加 1。我們介紹了以下基本情況： * 如果輸入的第一個字符是`I`，那么我們將在輸出向量中追加 1 和 2，并將最小可用數字設置為 3。將最新的`I`的索引設置為 1。 * 如果輸入的第一個字符為`D`，則我們在輸出向量中附加 2 和 1，最小可用數字設置為 3，而最新的`D`的索引設置為 0。現在，我們將輸入字符串從索引 1 迭代到結束，并： * 如果掃描的字符為`I`，則尚未使用的最小值附加到輸出矢量上。我們將最小數字的值增加。可用，最近的`I`的索引也會更新。 * 如果在輸入數組的索引`i`處掃描的字符為`D`，則在輸出中將輸出向量中的第`i`個元素附加到輸出中，并跟蹤最接近`D`左側的`I`，并將輸出向量中`I`和`D`之間的每個數字加 1。以下是相同的程序： ## C++ ``` // C++ program to print minimum number that can be formed // from a given sequence of Is and Ds #include<bits/stdc++.h> using namespace std; void printLeast(string arr) { ????// min_avail represents the minimum number which is ????// still available for inserting in the output vector. ????// pos_of_I keeps track of the most recent index ????// where 'I' was encountered w.r.t the output vector ????int min_avail = 1, pos_of_I = 0; ????//vector to store the output ????vector<int>v; ????// cover the base cases ????if (arr[0]=='I') ????{ ????????v.push_back(1); ????????v.push_back(2); ????????min_avail = 3; ????????pos_of_I = 1; ????} ????else ????{ ????????v.push_back(2); ????????v.push_back(1); ????????min_avail = 3; ????????pos_of_I = 0; ????} ????// Traverse rest of the input ????for (int i=1; i<arr.length(); i++) ????{ ????????if (arr[i]=='I') ????????{ ????????????v.push_back(min_avail); ????????????min_avail++; ????????????pos_of_I = i+1; ????????} ????????else ????????{ ????????????v.push_back(v[i]); ????????????for (int j=pos_of_I; j<=i; j++) ????????????????v[j]++; ????????????min_avail++; ????????} ????} ????// print the number ????for (int i=0; i<v.size(); i++) ????????cout << v[i] << " "; ????cout << endl; } // Driver program to check the above function int main() { ????printLeast("IDID"); ????printLeast("I"); ????printLeast("DD"); ????printLeast("II"); ????printLeast("DIDI"); ????printLeast("IIDDD"); ????printLeast("DDIDDIID"); ????return 0; } ```