DarkPassenger
BAN USERIf you do this recursively, this only need one line, and time complexity is O(n).
class Node {
public:
int value;
Node *left, *right;
};
bool checkBST(Node *root) {
return (root == NULL) ||
((root->left == NULL || root->left->value <= root->value) &&
(root->right == NULL || root->value <= root->right->value) &&
checkBST(root->left) && checkBST(root->right));
}
We just need to find the right position to swap and reverse. The time complexity is O(n) and space is O(1).
Please refer to STL's next_permutation implementation:
stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int getNextNumber(int number) {
vector<int> digits;
while (number > 0) {
digits.push_back(number % 10);
number /= 10;
}
int i = 0, ii = 1;
while (ii < digits.size() && digits[ii] > digits[i]) {
ii++;
i++;
}
if (ii != digits.size()) {
for (int i = 0; i < ii; ++i) {
if (digits[i] > digits[ii]) {
std::swap(digits[i], digits[ii]);
std::reverse(digits.begin(), digits.begin() + ii);
break;
}
}
} else {
return -1;
}
int next = 0;
for (vector<int>::reverse_iterator it = digits.rbegin(); it != digits.rend();
++it) {
next *= 10;
next += *it;
}
return next;
}
int main() {
cout << getNextNumber(4765) << endl;
}
I constructed an expression tree recursively. It works well. If there is n numbers and 4 operators, then the time should be O(4^n*n!), and the space is O(n^2) (mainly used in stack when doing recursion).
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
enum Op {ADD, MUL, SUB, DIV};
class Node {
public:
Node *left, *right;
int value;
Op op;
Node (int value) : value(value) { left = right = NULL; }
bool setChild (Node *left, Node *right, Op op) {
this->left = left;
this->right = right;
this->op = op;
switch (op) {
case ADD:
this->value = left->value + right->value;
break;
case SUB:
this->value = left->value - right->value;
break;
case MUL:
this->value = left->value * right->value;
break;
case DIV:
if (right->value == 0 || (left-value % right->value != 0))
return false;
this->value = left->value / right->value;
break;
}
return true;
}
void print() {
cout << left->value;
switch(op) {
case ADD:
cout << " + ";
break;
case SUB:
cout << " - ";
break;
case MUL:
cout << " * ";
break;
case DIV:
cout << " / ";
break;
}
cout << right->value << endl;
}
};
Node *constructExpressionTree(vector<Node*> &nodes, int target) {
if (nodes.size() == 1 && nodes[0]->value == target) {
return nodes[0];
}
int size = nodes.size();
Node *new_node = new Node(0), *result = NULL;
bool valid;
vector<Node*> next_nodes;
for (int i = 0; i < size && !result; ++i) {
for (int j = i + 1; j < size && !result; ++j) {
next_nodes.clear();
next_nodes.insert(next_nodes.end(), nodes.begin(), nodes.begin() + i);
next_nodes.insert(next_nodes.end(), nodes.begin() + i + 1, nodes.begin() + j);
next_nodes.insert(next_nodes.end(), nodes.begin() + j + 1, nodes.end());
next_nodes.push_back(new_node);
for (int op = ADD; op <= DIV; ++op) {
valid = new_node->setChild(nodes[i], nodes[j], static_cast<Op>(op));
if (valid && (result = constructExpressionTree(next_nodes, target))) {
new_node->print();
break;
}
if (op >= SUB) {
valid = new_node->setChild(nodes[j], nodes[i], static_cast<Op>(op));
if (valid && (result = constructExpressionTree(next_nodes, target))) {
new_node->print();
break;
}
}
}
}
}
if (!result)
delete new_node;
return result;
}
Node *construct(vector<int> numbers, int target) {
vector<Node*> expression;
for (vector<int>::iterator it = numbers.begin();
it != numbers.end(); ++it) {
Node *node = new Node(*it);
expression.push_back(node);
}
return constructExpressionTree(expression, target);
}
void print(Node *root, bool par = false) {
if (!root) {
cout << "no valid expression. " << endl;
return;
}
if (root->left && root->right) {
if (par)
cout << "(";
bool left_par = (root->op == MUL || root->op == DIV) &&
(root->left->op == ADD || root->left->op == SUB);
bool right_par = root->op == DIV ||
((root->op == MUL || root->op == SUB) &&
(root->right->op == ADD || root->right->op == SUB));
print(root->left, left_par);
switch(root->op) {
case ADD:
cout << " + ";
break;
case SUB:
cout << " - ";
break;
case MUL:
cout << " * ";
break;
case DIV:
cout << " / ";
break;
}
print(root->right, right_par);
if (par)
cout << ")";
} else {
cout << root->value;
}
}
void deleteNodes(Node *root) {
if (!root)
return;
deleteNodes(root->left);
deleteNodes(root->right);
delete root;
}
int main() {
vector<int> numbers;
int target = 24;
srand((unsigned)time(NULL));
numbers.push_back(rand() % 13 + 1);
numbers.push_back(rand() % 13 + 1);
numbers.push_back(rand() % 13 + 1);
numbers.push_back(rand() % 13 + 1);
copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " "));
cout << endl;
Node *root = construct(numbers, target);
print(root);
cout << endl;
deleteNodes(root);
}
this solution is wrong. if you predefined H and T, then HTT or HHT can form a obtuse triangle if the three points are close to each other.
- DarkPassenger March 07, 2013if it queries sum[0...n], it requires O(n) time anyway. so I guess preprocessing is not counted for the O(n^0.5) time complexity.
- DarkPassenger March 01, 2013Your first point is absolutely wrong. Complexity of construction of suffix tree is FAR MORE than linear. This method is not scalable when string s is very long, say, a million characters.
- DarkPassenger February 01, 2013Did you think about the time complexity?
- DarkPassenger February 01, 2013
I believe this question is about recursion:
- DarkPassenger March 27, 2013