买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1009|回复: 7
收起左侧

[树/链表/图] 关于cc150 4.9的复杂度

[复制链接] |试试Instant~ |关注本帖
我的人缘0
窗外一棵树 发表于 2015-8-17 09:23:45 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
搜了一下 以前有人问过这个问题,不过依然没看懂原因啊。。。http://www.1point3acres.com/bbs/thread-106857-1-1.html


原题是:
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

我把只考虑 从root出发,可以终结在任意点的情况写出来了
https://gist.github.com/leonw007/90dd6e31353ce071e82a

我没理解错的话,这个基本和答案是差不多的吧,等于跑了一遍DFS,时间复杂度是O(N);

那按照题目的意思,再考虑可以从任意点出发,不仅限于root的情况,不是应该对每一个node,运行一遍上述算法吗?那一共有n个node,不该是O(n^2)咩?

为什么答案说是O(n*logn)啊









上一篇:CC150 高频重点题目吐血总结
下一篇:我的LeetCode解题(258) - Java
我的人缘0
ericliu03 发表于 2015-8-17 10:57:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主,我的理解是 从任一点开始并不是把只从根开始的算法在每个点跑一遍
只从根开始的时候,遍历到每个点的时看一下从当前点到根的和是不是等于sum,等于就print
从任一点开始的时候,还是遍历到每个点的时候看一下,但不是看到根的和等不等于sum,而是一个长度为log(n)的循环,依次比较:此点自己的和是否等于sum,此点加此点父是否等于sum,此点加此点父加此点父的父是否等于sum。。。直到root,循环结束,移至下一个点。所以,所有以此点为终点的,和为sum的路径全部被记录下来。
不知道怎么形容说的啰嗦点,总的来说:“不是问‘这个点是否是一个和为sum路径的起点‘,而问‘这个点是否是一个和为sum的路径的终点’’”【1】。
不知道楼主明白没?

【1】cc150第五版,238页

评分

参与人数 1大米 +10 收起 理由
窗外一棵树 + 10 很有用的信息!

查看全部评分

回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
 楼主| 窗外一棵树 发表于 2015-8-17 11:07:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ericliu03 发表于 2015-8-17 10:57
楼主,我的理解是 从任一点开始并不是把只从根开始的算法在每个点跑一遍
只从根开始的时候,遍历到每个点 ...

谢谢啊 终于搞懂书上那段话是什么意思了
回复 支持 反对

使用道具 举报

我的人缘0
ericliu03 发表于 2015-8-17 21:54:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
窗外一棵树 发表于 2015-8-17 11:07
谢谢啊 终于搞懂书上那段话是什么意思了

明白就好~
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 窗外一棵树 发表于 2015-8-17 23:18:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

我按照您说的去实现了一下,好像只要稍作改动就好了。还有两个小问题,求指教

1. 这么实现的前提是否是  写TreeNode这个数据结构的时候必须设定parent?
也就是说 对于一个node,除了value,leftNode,rightNode, 还必须有parent这个变量。

2. 默认的打印顺序就由原来的 从头到尾 变成 反方向了对不?


祝早日拿到理想offer~~~
回复 支持 反对

使用道具 举报

我的人缘0
ericliu03 发表于 2015-8-18 01:23:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
三客优

其实说是parent,并不需要真正的去TreeNode 里面找parent变量,书不在手边,就拿你给的代码来说,public static void findSumPath(TreeNode root, int sum, int[] path, int level)函数中,path这个变量记录的就是从根到目前level节点的路径,也就是说 path[level]就是当前节点,而path[level-1]就是此节点的父节点,对不?
明白了这个,打印的问题也就迎刃而解啦

评分

参与人数 1大米 +10 收起 理由
窗外一棵树 + 10 赞耐心~

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 窗外一棵树 发表于 2015-8-18 01:43:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ericliu03 发表于 2015-8-18 01:23
三客优

其实说是parent,并不需要真正的去TreeNode 里面找parent变量,书不在手边,就拿你给的 ...

原来我之前理解错你的意思啦。。。

我把每个node从自己向root又递归了一遍。。

本来是
  1.                 findSumPath(root.leftNode, sum, path, level+1);
  2.                 findSumPath(root.rightNode, sum, path, level+1);
复制代码
被我改成
  1. findSumPath(root.parent, sum, path, level+1);
复制代码


这是我用parent link修改的代码https://gist.github.com/leonw007/85e469bef6fcaaac9482
所以print结果是个反的。。

太2了哈哈。。  原来只要加个循环就好了  太感谢了~~

回复 支持 反对

使用道具 举报

我的人缘0
ericliu03 发表于 2015-8-18 22:31:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
窗外一棵树 发表于 2015-8-18 01:43
原来我之前理解错你的意思啦。。。

我把每个node从自己向root又递归了一遍。。

哈哈 思想到是一样~明白了就好~
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /3 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-22 05:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表