跟随者数字解码
Problem statement:
问题陈述：
Given a pattern containing onlyI'sandD's.'I'stands for increasing and'D'for decreasing. Devise an algorithm to print the minimum number following that pattern. Digits are from1-9and digits can't repeat.
给定一个仅包含I和D的模式。“ I”代表增加，“ D”代表减少。 设计一种算法以按照该模式打印最小数量。 数字为1-9，数字不能重复。
Example:
例：
Input:IIDDIDD Output:12543876
Solution
解
The pattern & number to be generated
生成的图案和编号
Length of minimumnumber = string length+1
最小数目L的ength=字符串长度+ 1
Hence, maximum string length possible is 8, since we can construct only with different digits (1-9)
因此，最大字符串长度为8，因为我们只能用不同的数字(1-9)进行构造
'I'means the next digit will be 1 greater than the current &'D'means the next digit will be 1 less than the current digit
“ I”表示下一个数字比当前数字大1，“ D”表示下一个数字比当前数字小1。
"II" → 123
“ II”→123
"DD" → 321
“ DD”→321
The problem can be used with help of stack. The concept is to create stack with consecutive number same as depth of a local contiguous sequence of 'D'.
该问题可以在堆栈的帮助下使用。概念是创建具有与本地连续序列“ D”的深度相同的连续数字的堆栈。
Prerequisite:
先决条件：
Input pattern, string s
输入模式，字符串s
Stack st to store the digits
堆叠st以存储数字
Function findMinFromPattern(string s)1. Declare a stack st; 2. FOR i=0 : pattern lengthEnQueue (st, i+1); //push i+1 at first, i+1 becuase i is 0-indexed IF (entire pattern is processed || s[i] =='I')While(stack is not empty){ Pop and printEnd WhileEND IFEND FOREND FUNCTION
C++ Implementation
C ++实现
#include <bits/stdc++.h>using namespace std;void findMinFromPattern(string s){stack<int> st; //stack declared using STLfor(int i=0;i<=s.length();i++){//push i+1 at first, i+1 becuase i is 0-indexed st.push(i+1); //when string length is processed or pattern in Iif(s.length()==i || s[i]=='I' ){//pop and print until stack is emptywhile(!st.empty()){cout<<st.top();st.pop();}}}cout<<endl;}int main(){cout<<"enter pattern\n"; string s;cin>>s;if(s.length()>8){cout<<"Not possible,length>8\n";}else{cout<<"The minimum number generated is:\n";findMinFromPattern(s);//function to print}return 0;}
Output
输出量
First run:enter patternIIDDIDDThe minimum number generated is:12543876Second run:enter patternIIIIIIIIDDDDIIINot possible,length>8
Example with explanation:
带有说明的示例：
Pattern string:IIDDIDD0 th iterationi=0EnQueue(st,i+1)Stack status:1S[i]=='I'So pop and print until stack becomes emptyThus printing:1Output up to now:1Stack status;Empty stack-------------------------------------------------------------1st iterationi=1EnQueue(st,i+1)Stack status:2S[i]=='I'So pop and print until stack becomes emptyThus printing:2Output up to now:12Stack status;Empty stack-------------------------------------------------------------2nd iterationi=2EnQueue(st,i+1)Stack status:3S[i]=='D'Nothing to doOutput up to now:12Stack status;3-------------------------------------------------------------3rd iterationi=3EnQueue(st,i+1)Stack status:34(top)S[i]=='D'Nothing to doOutput up to now:12Stack status;34(top)-------------------------------------------------------------4th iterationi=4EnQueue(st,i+1)Stack status:345(top)S[i]=='I'So pop and print until stack becomes emptyThus printing:5, then 4,then 3Output up to now:12543Stack status;Empty stack-------------------------------------------------------------5th iterationi=5EnQueue(st,i+1)Stack status:6S[i]=='D'Nothing to doOutput up to now:12543Stack status;6-------------------------------------------------------------6th iterationi=6EnQueue(st,i+1)Stack status:67(top)S[i]=='D'Nothing to doOutput up to now:12543-------------------------------------------------------------7th iterationi=7EnQueue(st,i+1)Stack status:678(top)Entire string is processedPop and print until stack becomes emptyPrint:8, then 7, then 6Output up to now:12543876Exit:Minimum no is:12543876
翻译自: /icp/number-following-the-pattern.aspx
跟随者数字解码
如果觉得《跟随者数字解码_跟随模式的数字》对你有帮助，请点赞、收藏，并留下你的观点哦！
