由买买提看人间百态

topics

全部话题 - 话题: node1
1 2 下页 末页 (共2页)
g****9
发帖数: 163
1
写了一个graph的class 但是下面第一种写法是错误的,我不是太明白,是因为
GNode node1 = null;GNode node2 = null吗?这时候node1跟node2并没有allocate
memory,所以就算后面if statement里面的node1 = new GNode(key1) 也只是在if这个
block里面有效的吧,在最后node1.connect(node2)里node1 是不是还是null呢 求指
点。第二个graph class 就可以work的。
public Graph(int[][] adjacencyMatrix) {
nodes = new HashMap();
GNode node1 = null;
GNode node2 = null;
for (int i = 0; i < adjacencyMatrix.length; i++) {
int key1 = i + 1;
... 阅读全帖
s*******9
发帖数: 5
2
来自主题: Database版 - 问个RAC的问题
在虚拟机里装了个RAC,发现个问题:
环境是这样的:
oracle virtual box 4.3.14
redhat linux enterprise edition 5.10
oracle rac and oracle clusterware 10.2.0.5.0
crs_stat -t
ora....SM1.asm application ONLINE ONLINE node1
ora....E1.lsnr application ONLINE ONLINE node1
ora.node1.gsd application ONLINE ONLINE node1
ora.node1.ons application ONLINE ONLINE node1
ora.node1.vip application ONLINE ONLINE node1
ora....SM2.asm application ONLINE ONL... 阅读全帖
r*******y
发帖数: 1081
3
来自主题: JobHunting版 - 问一个题目
bool IsNodeInside(TreeNode * root, TreeNode * node){
if(root==NULL)
return false;
if(node == root)
return true;
bool tmp = IsNodeInside(root->left, node);
if(tmp == true)
return true;
tmp = IsNodeInside(root->right, node);
if(tmp == true)
return true;
return false;
}
TreeNode * find(TreeNode * root, TreeNode * node1, TreeNode * node2){
if(root == NULL)
return NULL;
if(node1==root)
retur... 阅读全帖
Y********f
发帖数: 410
4
学习了,今天花时间仔细看了一下morris traversal,同时练习了一下,测试了一个
case。
Node *getNext(Node* &bst)
{
Node *cur = bst;
while(cur)
{
if (cur->lch == NULL)
{
bst = cur->rch;
return cur;
}
Node *prev = cur->lch;
while(prev->rch && prev->rch != cur)
prev = prev->rch;
if (!prev->rch)
{
prev->rch = cur;
cur = cur->lch;
}
else
{
prev->rch = NULL;
bst ... 阅读全帖
d*******r
发帖数: 208
5
来自主题: JobHunting版 - A onsite被拒,面经,求分析失败原因
my bad. my revision won't work.
Wrote an nlogn code.
Node* LowCommonAnc(Node *node, Node *node1, Node *node2){
if(node==NULL || node1 == NULL || node2 == NULL) { return NULL; }
if (node == node1 || node == node2) { return node; }
if (isChildren(node->left, node1) && isChildren(node->left, node2)) {
// both go left
return LowCommonAnc(node->left, node1, node2);
} else if (isChildren(node->right, node1) && isChildren(node->right,
node2)) {
// both go right
... 阅读全帖
S**I
发帖数: 15689
6
☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖
p*****2
发帖数: 21240
7
我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root
p*****2
发帖数: 21240
8
来自主题: JobHunting版 - 问个二叉树删除结点的问题
我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root
p*****2
发帖数: 21240
9
来自主题: JobHunting版 - 发现一个很恶心的基础问题
merge=(node1, node2)->
return node2 if !node1
return node1 if !node2
node1.right=merge(node1.right,node2)
return node1
deleteNode=(root, val)->
if(root.val==val)
root=merge(root.left,root.right)
else if(val root.left=deleteNode(root.left,val)
else
root.right=deleteNode(root.right,val)
return root
s**********e
发帖数: 326
10
来自主题: JobHunting版 - 问一道题(1)
Given two BTs T1 and T2, return the larest common subtree
idea:
step one:
首先分别对T1, T2做预处理,求出每个subtree的nodes总个数,把得到的结果存到
hashtable里面,这一步时间复杂度O(N), N=number of nodes
step two:
从root开始从上到下对每对相对应的node pair,判断以他们为root的subtree是否相同
given node1 from t1, node2 from t2
f(node1,node2)= true if node1 == node2 && f(node1.left, node2.left) && f(
node1.right, node2.right)
这个过程可以使用dp的思想,建个hashtable存放f的值,key=node1.hashcode+"-"+
node2.hashcode, value=boolean
这一步时间复杂度O(N)
step three:
有了第一步的每个subtree 的size, 第二步的每对s... 阅读全帖
b***y
发帖数: 2799
11
☆─────────────────────────────────────☆
shuo (说说罢了) 于 (Thu Sep 22 16:28:10 2005) 提到:
其实是很简单的问题。 两个file,一个file有 node1 node2 C 三个field。另一个
file是个lookup table有 node E F三个field。输出是, node1 node2 C E(node1
) F(node1) E(node2) F(node2). 就是为node1,2找对应的E, F然后全部输出的意思
。 可是我不太会写程序,只能写最简单最笨的。 所以我写乐下边这个。 都还没管node2
, 想着先把node1 得E,F输出出来到一个out.txt里边,然后在运行一遍给node2找对应的E
, F。可是因为我的file1很大,几十万条record。 这个程序运行了2个小时乐,才1/5多
点。 可能也是file I/O的问题。 可是如果我不开关file2, 我不知道怎么让file2的
ifstream指针回到文件最顶上。 结果就是他只查找一遍,然
c*******r
发帖数: 309
12
来自主题: JobHunting版 - LCA复杂度是多少
public class LowestCommonAncestor {
public boolean cover(Node root, Node node) {
if (root == null)
return false;
if (root == node)
return true;
return cover(root.left, node) || cover(root.right, node);
}
public Node Ancestor(Node root, Node node1, Node node2) {
if (root == null)
return root;
if (cover(root.left, node1) && cover(root.left, node2))
return Ancestor(root.left, node1, node2);
i... 阅读全帖
c*******r
发帖数: 309
13
来自主题: JobHunting版 - LCA复杂度
public boolean cover(Node root, Node node) {
if (root == null)
return false;
if (root == node)
return true;
return cover(root.left, node) || cover(root.right, node);
}
public Node Ancestor(Node root, Node node1, Node node2) {
if (root == null)
return root;
if (cover(root.left, node1) && cover(root.left, node2))
return Ancestor(root.left, node1, node2);
if (cover(root.right, node1) && cover(roo... 阅读全帖
k*o
发帖数: 2
14
求牛人帮忙找bug。
题目是leetcode上的"Recover Binary Search Tree"。
思路是中序遍历,用递归做。
总是过不了OJ,在自己电脑上可以跑。
求大牛帮忙看看怎么回事。跪谢了!!!
我的代码如下:
public class Solution {
TreeNode node1 = null;
TreeNode node2 = null;
TreeNode last = null;
TreeNode current = null;
public void dfs(TreeNode root) {
if(root == null) {
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
dfs(left);
last = current;
current = root;
if(last!=nul... 阅读全帖
l**********9
发帖数: 537
15
这个流行的解法通不过 {0,1}的test case,上个星期还可以通过。看不出什么问题
,你们的还能通过吗?
public class Solution {
TreeNode node1 = null;
TreeNode node2 = null;
TreeNode prev = null;
public void recoverTree(TreeNode root) {
inorderTraverse(root);
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}

private void inorderTraverse(TreeNode root) {
if (root == null)
return;
inorderTraverse(root.left);
if (prev != null) {
... 阅读全帖
h*******e
发帖数: 1377
16
感觉答案 把 条件加强了 很可能 node1 node2 是选取2点, node1 -> node2 没有
route 而 node2 -> node 1 有route 这时候 如果把node1 作为start node2 做为
end...那就 不可能查出 node2 到 node1 的 route. 1 -> 2 1 -> 3 1 -> 4
4->1 5->4 求1 5 是否有通路 如果 start取 1 end取 5 一次bfs结果是 无通路
而实际 有 5 -> 4-> 1那就 不对了
S********g
发帖数: 45
17
来自主题: JobHunting版 - 报Google Offer并请教面试题
请问第一题简化后的。。
是不是除了有可能有circle 和tree就一样
还有比如 graph 1的入口是node1,node1左边是node2 右边是node3
然后graph 2的入口是node1‘, node1’的左边是node2‘ 右边是node3’
也就是除了左右互换了 剩下都一样
这两个图算一样嘛?
我的想法是两个树同步 bfs 要用2个queue 对不对呢?
多谢!
S********g
发帖数: 45
18
来自主题: JobHunting版 - 报Google Offer并请教面试题
请问第一题简化后的。。
是不是除了有可能有circle 和tree就一样
还有比如 graph 1的入口是node1,node1左边是node2 右边是node3
然后graph 2的入口是node1‘, node1’的左边是node2‘ 右边是node3’
也就是除了左右互换了 剩下都一样
这两个图算一样嘛?
我的想法是两个树同步 bfs 要用2个queue 对不对呢?
多谢!
j******3
发帖数: 16
19
unordered_set visited;
while(node1 != NULL)
{
visited.insert(node1);
node1 = node1->parent;
}
while(node2 != NULL)
{
if(visited.find(node2) != visited.end() ) break;
node2 = node2->parent;
}
return node2;
时空都是log(n),空手写的,错了轻喷
j********2
发帖数: 82
20
来自主题: JobHunting版 - 那个双堆求median的能不能这样做?
Maintain a BBST with parent pointers. We insert into the tree upon each new
number, and we also maintain two pointers of consecutive nodes from which we
can calculate the median.
1. If size of the tree is even, return (node1+node2)/2.
2. O/w, return node1 or node2, depending on the relationship of newly
inserted element and node1/node2.
c****7
发帖数: 13
21
来自主题: JobHunting版 - 请教各位大牛一个K-way merge 的问题
原题是leetcode上的merge k sorted lists
http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
这个题有好几种解法,比如divide and conquer, priority queue.
我写了个priority queue的。我的问题是, 如果现在要做 merge k sorted
array,怎样来设计这个priority queue才能最简单有效呢?
附上 merge-k-sorted-lists的代码
public static ListNode mergeKLists_priorityQueue(ArrayList kLists)
{
// border case
if(kLists.size()==0) return null;
if(kLists.size()==1) return kLists.get(0);
// create a Comparator based on the nod... 阅读全帖
m********c
发帖数: 105
22
来自主题: JobHunting版 - c/c++ double pointer研究
嗯,疏忽,竟然把那个写错了,多谢提醒!
内存泄露是有可能,但是我们不知道head是不是通过new创建的。比如下面的例子。
在函数里,*lpp = (*lpp)->next, 之前加上 delete *lpp
如下定义这个list node,
ListNode node1(1);
ListNode node2(1);
node1.next = &node2;
duplicateNode(&node1)的话就会报错,pointer being freed was not allocated
s***e
发帖数: 284
23
来自主题: CS版 - 请教一个搜索问题
也就是说,开始访问Node1的时候,并不能找到所有满足要求且包含node1的
所有集合。对么?
实际上,你的算法从node1开始时,只找到了一个满足条件的集合(当然,
这个集合的子集也都是满足条件的答案)。这个集合取决于你每次检查一个
node所得到的集合(比如a,b)里排在第一个的元素(比如n_i),继而决定
下一次检查哪些node到n_i符合条件。
而实际上,可以进行的选择要多得多。比如集合a是{3,5,7,9},
下一步你可以从任何一个元素开始判断其他元素是否到该元素满足距离
大于L。现在有4种方法扩展,然后这一步选择之后又面临着下一轮选择。
你的算法不能保证所有的可能的组合都被枚举到。
s*****l
发帖数: 2041
24
来自主题: Linux版 - 请教一个script的问题
想查看cluster上面每个分机的cpu使用情况。
主机和分机都是Fedora Linux(具体版本不知道,应该是比较新的),从主机连到分机
用ssh node#。我可以一个一个分机连进去,然后用top看cpu使用情况。但是每次都这
样比较麻烦。能不能在主机运行一个script自动查看所有分机的cpu使用情况?
我试了一下这个script:
#! /bin/ksh -f
ssh node1
top
但是连到分机node1后,需要手敲exit出来,而且后面top也是主机的cpu使用,而不是
分机node1的。有没有什么办法在script连进分机后,运行某个command,然后又自动退
出来?
那位Linux大鸟支个招?万分感谢!
c***y
发帖数: 560
25
来自主题: JobHunting版 - Least Common Ancester算法最优解
根据这个link:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29
LCA的最优解似乎还是O(N) in both time and space complexity
似乎basic idea is transform a tree to an array in Euler Tour, then conduct
RMQ between this range.
如果这样,假设找node1&node2的LCA, 为啥不求得root-node1 & root-node2 path, 然
后找他们的最深交集呢? 难道是因为如果pre-build RMQ,可以support任意两点之间的
LCA?
谢谢讨论, thanks.
c***g
发帖数: 472
26
来自主题: JobHunting版 - 150上这个是不是不对? (转载)
I guess the line 3 and line 4 is not correct.
If both the linked list is NULL but the carry is 1, it should create a
new node and the value is the carry, am I right?
Thanks so much!
2.4 You have two numbers represented by a linked list, where each node
contains a single digit. The digits are stored in reverse order, such
that
the 1’s digit is at the head of the list. Write a function that adds the
two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5), (5 -> 9 -> 2)
Outpu... 阅读全帖
p*****2
发帖数: 21240
27

import java.io.*;
import java.util.*;
public class test2
{
public static void main(String[] args) throws Exception
{
new test2().run();
}
PrintWriter out = null;
void run() throws Exception
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
Node node1 = new Node(1);
Node node4 = new Node(4);
Node node3 = new Node(3);
node3.left = node1;
node3.right = node4;
Node node6 = new Nod... 阅读全帖
g**********9
发帖数: 49
28
来自主题: JobHunting版 - MS onsite面经
have a flat xml string:
n1n2n3n4
How to convert it into a tree structure below. Suppose you have a XML parser
can tell you getNextTag(); isTagStartingNode(); isTagEndNode(); isTagString
()
n1
/
n2
/ \
n3 n4
Any idea?
s*******s
发帖数: 1031
29
来自主题: JobHunting版 - MS onsite面经
我的代码,用递归做。不一定对 。。
// n1n2n3n4
n1
/
n2
/ \
n3 n4
string getNextTag();
bool isTagStartingNode(string tag);
bool isTagEndNode(string tag);
bool isTagString(string tag)
struct TreeNode {
string value;
TreeNode *left;
TreeNode *right;

TreeNode(string v) : value(v), left(NULL), right(NULL) {}
};
TreeNode *parse(string startTag) {
// no more nodes left
if(str.size() == 0)
retu... 阅读全帖
v*****y
发帖数: 68
30

对于每个Node,需要存储i,range (number of left nodes in left subtree),left,
right
如果新的node插进来,如果这个node的位置在node1的左子树,需要更新node1的range。
楼上也提到了,这个方法不能保证树的平衡,在构造树的时候,可以使用其他方法保证
他的平衡性。
y*******5
发帖数: 887
31
来自主题: JobHunting版 - 求指点一道G家Iterator的题目
用composition pattern:
1:---
package NestedIterator;
public interface NestedNodeList extends Iterable {
}
2:---
package NestedIterator;
import java.util.Iterator;
public class Node implements NestedNodeList {
private E val;
public Node(E val) {
this.val = val;
}
@Override
public Iterator iterator() {
return new NodeIterator();
}
private class NodeIterator implements Iterator {
private boolean iterated = false;
@Override... 阅读全帖
v****s
发帖数: 1112
32
来自主题: CS版 - mysql index优化求助 (转载)
【 以下文字转载自 Programming 讨论区 】
发信人: vicfcs (ML+CV), 信区: Programming
标 题: mysql index优化求助
发信站: BBS 未名空间站 (Thu Feb 3 10:53:18 2011, 美东)
目前的一个project需要在mysql里面查询 两个node之间的value,
table columns:
LOOKUPTABLE (INT id, VARCHAR node1, VARCHAR node2, INT value)
问题是这个table有 10 millions rows, 一次select query时间大概是0.8 sec:
select value from LOOKUPTABLE where node1 = 'a' and node2 = 'b';
尝试用index来优化query,但是不知道最优的index应该是哪种?谢谢!包子有赏!
c**t
发帖数: 2744
33
来自主题: Database版 - How to write the query
Oracle (10g), table A (id, Node, ...), where id, Node combination is unique.
How to query if Node1, Node2, ... with id1 exists where Node1,Node2.., id1
are parameters (inputs)?
v****s
发帖数: 1112
34
来自主题: Database版 - mysql index优化求助 (转载)
【 以下文字转载自 Programming 讨论区 】
发信人: vicfcs (ML+CV), 信区: Programming
标 题: mysql index优化求助
发信站: BBS 未名空间站 (Thu Feb 3 10:53:18 2011, 美东)
目前的一个project需要在mysql里面查询 两个node之间的value,
table columns:
LOOKUPTABLE (INT id, VARCHAR node1, VARCHAR node2, INT value)
问题是这个table有 10 millions rows, 一次select query时间大概是 3 sec:
select value from LOOKUPTABLE where node1 = 'a' and node2 = 'b';
尝试用index来优化query,但是不知道最优的index应该是哪种?谢谢!包子有赏!
w*********r
发帖数: 2095
35
来自主题: Database版 - 如何在Unbuntu下启动oracle
下面是我从网上找到的。问题是如何export the ORACLE_SID=orcl1 for node1?
----------
This means that the ORACLE_SID is set to orcl - and that would be invalid
for a RAC instance as there are multiple instances per database and
identified by an instance number in addition (e.g. orcl1, orcl2 and so on).
Fix the ORACLE_SID in the environment, prior to firing up a sqlplus session.
Great! I just exported the ORACLE_SID=orcl1 for node1 and it worked.
Thanks a ton for the quick reply.
j*a
发帖数: 14423
36
来自主题: Java版 - 帮看看这个swing的小程序?
谢谢各位的回复。
实际上我只是想定制一个jcomponent,要能实现鼠标drag的时候它能跟着走就可以了。
于是我加了Node的两个实例,但是却只出现了一个。这里面有很多问题
0.Node1实例看不见。为此我加了Thread改颜色希望能在屏幕上找到它,未果。
1.contentpane.add()不管用
2.我的listener是加到Node的,debug的时候却发现整个jframe的drag都被Node2实例接
收到了,Node1一点反应也没有
3.改fg/bg后加repaint()也不管用
我最希望解决问题0
swing新手 看了半天 还在蛮撞阶段 sorry
s*****l
发帖数: 2041
37
来自主题: Linux版 - 请教:如何不用输入密码
用Suse(什么版本忘了,就两年前的事情)做的PC cluster
问题是每次从主机连到分机总是要输入密码
怎样才能不用输入密码?
e.g.
每次ssh node1总会提示密码,怎么才能自动记住密码,直接连到分机node1?
谢谢了先
g**d
发帖数: 723
38
来自主题: Linux版 - question about SMB+NFS
有两个LINUX computer, node0 通过NFS MOUNT node1的盘,
node1:/u1 /u1 nfs timeo=14,intr
然后node0用SMB share /u1 和本地硬盘 /u0 给Windows computer.
现在发现在Windows computer上一次从/u1上读很大的文件会有
Insufficient system resources exist to complete the requested service.
但读node0本地的硬盘/u0就没问题.
这是怎么回事? 谢了!
v****s
发帖数: 1112
39
来自主题: Programming版 - mysql index优化求助
目前的一个project需要在mysql里面查询 两个node之间的value,
table columns:
LOOKUPTABLE (INT id, VARCHAR node1, VARCHAR node2, INT value)
问题是这个table有 10 millions rows, 一次select query时间大概是0.8 sec:
select value from LOOKUPTABLE where node1 = 'a' and node2 = 'b';
尝试用index来优化query,但是不知道最优的index应该是哪种?谢谢!包子有赏!
g*****g
发帖数: 34805
40
那也不是,比如用java来学数据结构就很好。
不需要指针折腾来折腾去,也不会让你直接用collection的库,
学的就是结构而已。
class Node {
Node next;
int data;
}
Node node0 = new Node();
Node node1 = new Node();
node0.next = node1
这个代码多么干净,多么简单易懂。根本不需要讲pointer跟reference的区别。
因为只有reference.
c*******h
发帖数: 1096
41
来自主题: Programming版 - [c++] virtual member?
假设我有个 Node 类,里面有一个成员变量
Node *next;
用来指向下一个 Node。我从 Node 继承了一个子类,叫 Node1D。我希望 Node1
还是有一个成员变量叫 next,指向下一个 Node1。成员变量不像函数一样可以
virtual,那我应该怎么做呢?
A*******s
发帖数: 3942
42
来自主题: Statistics版 - An interesting question from mysas.net/forum
i happen to remember you had once introduced me deep-first-search algorithm
a few days ago on this board. Can we change this to DFS problem?
Suppose we use sql inner join, as Sir's way
data a1;
set a1;
uid=_n_;
run;
proc sql;
create table link as
select min(b.uid,c.uid) as node1, max(b.uid,c.uid) as node2
from a1 as b, a1 as c
where (b.id1=c.id1 or b.id2=c.id2 or b.id3=c.id3 or b.id4=c.id4)
and b.uid ^= c.uid;
quit;
proc sort data=link nodup;
by node1;
run;
After that we have graph-structur
a*****e
发帖数: 51
43
来自主题: JobHunting版 - 问最小窗口覆盖的面试题
What does 'the smallest window' mean? Dose it mean that within this window, every unique words appear? If it is the case, then the following solution attacks:
Build a suffix tree for the text, each node contains a link list of
positions of the corresponding words in ascending order. So you would have something like:
Node1: 4->12->27->30->...
Node2: 14->22->37->40->...
Node3: 2->5->12->28->...
.
Node M: 12->13->27->32->... M be the #of unique words
Maintain a variable MinD for the current minimu
y*c
发帖数: 904
44

The best way I can think of is to traverse the tree but use a stack or
vector to maintain the ancestors of current node during the traversal. Then
copy the ancestor vector/stack when the node is input node1 or node2. Then
search the LCA.
b****n
发帖数: 464
45
Keep 
track 
of
 two 
pointers 
in the linked&
#8233; list,
 and 
start 
them
 at 
the

beginning 
of 
the 
linked 
list.


At 
each 
iteration 
of 
the 

algorithm,
advance 
the 
first
 pointer 
by
one 
node 
and 
the
 second
 pointer by

two 
nodes.


If 
the 
two ̷... 阅读全帖
b******u
发帖数: 81
46
来自主题: JobHunting版 - 24点程序,有人能现场写出来么?
用 bool IsSameFor24 ( OperationNode node1, OperationNode node2 )
对 + *, 检查左右互换后是否相同。
也检查了 a + ( b + c ) = ( a + c ) + b 的情况。
有五种TREE
(a - b) - (c - d)
a - ( b - ( c -d ) )
a - ( (b - c) -d )
((a - b) - c) -d
(a - (b - c)) -d
p*****2
发帖数: 21240
47
来自主题: JobHunting版 - 上道图论的吧

输入是
一个整数数组,每个代表一个node的颜色
然后是一系列的关系
1 2
2 3
3 4
每一行代表一条边。1 2就是node1 和 node2 有一条边
需要自己定义数据结构
m***k
发帖数: 946
48
来自主题: JobHunting版 - 狗店面,求BLESS
只要能想个办法,用一个字符串唯一地表示这棵树,就可以通过比较两棵树的字符串是
否相等来得到答案。
显然这道题是要判断树的结构是否相等,跟结点上的value无关(如果也要求value,下
面的方法也work)。
假设树的结点无value,随便用一种方式给一棵树的每个结点编号(用visited/un-
visited, DFS/BFS皆可)。然后求出每个结点所有的父节点,用BFS可以实现。假设结
点i的所有父节点为a,b,c (a 然后对树进行分层表示,假设树为:
1
/ \
2 3
/ \ \
4 5 6
则字符串为:
[Node1][Node2_Node3][Node4_Node5_Node6]
然后把其中每个Nodei以Node(i|a,b,c)代替,最后得到的字符串就是这棵树的表示串(
即用这个串可以唯一地还原这颗树的结构)。
最后比较两棵树的表示串是否相等即可。
c*****a
发帖数: 808
49
来自主题: JobHunting版 - LCA复杂度
感觉是n^2吧,假设tree只有left child...一直往左找
而且好像有bug. return Ancestor(root.left, node1, node2);用了2次.....
h****2
发帖数: 46
50
来自主题: JobHunting版 - Google onsite前有两轮电面?
我的题目是:
实现一个familiy tree,每个node 有多个parent 多个children, 这个parent tree里
面可能有环
除了constructor destructor,要实现一个CommonAncestor(node1, node2)函数,判断
两个node 是否是亲戚
感觉不是很难,但是很难准备到他家的题目啊,看当时反应吧,我当时和面试官确认了
好久family tree的定义 太迥了 = =
1 2 下页 末页 (共2页)