JavaScript常用基础算法( 二 ) _JavaScript

二、字符串

回文字符串

//判断回文字符串function palindrome(str) { var reg = /[W_]/g; var str0 = str.toLowerCase().replace(reg, ""); var str1 = str0.split("").reverse().join(""); return str0 === str1;}

翻转字符串

function reverseString(str) { return str.split("").reverse().join("");}

字符串中出现最多次数的字符

数组去重

//数组去重function uniqueArray(arr) { var temp = []; for (var i = 0; i < arr.length; i++) { if (temp.indexOf(arr[i]) == -1) { temp.push(arr[i]); } } return temp; //or return Array.from(new Set(arr));}四、查找

二分查找

//二分查找function binary_search(arr, l, r, v) { if (l > r) { return -1; } var m = parseInt((l + r) / 2); if (arr[m] == v) { return m; } else if (arr[m] < v) { return binary_search(arr, m+1, r, v); } else { return binary_search(arr, l, m-1, v); }}

将二分查找运用到之前的插入排序中，形成二分插入排序，据说可以提高效率。但我测试的时候也许是数据量太少，并没有发现太明显的差距。。大家可以自己试验一下~（譬如在函数调用开始和结束使用console.time('插入排序耗时')和console.timeEnd('插入排序耗时')）

五、树的搜索/遍历

深度优先搜索

//深搜非递归实现function dfs(node) { var nodeList = []; if (node) { var stack = []; stack.push(node); while(stack.length != 0) { var item = stack.pop(); nodeList.push(item); var children = item.children; for (var i = children.length-1; i >= 0; i--) { stack.push(children[i]); } } } return nodeList;}//深搜递归实现function dfs(node, nodeList) { if (node) { nodeList.push(node); var children = node.children; for (var i = 0; i < children.length; i++) { dfs(children[i], nodeList); } } return nodeList;}

广度优先搜索

//广搜非递归实现function bfs(node) { var nodeList = []; if (node != null) { var queue = []; queue.unshift(node); while (queue.length != 0) { var item = queue.shift(); nodeList.push(item); var children = item.children; for (var i = 0; i < children.length; i++) queue.push(children[i]); } } return nodeList;}//广搜递归实现var i=0; //自增标识符function bfs(node, nodeList) { if (node) { nodeList.push(node); if (nodeList.length > 1) { bfs(node.nextElementSibling, nodeList); //搜索当前元素的下一个兄弟元素 } node = nodeList[i++]; bfs(node.firstElementChild, nodeList); //该层元素节点遍历完了，去找下一层的节点遍历 } return nodeList;}

高阶函数衍生算法
1.filter去重
filter也是一个常用的操作，它用于把Array的某些元素过滤掉，然后返回剩下的元素。也可以这么理解，filter的回调函数把Array的每个元素都处理一遍，处理结果返回false则过滤结果去除该元素，true则留下来
用filter()这个高阶函数，关键在于正确实现一个“筛选”函数。
其实这个筛选函数有多个参数，filter(function (element, index, self)，演示一个使用filter去重，像这样：
var r, arr = ['Apple', 'strawberry', 'banana', 'pear', 'apple', 'orange', 'orange', 'strawberry']; r = arr.filter(function (element, index, self) { return self.indexOf(element) === index; //拿到元素，判断他在数组里第一次出现的位置，是不是和当前位置一样，一样的话返回true，不一样说明重复了，返回false 。});2.sort排序算法
排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序，排序的核心是比较两个元素的大小。如果是数字，我们可以直接比较，但如果是字符串或者两个对象呢？直接比较数学上的大小是没有意义的，因此，比较的过程必须通过函数抽象出来。通常规定，对于两个元素x和y，如果认为x < y，则返回-1，如果认为x == y，则返回0，如果认为x > y，则返回1，这样，排序算法就不用关心具体的比较过程，而是根据比较结果直接排序。
值得注意的例子
// 看上去正常的结果:['google', 'Apple', 'Microsoft'].sort(); // ['Apple', 'Google', 'Microsoft'];// apple排在了最后:['Google', 'apple', 'Microsoft'].sort(); // ['Google', 'Microsoft", 'apple']// 无法理解的结果:[10, 20, 1, 2].sort(); // [1, 10, 2, 20]解释原因