JS面试中常见的算法题

2019-10-10 admin

前言 最近在准备秋招,做过了大大小小的公司的面试题,发现除了基础知识外,算法还是挺重要的。特意整理了一些常见的算法题,添加了自己的理解并实现。

除此之外,建议大家还可以刷刷《剑指offer》(但我还没刷完😂,任重道远呐)。此外,左神在牛客网上也有算法课程,听了基础班的感觉还不错,起码让我这个算法小白也能快速地理解了很多问题,知识付费的时代,这个真的是良心课程了。就我个人而言的话,平时为了解决一个算法问题,需要花很多时间去看帖子、看讲解,但很难真正转化为自己的思想(主要问题就是没有动手练),大家可以根据自己的需求,进行算法的学习。

话不多说,下面来看题。

目录

前言

1.验证一个数是否是素数

2.斐波那契

3.求最大公约数

4.数组去重

5.删除重复的字符

6.排序两个已经排好序的数组

7.字符串反向

8.字符串原位反转

9.判断是否是回文

10.判断数组中是否有两数之和

11.连字符转成驼峰

12.加油站问题-贪心算法

13.用正则实现trim() 清除字符串两端空格

14.岛问题:判断有几个岛

15.将数字12345678转化成RMB形式:12,345,678

16.删除相邻相同的字符串

17.宣讲会安排

18.汉诺塔问题

19.母牛生母牛问题

20.切割金条-贪心算法

1.验证一个数是否是素数 如果这个数是 2 或 3,一定是素数; 如果是偶数,一定不是素数; 如果这个数不能被3~它的平方根中的任一数整除,m必定是素数。而且除数可以每次递增2(排除偶数) function isPrime(num){

if (num === 2 || num === 3) {
    return true;
};
if (num % 2 === 0) {
    return false;
};
let divisor = 3,limit = Math.sqrt(num);
while(limit >= divisor){
    if (num % divisor === 0) {
        return false;
    }
    else {
        divisor += 2;
    }
}
return true;

} console.log(isPrime(30)); // false 2.斐波那契 最简单的做法:递归。 function fibonacci(n){

if (n <= 0) {
    return 0;
}
if (n == 0) {
    return 1;
}
return fibonacci(n-1) + fibonacci(n-2);

} 但是递归会有严重的效率问题。比如想要求得f(10),首先需要求f(9)和f(8)。同样,想求f(9),首先需要f(8)和f(7)…这样就有很多重复值,计算量也很大。

改进:从下往上计算,首先根据f(0)和f(1)计算出f(2),再根据f(1)和f(2)计算出f(3)……以此类推就可以计算出第n项。时间复杂度O(n)。 function fibonacci(n){

let ori = [0,1];
if (n < 2) {
    return ori[n];
};
let fiboOne = 1,fiboTwo = 0,fiboSum = 0;
for (let i = 2; i <= n; i++) {
    fiboSum = fiboOne + fiboTwo;
    fiboTwo = fiboOne;
    fiboOne = fiboSum;
}
return fiboSum;

} console.log(fibonacci(5)); 3.求最大公约数 除数 在a和b的范围内,如果同时a和b处以除数的余等于0,就将此时的除数赋值给res;除数自增,不断循环上面的计算,更新res。 function greatestCommonDivisor(a, b){

let divisor = 2,res = 1;
if (a < 2 || b < 2) {
    return 1;
};
while(a >= divisor && b >= divisor){
    if (a%divisor === 0 && b%divisor === 0) {
        res = divisor;
    }
    divisor++;
}
return res;

}; console.log(greatestCommonDivisor(8, 4)); // 4 console.log(greatestCommonDivisor(69, 169)); // 1 解法2: function greatestCommonDivisor(a,b){

if (b === 0) {
    return a;
} else {
    return greatestCommonDivisor(b,a%b);
}

}; 4.数组去重 对原数组进行遍历 获取arr[i]的值 j; 对应到辅助数组 exits 的位置 j 的值,如果没有,则证明arr[i] 的值没有重复,此时将 值j 存入res数组,并将辅助数组 j 位置的值置为 true。 最后返回res数组。 function removeDuplicate(arr){

if (arr === null || arr.length < 2) {
    return arr;
};
let res = [],exits = [];
for(let i = 0; i < arr.length; i++){
    let j = arr[i];
    while( !exits[j] ){
        res.push(arr[i]);
        exits[j] = true;
    }
}
return res;

} console.log(removeDuplicate([1,3,3,3,1,5,6,7,8,1])) // [1,3,5,6,7,8] 5.删除重复的字符 这一题的解法和上一题类似。

