Javascript面试问题整理

1. 给定一个字符串，判断其是否超长，其中的非英语系字符长度作为英语系字符的两倍来看待，如汉语的7个字，在这里要作为14字符长度来对待。

	function isLongerThan(str, limit){
		var length = str.length,
		    asciiCount;

		if(length > limit) return true;

		// 计算字符串中ASCii码的个数
		asciiCount = (str.match(/[\u0001-\u007f]+/g) || []).join("").length;

		length = (length - asciiCount) * 2 + asciiCount;

		return length > limit ? true : false;
	}

	isLongerThan("1234567890", 10);
	isLongerThan("12345678901", 10);
	isLongerThan("123456789测", 10);
	isLongerThan("12345678测", 10);

2. 给定n个1*3的长方形，用于填充n*3的区域，计算有多少种方法。

思路：一个3×3的区域可以用3个长方形横放或竖放填充，问题可以抽象为：在一个长度为n的标尺上，摆放任意个3×3的方块，有多少种摆法。 实现如下：

(function() {	
	this.numOfArranges = function (n){
		var numOfBlocks = parseInt(n/3), // 计算n个位置可以放置3×3盒子的个数
		    count = 1,
		    i;
		for(i=1;i<=numOfBlocks;i++){
			count += countOf(n, i);  // 依次将1到numOfBlocks个盒子放置在长度为n的标尺上，看有多少种
		}
		
		return count;
	}

	// 一定长度的标尺上放置特定个数的3×3盒子，有多少种组合
	// length：标尺的长度，numOfBlocks：盒子的个数
	function countOf(length, numOfBlocks){
		var left = length - numOfBlocks * 3;
		if(numOfBlocks == 1) {
			return (left >=0) ? (left + 1) : 0; // 只有一个盒子时，可放置位置的个数可直接得到。
		}
		else if(numOfBlocks > 1){ // 有多于一个盒子时，先放置一个在某位置，看剩余的位置和盒子有多少种组合
			var count = 0;
			for(var i=0;i<=left;i++){
				count += countOf(length-3-i, numOfBlocks-1);
			}
			return count;
		}
	}

})();

上面的方法存在的问题是：代码中的递归存在大量重复计算， 导致随着n的增大，计算所需的时间成级数式增加。在n=50时，需要花费几秒时间，而n=100时，几分钟都没有出结果。 因此做了优化，将每次递归调用的结果进行存储，当下次出现相同参数的调用时，直接返回，不再进行递归计算。实现如下，经测试，当n=1000时，需要20秒时间。

(function() {
	// 使用cache优化，去除重复计算
	this.numOfArranges_cache = function (n){
		var numOfBlocks = parseInt(n/3), // 计算n个位置可以放置3×3盒子的个数
		    count = 1,
		    i;
		for(i=1;i<=numOfBlocks;i++){
			count += countOf(n, i);  // 依次将1到numOfBlocks个盒子放置在长度为n的标尺上，看有多少种
		}
		
		return count;
	}

	// 一定长度的标尺上放置特定个数的3×3盒子，有多少种组合
	// length：标尺的长度，numOfBlocks：盒子的个数
	function countOf(length, numOfBlocks){
		var left = length - numOfBlocks * 3,
		    cache;
		if(numOfBlocks == 1) {
			return (left >=0) ? (left + 1) : 0; // 只有一个盒子时，可放置位置的个数可直接得到。
		}
		else if(numOfBlocks > 1){ // 有多于一个盒子时，先放置一个在某位置，看剩余的位置和盒子有多少种组合
			if((cache = countOf[length + '-' + numOfBlocks]) > 0)
			{
				return cache;
			}

			var count = 0;
			for(var i=0;i<=left;i++){
				count += countOf(length-3-i, numOfBlocks-1);
			}
			countOf[length + '-' + numOfBlocks] = count;
			return count;
		}
	}

})();