题解 | #诗#
诗
https://www.nowcoder.com/practice/7eef94e6f96f401b9078213cbc6c7eaf
题目链接
题目描述
给定一个由小写字母组成的字符串 。按照以下规则将字符串分行书写：
- 第一行：书写接下来的 1 个字母。
- 第二行：书写接下来的 2 个字母。
- 第三行：书写接下来的 3 个字母。
- ...
- 第
行：书写接下来的
- 以此类推，直到字符串中的所有字符都被写完。如果某一行需要
任务是收集每一行的首字母，并按顺序连接成一个新的字符串作为答案。
解题思路
这是一个简单的模拟题。我们可以按照题目描述的规则，一步步地从原始字符串中提取字符并构建答案。
我们需要维护两个变量来追踪整个过程：
- 一个指针
current_index，记录当前我们在原始字符串中处理到的位置。初始时，
current_index指向字符串的开头，即索引 0。 - 一个计数器
take_count，记录当前这一行需要书写多少个字符。根据规则，第一行需要 1 个，第二行 2 个，以此类推。所以take_count初始为 1。
算法流程:
-
初始化
current_index = 0，take_count = 1，以及一个空的答案字符串ans。 -
进入一个循环，循环的条件是
current_index必须小于字符串，确保我们还有字符可以处理。
-
在每一次循环中，我们模拟“书写新的一行”：
- 当前行的首字母就是位于
S[current_index]的字符。我们将这个字符追加到ans的末尾。 - 书写完这一行后，我们在原始字符串中的位置需要向后移动。移动的距离就是
take_count。所以，更新current_index = current_index + take_count。 - 为下一行做准备，需要书写的字符数会增加 1。所以，更新
take_count = take_count + 1。
- 当前行的首字母就是位于
-
循环会一直进行，直到
current_index大于或等于 -
最终得到的
ans字符串即为所求的答案。
代码
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin >> s;
string ans = "";
int current_index = 0;
int take_count = 1;
int n = s.length();
while (current_index < n) {
ans += s[current_index];
current_index += take_count;
take_count++;
}
cout << ans << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder ans = new StringBuilder();
int currentIndex = 0;
int takeCount = 1;
int n = s.length();
while (currentIndex < n) {
ans.append(s.charAt(currentIndex));
currentIndex += takeCount;
takeCount++;
}
System.out.println(ans.toString());
}
}
import sys
def solve():
s = sys.stdin.readline().strip()
ans = []
current_index = 0
take_count = 1
n = len(s)
while current_index < n:
ans.append(s[current_index])
current_index += take_count
take_count += 1
print("".join(ans))
solve()
算法及复杂度
-
算法: 模拟
-
时间复杂度: 设字符串长度为
current_index的值依次增加 1, 2, 3, ...。假设循环进行了current_index的值约等于。当这个值超过
，解得
。因此，循环执行的次数约为
，总时间复杂度为
-
空间复杂度: 我们需要一个额外的字符串来存储答案。答案字符串的长度与循环次数相同，即