function removeDuplicateChar(str){

if (!str || str.length < 2 || typeof str != "string") {
    return;
};
let charArr = [],res = [];
for(let i = 0; i < str.length; i++){
    let c = str[i];
    if(charArr[c]){
        charArr[c]++;
    }
    else{
        charArr[c] = 1;
    }
}
for(let j in charArr){
    if (charArr[j] === 1) {
        res.push(j);
    }
}
return res.join("");

} console.log(removeDuplicateChar(“Learn more javascript dude”)); // Lnmojvsciptu 6.排序两个已经排好序的数组 如果 b数组已经遍历完,a数组还有值 或 a[i] 的值 小于等于 b[i] 的值,则将 a[i] 添加进数组res,并 i++; 如果不是上面的情况,则将 b[i] 添加进数组res,并 i++; function mergeSortedArr(a,b){

if (!a || !b) {
    return;
};
let aEle = a[0],bEle = b[0],i = 1,j = 1,res = [];
while(aEle || bEle){
    if ((aEle && !bEle) || aEle <= bEle) {
        res.push(aEle);
        aEle = a[i++];
    }
    else{
        res.push(bEle);
        bEle = b[j++];
    }
}
return res;

} console.log(mergeSortedArr([2,5,6,9], [1,2,3,29])) // [1,2,2,3,5,6,9,29] 7.字符串反向 最简单的方法: function reverse(str){

let resStr = "";
for(let i = str.length-1; i >= 0; i--){
    resStr += str[i];
}
return resStr;

} console.log(reverse(“ABCDEFG”)); 方法2 function reverse2(str){

if (!str || str.length < 2 || typeof str != "string") {
    return str;
};
let res = [];
for(let i = str.length-1; i >= 0; i--){
    res.push(str[i]);
}
return res.join("");

} console.log(reverse2(“Hello”)); 将函数添加到String.prototype String.prototype.reverse3 = function(){

if (!this || this.length < 2) {
    return;
};
let res = [];
for(let i = this.length-1; i >= 0; i--){
    res.push(this[i]);
}
return res.join("");

} console.log(“abcdefg”.reverse3()); 8.字符串原位反转 例如:将“I am the good boy”反转变为 “I ma eht doog yob”。

提示:使用数组和字符串方法。

function reverseInPlace(str){

return str.split(' ').reverse().join(' ').split('').reverse().join('');

} console.log(reverseInPlace(‘I am the good boy’)); 9.判断是否是回文 function isPalindrome(str){

if (!str || str.length < 2) {
    return;
}
for(let i = 0; i < str.length/2; i++){
    if (str[i] !== str[str.length-1-i]) {
        return false;
    }
}
return true;

} console.log(isPalindrome(“madama”)) 10.判断数组中是否有两数之和 eg:在一个未排序的数组中找出是否有任意两数之和等于给定的数。

给出一个数组[6,4,3,2,1,7]和一个数9,判断数组里是否有任意两数之和为9。

这个题解得很巧妙,

循环遍历数组,let subStract = num - arr[i]; 如果 differ[subStract] 里有值,则返回true;如果没有,将 differ[arr[i]] 置为 true。 function sumFind(arr,num){

if (!arr || arr.length < 2) {
    return;
};
let differ = {};
for(let i = 0; i < arr.length; i++){
    let subStract = num - arr[i];
    if (differ[subStract]) {
        return true;
    }
    else{
        differ[arr[i]] = true;
    }
}
return false;

} console.log(sumFind([6,4,3,2,1,7], 9)); // true 11.连字符转成驼峰 如:get-element-by-id 转为 getElementById

let str = ‘get-element-by-id’; let arr = str.split(’-’); for(let i=1; i<arr.length; i++){ arr[i] = arr[i].charAt(0).toUpperCase() + arr[i].substring(1); } console.log(arr.join(’’)); // getElementById 12.加油站问题-贪心算法 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。并证明算法能产生一个最优解。 要求:

输入:第一行有2个正整数n和k,表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已加满油。第k+1 个加油站表示目的地。

