腾讯前端笔试题

Question

今天在网上看到一条腾讯的前端笔试题，大家看看有啥思路：
“几个字符串组成的数组["abcaaabbc","eaeaebe","cbacccc",...]等等，个数不限制，那么要求对这个数组排序，排序规则就是最多出现字符的次数升序排序，遇到相等的情况就对比第二多字符出现字数，依次类推。
那么上述的三个例子排序出来是：“cbacccc”（c出现5次）、“abcaaabbc”、“eaeaebe”（虽然出现最高次字符都是4次，但是第二个第二高的b出现了3次，比第三个第二高的a出现的2次高）。写一个函数实现上述功能”
 

Answer 1

发现自己真的好闲。闲到蛋疼。。抛砖引玉吧
Array.prototype.inArray=function (value){for (var i=0;i<this.length;i++){if (this[i] == value){return true;}}return false};
function arrSort(){
    this.arr=["abcaaabbc","eaeaebe","cbacccce","ddda","eeeea","fffffaa",'abcdefghijklmnopqrstuvwxyzzzz'];
    this.getArrayByCharCount=function(){
        var countArr=new Array();
        for(var i=0;i<this.arr.length;i++){
            countArr[i]=[];
            var chrArr=new Array();
            var chr=this.arr[i].split('');
            for(var j=0;j<chr.length;j++){
                if(!chrArr.inArray(chr[j])){
                    chrArr.push(chr[j]);
                    countArr[i].push(this.arr[i].split(chr[j]).length-1);//统计当前字母出现次数
                }
            };
            countArr[i].index=i;//标识原数组序列
        };
        return countArr;
    };
    this.showSortResult=function(){
        var arr=this.getArrayByCharCount();
        arr.sort(function(a,b){
            a.sort(function(a,b){return b-a});
            b.sort(function(a,b){return b-a});
            var str='';
            var o=a.length>b.length?b:a;
            for(var i=0;i<o.length;i++){
                str+=str.length==0?b[i]-a[i]:' || '+(b[i]-a[i]);
            };
            return eval(str);
        });
        var res='';
        for(var i=0;i<arr.length;i++){
            res+=res.length==0?'['+this.arr[arr[i].index]+']':',['+this.arr[arr[i].index]+']';
        }
        alert("最终排序为："+res);
    }
};
var as=new arrSort();
as.showSortResult();

Answer 2

搞了个随机数组测试效率，也改了下效果展示方式，200个数组，每个数组字符长度15。
<script type="text/javascript">
function getArrByRandom(){
    var seed = new Array( 'a','b','c','d','e','f','g','h','i','j','k','m','n','p','Q','r','s','t','u','v','w','x','y','z');
    seedlength = seed.length;
    var a = '';
    for (var i=0;i<15;i++) {
        j = Math.floor(Math.random()*seedlength);
        a += seed[j];
    }
    return a;
}var randomArray=new Array();
for(var i=0;i<200;i++){
    randomArray.push(getArrByRandom());
};Array.prototype.inArray=function (value){for (var i=0;i<this.length;i++){if (this[i] == value){return true;}}return false};
function arrSort(){
    this.arr=randomArray;
    this.getArrayByCharCount=function(){
        var countArr=new Array();
        for(var i=0;i<this.arr.length;i++){
            countArr[i]=[];
            var chrArr=new Array();
            var chr=this.arr[i].split('');
            for(var j=0;j<chr.length;j++){
                if(!chrArr.inArray(chr[j])){
                    chrArr.push(chr[j]);
                    countArr[i].push(this.arr[i].split(chr[j]).length-1);//统计当前字母出现次数
                }
            };
            countArr[i].index=i;//标识原数组序列
        };
        return countArr;
    };
    this.showSortResult=function(){
        var arr=this.getArrayByCharCount();
        arr.sort(function(a,b){
            a.sort(function(a,b){return b-a});
            b.sort(function(a,b){return b-a});
            var str='';
            var o=a.length>b.length?b:a;
            for(var i=0;i<o.length;i++){
                str+=str.length==0?b[i]-a[i]:' || '+(b[i]-a[i]);
            };
            return eval(str);
        });
        var res='';
        for(var i=0;i<arr.length;i++){
            res+='['+this.arr[arr[i].index]+']:"'+arr[i]+'"\n'
        }
        document.getElementById('arrsort').value="最终排序为：\n"+res;
    }
};
window.onload=function(){
    var as=new arrSort();
    as.showSortResult();
}</script>
<textarea  rows="30" cols="60" id="arrsort"></textarea>

