首页   注册   登录
 Lettersong 最近的时间轴更新

Lettersong

V2EX 第 92018 号会员,加入于 2015-01-15 20:39:02 +08:00
Lettersong 最近回复了
@metrue 居然在 V2 看到我家
2015-10-20 00:45:38 +08:00
回复了 9hills 创建的主题 职场话题 额,出了个算法题结果人家直接扭头就走了
自然语言描述:
struct node {

Elementtype data;

node *LChild;

node *RChild;

int level;

}

节点结构如上, level 用来标识节点所处的层数,

算法核心:层序遍历,需要用到队列

过程:

节点初始 level 都为 0

根节点入队

int maxLevel = 0;

while (队列不为空) {

node *tmp = 队列出队;

if (tmp->LChild) {

tmp->LChild 入队

tmp->LChild->level = tmp->level + 1;

}

if (tmp->RChild) {

tmp->RChild 入队

tmp->RChild->level = tmp->level + 1;

}

// 这一句保证最后 maxLevel 为最底层节点的层数

if (tmp->level > maxLevel) maxLevel = tmp->level;

}

上面的层序遍历时间复杂度为 O(n),做完之后每个节点都有自己所属的层数

vector<int> flag(maxLevel, 0);

再遍历一遍整棵树,每访问一个节点, flag.at(node->level) += 1;

时间复杂度仍然是 O(n)

最后扫一遍 flag 数组,找出最大的值就是宽度。

return 0;
2015-10-05 19:38:06 +08:00
回复了 kevinzhow 创建的主题 分享创造 给女朋友的 iOS 开发教程 iOS With Girlfriend
sketch 已买,看过的视频里,这是第一个从设计的角度出发的,期待
2015-05-27 22:00:24 +08:00
回复了 sparga 创建的主题 iPhone 爱疯信息 app 被乱码搞垮了
从备忘录发一条短信给那个人,帮他解掉,再让他发一条信息给你
2015-05-17 01:01:09 +08:00
回复了 tanteng 创建的主题 程序员 电脑升降椅多少价位的比较好?
第一眼看过去以为标题是『电椅多少价位的比较好』,心里想你们城里人真会玩……
2015-05-09 20:09:20 +08:00
回复了 wangzhenhuip 创建的主题 iDev 求过来人:给 ios 开发新人指条路~~
@a412739861 BNG的iOS编程第四版还是有不少地方对不上的……特别是xib相关的
2015-05-03 00:53:02 +08:00
回复了 wangzhenhuip 创建的主题 iDev 求过来人:给 ios 开发新人指条路~~
@wangzhenhuip 那就一起加油吧0.0
2015-05-02 13:11:55 +08:00
回复了 wangzhenhuip 创建的主题 iDev 求过来人:给 ios 开发新人指条路~~
@wangzhenhuip 0.0 课件里面的作业提出的需求都实现了吗,正在跟13-14的CS193P,想找个老司机指点一下
2015-04-30 20:17:36 +08:00
回复了 wangzhenhuip 创建的主题 iDev 求过来人:给 ios 开发新人指条路~~
@wangzhenhuip 看的CS193P是13-14年秋季的还是14年之后的IOS8+swift版的?
2015-03-10 20:06:09 +08:00
回复了 banxi1988 创建的主题 程序员 欢迎挑战:帮我解密女神发的一句话
@tomatoz
关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   960 人在线   最高记录 5043   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.3 · 10ms · UTC 23:06 · PVG 07:06 · LAX 16:06 · JFK 19:06
♥ Do have faith in what you're doing.