WEB前端必须掌握的一些算法题
Q1 判斷一個(gè)單詞是否是回文？
回文是指把相同的詞匯或句子，在下文中調(diào)換位置或顛倒過(guò)來(lái)，產(chǎn)生首尾回環(huán)的情趣，叫做回文，也叫回環(huán)。比如 mamam redivider .
很多人拿到這樣的題目非常容易想到用for 將字符串顛倒字母順序然后匹配就行了。其實(shí)重要的考察的就是對(duì)于reverse的實(shí)現(xiàn)。其實(shí)我們可以利用現(xiàn)成的函數(shù)，將字符串轉(zhuǎn)換成數(shù)組，這個(gè)思路很重要，我們可以擁有更多的自由度去進(jìn)行字符串的一些操作。
function checkPalindrom(str) { return str == str.split('').reverse().join(''); }Q2 去掉一組整型數(shù)組重復(fù)的值
比如輸入: [1,13,24,11,11,14,1,2] 輸出: [1,13,24,11,14,2] 需要去掉重復(fù)的11 和 1 這兩個(gè)元素。這道問(wèn)題出現(xiàn)在諸多的前端面試題中，主要考察個(gè)人對(duì)Object的使用，利用key來(lái)進(jìn)行篩選。
/** * unique an array **/ let unique = function(arr) { let hashTable = {}; let data = []; for(let i=0,l=arr.length;i<l;i++) { if(!hashTable[arr[i]]) { hashTable[arr[i]] = true; data.push(arr[i]); } } return data } module.exports = unique;Q3 統(tǒng)計(jì)一個(gè)字符串出現(xiàn)最多的字母
給出一段英文連續(xù)的英文字符竄，找出重復(fù)出現(xiàn)次數(shù)最多的字母
輸入 ： afjghdfraaaasdenas 輸出 ： a前面出現(xiàn)過(guò)去重的算法，這里需要是統(tǒng)計(jì)重復(fù)次數(shù)。
function findMaxDuplicateChar(str) { if(str.length == 1) { return str; } let charObj = {}; for(let i=0;i<str.length;i++) { if(!charObj[str.charAt(i)]) { charObj[str.charAt(i)] = 1; }else{ charObj[str.charAt(i)] += 1; } } let maxChar = '', maxValue = 1; for(var k in charObj) { if(charObj[k] >= maxValue) { maxChar = k; maxValue = charObj[k]; } } return maxChar; } module.exports = findMaxDuplicateChar;Q4 排序算法
如果抽到算法題目的話，應(yīng)該大多都是比較開(kāi)放的題目，不限定算法的實(shí)現(xiàn)，但是一定要求掌握其中的幾種，所以冒泡排序，這種較為基礎(chǔ)并且便于理解記憶的算法一定需要熟記于心。冒泡排序算法就是依次比較大小，小的的大的進(jìn)行位置上的交換。
function bubbleSort(arr) { for(let i = 0,l=arr.length;i<l-1;i++) { for(let j = i+1;j<l;j++) { if(arr[i]>arr[j]) { let tem = arr[i]; arr[i] = arr[j]; arr[j] = tem; } } } return arr; } module.exports = bubbleSort;除了冒泡排序外，其實(shí)還有很多諸如?插入排序,快速排序，希爾排序等。每一種排序算法都有各自的特點(diǎn)。全部掌握也不需要，但是心底一定要熟悉幾種算法。 比如快速排序，其效率很高，而其基本原理如圖(來(lái)自wiki)：
算法參考某個(gè)元素值，將小于它的值，放到左數(shù)組中，大于它的值的元素就放到右數(shù)組中，然后遞歸進(jìn)行上一次左右數(shù)組的操作，返回合并的數(shù)組就是已經(jīng)排好順序的數(shù)組了。
function quickSort(arr) {if(arr.length<=1) { return arr; } let leftArr = []; let rightArr = []; let q = arr[0]; for(let i = 1,l=arr.length; i<l; i++) { if(arr[i]>q) { rightArr.push(arr[i]); }else{ leftArr.push(arr[i]); } } return [].concat(quickSort(leftArr),[q],quickSort(rightArr)); } module.exports = quickSort;安利大家一個(gè)學(xué)習(xí)的地址，通過(guò)動(dòng)畫(huà)演示算法的實(shí)現(xiàn)。
HTML5 Canvas Demo: Sorting Algorithms
Q5 不借助臨時(shí)變量，進(jìn)行兩個(gè)整數(shù)的交換
輸入 a = 2, b = 4 輸出 a = 4, b =2這種問(wèn)題非常巧妙，需要大家跳出慣有的思維，利用 a , b進(jìn)行置換。
主要是利用 + - 去進(jìn)行運(yùn)算，類(lèi)似 a = a + ( b - a) 實(shí)際上等同于最后 的 a = b;
function swap(a , b) { b = b - a;a = a + b;b = a - b;return [a,b]; } module.exports = swap;Q6 使用canvas 繪制一個(gè)有限度的斐波那契數(shù)列的曲線？
數(shù)列長(zhǎng)度限定在9.
斐波那契數(shù)列，又稱(chēng)黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列主要考察遞歸的調(diào)用。我們一般都知道定義
fibo[i] = fibo[i-1]+fibo[i-2];生成斐波那契數(shù)組的方法
function getFibonacci(n) { var fibarr = []; var i = 0; while(i<n) { if(i<=1) { fibarr.push(i); }else{ fibarr.push(fibarr[i-1] + fibarr[i-2]) } i++; } return fibarr; }剩余的工作就是利用canvas?arc方法進(jìn)行曲線繪制了
DEMO
Q7 找出下列正數(shù)組的最大差值比如:
輸入 [10,5,11,7,8,9]輸出 6這是通過(guò)一道題目去測(cè)試對(duì)于基本的數(shù)組的最大值的查找，很明顯我們知道，最大差值肯定是一個(gè)數(shù)組中最大值與最小值的差。
function getMaxProfit(arr) {var minPrice = arr[0]; var maxProfit = 0; for (var i = 0; i < arr.length; i++) { var currentPrice = arr[i]; minPrice = Math.min(minPrice, currentPrice); var potentialProfit = currentPrice - minPrice; maxProfit = Math.max(maxProfit, potentialProfit); } return maxProfit; }Q8 隨機(jī)生成指定長(zhǎng)度的字符串
實(shí)現(xiàn)一個(gè)算法，隨機(jī)生成指制定長(zhǎng)度的字符竄。
比如給定 長(zhǎng)度 8 輸出 4ldkfg9j function randomString(n) { let str = 'abcdefghijklmnopqrstuvwxyz9876543210'; let tmp = '', i = 0, l = str.length; for (i = 0; i < n; i++) { tmp += str.charAt(Math.floor(Math.random() * l)); } return tmp; } module.exports = randomString;Q9 實(shí)現(xiàn)類(lèi)似getElementsByClassName 的功能
自己實(shí)現(xiàn)一個(gè)函數(shù)，查找某個(gè)DOM節(jié)點(diǎn)下面的包含某個(gè)class的所有DOM節(jié)點(diǎn)？不允許使用原生提供的 getElementsByClassName querySelectorAll 等原生提供DOM查找函數(shù)。
function queryClassName(node, name) { var starts = '(^|[ \n\r\t\f])', ends = '([ \n\r\t\f]|$)'; var array = [], regex = new RegExp(starts + name + ends), elements = node.getElementsByTagName("*"), length = elements.length, i = 0, element; while (i < length) { element = elements[i]; if (regex.test(element.className)) { array.push(element); } i += 1; } return array; }Q10 使用JS 實(shí)現(xiàn)二叉查找樹(shù)(Binary Search Tree)
一般叫全部寫(xiě)完的概率比較少，但是重點(diǎn)考察你對(duì)它的理解和一些基本特點(diǎn)的實(shí)現(xiàn)。 二叉查找樹(shù)，也稱(chēng)二叉搜索樹(shù)、有序二叉樹(shù)（英語(yǔ)：ordered binary tree）是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：
- 任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
- 任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
- 任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)；
- 沒(méi)有鍵值相等的節(jié)點(diǎn)。二叉查找樹(shù)相比于其他數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)在于查找、插入的時(shí)間復(fù)雜度較低。為O(log n)。二叉查找樹(shù)是基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)，用于構(gòu)建更為抽象的數(shù)據(jù)結(jié)構(gòu)，如集合、multiset、關(guān)聯(lián)數(shù)組等。
在寫(xiě)的時(shí)候需要足夠理解二叉搜素樹(shù)的特點(diǎn)，需要先設(shè)定好每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
class Node { constructor(data, left, right) {this.data = data; this.left = left; this.right = right; } }樹(shù)是有節(jié)點(diǎn)構(gòu)成，由根節(jié)點(diǎn)逐漸延生到各個(gè)子節(jié)點(diǎn)，因此它具備基本的結(jié)構(gòu)就是具備一個(gè)根節(jié)點(diǎn)，具備添加，查找和刪除節(jié)點(diǎn)的方法.
class BinarySearchTree {constructor() {this.root = null; } insert(data) { let n = new Node(data, null, null); if (!this.root) { return this.root = n; } let currentNode = this.root; let parent = null; while (1) { parent = currentNode; if (data < currentNode.data) { currentNode = currentNode.left; if (currentNode === null) { parent.left = n; break; } } else { currentNode = currentNode.right; if (currentNode === null) { parent.right = n; break; } } } } remove(data) { this.root = this.removeNode(this.root, data) } removeNode(node, data) { if (node == null) { return null; } if (data == node.data) { // no children node if (node.left == null && node.right == null) { return null; } if (node.left == null) { return node.right; } if (node.right == null) { return node.left; } let getSmallest = function(node) { if(node.left === null && node.right == null) { return node; } if(node.left != null) { return node.left; } if(node.right !== null) { return getSmallest(node.right); } } let temNode = getSmallest(node.right); node.data = temNode.data; node.right = this.removeNode(temNode.right,temNode.data); return node; } else if (data < node.data) { node.left = this.removeNode(node.left,data); return node; } else { node.right = this.removeNode(node.right,data); return node; } } find(data) { var current = this.root; while (current != null) { if (data == current.data) { break; } if (data < current.data) { current = current.left; } else { current = current.right } } return current.data; } } module.exports = BinarySearchTree;前言
javascript是一門(mén)非常靈活的語(yǔ)言，實(shí)際的開(kāi)發(fā)過(guò)程中我們也可以靈活的使用它而給我們的工作帶來(lái)便利，這篇文章記錄了自己平時(shí)學(xué)習(xí)過(guò)程中經(jīng)常用到的一些小技巧，整理出來(lái)作為筆記，也希望對(duì)感興趣的同學(xué)有所幫助。( 持續(xù)更新… )
1 獲取指定范圍內(nèi)的隨機(jī)數(shù)
當(dāng)我們需要獲取指定范圍(min,max)內(nèi)的整數(shù)的時(shí)候，下面的代碼非常適合。
| 123 | function?getRadomNum(min,max){return?Math.floor(Math.random() * (max - min +?1)) + min;} |
測(cè)試
2 隨機(jī)獲取數(shù)組中的元素
| 123 | function?getRadomFromArr(arr){return arr[Math.floor(Math.random()*arr.length)];} |
測(cè)試
3 生成從0到指定值的數(shù)字?jǐn)?shù)組
| 123 | var arr=[],length=100,i=1;for(;arr.push(i++)<length;){}console.log(arr) |
測(cè)試
4 打亂數(shù)字?jǐn)?shù)組的順序
| 12 | var arr = [1,2,3,4,5,6,7,'a','dsfs',8,9,'v'];arr.sort(function(){return?Math.random()-0.5}); |
測(cè)試
5 對(duì)象轉(zhuǎn)換為數(shù)組
| 1234567891011 | //注意對(duì)象必須是以下格式的才可以通過(guò)此方式轉(zhuǎn)化為數(shù)組//獲取的DOM集合，以及函數(shù)的arguments也可以通過(guò)此方式轉(zhuǎn)化為數(shù)組var obj={0:'qian',1:'long',2:'chu',3:'tian',length:4}var _slice=[].slice;var objArr=_slice.call(obj); |
測(cè)試
6 驗(yàn)證是否為數(shù)組
| 123 | function?isArray(obj){return?Object.prototype.toString.call(obj) ===?'[object Array]' ;} |
測(cè)試
7 獲取數(shù)組中最大或者最小值
| 123456 | function?maxAndMin(arr){return {max:Math.max.apply(null,arr.join(',').split(',')),min:Math.min.apply(null,arr.join(',').split(','))}} |
該方法適合一維或者多維數(shù)組求最大最小值的情況
測(cè)試
8 清空數(shù)組
| 1234567891011 | //方式一 通過(guò)將長(zhǎng)度設(shè)置為0var arr=[1,2,3,4,5];arr.length=0;//方式二 通過(guò)splice方法var arr=[1,2,3,4,5];arr.splice(0,arr.length);//方式三 通過(guò)將空數(shù)組 [] 賦值給數(shù)組(嚴(yán)格意義來(lái)說(shuō)這只是將ary重新賦值為空數(shù)組，之前的數(shù)組如果沒(méi)有引用在指向它將等待垃圾回收。)var arr=[1,2,3,4,5];arr=[]; |
9 保留指定小數(shù)位
| 12 | var num =4.345678;num = num.toFixed(4);?// 4.3457 第四位小數(shù)位以四舍五入計(jì)算 |
10 不要直接使用delete來(lái)刪除數(shù)組中的元素
數(shù)組在js中也是對(duì)象，有時(shí)候我們可能會(huì)通過(guò)delete來(lái)刪除數(shù)組中的元素，但是其實(shí)僅僅是將數(shù)組的元素的值賦值為了undefined。
| 123 | var arr=[1,2,3,4,5,'謙龍','雛田'];delete arr[5];console.log(arr,arr[5],arr.length); |
?
測(cè)試
可以通過(guò)splice來(lái)刪除數(shù)組中的某一項(xiàng)
| 123 | var arr=[1,2,3,4,5,'謙龍','雛田'];arr.splice(5,1);console.log(arr,arr[5],arr.length); |
?
測(cè)試
11 生成指定長(zhǎng)度的隨機(jī)字母數(shù)字字符串
| 12345 | function?getRandomStr(len) {var str =?"";for( ; str.length < len; str +=?Math.random().toString(36).substr(2));return str.substr(0, len);} |
測(cè)試
12 null 與 undefined
null == undefined,null == null 返回true,有時(shí)候我們?yōu)榱伺懦齨ull 和 undefined可以使用如下的代碼
| 12345 | function?test(obj){if(obj!=null){// obj除了undefined 和 null 之外都會(huì)走這里....這里寫(xiě)代碼邏輯}} |
13 找出數(shù)組中出現(xiàn)次數(shù)最的元素，并給出其出現(xiàn)過(guò)的位置
| 12345678910111213141516171819202122232425 | function?getMaxAndIndex(?arr ){var obj = {};arr.forEach(function(item,index){if(!obj[item]){obj[item]= {indexs: [index]}}else{obj[item]['indexs'].push(index);}});var num=0;//記錄出現(xiàn)次數(shù)最大值var str='';//記錄出現(xiàn)次數(shù)最多的字符var reArr;//返回最大值的位置數(shù)組for(var attr?in obj){var temp=obj[attr]['indexs'];if(temp.length>num){num=temp.length;str=attr;reArr=temp;}}return {maxStr:str,indexs:reArr}} |
測(cè)試結(jié)果
總結(jié)
以上是生活随笔為你收集整理的WEB前端必须掌握的一些算法题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Windows Telnet服务端口配置
- 下一篇： 如何在 iPhone、iPad 及 Ma