Answer 3

砖来了。。<script type="text/javascript">
var string = ["zzzz","ccewcwefg","cbacccccc", "zxcv........"];
var strLength = [];
for(var i in string)
{
var maxLength = 0;
var maxChar = '';
for(var j in string[i])
{
var len = string[i].split(string[i][j]).length-1;
if(string[i][j] != maxChar && len >= maxLength)
{
maxChar = string[i][j];
maxLength = len;
}
}
strLength[i] = [maxLength, i];
}
var len1 = strLength.length - 1;
for(var i=0;i<len1; ++i)
{
var len2 = strLength.length;
for(var j=i+1; j<len2; ++j)
{
if(strLength[i][0] < strLength[j][0])
{
var temp = strLength[i];
strLength[i] = strLength[j];
strLength[j] = temp;
}
}
}
var str = '';
for(var i in strLength)
{
str += string[strLength[i][1]]+'\n';
}
alert(str);
</script>

Answer 4

板砖来了：     var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        var revert = [];
        function sortby(a,b){
            var revertA = trans(a);
            var revertB = trans(b);
            return revertA < revertB;
            
            function trans(arr){
                var revert = [];
                for(var i in arr){
                    var q = arr.split(eval("/[^"+arr[i]+"]/g")).join('').length;
                    revert.push(q);
                }
                revert.sort();
                revert.reverse();
                console.debug(revert);
                return revert;
            }
        }
        array.sort(sortby);
        console.debug(array,9999);

Answer 5

搞了好久，对比了两种算法：
1、一种是类似于2楼的，把原数组转化为可得到正确结果的数字数组B，对数组B排序后得到顺序，映射给原数组。
2、写一个sortby回调函数
测了下，第一种算法的性能较好。在转化数字数组B的时候，要注意控制，遍历过个数的字符就不要再遍历了；下面是主要代码：
1、        var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        var revert = [];        var start = new Date().getTime();//start time 
        function charSort(array, revert){
            for(var i in array){
                var obj = {};
                for(var j in array[i]){
                    obj[array[i][j]] = '';
                }
                var k=[];
                for(var m in obj){
                    k.push(m);
                }
                var subrevert = [];
                for(var j in k){
                    var q = array[i].match(eval("/"+k[j]+"/g")).length;
                    subrevert.push(q);
                }
                subrevert.sort(function(m,n){
                    return m<n;
                });
                subrevert.index = i;
                revert.push(subrevert);
            }
            revert.sort();
            revert.reverse();
            var arraymirror = [];
            for(var i in revert){
                arraymirror[revert[i].index] = array[i];
            }
            array = arraymirror
            return array;
        }      
       
        charSort(array, revert);
        var end = new Date().getTime();
        document.write((end-start) + '<br />');
        console.debug(array);
2、        var array = ['abcaaabbc','aeaebbaebe','cbacccc','zzzyhhhhhhhiiiiii'];
        function sortby(a,b){
            var revertA = trans(a,[]);
            var revertB = trans(b,[]);
            return revertA < revertB;    
        }
        function trans(arr, revert){
            var obj = {};
            for(var i in arr){
                obj[arr[i]] = '';
            }
            var k=[];
            for(var i in obj){
                k.push(i);
            }
            for(var i=0; i<k.length; i++){
                var q = arr.match(eval("/"+k[i]+"/g")).length;
                revert.push(q);
            }
            revert.sort(function(m,n){
                return m<n;
            });
            return revert;
        }
        var start = new Date().getTime();
        array.sort(sortby);
        var end = new Date().getTime();
        document.write((end-start) + '<br />');
        console.debug(array,9999);
