(新卷,200分)- 评论转换输出（Java JS Python）

(新卷,200分)- 评论转换输出（Java & JS & Python）

题目描述

在一个博客网站上，每篇博客都有评论。

每一条评论都是一个非空英文字母字符串。

评论具有树状结构，除了根评论外，每个评论都有一个父评论。

当评论保存时，使用以下格式：

• 首先是评论的内容；
• 然后是回复当前评论的数量。
• 最后是当前评论的所有了评论。(子评论使用相同的格式嵌套存储)

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

例如，如果评论如下：

第一条评论是"helo,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：

最终题目要求的：

• 评论嵌套的最大深度 → 其实就是树的高度
• 嵌套级别为 i 的评论 → 其实就是树的第 i 层的所有节点

因此，本题我们需要还原出一个树结构。

那么，我们如何从一个字符串数组，例如用例1：

hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0

中，还原出一颗树呢？

字符串的组成是多个评论，每一个评论包括两个部分：评论内容 + 子评论数，比如用例1可以划分如下

【hello,2】,【ok,0】,【bye,0】,【test,0】,【one,1】,【two,1】,【a,0】

另外，每一个子评论都是紧跟着其父评论后面。如下面例子：

根评论A，子评论A1，子评论A2，根评论B，子评论B1，子评论B2

但是子评论本身也可以有子评论，因此完整的结构图应该是：

根评论A，子评论A1，子子评论A11，子子评论A12，子评论A2，子子评论A21，子子评论A22，根评论B，子评论B1，子子评论B11，子子评论B12, 子评论B2,子子评论B21，子子评论B22

这个时候，如果根据父评论的“子评论数”往后顺序遍历的话，得到的并不是该父评论的实际子评论信息。

正确的做法应该是递归的去遍历父评论的子评论。

比如，根评论A有2个子评论，分别是子评论A1，子评论A2，

因此，我们需要从根评论A开始往后遍历2个评论，但是每遍历一个评论，我们都需要检查被遍历的评论也有子评论，比如首先遍历到子评论A1，发现它也有2个子评论，分别是子子评论A11，子子评论A12，因此我们应该暂停根评论A的子评论遍历过程，而是优先去遍历其子评论A1的子子评论。

当然，如果子子评论也有子子子评论，则也需要按上面逻辑处理。

由于评论嵌套的层级是不确定的，因此上面过程需要使用递归。

在上面递归过程中，一个比较麻烦的问题是，递归处理完子评论A1后，如何反馈下一个子评论A2的位置给 → 重启遍历流程的根评论A。

因此，我们暂停根评论A的遍历流程时，对应的遍历指针指向的还是子评论A1的位置，而子评论A1递归结束后，重启遍历流程的根评论A的遍历流程指针还是指向子评论A1呢！！

这里为了避免繁琐的索引位置处理，我直接在一开始时，将所有的评论信息加入都队列中，每次都取出队头评论进行处理，这样的话，当前递归处理完子评论A1，那么队列头部自然而然就是子评论A2了。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { const comments = line.split(","); getResult(comments); }); function getResult(queue) { // 树结构 const tree = []; // 根评论层级为1 const level = 1; // 该循环用于取出根评论 while (queue.length > 0) { // 根评论 const comment = queue.shift(); // 如果树还没有对应层级，则初始化对应层级 if (tree.length < level) { tree.push([]); } // 将根评论加入树结构的第一层 tree[0].push(comment); // 该根评论有几个直接子评论 const childCount = parseInt(queue.shift()); // 按上面逻辑，递归处理子评论，子评论所处级别为level+1 recursive(queue, level + 1, childCount, tree); } // 树结构的高度，就是评论嵌套的最大深度 console.log(tree.length); // 树结构的每一层，记录对应嵌套级别的评论 for (let levelNodes of tree) { console.log(levelNodes.join(" ")); } } function recursive(queue, level, childCount, tree) { for (let i = 0; i < childCount; i++) { const comment = queue.shift(); if (tree.length < level) { tree.push([]); } tree[level - 1].push(comment); const count = parseInt(queue.shift()); if (count > 0) { recursive(queue, level + 1, count, tree); } } }

Java算法源码

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] comments = sc.nextLine().split(","); getResult(comments); } public static void getResult(String[] comments) { // 树结构 ArrayList<ArrayList<String>> tree = new ArrayList<>(); // 将输入的评论信息，转化为队列结构 LinkedList<String> queue = new LinkedList<>(Arrays.asList(comments)); // 根评论层级为1 int level = 1; // 该循环用于取出根评论 while (queue.size() > 0) { // 根评论 String comment = queue.removeFirst(); // 如果树还没有对应层级，则初始化对应层级 if (tree.size() < level) { tree.add(new ArrayList<>()); } // 将根评论加入树结构的第一层 tree.get(0).add(comment); // 该根评论有几个直接子评论 int childCount = Integer.parseInt(queue.removeFirst()); // 按上面逻辑，递归处理子评论，子评论所处级别为level+1 recursive(queue, level + 1, childCount, tree); } // 树结构的高度，就是评论嵌套的最大深度 System.out.println(tree.size()); // 树结构的每一层，记录对应嵌套级别的评论 for (ArrayList<String> levelNodes : tree) { System.out.println(String.join(" ", levelNodes)); } } public static void recursive( LinkedList<String> queue, int level, int childCount, ArrayList<ArrayList<String>> tree) { for (int i = 0; i < childCount; i++) { String comment = queue.removeFirst(); if (tree.size() < level) { tree.add(new ArrayList<>()); } tree.get(level - 1).add(comment); int count = Integer.parseInt(queue.removeFirst()); if (count > 0) { recursive(queue, level + 1, count, tree); } } } }

Python算法源码

import sys # 本题可能Python会maximum recursion depth exceeded in comparison, 因此这里可以将递归深度搞大点 sys.setrecursionlimit(5000) # 输入获取 queue = input().split(",") def recursive(queue, level, childCount, tree): for i in range(childCount): comment = queue.pop(0) if len(tree) < level: tree.append([]) tree[level - 1].append(comment) count = int(queue.pop(0)) if count > 0: recursive(queue, level + 1, count, tree) # 算法入口 def getResult(queue): # 树结构 tree = [] # 根评论层级为1 level = 1 while len(queue) > 0: # 根评论 comment = queue.pop(0) # 如果树还没有对应层级，则初始化对应层级 if len(tree) < level: tree.append([]) # 将根评论加入树结构的第一层 tree[0].append(comment) # 该根评论有几个直接子评论 childCount = int(queue.pop(0)) # 按上面逻辑，递归处理子评论，子评论所处级别为level+1 recursive(queue, level + 1, childCount, tree) # 树结构的高度，就是评论嵌套的最大深度 print(len(tree)) # 树结构的每一层，记录对应嵌套级别的评论 for levelNodes in tree: print(" ".join(levelNodes)) # 算法调用 getResult(queue)