「PAT甲级真题解析」Advanced Level 1004 Counting Leaves
admin
2024-03-31 19:43:13
0

PAT (Advanced Level) Practice 1004 Counting Leaves

问题分析

  1. 题设要求按照从根结点开始自顶向下输出树结构每一层的叶子结点数目。
  2. 这意味着我们需要设置计数器, 然后遍历树的每一个结点, 然后检查该结点是否是叶子结点,
    如果是叶子结点, 则将计数器中该层次叶子结点个数+1.
  3. 遍历树结构叶子结点可以用深度优先dfs搜索和广度优先搜索bfs.

完整步骤描述

  1. 获取输入: 树结点总个数, 非叶子结点个数
  2. 初始化记录器:
    • 各个结点的子节点组成记录器
    • 每层叶子结点个数记录器 = {0}
    • 最大层次 = 0
  3. 获取每一个非叶子结点的所有子节点:
    • 获取输入: 非叶子结点的ID, 其子节点个数, 各个子节点ID(记录到记录器中)
  4. 从根结点开始进行深度优先遍历或广度优先遍历(以下使用深度优先遍历):
    • 检查子节点组成记录器中, 该结点是否有子节点:
      • 如果没有, 则该结点为叶子结点:
        • 该层次叶子结点计数+1
        • 检查当前层次是否大于已记录的最大层次, 如果大于则更新记录的最大层次
    • 如果不是叶子结点, 则遍历每一个子节点, 递归进行上述检查
  5. 遍历完毕后, 输出记录的从顶层到最大层次的各个层次叶子结点数目.

伪代码描述

  1. get input: total_node_amount, non_left_node_amount
  2. init recorder/counter:
    • node_to_its_children = []
    • left_node_of_layer = {0}
    • max_depth = 0
  3. for i in range(0, total_node_amount):
    • get input: node_ID, children_amount:
      • for j in range(0, children_amount):
        • get input: child_ID
        • push child_ID into node_to_its_children[node_ID]
  4. dfs(index=1, depth=0):
    • if node_to_its_children[index].size() == 0:
      • left_node_of_layer[depth]++;
      • max_depth = max(max_depth, depth);
      • return;
    • else:
      • for child in node_to_its_children[index]:
        • dfs(child’s index, depth+1);
  5. for depth in range(0, max_depth):
    • print(node_to_its_children[depth]);

完整提交代码

/*
# 问题分析
1. 题设要求按照从根结点开始自顶向下输出树结构每一层的叶子结点数目。
2. 这意味着我们需要设置计数器, 然后遍历树的每一个结点, 然后检查该结点是否是叶子结点,
如果是叶子结点, 则将计数器中该层次叶子结点个数+1.
3. 遍历树结构叶子结点可以用深度优先dfs搜索和广度优先搜索bfs.# 完整步骤描述
1. 获取输入: 树结点总个数, 非叶子结点个数
2. 初始化记录器:- 各个结点的子节点组成记录器- 每层叶子结点个数记录器 = {0}- 最大层次 = 0
3. 获取每一个非叶子结点的所有子节点:- 获取输入: 非叶子结点的ID, 其子节点个数, 各个子节点ID(记录到记录器中)
4. 从根结点开始进行深度优先遍历或广度优先遍历(以下使用深度优先遍历):- 检查子节点组成记录器中, 该结点是否有子节点:- 如果没有, 则该结点为叶子结点:- 该层次叶子结点计数+1- 检查当前层次是否大于已记录的最大层次, 如果大于则更新记录的最大层次- 如果不是叶子结点, 则遍历每一个子节点, 递归进行上述检查
5. 遍历完毕后, 输出记录的从顶层到最大层次的各个层次叶子结点数目.# 伪代码描述
1. get input: total_node_amount, non_left_node_amount
2. init recorder/counter:- node_to_its_children = []- left_node_of_layer = {0}- max_depth = 0
3. for i in range(0, total_node_amount):- get input: node_ID, children_amount:- for j in range(0, children_amount):- get input: child_ID- push child_ID into node_to_its_children[node_ID]
4. dfs(index=1, depth=0):- if node_to_its_children[index].size() == 0:- left_node_of_layer[depth]++;- max_depth = max(max_depth, depth);- return;- else:- for child in node_to_its_children[index]:- dfs(child's index, depth+1);
5. for depth in range(0, max_depth):- print(node_to_its_children[depth]);
*/# include
# include
using namespace std;vector node_to_its_children[101];
int left_node_of_layer[101] = {0};
int max_depth = 0;void dfs(int index, int depth){if (node_to_its_children[index].size() == 0){left_node_of_layer[depth]++;max_depth = max(depth, max_depth);return ;}for (int i = 0; i < node_to_its_children[index].size(); i++){dfs(node_to_its_children[index][i], depth+1);}
}int main(){int total_node_amount, non_left_node_amount;scanf("%d %d", &total_node_amount, &non_left_node_amount);int node_ID, children_amount, child_ID;for (int i = 0; i < non_left_node_amount; i++){scanf("%d %d", &node_ID, &children_amount);for (int j = 0; j < children_amount; j++){scanf("%d", &child_ID);node_to_its_children[node_ID].push_back(child_ID);}}dfs(1, 0);printf("%d", left_node_of_layer[0]);for (int i = 1; i <= max_depth; i++){printf(" %d", left_node_of_layer[i]);}return 0;
}

相关内容

热门资讯

安卓 代替系统音效设置,打造个... 你有没有发现,手机里的那些系统音效有时候真的让人有点烦躁呢?比如那个每次接电话时“叮咚”一声,或者是...
安卓系统整体性,构建移动设备的... 你知道吗?在智能手机的世界里,安卓系统就像是个全能的魔术师,它不仅拥有丰富的魔法,还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过,在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢?没错,就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过,用手机也能轻松编曲?没错,就是那个你每天不离手的安卓系统手机!现在,我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现,现在的车载导航系统越来越智能了?尤其是那些搭载了安卓系统的车载导航,简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了,这可怎么办?别急,今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗,这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...