你的位置:首页 > Java教程

[Java教程]一个精妙的解决方案并非对于所有语言都是最优解


 今天无意间看到一篇文章(http://www.vaikan.com/google-interviewing-story/),看到里面有道面试题的算法挺有意思的。问题是这样的:
假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?
比如,如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true,所有在string2里的字母string1也都有。如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ

答案是false,因为第二个字符串里的Z字母不在第一个字符串里。
     面试官Guy给出了一种有意思的解法: 我给每个字母分配一个素数,从2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧?然后 —— 轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。
     这种算法我觉得是最快的算法之一,时间复杂度最多也就O(m+n)。于是,我尝试着用Js来实现这种算法。然而,坑爹的事情发生了。也许在其他种语言下,这种算法是最优算法之一,但在Js里,它绝对不是。因为它那坑爹的运算精度。浮点运算尤为明显。网上有很多解决Js浮点运算精度的方法。但其实,哪怕是整数运算,Js也存在精度问题。因为Js是弱类型语言,他的数字都是用浮点数表示的,并规定使用IEEE 754 标准的双精度浮点数表示。所以Js的number类型与java语言的double一样,都是64位浮点型(ieee 754)。double类型尾数最多可达到53位,所以理论上讲,js的精确整数最大为:Math.pow(2,53)-1 = 9007199254740991。说js的精确整数谓9007199254740992,也没错,但是,这只是一个巧合。

所以,第一个整数失真在:
alert(9007199254740992 == 9007199254740993);//true

也就是说,当我们的整数相乘结果大于2的53次方的时候,结果就会不精确了。
我根据那个算法,最初的Js代码如下:
  
var result = 1;var numObject = {  'A': 2,  'B': 3,  'C': 5,  'D': 7,  'E': 11,  'F': 13,  'G': 17,  'H': 19,  'I': 23,  'J': 29,  'K': 31,  'L': 37,  'M': 41,  'N': 43,  'O': 47,  'P': 53,  'Q': 59,  'R': 61,  'S': 67,  'T': 71,  'U': 73,  'V': 79,  'W': 83,  'X': 89,  'Y': 97,  'Z': 101};var init = function() {   compareString('ABCDEFGHLMNOPQRS', 'DBGSRQPOZ');};var compareString = function(str1, str2) {  var i,     j,     length;  //长的字符串每个字母相乘  for (i = 0, j = 1, length = str1.length; i < length; i++) {    result *= numObject[str1.substr(i, 1)];  }  //结果除以短的字符串的每个字母  for (i = 0, length = str2.length; i < length; i++) {     if (result % numObject[str2.substr(i, 1)] !== 0) {        console.log("str2"中的第" + (i + 1) + "个字母不存在str1中");        break;     } else {        result /= numObject[str2.substr(i, 1)];     }       }};init();

得到的结果自然不会和想象中的那么美好,因为第一个字符串“ABCDEFGHLMNOPQRS”所有字母相乘后的结果已经大于2的53次方了。
所以想出另外一种解决方法,当相乘的结果大于2的53的时候,再设置一个新的变量来存储接下来的乘积。之后再分别用每个乘积除以字符串2中的每个字母,
当每个乘积除以这个字母的余数都不为0时,说明这个字母不存在于字符串1中.
于是,对 compareString方法做了更改。同时,把result设置成一个对象
var resultObject = {  'result1': 1};


var compareString = function(str1, str2) {  var i,    j,    flag,    length;  //长的字符串每个字母相乘  for (i = 0, j = 1, length = str1.length; i < length; i++) {    //相乘结果大于2的53次方时,设置新的属性值result+j来统计结果    if (resultObject['result' + j] * numObject[str1.substr(i, 1)] > Math.pow(2, 53)) {      j++;      resultObject['result' + j] = 1;    }    resultObject['result' + j] *= numObject[str1.substr(i, 1)];  }  //结果除以短的字符串的每个字母  for (i = 0, length = str2.length; i < length; i++) {    flag = 0;    for (var z in resultObject) {      if (resultObject[z] % numObject[str2.substr(i, 1)] === 0) {        flag = 0;        break;      } else {        flag = 1;      }    }    if (flag == 1) {      console.log("str2中的第" + (i + 1) + "个字母不存在str1中");      break;    } else if (flag == 0 && i == length - 1) {      console.log("str2中的字母str1均存在");    }  }};

这样理论上是没问题了,但有个限制条件,str1的长度必须大于等于str2。

题目是查出所有小字符串里的字母在大字符串里都有,显然当用户如果先输入小字符串,再输入大字符串的话,结果就不尽如人意了。

所以,我们再对compareString方法做下优化,长字符串每个字母相乘前面部分做个判断,str1长度小于str2时,两个字符串互换值

var i,  j,  flag,  length,  strLong = 1, //默认str1为长字符串  strShort = 2, //默认str2为短字符串  strArray = [str1, str2];//当str1长度小于str2时if (str1.length < str2.length) {  strLong = 2;  strShort = 1;  str1 = strArray[1];  str2 = strArray[0];}

同时,输出结果那里更改如下:

if (flag == 1) {  console.log("str" + strShort + "中的第" + (i + 1) + "个字母不存在str" + strLong + "中");  break;} else if (flag == 0 && i == length - 1) {  console.log("str" + strShort + "中的字母str" + strLong + "均存在");}

这样,无论用户先输入长字符串或短字符串,就都能正常进行判断了。

所以,其实在JS中,这种算法并不是最优算法。

在JS中,还是把长字符串的每个字母存在到一个对象中作为它的属性,再轮询短的字符串,如果出现对象中没有的属性,则说明出现了长字符串中所没有的字母。

代码如下:

var numObject = {};var init = function() {  compareString('ABCDEFGHLMNOPQRS', 'DBGSRQPOZ');};var compareString = function(str1, str2) {  var i,    flag,    length,    strLong = 1, //默认str1为长字符串    strShort = 2, //默认str2为短字符串    strArray = [str1, str2];  //当str1长度小于str2时  if (str1.length < str2.length) {    strLong = 2;    strShort = 1;    str1 = strArray[1];    str2 = strArray[0];  }  //将字符串str1中的每个字母添加到numObject中作为它的属性  for (i = 0, length = str1.length; i < length; i++) {    //如果同一个字母出现多次,只对第一次添加属性    if (!numObject[str1.substr(i, 1)]) {      numObject[str1.substr(i, 1)] = 1;    }  }  for (i = 0, length = str2.length; i < length; i++) {    //如果str2中同一个字母出现多次,只对第一次进行比较    if (numObject[str2.substr(i, 1)] === 0) {      continue;    }    //如果numObject中不存在这个属性,说明这个字母str1中没有    if (!numObject[str2.substr(i, 1)]) {      console.log("str" + strShort + "中的第" + (i + 1) + "个字母不存在str" + strLong + "中");      return;    } else {      //已经出现过一次了,赋值为0      numObject[str2.substr(i, 1)] = 0;    }  }  console.log("str" + strShort + "中的字母str" + strLong + "均存在");};init();

的确,在实践中,还是最后这种解决方法更加通用。无论哪一种语言都是。因为他更加通俗易懂,也不需要跟一些大数乘除打交道。

只是最近看到这个文章觉得用素数来解决这个问题确实很有趣,也是我之前从未想过的。虽然这个方法对于JS并非最优方案,但实践过程中仍然颇有收获。