📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2232| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

[二分/排序/搜索] 问一道google的oa 完全没头绪

全局:

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

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

x
曾经看到的 想了好久。原帖子找不到了 我复述下input是一个array。比如10 5 9 4 8 3,
问,这个array能分成最少多少个nonoverlapping decreasing substring。
比如这个例子,就是两个:10 9 8 和 5 4 3
再比如 input是10 9 8 6 20 7 5,也是两个: 10 9 8 6和20 7 5
我直觉是用dp,但是完全没头绪

评分

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

查看全部评分


上一篇:从基础开始刷题,循序渐进一天2-3题,欢迎加入~
下一篇:437. Path Sum III
推荐
magicsets 2018-11-30 05:48:44 | 只看该作者
全局:
这题实际上等价于求数列中的最长不下降子序列 —— 后者是比较基础的DP问题,有O(n^2)或者O(n log(n))的方法

然后要证明等价性,我们有如下
--
(对偶定理):给定任意一个array,其最小的non-overlapping decreasing子序列数量 等于 最大的non-decreasing子序列长度。


可以使用Dilworth's theorem( https://en.wikipedia.org/wiki/Dilworth%27s_theorem )来证明上面的对偶定理。下面是简略的证明过程:

首先将原数列中每个值附带上其数组下标成为一个二元组,记扩充后的数列为S。
例如原数列 [10 5 9 4 8 3] 扩充后变为:[(0, 10) (1, 5) (2, 9) (3, 4) (4, 8), (5, 3)]

然后关于S定义偏序关系 “<”:对于S中任意两个二元组a和b,a < b 当且仅当 a[0] < b[0]且a[1] > b[1]
使用上面的例子,我们有 (0, 10) < (1, 5)、(1, 5) < (3, 4) 、等等,但是(1, 5)和(2, 9)之间不存在偏序关系。

下面是关键部分:
(1) 我们称S的任意一个子序列 s0, s1, ..., sk 构成一个链(chain),当且仅当 s0 < s1 < ... < sk
(2) 我们称S的任意一个子序列构成一个反链(anti-chain),当且仅当该子序列中任意两个元素之间都不存在“<”偏序关系

例如 (0, 10) (2, 9) (4, 8) 就构成了一个链,而(1, 5) (4, 8)就构成了一个反链 —— 易知S中一个子序列构成一个反链 当且仅当 该子序列是一个不下降子序列。

现在引入Dilworth's theorem一个陈述:对于任意一个偏序集合,其任意反链中的最大元素数量 等于 该集合可以分割成的最少的链的数量 —— 由此得证前述的对偶定理
( Dilworth定理的证明参考: http://math.mit.edu/~cb_lee/18.318/lecture8.pdf )

评分

参与人数 4大米 +10 收起 理由
laurel_123 + 3 给你点个赞!
达失败 + 3 理论大佬66666666
stultus + 3 正解
EbyccoCheng + 1 赞一个

查看全部评分

回复

使用道具 举报

推荐
magicsets 2018-11-30 11:06:27 | 只看该作者
全局:
stultus 发表于 2018-11-30 10:43
膜一个。能问下这种牵涉到挺多数学概念的算法书有什么比较好的书推荐么……感觉看这类书会受苦但是不看的 ...

我也不知道哪些书比较好.. 不过平时可以多积累积累,比如说这个帖子的问题之所以想到这个证明,是因为之前有帖子里有人问Meeting Room II的贪心解法为什么是对的( https://www.1point3acres.com/bbs ... tml?_dsign=dafb76ab ),我稍微查了下了解到了关于partially ordered set / chain decomposition / Dilworth's theorem的一些东西。然后这个帖子里的问题很明显与chain decomposition有关,就联系起来了。
回复

使用道具 举报

推荐
wenya98 2018-11-30 01:30:02 | 只看该作者
全局:
我觉得这个题用backtracking + recursion + buffer 做还是挺简单的吧
不过复杂度肯定高一点
回复

使用道具 举报

🔗
 楼主| EbyccoCheng 2018-11-29 12:46:50 | 只看该作者
全局:
笔误 不是substring, 是subsequence
回复

使用道具 举报

🔗
stultus 2018-11-29 14:12:09 | 只看该作者
全局:
emmm,你这个字串其他的限制么?比如说我看到这道题第一想法是一遍遍找最长下降子序列,但是这样的话第一个样例的结果是10 9 8 3/5 4 3了,虽然说结果还是两个但是和你的样例结果就不一样了……而且时间复杂度最低也要O(n^2logn)感觉有更好的。

补充内容 (2018-11-29 14:13):
例子说错了……打字的时候没带脑子……是10 5 4 3/9 8
回复

使用道具 举报

全局:
我感觉用greedy可以解决,
时间O(nlogm),m是结果最终有多少个subseqence, n是数组长,
空间是O(m)
用一个multiset记录当前每个子队列的最小值,
来一个新的数看看能不能在multiset找到minimum bigger(或者说是upper_bound)的项,如果有,将找到的项删除,无论找不找的到都将新的数加入multiset中,result就是最终multiset的size。

补充内容 (2018-11-29 07:45):
等等,好像有错, nonoverlapping 怎么理解?
回复

使用道具 举报

🔗
 楼主| EbyccoCheng 2018-11-30 01:13:01 | 只看该作者
全局:
stultus 发表于 2018-11-29 14:12
emmm,你这个字串其他的限制么?比如说我看到这道题第一想法是一遍遍找最长下降子序列,但是这样的话第一个 ...

只要子串个数相同就行
最长下降的话不对的,
比如第二个例子
从10开始的最长下降是10 9 8 7 5
还剩6 和 20
这样就需要3个子串

补充内容 (2018-11-30 01:26):
额 不是子串个数相同 是子串个数对就行
回复

使用道具 举报

🔗
 楼主| EbyccoCheng 2018-11-30 01:15:39 | 只看该作者
全局:
linyu203 发表于 2018-11-29 20:27
我感觉用greedy可以解决,
时间O(nlogm),m是结果最终有多少个subseqence, n是数组长,
空间是O(m)

就是input array里面的每个数字只能出现在一个子串里,然后所有子串的长度合起来就是input的长度。
比如说input是5 3 4 2,那么5 4 和 3 2就是nonoverlapping的子串
回复

使用道具 举报

🔗
stultus 2018-11-30 10:43:48 | 只看该作者
全局:
magicsets 发表于 2018-11-30 05:48
这题实际上等价于求数列中的最长不下降子序列 —— 后者是比较基础的DP问题,有O(n^2)或者O(n log(n))的方 ...

膜一个。能问下这种牵涉到挺多数学概念的算法书有什么比较好的书推荐么……感觉看这类书会受苦但是不看的话遇到这类问题又分析不出来=<=
回复

使用道具 举报

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

本版积分规则

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