评论转换输出 - 华为OD统一考试

OD统一考试

分值： 200分

题解： Java / Python / C++

alt

题目描述

在一个博客网站上，每篇博客都有评论。每一条评论都是一个非空英文字母字符串。

评论具有树状结构，除了根评论外，每个评论都有一个父评论。当评论保存时，使用以下格式：

首先是评论的内容；

然后是回复当前评论的数量。

最后是当前评论的所有子评论。(子评论使用相同的格式嵌套存储)

所有元素之间都用单个逗号分隔。

例如，如果评论如下：

第一条评论是"hello,2,ok,0,bye,0",第二条评论是"test,0",第三条评论是"one,1,two,1,a,0"。所有评论被保存成"hello,2,ok,0，bye,0,test,0,one,1,two,1,a,0"。

对于上述格式的评论，请以另外一种格式打印：

首先打印评论嵌套的最大深度。

然后是打印n行，第i(1≤i≤n)行对应于嵌套级别为i的评论(根评论的嵌套级别为1)。

对于第i行，嵌套级别为的评论按照它们出现的顺序打印，用空格分隔开。

输入描述

一行评论。由英文字母、数字和英文逗号组成。保证每个评论都是由英文字符组成的非空字符串。每个评论的数量都是整数(至少由一个数字组成)。整个字符串的长度不超过10^6。给定的评论结构保证是合法的。

输出描述

按照给定的格式打印评论。对于每一级嵌套，评论应该按照输入中的顺序打印。

示例1

输入：
hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0

输出：
3
hello test one
ok bye two
a

示例2

输入：
A,5,A,0,a,0,A,0,a,0,A,0

输出：
2
A
A a A a A

示例3

输入：
A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0

输出：
4
A K M
B F H L N O
C D G I P
E J

题解

题目类型：树状结构的遍历，可以使用深度优先搜索（DFS）。

解题思路：

定义一个评论类，包含评论内容、回复数量以及回复的评论列表。
使用递归解析评论数据，构建评论树。
使用深度优先搜索（DFS）遍历评论树，按照嵌套级别将评论内容存储到对应的列表中。
输出最大嵌套深度和每个嵌套级别的评论内容。

代码描述：

定义Comment类，包含评论内容、回复数量、回复的评论列表。
解析评论数据的函数parseComment。
深度优先搜索的函数dfs，将评论内容按照嵌套级别存储到result列表中。
主函数中读取输入，构建评论树，进行深度优先搜索，并输出结果。

时间复杂度：假设评论数为N，则构建评论树和深度优先搜索的时间复杂度为O(N)。

空间复杂度：需要存储评论树和结果列表，空间复杂度为O(N)。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Comment {
    /**
     * 评论类
     */
    String data;
    int replyCnt;
    List<Comment> replys;

    public Comment(String data, int replyCnt) {
        this.data = data;
        this.replyCnt = replyCnt;
        this.replys = new ArrayList<>();
    }
}

/**
 * @author code5bug
 */
public class Main {

    static int idx;
    static String[] ds;
    static List<List<String>> result;

    /**
     * 解析评论数据
     *
     * @return
     */
    public static Comment parseComment() {
        String data = ds[idx];
        int replyCnt = Integer.parseInt(ds[idx + 1]);
        idx += 2;
        Comment comment = new Comment(data, replyCnt);
        for (int i = 0; i < replyCnt; i++) {
            comment.replys.add(parseComment());
        }
        return comment;
    }

    /**
     * 遍历评论内容，并将评论的内容放到result的对应的嵌套级别中
     *
     * @param comment
     * @param level
     */
    public static void dfs(Comment comment, int level) {
        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(comment.data);

        for (Comment rep : comment.replys) {
            dfs(rep, level + 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ds = scanner.nextLine().split(",");
        idx = 0;
        int N = ds.length;
        List<Comment> comments = new ArrayList<>();

        while (idx < N) {
            comments.add(parseComment());
        }

        result = new ArrayList<>();
        for (Comment comment : comments) {
            dfs(comment, 0);
        }

        System.out.println(result.size());
        for (List<String> cs : result) {
            System.out.println(String.join(" ", cs));
        }
    }
}

Python

class Comment:
    """评论类"""

    def __init__(self, data, reply_cnt) -> None:
        self.data = data
        self.reply_cnt = reply_cnt
        self.replys = []


def parse_comment() -> Comment:
    """解析评论数据"""
    global idx, ds
    data, reply_cnt = ds[idx], int(ds[idx + 1])
    idx += 2
    comment = Comment(data, reply_cnt)
    for _ in range(reply_cnt):  # 评论的回复
        comment.replys.append(parse_comment())
    return comment


def dfs(comment: Comment, level: int):
    """遍历评论内容，并将评论的内容放到result的对应的嵌套级别中"""
    global result
    if len(result) <= level:
        result.append([])
    result[level].append(comment.data)

    for rep in comment.replys:
        dfs(rep, level + 1)


ds = input().split(",")
idx, N = 0, len(ds)
comments = []
while idx < N:
    comments.append(parse_comment())

result = []
for comment in comments:
    dfs(comment, 0)

print(len(result))
for cs in result:
    print(" ".join(cs))

C++

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

// 评论类
class Comment {
public:
    string data;
    int replyCnt;
    vector<Comment> replys;

    Comment(const string& data, int replyCnt) : data(data), replyCnt(replyCnt) {}
};

int idx;
vector<string> ds;
vector<vector<string>> result;

/**
 * 解析评论数据
 *
 * @return
 */
Comment parseComment() {
    string data = ds[idx];
    int replyCnt = stoi(ds[idx + 1]);
    idx += 2;
    Comment comment(data, replyCnt);
    for (int i = 0; i < replyCnt; i++) {
        comment.replys.push_back(parseComment());
    }
    return comment;
}

/**
 * 遍历评论内容，并将评论的内容放到result的对应的嵌套级别中
 *
 * @param comment
 * @param level
 */
void dfs(const Comment& comment, int level) {
    if (result.size() <= static_cast<size_t>(level)) {
        result.emplace_back();
    }
    result[level].push_back(comment.data);

    for (const Comment& rep : comment.replys) {
        dfs(rep, level + 1);
    }
}

int main() {
    string input;
    getline(cin, input);
    istringstream iss(input);
    string token;
    while (getline(iss, token, ',')) {
        ds.push_back(token);
    }

    idx = 0;
    int N = ds.size();
    vector<Comment> comments;

    while (idx < N) {
        comments.push_back(parseComment());
    }

    result.clear();
    for (const Comment& comment : comments) {
        dfs(comment, 0);
    }

    cout << result.size() << endl;
    for (const auto& cs : result) {
        cout << cs[0];
        for (size_t i = 1; i < cs.size(); ++i) {
            cout << " " << cs[i];
        }
        cout << endl;
    }

    return 0;
}