折腾过程中，想起大学那会，数据结构老师纠结各种查找算法，现在看来是多么有用。怎样用好循环，是很值得研究的事情。

Answer 6

var arr = ["abcaaabbc","eaeaebe","cbacccc"];
//var arr = ["bcd","bbc","aad","ccab"];arr.sort(function(a,b)
{
var m = repeat(a), n=repeat(b), min = Math.min(m.length, n.length);
function repeat(str)
{
var r = str.split('').sort().join('').match(/(.)\1*/g);
return r.sort(function(a,b){return b.length-a.length})
}
for (var i=0; i<min; i++)
{
var x = m[i].length, y = n[i].length;
if (x !== y) return y - x;
}
return 0; // 类似 ["bbc","aad","ccab"] 规则不明无法编码
});console.log(arr);性能上或许比5楼大大的好一点

Answer 7

内嵌函数正则改改，不重复的字符就不要了： function repeat(str)
{
var r = str.split('').sort().join('').match(/(.)\1+/g);
return r ? r.sort(function(a,b){return b.length-a.length}) : []
}
外面判断一下min==0的情况。

Answer 8

今早看了下，我的问题很大呀！！！
之前我都不敢用console.debug来输出，firebug直接崩溃。看来有很多地方值得改进哟！

Answer 9

事实证明，不开启firebug等调试器的时候，我的第一种方案速度和8楼的是在一个量级上的。
不知道开启firebug的时候为什么那么慢。

Answer 10

Vidor 对正则的用法很是有点熟然于心的意思
看另一个贴子求解字符串长度的用法也很是巧妙，这里对字符归类的应用也很是巧妙呀赞一个。对正则一向是一知半解的，简单点的倒好说。复杂型的我得搞老长时间。。

Answer 11

8楼代码瞬间把我折服了！获得了一点点体会：
1、明明有length属性可以直接判断；我却新建了数组来放这个length，这个应该是开销比较大的
2、除了sortby回调本身要参与循环之外，在回调函数里面，只有一个主要循环；而我有好几个循环呢，重复的遍历，开销也很大。这应该是算法上的累赘。
3、尽量减少循环的次数，无论是Math.min(m.length, n.length);还是r ? r.sort(function(a,b){return b.length-a.length}) : []都是为了减少循环次数；我记得我在当时是有想到，可是么有做到。
4、str.split('').sort().join('').match(/(.)\1*/g);这样获得关键序列的方式很优雅，相比之下，我的方法很拙劣。嗯，能想到的就这些了。以后做这样的算法题，一开始的思考比后来的千辛万苦优化更重要。

Answer 12

是因为用for in循环了数组的缘故。IE不支持。

Answer 13

不要这么说，互相学习，其实我很菜的。重复字符统计，基本上两种方法（我的水平想不出第三种），键值映射或正则。
键值映射应该优于正则，str.split('').sort().join('').match(/(.)\1+/g) 内部实现循环不会少。我测试了一下：
function byRepeat(a,b)
{
var m = repeat(a), n=repeat(b), min = Math.min(m.length, n.length), max = Math.max(m.length, n.length);
function repeat(str)
{
var a=[], o={}, len=str.length;
for (var i=0; i<len; i++) // 键-值映射
{
var s=str.charAt(i); // 比 substr(i,1) 快点
// 第二次出现再push()
!(s in o) ? o[s]=undefined : (o[s]==undefined) ? (o[s]=a.length, a.push(2)) : a[o[s]]++;
}
return a.sort(function(a,b){b-a});
}
for (var i=0; i<min; i++)
{
if (m[i] !== n[i]) return n[i] - m[i];
}
if (min!=max) return m.length==max ? -1 : 1;
return 0;
}var arr = ["abcaaabbc","eaeaebe","cbacccc"];
arr.sort(byRepeat);
console.log(arr);Firefox、Chrome有明显提升，IE9反而略逊于正则。总体表现Chrome最差，IE9最好。