专栏首页深度学习和计算机视觉每日一题C++版(树的高度)

每日一题C++版(树的高度)

编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程)

特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。

树的高度

题目描述

现在有一个由有序数对组成的树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度

输入描述:

输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,

下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号

输出描述:

输出树的高度,为一个整数

示例

输入

5

0 1

0 2

1 3

1 4

输出

3

解析

其实这里面的树,也就是链表。如果可以使用容器将同一高度的节点放在一个容器内,这个高度内的节点的子节点放在下一层绒球内。父节点放在上一层容器。由于我们不能总是先发现父节点,因此这个容器也会在首段插入数据。因此我们需要使用两端插入数据比较快的容器,因此我们选用list容器。而这个容器内的元素也应该是一个容器(为了方便我们插入同样高度的新节点)。

这样首先我们就在每一层中寻找父节点,如果找到,就将其子节点插入(存入)下一层;如果没有找到,我们就在每一层中寻找子节点,如果找到,就将其父节点插入(存入)上一层,并且将这个节点从需要插入“树”中的数据里面删除。最后只要看这个list容器的size就可以了。

代码

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
  int index;
  while (cin >> index)
  {
    list<vector<int>> joint;
    list<vector<int>> tree;
    for (int i = 0; i < index-1; i++)
    {
      vector<int> subjoint;
      int father, son;
      cin >> father >> son;
      subjoint.push_back(father);
      subjoint.push_back(son);
      joint.push_back(subjoint);
      if (tree.empty())
      {
        vector<int> father_t;
        father_t.push_back(father);
        vector<int> son_t;
        son_t.push_back(son);
        tree.push_back(father_t);
        tree.push_back(son_t);
      }
    }
    while (!joint.empty())
    {
      for (auto i = joint.cbegin(); i != joint.cend(); )
      {
        bool add = false;
        for (auto m = tree.begin(); m != tree.end(); m++)
        {
          int father = (*i)[0];
          int son = (*i)[1];
          auto findfather = find((*m).cbegin(), (*m).cend(), father);
          auto findson = find((*m).cbegin(), (*m).cend(), son);
          auto lastone = tree.cend();
          lastone--;
          if (findfather != (*m).cend())
          {
            if (m == lastone)
            {
              vector<int> subjoint;
              subjoint.push_back(son);
              tree.push_back(subjoint);
              i = joint.erase(i);
              add = true;
              break;
            }
            if (m != lastone)
            {
              m++;
              (*m).push_back(son);
              m--;
              i = joint.erase(i);
              add = true;
              break;
            }
          }
          else if (findson != (*m).cend())
          {
            if (m == tree.begin())
            {
              vector<int> subjoint;
              subjoint.push_back(father);
              tree.push_front(subjoint);
              i = joint.erase(i);
              add = true;
              break;
            }
            if (m == tree.begin())
            {
              m++;
              (*m).push_back(father);
              m--;
              i = joint.erase(i);
              add = true;
              break;
            }
          }
        }
        if (!add)
        {
          i++;
        }
      }
    }
    cout << tree.size() << endl;
  }
  return 0;
}

本文分享自微信公众号 - 小白学视觉(NoobCV),作者:小白学视觉

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日一题C++版(二叉树的高度)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 每日一题C++版(袋鼠过河)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 修正!【从零学习OpenCV 4】分割图像——分水岭法

    分水岭算法与漫水填充法相似,都是模拟水淹过山地的场景,区别是漫水填充法是从局部某个像素值进行分割,是一种局部分割算法,而分水岭法是从全局出发,需要对全局都进行分...

    小白学视觉
  • 【专知-关关的刷题日记19】Leetcode 118. Pascal&#39;s Triangle

    题目 Given numRows, generate the first numRows of Pascal's triangle. For example, ...

    WZEARW
  • 二分法查找元素

    青木
  • Leetcode 84 Largest Rectangle in Histogram

    Given n non-negative integers representing the histogram's bar height where the...

    triplebee
  • 2016年第七届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • 学界 | 传播动态学的主动监控:一种组稀疏贝叶斯学习方法

    AI 科技评论按:本文作者吉林大学博士生裴红斌,本文为对他发表在 AAAI 2018 论文的独家解读稿件,未经许可不得转载。 Group Sparse Bay...

    AI科技评论
  • hadoop2.7.3源码解析之hdfs删除文件全流程分析h

    客户端通过ClientProtocol.delete(String, boolean)方法来删除文件,最终实现是NameNodeRpcServer.delete...

    大数据技术与应用实战
  • 别走!这里有个笔记:图文讲解 AQS ,一起看看 AQS 的源码……(图文较长)

    " AbstractQueuedSynchronizer 抽象队列同步器,简称 AQS 。是在 JUC 包下面一个非常重要的基础组件,JUC 包下面的并发锁 R...

    程序员小航

扫码关注云+社区

领取腾讯云代金券