summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2019-01-11 19:54:13 -0600
committerHaidong Ji2019-01-11 19:54:13 -0600
commit8fb3943122786e9ab13bf06cae6ad9ab70860fc4 (patch)
tree029272f25cc7d46a65bf174df02b15bde3368c60 /Sources
parent947da6a7c9dd61dad5bc8fa6d84bb0ed590c251b (diff)
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.
Diffstat (limited to 'Sources')
-rw-r--r--Sources/DataStructure.cpp185
1 files changed, 90 insertions, 95 deletions
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 <iostream>
-#include <stack>
+#include <queue>
#include <algorithm>
#include <vector>
//#include <gtest/gtest.h>
-using std::string;
-using std::stack;
+using std::vector;
+using std::queue;
-const std::vector<char> brackets = {'[',']','(',')','{','}'};
+class Node;
-static string checkBracket(string exp) {
- stack<char> 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<Node *> 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<Node *> getChildren() {
+ return children;
+ }
+
+ void setKey(int theKey) {
+ key = theKey;
+ }
+};
+
+int treeLevelCounter(vector<Node> &nodes, int rootIndex) {
+ int levelCounter = 1;
+ queue<Node *> 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<int> &a) {
+ vector<Node> 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<int> 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<int> 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<int> 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<int> 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<int> a(an);
+ for (size_t i = 0; i < an; i++) {
+ std::cin >> a[i];
+ }
+ std::cout << getHeight(a) << std::endl;
}