输出:输出编程计算出的最少加油次数。如果无法到达目的地,则输出”NoSolution”。

function greedy(n, k, arr){ // n:加满可以行驶的公里数; k:加油站数量; arr:每个加油站之间的距离数组

if (n == 0 || k == 0 || arr.length == 0 || arr[0] > n) {
    return "No Solution!";  // arr[0] > n :如果第一个加油站距离太远,也无法到达
};
let res = 0, distance = 0;  // res:加油次数;distance:已行驶距离
for(let i = 0; i <= k; i++){
    distance += arr[i];
    if (distance > n) {  // 已行驶距离 > 加满可以行驶的公里数
        if(arr[i] > n){  // 如果目前加油站和前一个加油站的距离 > 加满可以行驶的公里数,则无法到达
            return "No Solution!";
        };
        // 可以在上一个加油站加油,行驶到目前的加油站i:
        distance = arr[i];
        res++;  // 加油次数+1
    }
}
return res;

} let arr = [1,2,3,4,5,1,6,6]; console.log(greedy(7,7,arr)) // 4 13.用正则实现trim() 清除字符串两端空格 String.prototype.trim1 = function(){

// return this.replace(/\s*/g,"");  // 清除所有空格
return this.replace(/(^\s*)|(\s*$)/g,"");  // 清除字符串前后的空格

}; console.log(" hello word ".trim1()) // "hello word" 14.岛问题:判断有几个岛 一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右 四个位置相连,如果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?

可以看我之前的讲解。Javascript实现岛问题

15.将数字12345678转化成RMB形式:12,345,678 思路:将字符串切割成数组再反转,遍历数组,加入辅助数组,当数组长度为3的倍数,再向辅助数组加入 “,”。

function RMB(str){

let arr = str.split("").reverse();
let res = [];
for(let i = 0; i < arr.length; i++){
    res.push(arr[i]);
    if ((i + 1) % 3 === 0) {
        res.push(",");
    }
}
return res.reverse().join("");

} console.log(RMB(“12345678”)) 16.删除相邻相同的字符串 function delSrt(str){

let res = [], nowStr;
for(let i = 0; i < str.length; i ++){
    if (str.charAt(i) != nowStr) {
        res.push(str.charAt(i));
        nowStr = str.charAt(i);
    }
}
return res.join("");

} console.log(delSrt(“aabcc11”)) 17.宣讲会安排 一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(数组,里面是一个个具体的项目),你来安排宣讲的日程,要求会议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。

步骤:

先按照会议的end时间升序排序; 排除了因为正在进行会议而无法进行的会议(now > obj[i].start); 会议能举行,则 res++,并且更新目前时间now (now = obj[i].end;)。 function getMostCount(obj){

if (!obj || obj.length < 1) {
    return;
};
obj.sort(sortEndTime);
let res = 1, now = obj[0].end;
for(let i = 1; i < obj.length; i++){
    if (now < obj[i].start) {
        res++;
        now = obj[i].end;
    }
}
return res;

} // 自定义排序法 function sortEndTime(obj1,obj2){

return obj1.end - obj2.end;

} var obj = [

{start:6,end:8},
{start:7,end:9},
{start:11,end:12},
{start:10,end:14},
{start:16,end:18},
{start:17.5,end:21},
{start:15,end:17},
{start:22,end:23}

]; console.log(“最大场次:” + getMostCount(obj)); 18.汉诺塔问题 把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

思路:

递归解决:把问题转化为规模缩小了的同类问题的子问题; 明确递归结束的条件(base case):n == 1 其他过程:from:来源地;to:目的地;help:辅助。 function hanoiProcess(n,from,to,help){

if (n < 1) {
    return;
}
if (n == 1) {  // 最后一个从from移到to
    console.log("Move 1 from " + from + " to " + to);
} else{
    hanoiProcess(n-1, from, help, to);  // 前n-1个从from移到help上,可以借助to
    console.log("Move "+ n +" from " + from + " to " + to);
    hanoiProcess(n-1, help, to, from);  // 再把n-1个从help移到to,可以借助from
}

} hanoiProcess(3, “左”, “右”, “中”); 结果:

Move 1 from 左 to 右 Move 2 from 左 to 中 Move 1 from 右 to 中 Move 3 from 左 to 右 Move 1 from 中 to 左 Move 2 from 中 to 右 Move 1 from 左 to 右

