【新手报到】两道腾讯的笔试题

第一题也没看明白是啥意思。最大相同子串，子串是什么意思？第二题简单点：
var arr1=[[1,2,5,7],[1,2,5,7,9],[2,3,5,6,7],[2,3,5,7,7]];
arr1.sort(function(a,b){
    var res=b.length-a.length,min=Math.min(a.length,b.length);
    if(min==0){return res}
    for(var i=0;i<min;i++){
        var c=a.slice(0),d=b.slice(0);
        c.sort(function(a,b){return b-a});
        d.sort(function(a,b){return b-a});
        res+=' || '+(d[i]-c[i]);
    };
    return eval(res);

});
var res='';
for(var i=0;i<arr1.length;i++){
    res+='['+arr1[i]+']\n'
}
alert("排序结果：\n"+res)

呃，数组的复制应该移出for循环
arr1.sort(function(a,b){
    var res=b.length-a.length,min=Math.min(a.length,b.length);
    if(min==0){return res}
    var c=a.slice(0),d=b.slice(0);
    c.sort(function(a,b){return b-a});
    d.sort(function(a,b){return b-a});
    for(var i=0;i<min;i++){
        res+=' || '+(d[i]-c[i]);
    };
    return eval(res);

});

#1.无脑型算法,空间换时间，时间上最差应该是O(N*N)吧，纯属打酱油。
  <script type='text/javascript'>

    var findMaxRepeat = function(a){
      var i=0,o={},same=[],pos=0,cur=0,max=[],len=a.length,end=0;
      while(a[i]!=undefined){
        if(end) break;
        if(o[a[i]]){
          for(var j=0,k=o[a[i]].length;j<k;j++){
            pos   = o[a[i]][j];
            cur   = i;
            same  = [];
            while(a[pos] == a[cur] && pos < i){
              if(cur >= len-1) end=1;
              same[same.length] = a[pos];
              pos++;cur++;
            }
            max = max.length > same.length ? max : same;
          }
        }
        //记录每个字符出现的位置，方便下次逐个匹配。
        o[a[i]] = o[a[i]] || [];
        o[a[i]].push(i);

        i++;
      }
       return max.join('');
    }
    alert(findMaxRepeat("aaaaaaaaaa"));//最差就是1000个重复字符。
    alert(findMaxRepeat("csdn的名字就叫csdn的名字你在哪儿啊"));
  </script>#2.取巧,<script type='text/javascript'>
var a = [[1,3,5,7],[1,2,3,5,9],[1,3,5,8]];
a.sort(function(h,t){
  return h.length < t.length || (h.join('')*1) < (t.join('')*1);
})
alert(a);
</script>

看了半天，对SORT方法里面的操作还是没大看懂，能详细解释一下么？

嗯。8楼朋友的第二题可能是误会了你意思。
你看不懂最简单的方法就是：alert()；哪里不知道是什么意思，就alert一下下。就啥都明白了

我做了下第一题，第二题做法大同小异，我就不贴代码了
基本思想贪婪算法function maxRepeat(str) {
var max = 0;
var index = 0;
var len = str.length;
while(index + max + 1 < len) {
var test = str.substr(index, max + 1);
var test_len = test.length;
if(str.slice(index+1).indexOf(test) > -1) {
max = test_len;
var maxRepeatString = test;
} else {
index++;
}

}
return {max: max, maxRepeatString: maxRepeatString};
}

Good job!!!//不用slice
if(str.indexOf(test,index+1) > -1)

兄弟，我发现你有点OOP的思维定势，有时候回归简单才是王道，呵呵。

测试数据“aaaabbbbbbbbccd” 返回结果bbbbbbb，八个b返回了7个b

赞一个！这应该是思路最好的一种办法。组合成一个数字。好思路呀。学习了不过，全面考虑的话还是要排下序var a = [[1, 3, 5, 8,6], [1, 2, 3, 5, 9], [1, 3, 7,5,8]];
a.sort(function (a, b) {
    var c=a.slice(0),d=b.slice(0);
    c.sort(function(a,b){return b-a});
    d.sort(function(a,b){return b-a});
    return parseInt(d.join(''))-parseInt(c.join(''));
});

