乘风破浪：LeetCode真题_038_Count and Say

 乘风破浪：LeetCode真题_038_Count and Say

一、前言

    这一道题目，很类似于小学的问题，但是如果硬是要将输入和结果产生数值上的联系就会产生混乱了，因此我们要打破思维定势。

二、Count and Say

 2.1 问题

 

2.2 分析与解决

    这道题最难的其实是理解，因为描述的不尽其意，所以很难理解，其实就是根据最开始的字符串，不断的扩展，输入的N，代表的是经过N次之后的结果，与其中的结果没有任何关系。

1 /** 2 * 题目大意 3 * n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1， 4 * 所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于上次字符串是21， 5 * 有1个2和1个1，所以输出1211。依次类推，写个countAndSay(n)函数返回字符串。 6 * 7 * 解题思路 8 * 第一种情况：n<0时返回null。 9 * 第二种情况：当n=1时，返回1 10 * 第三种情况：当n>1时，假设n-1返回的字符串是s，对s的串进行处理，对不同的数字 11 * 进行分组比如112365477899，分成11，2，3，6，5，4，77，8，99。最有就2个1， 12 * 1个2，1个3，1个6，1个5，一个4，2个7，1个8，2个9，就是211213161614271829，返回此结果。 13 */

    理解题意之后，其他的就好办了：

public class Solution {public String countAndSay(int n) {if (n < 1) {return null;}String result = "1";for (int i = 2; i <= n; i++) {result = countAndSay(result);}return result;}public String countAndSay(String str) {StringBuilder builder = new StringBuilder(128);int count = 1;for (int i = 1; i < str.length(); i++) {if (str.charAt(i) == str.charAt(i - 1)) {count++;} else {builder.append(count);builder.append(str.charAt(i - 1));count = 1;}}builder.append(count);builder.append(str.charAt(str.length() - 1));return builder.toString();} }

     当然也可以用递归来做，其实道理是一样的，速度稍微慢一点：

public class Solution {public String countAndSay(int n) {if(n == 1) { return "1"; }String s = countAndSay(n-1);int i = 0;String out = "";while(i < s.length()) {int j = i+1;while(j < s.length() && s.charAt(i) == s.charAt(j)) {j += 1;}out = out + (j-i) + s.charAt(i);i = j;}return out;} }

 

三、总结

     题目的理解非常重要，有的时候靠自己的猜测是不正确的。

转载于:https://www.cnblogs.com/zyrblog/p/10224703.html

总结

以上是生活随笔为你收集整理的乘风破浪：LeetCode真题_038_Count and Say的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。