请各位读者添加一下作者的微信公众号，以后有新的文章，将在微信公众号直接推送给各位，非常感谢。
0. 前言
今天一直在整理关于面试的内容，希望能够让我的兄弟姐妹们在未来能够有所借鉴。
在整理的时候，发现有一位歪果友人写的文章非常6，所以趁机翻译一下，分享给大家。
译文的原文如下：
1.正文
在今天的文章中会是一个非常重要的主题,即:在JavaScript中算法和数据结构。这是编程的一个重要话题。我们不应该有偏见——Javascript很适合这一目的。也许有些事情将在解说语言有点困难,但是别人会简化,例如基本堆栈实现(FIFO)。
1.1 Factorial(阶乘)
在开始一个典型的例子——阶乘和递归。
示例——计算阶乘JavaScript:
function factorial(n) {
if (n == 0)
return 1;
else
return (n * factorial(n-1));
}
alert(factorial(5));
1.2 Leap year(闰年)
下一个算法是检查是否某一年是一个闰年。
// is leap year - JavaScript
function checkLeapYear(year) {
if ( ((year % 4 == 0)
&&
(year % 100 != 0)) || (year % 400 == 0) ) {
alert(year + ' is leap');
return true;
} else {
alert(year + ' is NOT leap');
return false;
}
}
alert(checkLeapYear(2012));
alert(checkLeapYear(2013));
1.3 Min-Max algorithm(Min-Max算法)
所以确定最低和最高的给定值。
示例——在JavaScript min-max算法的实现:
var tab = new Array(16, 9, 86, 48, 59, 2, 78, 240, 18);
// default
var min = tab[0];
var max = tab[0];
for (var i = 0; i < tab.length; i++) {
if (min > tab[i]) {
min = tab[i];
}
if (max < tab[i]) {
max = tab[i];
}
}
alert("Min = " + min + ", Max = " + max);
这是一个简单,但有效实施基于数组中元素之间的比较。
1.4 Random string(随机字符串)
这个算法是一个简单的发生器的随机字符串。
var _list = "abcdefghijklmnopqrstuvwxyz9876543210";
function randomStringGenerator(how_long) {
var tmp = '', i = 0;
var list_len = _list.length;
for (i = 0; i < how_long; i++) {
tmp += _list.charAt(Math.floor(Math.random() * list_len));
}
return tmp;
}
alert(randomStringGenerator(8));
实现基于输入的字符列表(它可以是任何调整)。
1.5 Binary search(二分查找)
基于“分而治之”,二叉搜索一个简单但最优方法找到价值甚至在大输入列表。
在JavaScript的例子——二进制搜索:
inputList = new Array();
inputList[0] = 'E';
inputList[1] = 'I';
inputList[2] = 'O';
inputList[3] = 'P';
inputList[4] = 'Q';
inputList[5] = 'R';
inputList[6] = 'T';
inputList[7] = 'U';
inputList[8] = 'W';
inputList[9] = 'Y';
function binarySearch(inputList, key) {
var left = 0;
var right = inputList.length - 1;
while (left <= right) {
var mid = parseInt((left + right) / 2);
if (inputList[mid] == key)
return mid;
else if (inputList[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return 'Not found';
}
alert(binarySearch(inputList, 'T'));
alert(binarySearch(inputList, 'Z')); // Not found
参见:计算复杂性。
