V2EX › clatisus 的所有回复 › 第 1 页 / 共 2 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

1 2

❮

❯

2019 年 6 月 19 日

回复了 Newbing 创建的主题 › macOS › macOS mojave 10.14.1 WI-FI crash 并且卡住整个 OS 的 menubar

每天第一次打开电脑都会出问题只能每次 kill airportd 有人解决了吗

2019 年 5 月 17 日

回复了 letianqiu 创建的主题 › 程序员 › 今天的一道面试题没能写出来，求思路。

好像还有个更快的做法：

你对行进行容斥，枚举有几行满足行是同色的，然后就只需要对每一列选一个颜色使得列不同色。这里的列是独立的，计算一列的答案之后快速幂 O(log n) 就可以。

所以复杂度是 O(mlog n)，这里 m=3，因为容斥只需要知道有多少行同色，乘上组合数就行，不用枚举 2^m。

2019 年 5 月 17 日

回复了 baozijun 创建的主题 › 问与答 › 请问学习游泳需不需要报班呢

建议报班如果自学动作不标准后面很难纠正过来

2019 年 5 月 17 日

回复了 letianqiu 创建的主题 › 程序员 › 今天的一道面试题没能写出来，求思路。

@HuHui 阿里笔试界面…一言难尽的丑而且还有摄像头验证保证你没有办法低头打草稿

2019 年 5 月 17 日

回复了 letianqiu 创建的主题 › 程序员 › 今天的一道面试题没能写出来，求思路。

dp[i][j][k] (i,j,k\in {0,1,2,3})。每一行记录四种状态：全红、全蓝、全绿、已经至少有两种颜色。

转移的时候枚举这一列的颜色，有 24 种（去掉全色）。

这道题 n 不大，直接转移的话复杂度是 O(4^3*24*n)。矩阵乘法优化的话就是 O((4^3)^3*log n)。

2019 年 5 月 15 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@ihac 加个好友吗

2019 年 5 月 6 日

回复了 ccb1025 创建的主题 › 问与答 › aw(苹果表)有什么用？请问一下使用场合？

aw4
1. 游泳
2. 及时查看微信消息
3. 刷地铁卡

aw 的充电速度还是蛮快的

2019 年 4 月 30 日

回复了 jianfa2003 创建的主题 › 程序员 › 是什么原因让你踏入程序猿的道路！

高二学了信息学竞赛

2019 年 4 月 30 日

回复了 zhouweiluan 创建的主题 › 随想 › 发现最近无意中看时间，总是会看到 12:34 分，无论中午和晚上都会经常触发这件事，这个情况已经持续了很久了。

+1 高中开始就发现每晚 20:15 左右看一次时间

2019 年 4 月 30 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@hyserendipity 不太确定能不能透露面试题但都是算法题因为打过 acm 所以觉得难度一般建议多刷刷 leetcode ～

2019 年 4 月 30 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@wezzard 感谢建议最后选择了 Airbnb

2019 年 4 月 27 日

回复了 hakono 创建的主题 › 问与答 › 请教一道某公司的（简单？）算法题？

@clatisus 补充：这样 n 不管多大都可以，如果是区间 [l, r] 的话，就 r 的答案减去 l - 1 的答案。

2019 年 4 月 27 日

回复了 hakono 创建的主题 › 问与答 › 请教一道某公司的（简单？）算法题？

如果剔除的数字个数很少的话，可以枚举它们的子集，然后用容斥原理。

假设剔除 m 个数字，复杂度就 O(2^m)。

2019 年 4 月 26 日

回复了 banxi1988 创建的主题 › LeetCode › [笨方法学算法] 992-K 个不同整数的子数组 [算法求优化]

@clatisus 补充：时间复杂度 O(n\log n)，空间复杂度 O(n)。

2019 年 4 月 26 日

回复了 banxi1988 创建的主题 › LeetCode › [笨方法学算法] 992-K 个不同整数的子数组 [算法求优化]

枚举答案区间的左端点 l，考虑有多少个 r 可以满足要求。

我们只需要把下标在 [l, n] 中所有数字的第一次出现位置加上 1，记一个前缀和，这里用数据结构 segment tree （线段树）就可以。

然后找到前缀和为 k 和 k + 1 的位置，这两个位置中间的位置就是合法的 r。

考虑现在 l 加 1，那么 l 这个位置的贡献就要删掉，记录 next[l] 表示 l 这个位置数字的下一次出现，把它加 1。

2019 年 4 月 26 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@mio4 没搜到诶？

2019 年 4 月 26 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@vigoss airbnb 有什么坑吗？

2019 年 4 月 26 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@mio4 6

2019 年 4 月 26 日

回复了 clatisus 创建的主题 › 职场话题 › 实习比较字节跳动 vs Hulu vs Airbnb

@wedoub 感谢回复～确实企业文化很重要国内公司文化都有点吓人

1 2

❮

❯