Linfuzki
BAN USERSave the result in a doubly linked list:
Node* multiply(Node* a, Node* b) {
if (!a || !b) return NULL;
DNode* result = new DNode();
Node* cur_a = a;
while (cur_a) {
Node* cur_b = b;
DNode* cur_result = result;
while (cur_b) {
cur_result->increase(cur_a->value * cur_b->value);
cur_b = cur_b->next;
if (cur_b) cur_result = cur_result->get_next();
}
cur_a = cur_a->next;
if (cur_a) result = result->get_next();
}
DNode* head = result->get_head();
Node* product = head->create_node();
delete head;
return product;
}
Implementation for DNode:
struct Node {
int value;
Node* next;
};
struct DNode {
int value;
DNode* next;
DNode* previous;
DNode() : value(0), next(NULL), previous(NULL) {}
~DNode() { delete next; }
void increase(int a) {
value += a;
if (value >= 10) {
int d = value /10;
value %= 10;
get_previous()->increase(d);
}
}
DNode* get_next() {
if (next) return next;
next = new DNode();
next->previous = this;
return next;
}
DNode* get_previous() {
if (previous) return previous;
previous = new DNode();
previous->next = this;
return previous;
}
DNode* get_head() {
if (!previous) return this;
return previous->get_head();
}
Node* create_node() {
Node* node = new Node();
node->value = value;
node->next = next ? next->create_node() : NULL;
return node;
}
};
struct Node {
Node* next;
Node* random;
int value;
};
Node* copy(Node* head) {
if (!head) return NULL;
// copy the list
Node* cur = head;
while (cur) {
Node* node = new Node();
node->value = cur->value;
node->random = NULL;
node->next = cur->next;
cur->next = node;
cur = node->next;
}
// update random correctly
cur = head;
while (cur) {
cur->next->random = cur->random ? cur->random->next : NULL;
cur = cur->next->next;
}
// split list
Node* newhead = head->next;
Node* newcur = newhead;
cur = head;
while (cur) {
cur->next = newcur->next;
cur = cur->next;
newcur->next = cur ? cur->next : NULL;
newcur = newcur->next;
}
return newhead;
}
Go through the matrix row by row; for each row, record the maximum height each column can reach. Then it becomes a skyline problem, which can be solved in O(n).
Overall, the time complexity is O(n * n) and the space complexity is O(n);
#include <vector>
#include <stack>
using namespace std;
int get_max_area(const vector<vector<int> >& m) {
int result = 0;
vector<int> h(m[0].size() + 1, 0);
for (int i = 0; i < m.size(); ++i) {
stack<int> s;
for (int j = 0; j <= m[i].size(); ++j) {
if (j < m[i].size())
h[j] = (m[i][j] == 0) ? 0 : h[j] + 1;
while (!s.empty() && h[s.top()] > h[j]) {
int top = s.top();
s.pop();
int begin = s.empty() ? 0 : s.top() + 1;
result = max(result, h[top] * (j - begin));
}
s.push(j);
}
}
return result;
}
Hi Pavi,
Part 1 is for the original question and part 2 is for the follow up question.
For your questions:
- update(node) updates the value of node and its subtree, and returns the sum of the node & its subtree
- as mentioned above, the sum of the node & its subtree is returned; since node already contains the sum of its subtree, the result value would be node->value * 2
- say, if a parent node expects a value of 20, then its child node need only half of it, which is 10, because the subtree of the child node can contribute the other half. On the other hand, if the expected value is odd, e.g. 21, then 21 / 2 is 10, which is not enough to meet 21; the expected value is increased by 1 to deal with that.
Please let me know if it doesn't make sense
RepNoraLillian, Applications Developer at Coupondesh
Nora, working as a ghostwriter with a history in manuscript development, proofreading, and editing, I apply with enthusiasm for this ...
RepElijahMiller, abc at A9
I am highly organized with exceptional commitment to task completion and quality assurance when working with computer software programs. I ...
RepMacHeist, Data Scientist at British Telecom
Mac, a Desktop Publishing Specialist at VitaGrey, where I provide document formatting and publishing support to a wide variety of ...
Repanayadonal67, Animator at ABC TECH SUPPORT
AnayaDonal and I am a City planners. I have completed all my studies from Chicago. It's been a long ...
Reprmansummers, Accountant at Alcatel Lucent
I'm Rman! I graduated from the University of Arizona with a Bachelor's degree in Psychology and Education. I ...
RepShivelyFauver, Animator at AMD
Project Management Assistant with a proven record in developing and managing project budgets, completing presentations and reports. As nowadays astrology ...
RepRileyLopez, Android Engineer at A9
I am working as a network administrator in a technical support company. I planned and recommended network hardware, systems, management ...
RepSimonPister, Blockchain Developer at Absolute Softech Ltd
Simon , a food scientist , records the Tracking status of all existing ingredients during the review and updating process and communicates ...
I'm afraid it won't work for case like this:
- Linfuzki March 23, 2014001
001
111