这样显示结果就对了，这个算法相同子串的最后一个数的下一个不再相同的时候，直接跳出了循环没有加到返回数组里，要不用do while应该也可以解决JScript code
<script type='text/javascript'>
       function maxRepeat(str) {
    var max = 0;
    var index = 0;
    var len = str.length;
    while(index + max + 1 < len) {
        var test = str.substr(index, max + 1);
        var test_len = test.length;
        if(str.slice(index+1).indexOf(test) > -1) {
            max = test_len;
            var maxRepeatString = test+str.substr(index+1,1);
        } else {
            index++;
        }

    }
    return  maxRepeatString;
}
   var a="aaaabbcc";
   alert(maxRepeat(a)); </script>

真是凡事怕认真。
这俩题目现在看来似乎都描述不清，包括第二题，需要明确怎么个叫按内容排，现在有点理解不能，是否有限定每个数组项都是小于10的自然数，我按我那个方法排序，结果就是A2，A3，A1,不过没在ie下测。
#32楼"aaaabbcc"居然返回的是aaaa?不是aa?
题目说的是相同子串，不是连续字符最长的串吧，不过即使这样也没说明是需要'重叠'计算的，还是需要'不重叠'计算的.
我#8楼是按‘不重叠’的找，
比如‘aaaaaaaa’ 8个a,最长的子串我认为是'aaaa'，对半分嘛，一个位置不做两次扫描，不过算法实现还有点问题
而#14楼是'重叠'的找
同样8个a，会返回7个a,因为子串{0-6}和子串{1-7}是相同的。 var findMaxRepeat = function(a,t){
          var i=0,o={},same=[],pos=0,cur=0,max='',len=a.length,end=0,ret=[],c=t||0;
          while(i < len){
            if(end) break;
            if(o[a[i]]){
              for(var j=0,k=o[a[i]].length;j<k;j++){
                pos   = o[a[i]][j];
                cur   = i;
                same  = [];
                while(a[pos] == a[cur]){
                  if(c && (pos > i))
                  {
                    i = cur;
                    break;
                  }
                  if(cur >= len-1) end=1;
                  same[same.length] = a[pos];
                  pos++;cur++;
                }
                if(max.length < same.length){
                    max = same.join('');
                    ret = [max];
                }
                if(max.length == same.length && max != same.join('')){
                    ret[ret.length] = same.join('');
                }
              }
            }
            o[a[i]] = o[a[i]] || [];
            o[a[i]].push(i);
            i++;
          }
          console.log(o)
           return ret;
        }
  console.log(findMaxRepeat("atatatatat"))//不重叠找
  console.log(findMaxRepeat("atatatatat"),1)//重叠找

