leetcode38. 外观数列

短命女 2023-07-23 10:00 31阅读 0赞

## 题目描述： ##

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

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* 项。

注意：整数序列中的每一项将表示为一个字符串。

## 思路： ##

思路不难，实现起来稍微复杂。就是按照你在纸上求解的思路，进行实现。遍历的时候计数，碰到不同的数字就把前面记录的写下来。当遍历到最后也到再添加记录。整体的思路比较明确，但是实现的方式还是复杂很多。可以用其他的容器来消除冗余代码。

class Solution {
        public String countAndSay(int n) {
            // 添加原始数据1
    		List<Character> original = new ArrayList<Character>();
    		original.add('1');
    		if(n == 1)
    			return "1"; // 基础样例
    		
    		List<Character> replace; // 替换数组
    		int i, j, count = 0;
    		char temp;
    		for(j = 1; j < n; j++) {
    			count = 0;
    			temp = original.get(0);
    			replace = new ArrayList<Character>();
    			for(i = 0; i < original.size(); i++) {			
    				if(original.get(i) == temp) { // 找个数
    					count++;
    				}
    				if(original.get(i) != temp) { // 碰到不同就add
    					replace.add(String.valueOf(count).charAt(0)); // 这里添加int类型的数字要转型
    					replace.add(temp);
    					temp = original.get(i);
    					count = 1;
    				}
    				if(i == original.size() - 1) { // 遍历到最后再add一次
    					replace.add(String.valueOf(count).charAt(0));
    					replace.add(temp);
    					original = replace;
    					break;
    				}		
    			}
    		}	
    		StringBuilder sBuilder = new StringBuilder(); // 最后把数组转为字符串
    		for(char x : original)
    			sBuilder.append(x);
    		return sBuilder.toString();
        }
    }