一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 2381|回复: 34
收起左侧

[树/链表/图] 在leetcode面经上发现一道有意思的题目,大家可以一起讨论一下

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
yyoung 发表于 2019-6-14 16:22:49 | 显示全部楼层 |阅读模式
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   92% (114)
 
 
7% (9)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
内容是这样的:
Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the repeating number >= 3)
input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]
return: [1, 1]
Time complexity should be better than O(n^2)
Mod edit: To slow down the posting of O(n^2) and O(n) "correct" solutions, here is another testcase:
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should return [3,1,3,2,3]
我想了很久只能想出暴力的dfs尝试每一个可能,但是根据出题人这道题可以优于O(n^2)不知道是说出来坑人的还是真有更优的解法

评分

参与人数 3大米 +18 收起 理由
Kyrazzzzz + 1 给你点个赞!
14417335 + 15
reliveinfire + 2 <font style="vertical-align: inh

查看全部评分


上一篇:用go刷题的lib求推荐
下一篇:发一道碰到的数组题
我的人缘0
lokilokiloki 发表于 2019-6-15 02:47:46 | 显示全部楼层
本楼: 👍   100% (6)
 
 
0% (0)   👎
全局: 👍   91% (129)
 
 
8% (12)    👎
说 O(n) 的都是胡 JB 扯, 这题只能 DFS, On2 都不行
回复

使用道具 举报

我的人缘0
magicsets 发表于 2019-6-15 12:40:39 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (769)
 
 
1% (8)    👎
这个问题可以用两阶段的动态规划做吧,时间是O(n^3),不知道可不可以进一步优化了

--
首先我们定义一个数组A可以被“全消除”,记作 IsFullyCrushable(A),当且仅当存在一个消除过程,使得A中的所有元素最后都被消除掉。

然后,给定输入数组S,定义可以全消除的区间集合:I = { [i, j] | IsFullyCrushable( S[i..j] ) }

也就是说I是S中可以被全消除的所有子串的区间集合,易知I中的区间数量不超过 n^2

举个例子,对于 S = 322233322,可以被全消除的子串有:
(1) 区间 [1, 3]: .222.....
(2) 区间 [4, 6]: ....333..
(3) 区间 [0, 5]: 322233...
(4) 区间 [0, 6]: 3222333..
(5) 区间 [1, 6]: .222333..
(6) 区间 [1, 7]: .2223332.
(7) 区间 [1, 8]: .22233322
(8) 区间 [2, 8]: ..2233322
(9) 区间 [3, 8]: ...233322

那么对应的 I 就是上面9个区间的集合。

然后我们有如下关键性质:

定理(a):给定数组S,通过一系列消除过程可以消除的最大长度K,等于I中互不相交的区间子集的最大总长度

还是上面的例子,那么最大的互不相交区间集合总长度是K = 8(这个例子里最优解只有一个元素[1, 8],但是把输入弄复杂一点的话最优解就会是多个区间组成的集合了)

然后原题要计算的是最短剩余长度,那么返回 len(S) - K 即可。


所以接下来需要进一步回答三个问题:
--
1. 定理(a)如何证明?

定理(a)本身可以通过考察消除过程来证明,这里略过..

--
2. 给定I,如何求I中互不相交区间子集的最大总长度?

本质上是一个weighted interval scheduling problem,可以先排序,再DP,参考这里:https://courses.cs.washington.ed ... ides/06dp-sched.pdf

时间复杂度由排序时间决定,因为I中元素数量不超过n^2,所以就是 O(n^2 * log(n))

--
3. 如何计算得到集合 I ?

为了简洁,记 C(i, j) = IsFullyCrushable( S[i..j] ),那么对于所有区间[i, j],计算C(i, j)并将值为"true"的区间加入I即可。

现在我们要写出C(i, j)的状态转移方程,那么就是C(i, j)值为true,当且仅当下面任一条件被满足:
(1) S[i..j]全部为同一字符且长度大于等于3
(2) 存在i < k < j,使得 C(i, k)为true 且 C(k + 1, j)为true
(3) 存在i < m < n < j,使得C(m, n)为true 且 S[i..m-1]并上S[n+1,j]全部为同一字符且长度大于等于3

