今日面试题:相伴一生

给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。

例1:10101010 结果就是其本身。

例2:1101000 结果是110100

请大家展开自己的思路。

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

构造最大数分析

原题

给定只包含正数的数组,给出一个方法,将数组中的数拼接起来,得到的数,是最大的。 例如: [4, 94, 9, 14, 1] 拼接之后,所得最大数为:9944141

分析

初看这个题目,肯定是要排序的。按照从左到右的第一个位置的数字,从大到小进行排序。如题目中的例子,结果是:

94 9 4 14 1

直接拼接为9494141显然不是最大的。那很自然的想法,就是考虑从左到右第二位的数字。考虑9和94的第二个数字,9没有第二个数字如何处理?这里有一个小技巧,就是用9补位。为什么用9呢?994>949,因为4<9,所以,拼接的方式 9 + “” + 94. 为了方便我们排序,所以用9进行了补位。

再看一个例子:56,54,5。第一次排序结果为:

56 54 5

第二次呢?

56 55 54

此时要注意,第二55,是由5补位而来的。

再看一个复杂一点的例子,包含了:1位数,2位数,3位数:96 9 95 556 56 55 5 554 54 3 2 1

第一次排序:

96 9 95 556 56 55 5 554 54 3 2 1
96 9 95 556 56 55 5 554 54 3 2 1

第二次排序:

9 96 95 56 556 55 5 554 54 3 2 1
99 96 95 56 556 55 55 554 54 3 2 1

上面一行,是原始数字,下面一行,经过补位了。

第三次排序

9 96 95 56 556 55 5 554 54 3 2 1
99 96 95 565 556 555 555 554 545 3 2 1

第四次排序

9 96 95 56 556 55 5 554 54 3 2 1
99 96 95 565 556 555 555 554 545 3 2 1

处理最后三个个位数即可。则最终的结果是: 996955655655554554321

上面的算法,排序处理自左向右第一位,然后处理第二位,一次类推,如果某一组内,即第一个数字相同的一组,长度不同时,采用第一位进行补位。

一个巧妙的方法

我们在上面的方法中,相当于,比较两个数字的时候,把两个数字拆开,逐位进行比较。那我们接下来,就是将这两个数字,作为一个整体,进行比较。然后一次排序,就得到了结果。给定例子:5,54,56

比较5和54,实际上就是比较545和554哪个大

比较5和56,实际上就是比较556和565哪个大

比较54和56,实际上就是比较5456和5654哪个大

那我们对快排程序做一下变化,当两个数字a和b进行比较时,比较的是ab和ba两个数字的大小即可。只是比较发生了变化,剩下的和快排都是一样的。

相比较而言,后面这种方法,更简单易懂一些,而且,看上去要美很多,但是确不容易那么直接的想到。我们在平时积累的过程中,就要尝试多多的方法,即使看起来不那么美的方法,这些思路的开拓,会帮助我们举一反三,帮助我们在遇到新的题目的时候,游刃有余。

【分析完毕】

本文来自微信:待字闺中,2013-07-20发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。