今日面试题：子序列数目；及数组墙分析

雨点打透心脏的1/2处 2022-08-22 11:26 57阅读 0赞

## 来源:http://mp.weixin.qq.com/mp/appmsg/show?\_\_biz=MjM5ODIzNDQ3Mw==&appmsgid=10000333&itemidx=1&sign=00f7c4cf3edb620b963fc5e7fe7a75e8\#wechat\_redirect ##

2013-11-19  王亚洲  待字闺中

![0_tp_webp_wxfrom_5][]

今日面试题：子序列数目

给定两个字符串s和t(len(s)>len(t))，t可能是s的一个子序列。求所有s的子序列集合中，有多少个子序列等于t。例如s="abbbc"，t="abc"，结果为3，即在s的所有子序列集合中，有3个子序列为t。

==========================================

数组墙分析

原题

给定一个正整数数组如\[2,5,1,2,3,4,7,7,6\]，数组中每个数代表一个墙的高度，如图，

![0][]

问：往墙里倒水，墙之间的水坑总共可以装多少水呢？

分析

题目中的例子，可以装水的示意图如下：

![0 1][]

木桶短板理论：一只木桶盛水的多少，并不取决于桶壁上最高的那块木块，而恰恰取决于桶壁上最短的那块。此问题同样也是这样的道理，不同的是，此处的短板是相对而言的，畜水的多少由两个邻近的最长的板所决定，且这两个长板不相邻。 如果这是一个递增的数组或是递减的数组或是先增后减的数据，显然是不能装水的,因为最长的板总是在一块的。如要装水则要求当从左往右遍历数组时，紧邻的右边的数比左边数小，且不会一直小下去；同样当从右往左遍历数据时，要求紧邻的左边的数据比右边的数小且不会一直小下去。 假如我们从左至右遍历数组，每个下标畜水的量最多为(目前为止的最大值-当前下标的值)，可问题是此值是不确定，因为右边的长板在哪我们不知道。

但是，如果我们指定两个指针分别从数组两端向中间移动，当两个指针相遇时过程结束，在移动的过程中，比较两个指针处值的大小，值小的一方指针向前移动一位(对左边的指针来说往右是前，对右边的指针来说往左是前)，如要移动后的值比移动前的值小，则说明此处可以畜水；如果移动后的值比移动前的值大，则此处不能畜水。如此递归下去，时间复杂度为O(n) ，分析完毕。示例代码如下：

![0 2][]

进一步，把问题稍微改一下，如果水坑不是连续的，不要求求出总的畜水值，而是畜水最多的那个值，要怎么做呢？分析同上，两个指针分别从两端向中间遍历，相遇时过程结束；对于大小为n的数组，最多可以有 n/2 个不连续的水坑，当左右指针在移动时，每  当遇到一个新的最大值大值则意味着一个水坑的分界点。当找出所有的水坑后，再对所有的结果做一次排序(如果仅要最大值是不需要排序的)，就可以了。示例代码如下：

![0 3][]

【分析完毕】

[0_tp_webp_wxfrom_5]: /images/20220722/9c964e28b1b540c28729c3e3ca9d38b1.png
[0]: /images/20220722/62467380103c4794b7ea7ae2141640ed.png
[0 1]: /images/20220722/df59129404424196a8abeea4457495a9.png
[0 2]: /images/20220722/1b098902bccd46edb5fe838f0d895cbd.png
[0 3]: /images/20220722/0ad834ca933c40968a1178756e7b03c4.png