从零开始算法之路 ---- 报数

Dear 丶 2021-10-15 16:19 421阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/count-and-say/][https_leetcode-cn.com_problems_count-and-say]  
**题目描述:(题目详情请点击链接)**  
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.      1
2.      11
3.      21
4.      1211
5.      111221

1 被读作 “one 1” (“一个一”) , 即 11。  
11 被读作 “two 1s” (“两个一”）, 即 21。  
21 被读作 “one 2”, “one 1” （“一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。  
**注意:** 整数顺序将表示为一个字符串。

**题意：** 对序列前一个数进行报数，数列第一项不是1吗，那第二项就报第一项的有1个1，输出11，然后第三项就在第二项的基础上报数，第二项是11，第三项不就是2个1么，然后输出21。

**思路：** 定义一个字符串类型的 vecotr 变量 ( vector count ), 做两个个循环把 报数序列存到count 中，返回 count\[n-1\] 中 ，详情看代码 。  
**代码：**

// 把报数到数字的个数存到临时字符串变量 temporaryStr 中 
    void processStr(string &temporaryStr , int sum){ 
    	switch(sum){ 
    		case 1 : temporaryStr += "1";break;
    		case 2 : temporaryStr += "2";break;
    		case 3 : temporaryStr += "3";break;
    		//default: ; 
    	}
    }
    
    // 把报数到的数字存到临时字符串变量 temporaryStr 中 
    void processStr(string &temporaryStr , char score){ 
    	switch(score){ 
    		case '1' : temporaryStr += "1";break;
    		case '2' : temporaryStr += "2";break;
    		case '3' : temporaryStr += "3";break;
    		//default: ; 
    	}
    }
    
    class Solution { 
    public:
        string countAndSay(int n) { 
        	// 定义一个字符串类型的 vecotr 变量存储报数序列
    		vector<string> count;
    		// 定义一个临时字符串变量存储 报数到数字的个数 和 报数到的数字 
    		string temporaryStr;
    		/* 1. 说明：count[i] vector<string> 类型 count[i][j] 是 char 类型，即报数序列中的每一个数字 2. 定义一个 char 型变量，暂时存储 报数序列中的每一个数字 */ 
    		char score;
    		// 记录报数到的同种类型的数字有几个 
    		int sum = 0; 
    		// 第一个报数序列先存进 count，即 1. "1" 
    		count.push_back("1");
    		// count 是从 0 开始存储，所以只需要报数到 n-1 项 
    		for(int i = 0; i < n; i++){ 		
    		    // 临时存储每一个报数序列的大小，即数字的个数 
    			int size = count[i].size();
    			// 这个循环真正开始报数，哪一个数字有几个 
    			for(int j = 0; j < size; j++){ 
    				// 记录下当前报数到的数字 
    				score = count[i][j];
    				// 统计报数到数字个数 
    				sum++;
    				// 如果当前报数到的数字不等于下一个将要报数的数字，把报数结果：个数和数字存储进 temporaryStr
    				if( j+1 < size && score != count[i][j+1]){ 
    					processStr(temporaryStr , sum);
    					processStr(temporaryStr , score);
    					// 重置计数变量，开始下一个数字的报数 
    					sum = 0;
    				}									
    			}
    			// 一个报数序列报数完毕， 把报数结果：个数和数字存储进 temporaryStr
    			processStr(temporaryStr , sum);
    			processStr(temporaryStr , score);
    			// 把报数序列的最终结果存进 count 中 
    			count.push_back(temporaryStr);
    			// 重置临时字符串变量，进行下一个序列的报数 
    			temporaryStr = "";  
    			// 重置计数变量，开始下一个序列的报数
    			sum = 0;				
    		}		
            return count[n-1]; 
        }
    
    	
    };

[https_leetcode-cn.com_problems_count-and-say]: https://leetcode-cn.com/problems/count-and-say/