专栏首页ACM算法日常leetcode 38 | 报数(简单题)

leetcode 38 | 报数(简单题)

报数序列是指一个整照其中的整数的顺序进数序列,按行报数,得到下一个数。其前五项如下:

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

1 被读作 "one 1" ("一个一") , 即 1111 被读作 "two 1s" ("两个一"), 即 2121 被读作 "one 2", "one 1""一个二" , "一个一") , 即 1211

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

题意:是不是跟笔者一样,刚看完题目都不知道这个题目在说些什么~其实它就是第一个是1,第二个就是上一个的读法,即1个1,所以第二个就是11,然后第三个又是上个的读法,2(两)个1,所以第三个为21,以此类推。这下是不是懂了题目的意思呢~

分析:我们可以写一个say()方法,用来"读"上一个数,其中用一个count计数器来记录相同元素,用一个flag变量来标志当前读取到上一个字符串的哪个位置,然后通过"读"出几个几,来拼接一下字符串,返回这个字符串。对这个方法循环使用n-1次,即可得出第n个的"读"数序列。

代码实现:

char* countAndSay(int n) {
    if (n == 1) return "1";
    char * cur = malloc(2);
    char * temp;
    cur[0] = '1';
    cur[1] = 0;
    int len, idx, j, count;
    for (int i = 2; i <= n; i++) {
        len = strlen(cur);
        temp = malloc(3 * len);
        memset(temp, 0, 3 * len);
        count = 1;
        for (idx = 1, j = 0; idx < len; idx++) {
            if (cur[idx] == cur[idx - 1]) count++;
            else {
                temp[j++] = '0' + count;
                temp[j++] = cur[idx - 1];
                count = 1;
            }
        }
        temp[j++] = '0' + count;
        temp[j] = cur[len - 1];
        free(cur);
        cur = temp;
    }
    return cur;
}

int main (){ //此处为一个测试例子
    printf("%s\n", countAndSay(5));
}

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode 6 | Z字形变换

    比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

    ACM算法日常
  • UVA11988:悲剧文本(模拟链表)

    You’re typing a long text with a broken keyboard. Well it’s not so badly broken....

    ACM算法日常
  • 点分治入门

    其实点分治是树分治的一种, 树分治包括点分治和边分治. 边分治不在本文介绍范围内.

    ACM算法日常
  • 650. 只有两个键的键盘 Krains 2020-08-02 09:39:39 动态规划DFS

    Krains
  • geotools中泰森多边形的生成

    泰森多边形又叫冯洛诺伊图(Voronoi diagram),得名于Georgy Voronoi,是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。

    lzugis
  • 使用IntelliJ IDEA开发SpringMVC网站(二)框架配置

    注:此文承接上一文:使用IntelliJ IDEA开发SpringMVC网站(一)开发环境

    bear_fish
  • 软件分享_皮一波

    歪先生
  • 如何设计一个秒杀系统

    声明:本人并未参与过真正的秒杀系统设计,以下是本人学习笔记,自测通过,但可能并不完善,仅供参考,若用于生产出现问题,本人概不负责。

    贪挽懒月
  • LeetCode 853. 车队(排序)

    每辆车 i 以恒定的速度 speed[i] (英里/小时),从初始位置 position[i] (英里) 沿车道驶向目的地。

    Michael阿明
  • 「应用现代化」应用程序现代化的最佳实践和方法

    应用程序现代化是对传统软件编程的重新利用,以使其与当前业务需求更紧密地协调一致。这是企业保持竞争力的关键。虽然存在许多挑战,但通过这一过程获得的效率有助于公司保...

    首席架构师智库

扫码关注云+社区

领取腾讯云代金券