4道算法笔试题与1道前端题

Posted by luoway on October 11, 2015

首先,我得补补算法复杂度的概念……

算法复杂度,即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。
时间复杂度:独立于机器的软、硬件系统来分析算法的时间耗费,则设每条语句执行一次所需的时间均是单位时间,一个算法的时间耗费就是该算法中所有语句的频度之和。
渐近时间复杂度评价算法时间性能:主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

至于空间复杂度,一般情况下是不考虑空间复杂度的。

以下算法题我只给出算法的时间复杂度。

题一

输入一个二维横纵向递增数组,以及一个数,求判断这个数是否在数组中的算法,给出算法复杂度

var inp = readline();
var tArr = inp.slice(0, inp.length-2).split("\n");
var arr = [], num = inp.slice(-1);
for(var i=0, len=tArr.length; i<len; i++){
	arr.push(tArr[i].split(" "));
}
arr.join();	//至此连成一个一元数组

if((function () {
        for(var j = 0, len2=arr.length; j < len2; j++){
            if (arr.indexOf(num)){return true;}
        }
        return false;
    })()){
    print("整数"+ num +"存在数组中");
}else{
    print("整数"+ num +"不存在数组中");
}

时间复杂度为O(n);

题二

题目大致上是:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个递增的排序的数组的一个旋转,输出旋转数组的最小元素。例如输入{1,2,3,4,5}的一个旋转为{3,4,5,1,2},该数组的最小值为1。

笔试时我直接写上了遍历数组,通过比较大小得出数组最小值。

现在查询关键词“旋转数组”,正好发现了这原来是一道面试题:旋转数组的最小数字

这道题目应该用“二分查找”的思路来解决。

//二分法查找旋转数组最小值

function minNum(arr){
    if(arr===null||arr.length<0){
        print('非法输入');
    }
    var start = 0, end = arr.length - 1;
    while(arr[start]>=arr[end]){
        if(1 === end-start){
            return arr[end];
        }
        var mid = parseInt((start - end)/2);
        if(arr[mid]===arr[start] && arr[mid]===arr[end]){
            var result = arr[start];
            for(var i = start+1; i < end; i++){
                if(arr[i] < result) result = arr[i];
            }
            return result;
        }
        if(arr[mid]>=arr[start]){//则从start到mid的序列为递增序列,取后一半数组
            start = mid;
        }else if(arr[mid]<=arr[end]){//则从mid到end的序列为递增序列,取前一半数组
            end = mid;
        }
    }
    return arr[start];
}

var arr = readline();
pirnt(minNum(arr));

时间复杂度为O(log(2)N),以2为底n的对数。

题三

输入一个字符串,输出该字符串所有字符的排列组合,如: 输入”abc” 输出”a”,”b”,”c”,”ab”,”ac”,”bc”,”abc”

这是一道经典的字符串组合题,以下是我的原创算法

/*求字符串字符的所有组合
思路:倒序计算组合,例如
abc
ab,ac,bc
a,b,c
可见下层是上层每个结果去除一个字符,经过去重得到的结果。*/

var str, result = [];
str = readline();

//从字符串str中删除第index个字符,index范围:0~str.length-1
function delStr(str, index) {
    if(index === 0){
        return str.slice(1);
    }
    else if(index === str.length-1){
        return str.slice(0, -1);
    }else{
        var str1 = str.slice(0, index),
            str2 = str.slice(index+1);
        return str1+str2;
    }
}

//递归函数
function decrease(str){
    result.push(str);
    for(var i = 0, newStr, len = str.length; i<len; i++){
        newStr = delStr(str, i);
        if(newStr.length>1){
            decrease(newStr);
        }else{
            result.push(newStr);
        }
    }
}

//数组去重
Array.prototype.unique=function(){
    var n = [];
    for(var i = 0; i < this.length; i++)
    {
        //如果当前数组的第i 已经保存进了临时数组,那么跳过,否则把当前项push 到临时数组里面
        if (n.indexOf(this[i]) == -1) n.push(this[i]);
    }
    return n;
};

decrease(str);
print(result.unique());

时间复杂度为O(n!),其中有很多重复计算。 提高效率的算法:

  1. 使用二进制表示各字符是否存在;
  2. 加法计算组合 使用每层长度只变 1 。
    如 abcd

    a b c d
    ab ac ad bc bd cd
    abc abd acd bcd
    abcd

没有重复,比递减更好。 更新:使用二进制更直观。https://www.v2ex.com/t/227151

题四

题目描述大概如下:

硬币组合 条件1:整数,每个硬币面值与前一个是倍数关系 条件2:出币机会根据金额给出最少的硬币数 eg.1,2,4,12 出币机的出币中,全部硬币面值都出现的金额有19、23以及大于23的任意金额。

现要求给出计算任意硬币组合是否有全部硬币面值都出现的最小金额的算法。

这题描述是有问题的,可能是我的理解记忆错误。 在条件1的限制下,任意硬币组合一定有全部硬币面值的最小金额 = 每个面值硬币的和。

查询关键词“硬币组合”,类似的算法题也有很多,有兴趣的话请自行研究。

前端题

CodeA:

!(function(){
	var num = 1;
	var exp ={};
	function add(num){
		return num++;
	}
	exp.getAddNum = function(){
		return add(num);
	};
	window.a = exp;
})();

console.log(a.getAddNum());	//1
console.log(a.getAddNum());	//1

CodeB:

!(function(){
	var num = 1;
	var exp ={};
	function add(){
		return num++;
	}
	exp.getAddNum = function(){
		return add();
	};
	window.a = exp;
})();

console.log(a.getAddNum());	//1
console.log(a.getAddNum());	//2

求以上Code的输出。

在CodeB中出现的闭包与匿名函数,完整符合上一篇文章的例子程序。

CodeB中function add()不含参数,
add()返回的num使用作用域链上的num = 1,并且add()与调用其的getAddNum()方法构成闭包,阻止了num被回收,num++生效。

笔试当时纠结CodeA使用作用域链的知识也成功解决:

CodeA中function add(num)含参数,
getAddNum()以作用域链上的num = 1作为add(num)的参数传入,在函数add(num)中,num是形参,不同于其上级的num,是新的局部变量,每次调用add(num)结束后被回收,即num++无效。