编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程) 特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。 现在有一个由有序数对组成的树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度 输入的第一行表示节点的个数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; }
|