leetcode第38题

简介: 难在了题目是什么意思呢?初始值第一行是 1。第二行读第一行,1 个 1,去掉个字,所以第二行就是 11。第三行读第二行,2 个 1,去掉个字,所以第三行就是 21。第四行读第三行,1 个 2,1 个 1,去掉所有个字,所以第四行就是 1211。第五行读第四行,1 个 1,1 个 2,2 个 1,去掉所有个字,所以第五航就是 111221。第六行读第五行,3 个 1,2 个 2,1 个 1,去掉所以个字,所以第六行就是 312

image.png

难在了题目是什么意思呢?

初始值第一行是 1。

第二行读第一行,1 个 1,去掉个字,所以第二行就是 11。

第三行读第二行,2 个 1,去掉个字,所以第三行就是 21。

第四行读第三行,1 个 2,1 个 1,去掉所有个字,所以第四行就是 1211。

第五行读第四行,1 个 1,1 个 2,2 个 1,去掉所有个字,所以第五航就是 111221。

第六行读第五行,3 个 1,2 个 2,1 个 1,去掉所以个字,所以第六行就是 312211。

然后题目要求输入 1 - 30 的任意行数,输出该行是啥。

解法一 递归

可以看出来,我们只要知道了 n - 1 行,就可以写出第 n 行了,首先想到的就是递归。

第五行是 111221,求第六行的话,我们只需要知道每个字符重复的次数加上当前字符就行啦。

1 重复 3 次,就是 31,2 重复 2 次就是 22,1 重复 1 次 就是 11,所以最终结果就是 312211。

publicStringcountAndSay(intn) {
//第一行就直接输出if (n==1) {
return"1";
    }
//得到上一行的字符串Stringlast=countAndSay(n-1);
//输出当前行的字符串returngetNextString(last);
}
privateStringgetNextString(Stringlast) {
//长度为 0 就返回空字符串if (last.length() ==0) {
return"";
    }
//得到第 1 个字符重复的次数intnum=getRepeatNum(last);
// 次数 + 当前字符 + 其余的字符串的情况returnnum+""+last.charAt(0) +getNextString(last.substring(num));
}
//得到字符 string[0] 的重复个数,例如 "111221" 返回 3privateintgetRepeatNum(Stringstring) {
intcount=1;
charsame=string.charAt(0);
for (inti=1; i<string.length(); i++) {
if (same==string.charAt(i)) {
count++;
        } else {
break;
        }
    }
returncount;
}

时间复杂度:

空间复杂度:O(1)。

解法二 迭代

既然有递归,那就一定可以写出它的迭代形式。

publicStringcountAndSay(intn) {
Stringres="1";
//从第一行开始,一行一行产生while (n>1) {
Stringtemp="";
for (inti=0; i<res.length(); i++) {
intnum=getRepeatNum(res.substring(i));
temp=temp+num+""+res.charAt(i);
//跳过重复的字符i=i+num-1;
        }
n--;
//更新res=temp;
    }
returnres;
}
//得到字符 string[0] 的重复个数,例如 "111221" 返回 3privateintgetRepeatNum(Stringstring) {
intcount=1;
charsame=string.charAt(0);
for (inti=1; i<string.length(); i++) {
if (same==string.charAt(i)) {
count++;
        } else {
break;
        }
    }
returncount;
}

时间复杂度:

空间复杂度:O(1)。

递归里边又用了一个递归,我觉得这点有点意思。

目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-475:供暖器
leetcode-475:供暖器
59 0
|
9月前
|
leetcode-474:一和零
leetcode-474:一和零
49 0
LeetCode 1904. 你完成的完整对局数
一款新的在线电子游戏在近期发布,在该电子游戏中,以 刻钟 为周期规划若干时长为 15 分钟 的游戏对局。这意味着,在 HH:00、HH:15、HH:30 和 HH:45 ,将会开始一个新的对局,其中 HH 用一个从 00 到 23 的整数表示。游戏中使用 24 小时制的时钟 ,所以一天中最早的时间是 00:00 ,最晚的时间是 23:59 。
112 0
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
92 0
leetcode第41题
对于这种要求空间复杂度的,我们可以先考虑如果有一个等大的空间,我们可以怎么做。然后再考虑如果直接用原数组怎么做,主要是要保证数组的信息不要丢失。目前遇到的,主要有两种方法就是交换和取相反数。
104 0
leetcode第41题
leetcode第50题
求幂次方,用最简单的想法,就是写一个 for 循环累乘。 至于求负幂次方,比如 2^{-10}2−10,可以先求出 2^{10}210,然后取倒数,1/2^{10}1/210 ,就可以了 double mul = 1; if (n > 0) { for (int i = 0; i < n; i++) { mul *= x; } } else { n = -n; for (int i = 0; i < n; i++) { mul *= x; } mul = 1 / mul; }
115 0
leetcode第50题
leetcode第47题
基本上都是在上道题的基础上改出来了,一些技巧也是经常遇到,比如先排序,然后判断和前一个是否重复。利用 Hash 去重的功能。利用原来的存储空间隐藏掉数据,然后再想办法还原。
100 0
leetcode第47题
leetcode第42题
也就是红色区域中的水, 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2,temp ++,高度大于等于 2,ans = ans + temp,temp = 0。 temp 初始化为 0 ,ans 此时等于 2。 height [ 0 ] 等于 0 < 2,不更新。 height [ 1 ] 等于 1 < 2,不更新。 height [ 2 ] 等于 0 < 2, 不更新。 height [ 3 ] 等于 2 >= 2, 开始更新 height [ 4 ] 等于 1 < 2,temp = temp + 1 = 1。 h
118 0
leetcode第42题
leetcode第39题
对回溯法又有了更深的了解,一般的架构就是一个大的 for 循环,然后先 add,接着利用递归进行向前遍历,然后再 remove ,继续循环。而解法二的动态规划就是一定要找到递进的规则,开始的时候就想偏了,导致迟迟想不出来。
leetcode第39题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等