leetcode-38 Count And Say
发布日期:2021-08-26 19:03:35 浏览次数:10 分类:技术文章

本文共 2229 字,大约阅读时间需要 7 分钟。

问题描写叙述:

The count-and-say sequence is the sequence of integersbeginning as follows:

1, 11, 21,1211, 111221, ...

1 is read off as "one1" or 11.

11 is read off as "two1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n,generate the nth sequence.

Note: The sequence of integerswill be represented as a string.

 

问题分析:

    题目的意思指:每一个数字串。从最高位開始读起,相应每一个数字的个数x个,其值为y;则记为xy;且每一个数字串与其前一个数字串相关;

    这里是个非常明显的递归,能够使用递归解法,也能够使用循环解法。

两种解法核心都是统计数字串中每一个数字连续出现的次数。

    这里仅需推断当前数字与后一个数字是否同样,

若同样,则count++,计算反复的数据次数。直至该数字与后一个数字不同,或者到了数组尾部;此时将该数字的次数与其值加入入结果String就可以。

代码:

递归解法:

public class Solution {    public String countAndSay(int n){        String result = "";        if (n <= 0)            return result;               return unitDo(n);           }       // 递归解法    private String unitDo(int n) {        if(n <= 1)            return "1";               String pre = unitDo(n - 1);        char[] datas = pre.toCharArray();        StringBuffer resultBuffer = new StringBuffer();               int count = 1;               for(int i = 0; i < datas.length; i++) {            if( (i >= datas.length - 1) || datas[i]!= datas[i + 1] ) {                resultBuffer.append(count);                resultBuffer.append(datas[i]);                count= 1;            }else {                count++;            }        }        return resultBuffer.toString();           }}
 

非递归解法:

// 非递归解法    public String countAndSay2(int n){               String result = "";        if (n <= 0)            return result;        String pre = "1";        char[] datas;        StringBuffer resultBuffer;        int count;               for (int j = 1; j < n;j++) {            datas= pre.toCharArray();            resultBuffer= new StringBuffer();            count= 1;                       //核心部分不变            for(int i = 0; i < datas.length;i++) {                if( (i >= datas.length - 1) || datas[i]!= datas[i + 1] ) {                    resultBuffer.append(count);                    resultBuffer.append(datas[i]);                    count= 1;                }else {                    count++;                }            }            pre= resultBuffer.toString();        }             return pre;    }

转载于:https://www.cnblogs.com/clnchanpin/p/7398018.html

转载地址:https://blog.csdn.net/weixin_33894992/article/details/94626715 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:提高效率—编程中的技巧
下一篇:Android内存泄露之开篇

发表评论

最新留言

不错!
[***.144.177.141]2025年02月11日 14时42分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章