这个状态转移方程的时间复杂度主要在(2)需要枚举所有k,综合起来就是 O(n^3)

注意到对于(3)式我们不需要枚举所有m,n,只要同时从左从右贪最多的同一字符然后检查即可,其正确性可以用数学归纳法证明


补充内容 (2019-6-16 03:09):
谢谢zjck1995指出来计算I时没有考虑到 5 1 1 1 5 1 1 1 5 这种情况,处理方法可以引入一个新函数H(i, j)表示消除后可以得到的最多"i位置上的字符"个数,然后式子(3)改为 H(i, j) >= 3,具体可以看下面帖子的讨论

补充内容 (2019-6-16 14:34):
写了一份参考代码:http://cpp.sh/3jcqk

评分

参与人数 3大米 +13 收起 理由
Chagrin + 2 给你点个赞!
Kyrazzzzz + 1 很有用的信息!
14417335 + 10

查看全部评分

回复

使用道具 举报

我的人缘0
zjck1995 发表于 2019-6-14 22:35:51 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (46)
 
 
0% (0)    👎

评分

参与人数 2大米 +2 收起 理由
EdsgerW + 1 给你点个赞!
14417335 + 1

查看全部评分

回复

使用道具 举报

我的人缘0
tongliuu 发表于 2019-6-16 05:03:37 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎
所有说o(n)的请用你的算法测试一下aaabbbabbba这个testcase
回复

使用道具 举报

我的人缘0
moluren 发表于 2019-6-15 11:16:43 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   90% (378)
 
 
9% (39)    👎
lokilokiloki 发表于 2019-6-15 02:47
说 O(n) 的都是胡 JB 扯, 这题只能 DFS, On2 都不行

同意你的说法,除了DFS真的想不到更好的办法了。
期待高人的解法。
回复

使用道具 举报

我的人缘0
reliveinfire 发表于 2019-6-14 18:00:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
我连 O(N^2) 都想不出来...
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
瞄了一眼,感觉用一个sliding window size of 3,线性时间可以解。dequeue或者手工模拟都行吧
回复

使用道具 举报

我的人缘0
gantheory 发表于 2019-6-14 22:13:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
把这个array,建成double linked list,可以在O(n)做完
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
Frango 发表于 2019/06/14 21:29:08
瞄了一眼,感觉用一个sliding window size of 3,线性时间可以解。dequeue或者手工模拟都行吧

大于三的连接也要消除啊
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
zxcvbn3018 发表于 2019/06/14 22:53:17


大于三的连接也要消除啊

早上急着考试没表达清楚。
如果dq空或者当前字母和dp末字母相同,当前字母push到dq末尾.
否则,如果dq大小大于等于3,消除dq内所有字母,poll all,新字母入dq.如果dq大小小于3,保留所有dq字母poll all,新字母入dq
回复

使用道具 举报

我的人缘0
tianlong1989 发表于 2019-6-15 00:54:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (92)
 
 
0% (0)    👎
Frango 发表于 2019-6-14 09:43
早上急着考试没表达清楚。
如果dq空或者当前字母和dp末字母相同,当前字母push到dq末尾.
否则,如果dq大 ...

2223332 最后一个2你准备怎么办
回复

使用道具 举报

我的人缘0
silenceleaf 发表于 2019-6-15 01:05:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (21)
 
 
0% (0)    👎
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] 怎么判断消掉的顺序?比如这个case是先消除index为2的三个2,还是index为5的三个1?顺序会影响输出的结果
回复

使用道具 举报

我的人缘0
WarriorZ 发表于 2019-6-15 01:12:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (610)
 
 
6% (40)    👎
Use stack could solve this problem in linear time. The result should store in the stack finally, we may need another stack to store the current continue elements in the stack.
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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

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

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-21 14:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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