See how Fed stabs taxpayers in the back (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

See how Fed stabs taxpayers in the back (转载)

See how Fed stabs taxpayers in the back (转载)# Stock

a*e2010-05-07 07:05

1 楼

知道要O(1)space的得用Morris Traversal。但想先写个简单的，却发现改了好几次。
1。开始没想清楚怎么把那两个错误的node找出来
2. 应该用*& 的地方用了*。后来发现不作为param来pass还更简单。
但这样也有很多行，等有时间写个Morris的比较下。感觉也不是那么简单啊，sigh！
class Solution {
public:
TreeNode *first, *second, *pre;
void helper(TreeNode *cur)
{
if (cur==NULL)
return;

helper(cur->left);
if (pre)
{
if (pre->val>cur->val)
{
if (first==NULL)
{
first = pre;
second = cur;
}
else
second = cur;
}
}
pre = cur;
helper(cur->right);
}
void recoverTree(TreeNode *root) {
if (root==NULL||(root->left==NULL && root->right==NULL))
{
return;
}
first=NULL, second=NULL, pre=NULL;
helper(root);
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
之前pass param的
class Solution {
public:
void helper(TreeNode *cur, TreeNode *&first, TreeNode *&second, TreeNode
*&pre)
{
if (cur==NULL)
return;

helper(cur->left, first, second, pre);
if (pre)
{
if (pre->val>cur->val)
{
if (first==NULL)
{
first = pre;
second = cur;
}
else
second = cur;
}
}
pre = cur;
helper(cur->right, first, second, pre);
}
void recoverTree(TreeNode *root) {
if (root==NULL||(root->left==NULL && root->right==NULL))
{
return;
}

vector t;
TreeNode *first=NULL, *second=NULL, *pre=NULL;
helper(root,first, second, pre);
int tmp = first->val;
first->val = second->val;
second->val = tmp;

}
};

N*n2010-05-07 07:05

2 楼

【以下文字转载自 USANews 讨论区】
发信人: NeverLearn (24K Golden Bear), 信区: USANews
标题: See how Fed stabs taxpayers in the back
发信站: BBS 未名空间站 (Fri May 7 21:56:56 2010, 美东)
And yet Obama is busy shielding Federal Reserve from any serious auditing.

y*n2010-05-07 07:05

3 楼

看了MM这股劲，我知道以前版上说中国女生面试容易都是假的。而是你们有聪明，又整
备的好。

a*e2010-05-07 07:05

4 楼

多谢多谢，不过要狂汗一下。周围聪明人好多好多，不分性别。
看到版上很多牛人，就想抛砖引玉讨论一下。我平时就动作慢，写程序很慢，准备也很
慢。一紧张就想不清楚。
听说那些题都要做到10分钟就能写出来，也不知道啥时候能达到那个地步。

y*n2010-05-07 07:05

5 楼

你不Pass的方法用了Global Variable, 有的面试官可能或让你改一下。

【在 a***e 的大作中提到】

: 知道要O(1)space的得用Morris Traversal。但想先写个简单的，却发现改了好几次。
: 1。开始没想清楚怎么把那两个错误的node找出来
: 2. 应该用*& 的地方用了*。后来发现不作为param来pass还更简单。
: 但这样也有很多行，等有时间写个Morris的比较下。感觉也不是那么简单啊，sigh！
: class Solution {
: public:
: TreeNode *first, *second, *pre;
: void helper(TreeNode *cur)
: {
: if (cur==NULL)

a*e2010-05-07 07:05

6 楼

嗯，试图写O（1）的，发现用vector把指针装起来，再pass reference容易一些。但是
不知道为啥初始化的时候下面这个不行
vector m(2, NULL);
Compile Error
required from ‘std::vector<_tp _alloc="">::vector(_InputIterator, _
InputIterator, const allocator_type&) [with _InputIterator = int; _Tp =
TreeNode*; _Alloc = std::allocator; std::vector<_tp _alloc="">::
allocator_type = std::allocator]’
得换成这几行
vector m;
m.push_back(NULL);
m.push_back(NULL);
还没仔细debug 为什么下面这个答案不对，而后面那个就对。
错误的
class Solution {
public:
void helper(TreeNode *pre, TreeNode *cur, vector &mistakes )
{
if(pre)
{
if (pre->val>cur->val)
{
if (mistakes[0]==NULL)
{
mistakes[0] = pre;
}
mistakes[1] = cur;
}
}

}
void recoverTree(TreeNode *root) {
if (root==NULL||(root->left==NULL && root->right==NULL))
{
return;
}
TreeNode *first=NULL, *second=NULL, *pre=NULL, *cur=root;
vector m;
m.push_back(NULL);
m.push_back(NULL);

while(cur)
{
if (cur->left==NULL)
{
helper( pre, cur, m);
pre = cur;
cur = cur->right;
}
else
{
pre = cur->left;
while(pre->right!=NULL&&pre->right!=cur)
{
pre = pre->right;
}

if (pre->right==NULL)
{
pre->right = cur;
pre = cur;
cur = cur->left;
}
else
{
helper( pre, cur, m);
pre->right = NULL;
pre = cur;
cur = cur->right;
}
}
}
int tmp = m[0]->val;
m[0]->val = m[1]->val;
m[1]->val = tmp;

}
正确的
void helper(TreeNode *pre, TreeNode *cur, vector &mistakes )
{
if(pre)
{
if (pre->val>cur->val)
{
if (mistakes[0]==NULL)
{
mistakes[0] = pre;
}
mistakes[1] = cur;
}
}

}
void recoverTree(TreeNode *root) {
if (root==NULL||(root->left==NULL && root->right==NULL))
{
return;
}
TreeNode *first=NULL, *second=NULL, *pre=NULL, *cur=root;
vector m(2, NULL);

while(cur)
{
if (cur->left==NULL)
{
helper( pre, cur, m);
pre = cur;
cur = cur->right;
}
else
{
auto node = cur->left;

while(node->right!=NULL&&node->right!=cur)
{
node = node->right;
}

if (node->right==NULL)
{
node->right = cur;
cur = cur->left;
}
else
{
helper( pre, cur, m);
node->right = NULL;
pre = cur;
cur = cur->right;
}
}
}
int tmp = m[0]->val;
m[0]->val = m[1]->val;
m[1]->val = tmp;

}

a*e2010-05-07 07:05

7 楼