Javascript面试有关问题整理

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;}}})();

查看更多 下一篇