From 8fb3943122786e9ab13bf06cae6ad9ab70860fc4 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 11 Jan 2019 19:54:13 -0600 Subject: Tree height partially done. Partially because it didn't pass time limitations for test case 19 out of 24. I suspect it's pointer reference stuff that was the cause of the issue. Checking in for now, I need to research and learn more and will tackle this again so it passes all tests.--- Sources/DataStructure.cpp | 185 ++++++++++++++++++++++------------------------ 1 file changed, 90 insertions(+), 95 deletions(-) (limited to 'Sources') diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 1360ef5..b82f908 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,115 +1,110 @@ #include -#include +#include #include #include //#include -using std::string; -using std::stack; +using std::vector; +using std::queue; -const std::vector brackets = {'[',']','(',')','{','}'}; +class Node; -static string checkBracket(string exp) { - stack charStack; - int unmatchedOpeningBracket = 0; - int count = 0; - for (int i = 0; i < exp.length(); i++) { - char c = exp[i]; - if (!(std::find(brackets.begin(), brackets.end(), c) !=brackets.end())) { - count = count + 1; - continue; - } +class Node { +public: + int key; + Node *parent; + vector children; - if (c == '[' || c == '(' || c == '{') { - charStack.push(c); - count = count + 1; - unmatchedOpeningBracket = count; - } else { - if (charStack.empty()) - return std::to_string(i+1); - char top = charStack.top(); - charStack.pop(); - if ((top == '[' && c != ']') || (top == '(' && c != ')') || (top == '{' && c != '}')) { - return std::to_string(i+1); - } else { - unmatchedOpeningBracket = unmatchedOpeningBracket - 1; - } - count = count + 1; - } - } - if (charStack.empty()) - return "Success"; - else if (unmatchedOpeningBracket > 0) { - return std::to_string(unmatchedOpeningBracket); - } - return std::to_string(count); + Node() { + this->parent = NULL; + } + + void setParent(Node *theParent) { + parent = theParent; + parent->children.push_back(this); + } + + vector getChildren() { + return children; + } + + void setKey(int theKey) { + key = theKey; + } +}; + +int treeLevelCounter(vector &nodes, int rootIndex) { + int levelCounter = 1; + queue q; + int popCount = 0; + int childrenCount = nodes[rootIndex].getChildren().size(); + int grandChildrenCount = 0; + for (int i = 0; i < childrenCount; i++) { + q.push(nodes[rootIndex].getChildren()[i]); + } + while (!q.empty()) { + if (popCount < childrenCount) { + Node *n = q.front(); + q.pop(); + int i = n->children.size(); + if (i != 0) { + for (int j = 0; j < i; j++) { + q.push(n->children[j]); + } + } + grandChildrenCount = grandChildrenCount + i; + popCount = popCount + 1; + } else { + popCount = 0; + childrenCount = grandChildrenCount; + grandChildrenCount = 0; + levelCounter = levelCounter + 1; + } + } + return levelCounter + 1; +} +int getHeight(vector &a) { + vector nodes; + nodes.resize(a.size()); + int rootIndex = 0; + for (int i = 0; i < a.size(); i++) { + int parentIndex = a[i]; + nodes[i].setKey(i); + if (parentIndex == -1) { + rootIndex = i; + } else { + nodes[i].setParent(&nodes[parentIndex]); + } + } + return treeLevelCounter(nodes, rootIndex); } -//TEST(CheckBracket, t1) { -// string exp = "[]"; -// ASSERT_EQ("Success", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t2) { -// string exp = "{}[]"; -// ASSERT_EQ("Success", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t3) { -// string exp = "[()]"; -// ASSERT_EQ("Success", checkBracket(exp)); +//TEST(GetTreeHeight, t1) { +// vector a = {4, -1, 4, 1, 1}; +// ASSERT_EQ(3, getHeight(a)); //} // -//TEST(CheckBracket, t4) { -// string exp = "(())"; -// ASSERT_EQ("Success", checkBracket(exp)); +//TEST(GetTreeHeight, t2) { +// vector a = {-1, 0, 4, 0, 3}; +// ASSERT_EQ(4, getHeight(a)); //} // -//TEST(CheckBracket, t5) { -// string exp = "{[]}()"; -// ASSERT_EQ("Success", checkBracket(exp)); +//TEST(GetTreeHeight, t3) { +// vector a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1}; +// ASSERT_EQ(4, getHeight(a)); //} // -//TEST(CheckBracket, t6) { -// string exp = "{"; -// ASSERT_EQ("1", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t7) { -// string exp = "{[}"; -// ASSERT_EQ("3", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t8) { -// string exp = "foo(bar);"; -// ASSERT_EQ("Success", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t9) { -// string exp = "foo(bar[i);"; -// ASSERT_EQ("10", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t10) { -// string exp = "[](()"; -// ASSERT_EQ("3", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t11) { -// string exp = "{[}haha"; -// ASSERT_EQ("3", checkBracket(exp)); -//} -// -//TEST(CheckBracket, t12) { -// string exp = "haha{[}"; -// ASSERT_EQ("7", checkBracket(exp)); +//TEST(GetTreeHeight, t4) { +// vector a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5}; +// ASSERT_EQ(6, getHeight(a)); //} int main() { - std::string text; - getline(std::cin, text); - - std::cout << checkBracket(text) << '\n'; - - return 0; + size_t an; + std::cin >> an; + vector a(an); + for (size_t i = 0; i < an; i++) { + std::cin >> a[i]; + } + std::cout << getHeight(a) << std::endl; } -- cgit v1.2.3