LeetCode //C - 38. Count and Say Medium Topics Companies

server/2024/9/24 23:26:36/

38. Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

  • countAndSay(1) = “1”
  • countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string “3322251”:
在这里插入图片描述
Given a positive integer n, return the n t h n^{th} nth term of the count-and-say sequence.
 

Example 1:

Input: n = 1
Output: “1”
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: “1211”
Explanation:
countAndSay(1) = “1”
countAndSay(2) = say “1” = one 1 = “11”
countAndSay(3) = say “11” = two 1’s = “21”
countAndSay(4) = say “21” = one 2 + one 1 = “12” + “11” = “1211”

Constraints:
  • 1 <= n <= 30

From: LeetCode
Link: 38. Count and Say


Solution:

Ideas:
  1. Base Case: If n is 1, the function returns the string “1”, since the first term of the sequence is always “1”.
  2. Recursive Call: For n greater than 1, the function calls itself to calculate the (n-1)th term. This is because to say the nth term, you need to know the (n-1)th term first.
  3. Calculating the Length: It then calculates the length of the (n-1)th term to determine how much memory to allocate for the nth term. The allocation is generous to ensure there’s enough space since the length of the sequence can grow with each term. The malloc function is used to allocate the memory, and the sprintf function is used to convert the counts and digits into a string format.
  4. Building the nth Term: The function iterates through the digits of the (n-1)th term. For each group of the same digit, it counts how many times that digit appears consecutively (count). It then writes the count and the digit itself into the result string. The sprintf function returns the number of characters written (excluding the null terminator), which is used to update the result_index to know where to write the next characters.
  5. Ending the String: Once all groups of digits have been processed, a null terminator (‘\0’) is added to the end of the result string to properly terminate it.
  6. Memory Management: The function then frees the memory allocated for the (n-1)th term since it is no longer needed. This is important to prevent memory leaks.
  7. Return Result: Finally, the nth term, now stored in result, is returned to the caller. The caller, in this case, the main function, is responsible for freeing this memory after it’s done using it.
Code:
char* countAndSay(int n) {if(n == 1) return strdup("1");// Recursively call countAndSay to get the previous termchar* prev_term = countAndSay(n - 1);int length = strlen(prev_term);// Calculate the maximum length of the result// In the worst case, the length doubles (e.g., "1" -> "11")char* result = malloc(2 * length + 1);int result_index = 0;for(int i = 0; i < length; i++) {int count = 1;// Count the number of identical digitswhile(i + 1 < length && prev_term[i] == prev_term[i + 1]) {count++;i++;}// Append count and digit to the result stringresult_index += sprintf(result + result_index, "%d%c", count, prev_term[i]);}// Free the memory allocated for previous termfree(prev_term);// Add the null terminator to the result stringresult[result_index] = '\0';return result;
}

http://www.ppmy.cn/server/26999.html

相关文章

两性情感课程笔记 2020~2023

2020 剽悍生活博客七爱哦耶浪迹小鹿魔卡Chris李越泰阳欧阳浮夸舞步爱情光谱乌鸦倪称男哥路易梵公子绅士派艾克迪诺校长感觉流卡卡危险人物晓辉爱上情感恋爱研习社摄影艾瑞克Chic情叔明日恋爱情受最绅士魅男其它 2021 城市猎人知乎文章 20210926阿尔法安小妖曹学敏Chris七分学…

【Docker学习】docker stop深入研究

本想将stop、start、restart、kill、pause、unpause这几个命令一起打包学习&#xff0c;但使用stop的过程中发现了一些可深入探讨的课题&#xff0c;因此这次只说docker stop。 命令&#xff1a; docker container stop 描述&#xff1a; 停止一个或多个运行中的容器。容器内的…

TCP流套接字编程

TCP流套接字编程 ServerSocket API ServerSocket 是专门给服务器使用的 Socket 对象。 构造方法 方法签名 方法说明 ServerSocket (int port) 创建一个服务端流套接字Socket&#xff0c;并绑定到指定端口 普通方法 方法签名 方法说明 Socket accept() 开始监听指定…

使用docker创建rocketMQ主从结构,使用

1、 创建目录 mkdir -p /docker/rocketmq/logs/nameserver-a mkdir -p /docker/rocketmq/logs/nameserver-b mkdir -p /docker/rocketmq/logs/broker-a mkdir -p /docker/rocketmq/logs/broker-b mkdir -p /docker/rocketmq/store/broker-a mkdir -p /docker/rocketmq/store/b…

经典机器学习法---感知模型机

优质博文&#xff1a;IT-BLOG-CN 1、模型形式 感知机模型主要用于解决二分类问题&#xff0c;即响应变量Y是个二分类变量&#xff08;如性别&#xff09;。其基本思想是拟找出一个超平面S&#xff0c;将样本空间中的训练集分为两个部分&#xff0c;使得位于超平面S合一侧的点具…

ESP32 蓝牙:使用 BTstack 库

ESP32S3+双模蓝牙智能音箱项目总目录_esp32蓝牙音箱-CSDN博客 目录 1.下载BTstack的源码 2.下载esp32的源码 3.基于BTstack源码生成esp32组件

ip ssl证书无限端口网站

IP SSL证书是由CA认证机构颁发的一种特殊数字证书。大部分SSL数字证书都需要用户使用域名进行申请&#xff0c;想要对公网IP地址加密实现https访问就需要申请IP SSL证书。IP SSL证书采用了强大的加密算法&#xff0c;可以有效地防止数据在传输过程中被窃取或篡改&#xff0c;具…

二,网络安全常用术语

黑客&#xff08;hacker&#xff09;——对计算机技术非常擅长的人&#xff0c;窃取数据&#xff0c;破坏计算机系统&#xff1b;全球最知名的一个黑客组织匿名&#xff08;Anonymous&#xff09;。 脚本小子——刚刚入门安全行业&#xff0c;学习了一些技术&#xff0c;只会用…