12
返回列表 发新帖
楼主: lyzero00
跳转到指定楼层
上一主题 下一主题
收起左侧

L家phone screen

🔗
readman 2014-7-31 21:40:09 | 只看该作者
全局:

n2...傻了...求不拍...
我其实想问下, 这题有没有方法可以不访问每个元素...
要是没有直接两个for循环不就行了么
回复

使用道具 举报

🔗
 楼主| lyzero00 2014-8-1 04:36:24 | 只看该作者
全局:
readman 发表于 2014-7-16 00:03
楼主用什么语言面的

Java   这应该没什么关系吧
回复

使用道具 举报

🔗
 楼主| lyzero00 2014-8-1 04:36:37 | 只看该作者
全局:
rengokantai 发表于 2014-7-16 00:55
这是实习还是全职的电面?

Full time的
回复

使用道具 举报

🔗
北美农民 2014-8-1 09:38:43 | 只看该作者
全局:
readman 发表于 2014-7-31 08:40
n2...傻了...求不拍...
我其实想问下, 这题有没有方法可以不访问每个元素...
要是没有直接两个for循环 ...

你指的n是什么?

如果n是指叶子节点个数, 难道不是只需要遍历一次所有元素, 边乘边累加就行了么? O(n)
回复

使用道具 举报

🔗
readman 2014-8-1 09:45:24 | 只看该作者
全局:
北美农民 发表于 2014-8-1 09:38
你指的n是什么?

如果n是指叶子节点个数, 难道不是只需要遍历一次所有元素, 边乘边累加就行了么? O ...

{{1,2,3,4,5........ n},{1,2,3,4,5........n},{1,2,3,4,5........n}, ............m}

不需要遍历m个子list中的每一个n么?
回复

使用道具 举报

🔗
ellenren 2014-8-1 09:58:00 | 只看该作者
全局:
这题可不可以用stack 遍历一次解决O(n)
回复

使用道具 举报

🔗
 楼主| lyzero00 2014-8-1 10:26:37 | 只看该作者
全局:
ellenren 发表于 2014-8-1 09:58
这题可不可以用stack 遍历一次解决O(n)

O(N)解决。。。 不用stack
回复

使用道具 举报

🔗
北美农民 2014-8-1 10:30:16 | 只看该作者
全局:
readman 发表于 2014-7-31 20:45
{{1,2,3,4,5........ n},{1,2,3,4,5........n},{1,2,3,4,5........n}, ............m}

不需要遍历m个 ...

。。。。。如果你的n是这个意思, 你这个例子深度是2, 那么如果深度是3, 就是n^3的复杂度了?
回复

使用道具 举报

🔗
readman 2014-8-1 10:31:34 | 只看该作者
全局:
北美农民 发表于 2014-8-1 10:30
。。。。。如果你的n是这个意思, 你这个例子深度是2, 那么如果深度是3, 就是n^3的复杂度了?

表述n有问题..最近脑抽哈...... 闭贴闭贴闭贴闭贴
回复

使用道具 举报

🔗
zhenggao1986 2014-8-10 12:36:02 | 只看该作者
全局:
这个玩意不是1分钟就能写出个O(n)吗?

import java.util.ArrayList;

public class Cardinality {
        public static int getCardinality(String input) {
                int level = 0, sum = 0;
                for (char c : input.toCharArray()) {
                        if (c == '{') ++level;
                        if (c == '}') --level;
                        if (c >= '0' && c <= '9') sum += level * (c - '0');
                }
                return sum;
        }

        public static void main(String[] args) {
                System.out.println(Cardinality.getCardinality("{{1,1},2,{1,1}}"));
                System.out.println(Cardinality.getCardinality("{1,{4,{6}}}"));
        }
}

测试结果
10
27

补充内容 (2014-8-10 12:38):
第一行的ArrayList 不需要用哦,可以删掉,实在是写的太快了,本想用来着,后来发现太简单了根本不需要其他数据结构。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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