1140 Look-and-say Sequence

2020-04-17  本文已影响0人  胖胖的熊管家

题目

先吐槽一下:

这道题的英文我没读懂啥意思,后来去找了别人写的中文,一下子也没读懂啥意思,什么鬼❓

死命看题:

题目的意思是:
第一个数是给定的一个D,
那么第二个数的就是D1,原因是第一个数只有1个D;
第三个数是D111,原因是第二个数有1个D,和,1个1;
第四个数是D113,原因是第三个数有1个D,3个1;
第五个数是D11231,原因是第四个数有1个D,2个1,1个3;
...
到这里我好像明白题目的意思了,就是每一个数的构成都是要看上一个数有哪些数组成,形如:D+x1+x1的个数+x2+x2的个数...

但是!

第六个数的例子是D112213111,如果按照上述我理解的意思,那么应该是看第五个数,有1个D,3个1,1个2,1个3;那么应该是D1132131,怎么回事?!为什么最后1个1不算进去?!

所以!真相是!

它的确是数个数,但是数的是连续数的个数!

Sample Input
1 8
Sample Output
1123123111

解法

法一:C++
思路:

用vector,然后遍历循环找出连续数的个数,然后push_back进去。
说起来这么简单,但是我被它的多个循环给搞晕了头。(有预感以后的递归、动态规划可能俺...)
呐,细细剖析循环的话是这样的:
1.首先,要有个循环实现题目要求的求第n个数(发现写循环的时候i<n-1才是第n个数!!);
2.进入求第n个数后,要拿第n-1个数来循环找到第n-1个数的元素组成;而在这个循环中,目标是找到连续重复数的个数,一旦不连续就得break;所以这里用while+for循环。

源代码:
#include <iostream>
#include <cstdio>
#include <math.h>
#include<vector>
#include <string.h>
#include <sstream>

using namespace std;

int main() {
    int d,n;
    scanf("%d %d",&d,&n);
    
    vector<int> sequence;
    vector<int> temp;
    int num,count,index;
    num = d;
    index=0;
    sequence.push_back(d);
    for(int i=0;i<n-1;i++){
        num = sequence[0];
        count = 0;
        index = 0;
        while (index != sequence.size()) {
            for(int k=index;k<sequence.size();k++){
                if(sequence[k] == num){
                    count++;
                    index++;
                }
                else{
                    break;
                }
            }
            temp.push_back(num);
            temp.push_back(count);
            count = 0;
            num = sequence[index];
        }
        
        sequence = temp;
        temp.clear();
    }
    
    for (int i=0; i<sequence.size(); i++) {
        cout<<sequence[i];
    }
    
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读