c++-c++编程基础之leetcode题解第38题外观数列.zip_LeetCode第38题C++实现资源-CSDN下载

共1个文件

md：1个

需积分: 50 21 浏览量 2024-04-08 05:29:22 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第38题，名为“外观数列”（Count and Say），是一道有趣的题目，旨在考察程序员对字符串处理和迭代的理解。在这个问题中，我们需要构建一个序列，其中每个数字都是前一个数字的描述。外观数列的定义如下：序列1（第一项）是1。对于每一后续项，描述前一项的方式如下：读出前一项中连续相同数字的个数，然后是该数字。例如，序列2是11（两个1），序列3是21（一个2，一个1），序列4是1211（一个1，一个2，两个1）。解决这道题的关键在于理解如何将当前项转化为下一项。以下是一种可能的C++实现策略： 1. 我们从给定的初始序列（通常是"1"）开始。 2. 创建一个空字符串，用于存储当前项的描述。 3. 对于当前项中的每一个字符，统计连续相同的字符数量。 4. 将字符数量和字符本身添加到描述字符串中。 5. 重复步骤3和4，直到生成所有需要的序列项。 C++代码实现可能如下： ```cpp #include <iostream> #include <string> std::string countAndSay(int n) { std::string seq = "1"; // 初始化序列 for (int i = 1; i < n; ++i) { std::string nextSeq; int count = 1; for (size_t j = 1; j < seq.size(); ++j) { if (seq[j] == seq[j - 1]) { ++count; } else { nextSeq += std::to_string(count) + seq[j - 1]; count = 1; } } nextSeq += std::to_string(count) + seq.back(); // 添加最后一个元素 seq = nextSeq; } return seq; } int main() { int n = 5; // 求序列的第5项 std::cout << countAndSay(n) << std::endl; return 0; } ``` 这个程序首先定义了一个`countAndSay`函数，它接受一个整数`n`作为参数，表示要生成的序列项的个数。通过循环，它逐步构建并返回序列的第`n`项。在`main`函数中，我们可以调用`countAndSay`并打印结果。 C++语言提供了丰富的标准库，使得处理字符串和数据结构变得相对简单。在这个例子中，我们利用了`std::string`的特性，如迭代、比较和拼接。同时，通过使用`std::to_string`将整数转换为字符串，以便与字符进行拼接。 LeetCode上的问题通常会涉及多种算法和数据结构，通过解决这些问题，开发者可以深入理解C++的特性和编程技巧，这对于提高编程技能和准备面试都非常有帮助。本例中，我们运用了迭代、字符串操作和动态规划的思维，这些都是C++程序员必备的技能。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第38题外观数列.zip （1个子文件）

c++_c++编程基础之leetcode题解第38题外观数列

README.md 3KB

# [38. Count and Say (Medium)](https://leetcode.com/problems/count-and-say/) The count-and-say sequence is a sequence of digit strings defined by the recursive formula: <ul> <li><code>countAndSay(1) = "1"</code></li> <li><code>countAndSay(n)</code> is the way you would "say" the digit string from <code>countAndSay(n-1)</code>, which is then converted into a different digit string.</li> </ul> To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying. For example, the saying and conversion for digit string <code>"3322251"</code>: <img alt="" src="https://assets.leetcode.com/uploads/2020/10/23/countandsay.jpg" style="width: 581px; height: 172px;"> Given a positive integer <code>n</code>, return the <code>nth</code> term of the count-and-say sequence.   Example 1: <pre>Input: n = 1 Output: "1" Explanation: This is the base case. </pre> Example 2: <pre>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" </pre>   Constraints: <ul> <li><code>1 <= n <= 30</code></li> </ul> **Companies**: [Bloomberg](https://leetcode.com/company/bloomberg), [Microsoft](https://leetcode.com/company/microsoft), [Facebook](https://leetcode.com/company/facebook), [Adobe](https://leetcode.com/company/adobe), [Goldman Sachs](https://leetcode.com/company/goldman-sachs) **Related Topics**: [String](https://leetcode.com/tag/string/) **Similar Questions**: * [Encode and Decode Strings (Medium)](https://leetcode.com/problems/encode-and-decode-strings/) * [String Compression (Medium)](https://leetcode.com/problems/string-compression/) ## Solution 1. Recursive ```cpp // OJ: https://leetcode.com/problems/count-and-say/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(N) class Solution { public: string countAndSay(int n) { if (n == 1) return "1"; string s = countAndSay(n - 1), ans; for (int i = 0, N = s.size(); i < N; ++i) { char d = s[i]; int cnt = 1; while (i + 1 < N && s[i + 1] == s[i]) ++i, ++cnt; ans += to_string(cnt) + d; } return ans; } }; ``` ## Solution 2. Iterative ```cpp // OJ: https://leetcode.com/problems/count-and-say/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(N) class Solution { public: string countAndSay(int n) { string ans = "1"; while (--n) { string next; int i = 0; while (i < ans.size()) { char c = ans[i]; int cnt = 0; while (i < ans.size() && ans[i] == c) ++cnt, ++i; next += to_string(cnt) + c; } ans = next; } return ans; } }; ```

评论收藏

内容反馈