Eidolon.C
BAN USERYour idea is good, however it should not be calculated in that way. If we do like that, then the prob(red, pop, arrive not earlier on fri.) = 0.4 * 0.4 * 0.7 is also larger than black&rock.
The problem is P(Red&pop|Fri) != P(Fri|Red&pop).
if we assume the conditions are mutual independent, P(Fri|Red&pop) = P(Fri&Red&pop) / P(Red&pop) = P(Fri), so they are all the same.
Actually it's a para-curve, let's say the start point of the bird is (0,0) and the horizontal line is x axis, and right is the positive direction, so the curve is: y = d1 (x)^2.
now given y = n * d2, the distance between (x,y) and (0,0) is required, it's not hard.
maybe because you didn't check node->left before you use node->left->value, and node->right too, in
if (count) {
evaluate(node->left, total + node->value + NODE->LEFT->VALUE, count - 1);
...
by the way, i think your logic is not right, as for the weight belongs to the edge, not the node. fyi, a better tree maybe like this:
class EdgeTreeNode {
public:
int left_weight;
int right_weight;
EdgeTreeNode *left, *right, *parent;
};
here is an O(N) solution based on finding max and min elements in k window:
int maxProfit(vector<int> &nums, int k = 100) {
int n = nums.size();
if (n < 2) return 0;
vector<int> prices{ nums[0] };
for (int j = 1; j < n; ++j) prices.push_back(prices.back() + nums[j]);
int maxpro = 0, maxbuy = 0, maxsell = 0, buy = 0, sell = 0, pro = 0;
deque<int> buytime;
deque<int> selltime;
for (int i = 0; i < n; ++i) {
while (!buytime.empty() && i - buytime.front() >= k) buytime.pop_front();
while (!buytime.empty() && nums[buytime.front()] >= nums[i]) buytime.pop_front();
while (!buytime.empty() && nums[i] <= nums[buytime.back()]) buytime.pop_back();
buytime.push_back(i);
while (!selltime.empty() && !buytime.empty() && selltime.front() <= buytime.front()) selltime.pop_front();
while (!selltime.empty() && nums[selltime.front()] <= nums[i]) selltime.pop_front();
while (!selltime.empty() && nums[i] >= nums[selltime.back()]) selltime.pop_back();
selltime.push_back(i);
pro = nums[selltime.front()] - nums[buytime.front()];
if (maxpro < pro) maxpro = pro;
}
return maxpro;
}
I think the meaning of this problem is how many numbers in range [1, 100000] contains an EVEN NUMBER of ODD DIGIT, which means the numbers should have odd digit(don't count 0 odd digit numbers), and the count of odd digit should be even, like 11, 13, 15, 110, 1100... and not 1, 3, 12, 111...
Actually it's a intricate problem.
I use brute force method checked numbers in range [1, 20000] and [100000, 106000] and the following method is correct.
int countSmall(int st, int en) {
if (st > en) return 0;
int res = 0, oddcount = 0, tmp;
for (int i = st; i <= en; ++i) {
tmp = i;
oddcount = 0;
while (tmp) { if (tmp & 1) ++oddcount; tmp /= 10; }
if (oddcount % 2 == 0 && oddcount) res++;
}
return res;
}
int countEvenOdd(int end) {
int fullcount = end / 100 ;
int res = fullcount / 2 * 75;
res += countSmall(fullcount * 100, end);
int tmp = fullcount - 1, oddcount = 0;
while (tmp) { if (tmp & 1) ++oddcount; tmp /= 10; }
if (fullcount) res += 25 * countEvenOdd(fullcount - 1);
if (fullcount & 1) res += (oddcount & 1) ? 50 : 25;
return res;
}
correct me if I'm not right, thanks.
- Eidolon.C July 28, 2015maybe use a circle buffer list can solve it:
const int BUFSIZE = 1024;
class ListNode {
public:
char *buffer;
ListNode() { buffer = new char[BUFSIZE]; }
~ListNode() { delete[] buffer; }
};
ListNode *curr_read = new ListNode(), *curr_write = curr_read;
curr_read->next = curr_write;
int curr_read_ind = 0, curr_write_ind = 0;
void input(InputDevice in) {
while (true) {
if (curr_read_ind == BUFSIZE) {
curr_read_ind = 0; // reset read index
if (curr_read->next == curr->write) { // create a new buffer node
ListNode *tmp = new ListNode();
tmp->next = curr->read->next;
curr->read->next = tmp;
}
curr_read = curr->read->next;
}
if (in.hasNext()) {
curr_read->buffer[curr_read_ind] = in.read();
curr_read_ind++;
}
}
}
void output(WriteDevice out) {
while (true) {
while (curr_write == curr_read) {} //wait for input device
while (curr_write_ind != BUFSIZE) { out.write(curr_write->buffer[curr_write_ind]); curr_write_ind += 2; }
curr_write_ind = 0;
curr_write = curr_write->next;
}
}
correct me if I'm wrong, thanks!
- Eidolon.C July 28, 2015first we should check how to handle circle like ab->ba.
here I use a set to detect circle and only save {ab, ba}.
connect the last node to the root, then we can use a recursive function to handle all nodes.
class SListNode {
public:
string v;
SListNode *next;
SListNode(string s) : v(s), next(NULL) {};
};
vector<vector<string>> line(SListNode *root, vector<string> &pre, set<string> &predic) {
vector<vector<string>> res;
string &tmp = root->v;
pre.push_back(root->v);
predic.insert(root->v);
SListNode *p = root->next;
while (p != root) {
if (p->v[0] == tmp.back() && predic.find(p->v) == predic.end()) {
auto tmpres = line(p, pre, predic);
res.insert(res.end(), tmpres.begin(), tmpres.end());
}
p = p->next;
}
if (res.empty()) {
res.push_back(pre);
}
predic.erase(root->v);
pre.pop_back();
return res;
}
vector<vector<string>> line(SListNode *root) {
if (!root) return vector<vector<string>>();
SListNode *p = root;
while (p->next) p = p->next;
p->next = root;
vector<string> tmp;
set<string> tmpdic;
auto res = line(root, tmp, tmpdic);
p->next = NULL;
return res;
}
sample result:
Here ew
Here error roll long
another test case: ab->ba->acd->bcd
result:
ab ba acd
ab bcd
There are three kinds of users: owner, renter, guest
behaviors:
owner: identify; upload items, manage items (including item description, duration, rent and deposit); receipt return
renter: identify; search items, request for items, pay to vrbo(including rent and deposit), receipt item, return
guest: search items.
Sort of like that. To design a system we should analysis the roles and the requirements, correct me if I'm wrong or inform me if you have any better ideas, thanks.
I think this will work too:
- Eidolon.C September 07, 2015