19.母牛生母牛问题 母牛每年生一只母牛,新出生的母牛成长三年后也能每年生一只母牛,假设不会死。求N年后,母牛的数量。

思路:

因为新生的母牛,只有等到第四年才能生小母牛。所以前4年,只有原来的一头母牛每年生一头。 第五年以后,除了有前一年的牛数量,还有三年前的牛可以生新的小牛。(最近3年内生的牛还不能生) function cow(n){

if (n < 1) {
    return;
};
let count = 0;
if (n > 4) {
    count = cow(n-1) + cow(n-3);
} else{
    count = n;
}
return count;

} let n = 7; console.log(n + " 年后,牛的数量是: " + cow(n)) // 7 年后,牛的数量是: 13 20.切割金条-贪心算法 一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60。金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50,花费60。再把长度50的金条分成20和30, 花费50。一共花费110铜板。但是如果先把长度60的金条分成30和30,花费60。再把长度30 金条分成10和20,花费30。一共花费90铜板。 输入一个数组,返回分割的最小代价。

这个也可以看我之前的博文介绍。js实现切割金条问题

如果有更好的解法,感谢大佬赐教!我的解法太普通了,有时间再改进下。

算法问题先写到这,如果还有更多的面试题,也可以和我交流交流,相互学习呀! ———————————————— 版权声明:本文为CSDN博主「Allison-L」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/weixin_…

[转载]原文链接:https://segmentfault.com/a/1190000020635581

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-77032.html

文章标题:JS面试中常见的算法题

相关文章
Node.js 2014这一年发生了什么
Node.js 的 2014 年充满了不幸和争议. 这一年 Noder 们经历了太多的伤心事, 经历了漫长的等待, 经历了沉重的分裂之痛. 也许 Noder 们不想回忆14年 Node.js land 发生的事情, 但正因为痛才更有铭记的价...
2015-11-12
Vue.js组件tab实现选项卡切换
本文实例为大家分享了vue插件tab选项卡的具体代码,供大家参考,具体内容如下 效果图: 代码如下: &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot;&gt; &lt;head&gt; ...
2017-03-13
jsdom 中文文档(纯翻译)
jsdom是一个纯粹由 javascript 实现的一系列 web标准,特别是 WHATWG 组织制定的DOM和 HTML 标准,用于在 nodejs 中使用。大体上来说,该项目的目标是模拟足够的Web浏览器子集,以便用于测试和挖掘真实世界...
2018-05-14
React.js编程思想
JavaScript框架层出不穷,在很多程序员看来,React.js是创建大型、快速的Web应用的最好方式。这一款由Facebook出品的JS框架,无论是在Facebook还是在Instagram中,它的表现都非常出色。 使用React.j...
2015-11-12
从2014年的发展来展望JS的未来将会如何
&lt;font face=&quot;寰�杞�闆呴粦, Arial, sans-serif &quot;&gt;2014骞达紝杞�浠惰�屼笟鍙戝睍杩呴€燂紝鍚勭�嶈��瑷€灞傚嚭涓嶇┓锛屼互婊¤冻鐢ㄦ埛涓嶆柇鍙樺寲鐨勯渶姹傘€傝繖浜涜��...
2015-11-12
破解前端面试(80% 应聘者不及格系列):从 闭包说起
不起眼的开始 招聘前端工程师,尤其是中高级前端工程师,扎实的 JS 基础绝对是必要条件,基础不扎实的工程师在面对前端开发中的各种问题时大概率会束手无策。在考察候选人 JS 基础的时候,我经常会提供下面这段代码,然后让候选人分析它实际运行的结...
2017-06-02
three.js实现围绕某物体旋转
话不多说,请看代码: 可以拖动右上角观察变化 &lt;!DOCTYPE html&gt; &lt;html lang=&quot;en&quot; style=&quot;width: 100%; height:100%;&quot;&gt...
2017-02-17
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
JS中的语音合成——Speech Synthesis API
JS中的语音合成——Speech Synthesis API 简介 HTML5中和Web Speech相关的API实际上有两类,一类是“语音识别(Speech Recognition)”,另外一个就是“语音合成(Speech Synthes...
2018-05-17
NodeJS参考手册pdf版
下载地址:Nodejs参考手册PDF版下载 ...
2015-11-12
回到顶部