14楼也是按‘不重叠’的找，不过 if(str.slice(index+max+1).indexOf(test) > -1 疏忽少加一个max。

求解第一题我觉得最快的方法就是数学方法，时间复杂度0(n),空间复杂度0(1)
/**-------------------------
* n1和n2满足如下条件:
*    1. n1    + n2    = sum;
*    2. n1*n1 + n2*n2 = sqSum;
* 用角坐标表示n1、n2后可以将
* 条件合并为: sqrt(sqSum)*sin(z) + sqrt(sqSum)*cos(z) = sum
* 化简为  ：1 + 2*sin(z)*cos(z) = sum*sum/sqSum
* 化简为  ：sin(2*z) = (sum * sum)/sqSum - 1
* 所以弧度为：z = Math.asin( (sum * sum)/sqSum - 1)/2
* 所以n1    : Math.floor(Math.sin(sqrt(sqSum) * sin(z)))
* 所以n2    : Math.floor(Math.cos(sqrt(sqSum) * sin(z)))
*-------------------------*/function test(){
  //模拟抽取
  var a   = [];
  var max = 100000;
  var n1  = Math.floor(Math.random() * (max+1));
  var n2  = Math.floor(Math.random() * (max+1));
  for(var i=1; i<=max; i++){
      if( i != n1 && i != n2 ){
          a.push(i);
      }
  }  //计算两数和与平方和
  var sum   = (max + 1)*(max/2);
  var sqSum = max*(max+1)*(2*max+1)/6; //平方和公式: n(n+1)(2n+1)/6
  var num;
  for(var i=0,len=a.length; i<len; i++){
    num    = a[i];
    sum   -= num;
    sqSum -= num*num;
  }  //计算两数
  var z = Math.asin(sum*sum/sqSum - 1)/2;
  var r = Math.sqrt(sqSum);
  var n3= Math.round(r * Math.sin(z));
  var n4= Math.round(r * Math.cos(z));

  //检验是否通过测试
  return [
    [n1, n2].sort().join(','),
    [n3, n4].sort().join(',')
  ]
}var i, a;
for(i=0; i<1000; i++){
  a = test();
  if(a[0] != a[1]){
    console.error(i + '\tnot passed test: ' + a);
  }
}

我确实是按重叠找的，如果不重叠就+个max，这个确实要明确题目，题意不明确害死人啊

效率不太高。<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title></title>
</head>
<body>
<script type="text/javascript">
+function(){
var arr = [[1,2,3,7],[1,2,3,4,5],[1,2,3,8]];
arr.sort(function(a, b){
return b.length == a.length ? b.join('') - a.join('') : b.length - a.length;
});
document.write(arr.join('<br/>'));
document.write("</br></br>");
}();

+function(){
function makestring(len){
var arr = [];
for(var i = 0; i < len; i++){
arr.push(parseInt(Math.random()*10));
}
return arr.join('');
}
function find(str){
var len = str.length, max = len / 2, i, sub;
while(max > 0){
for(i = 0; i + max * 2 <= len; i++){
sub = str.substr(i, max);
if(str.indexOf(sub, i + max) >= 0){
return {len:max, start:i, text:sub};
}
}
max--;
}
return {len:0};
}
var str = makestring(1000);
var ret = find(str);
var fmt = str.replace(new RegExp("("+ret.text+")", "g"), "<font color='red'>$1</font>").replace(/(\d)/g, "$1 ");
document.write( fmt + '<br/><br/>');
document.write(ret.len + "_" + ret.start + "_" + ret.text + "<br/>");
}();
</script>
</body>
</html>

问题1,如果只需要输出任意最长配对字串.<script language = 'javascript'>
var input = 'asdkfllajsdf oinpqwj fm,zxj cvioqwuj pofamsn,l;df jaopsiduf jaskl;djf aosiduf askdjf kla;sdjf oiasdjf aslkdfj aosipduf jaskdfj aslkd;fj opaisduf ioasdjf ioasdjf klasdfj asipoduf iopasddjf aklsdjf kaskdhfjkasdhdfjkhqw9uier aksdjfhklajsdfkasdjf opaisue rqowkj eroijsdafk lansddkjfj alskdfj iopasduf klasdjf askl;dfj aiospdfu klxzcvn iuoasou foiargnbkjlsckjghv 8912345rusdai fasjdtuf089q34jrfkjasldfj iasdf 89-23 rasedfj';var test = function(){
for(var subLen = input.length - 1;subLen > 0; subLen-- ){
var max = input.length - subLen;
var array = new Array();
for(var offset = 0; offset < max; offset ++ ){
var str = input.substring(offset,offset + subLen);
for(var i = 0;i<array.length;i++){
if(array[i] === str){
return str;
}
}
array.push(str);
}
}
}alert(test(input));</script>

笔误:
for(var offset = 0; offset <= max; offset ++ ){
}
更正下.

第二题var aa = [[1,3,8,5],[1,2,3,5,9],[1,3,5,7]];
function ch1(x,y) {
    if(x.length>y.length) return 1;
    if(x.length<y.length) return -1;
    if(x.length == y.length) {
        if(Math.max.apply(null,x) > Math.max.apply(y)) return 1;
        if(Math.max.apply(null,x) < Math.max.apply(y)) return -1;
        return 0;
    }
}
function compare(x,y) {
    if(x<y) return -1;
    if(x>y) return 1;
    return 0;
}
aa =aa.sort(ch1);
for(var i=0;i<aa.length;i++) {
    aa[i] = aa[i].sort(compare);
}console.log(aa);方法需要优化，但也算实现了

调试易

【新手报到】两道腾讯的笔试题

解决方案 »