web前端开发面试中常见的算法题(JS)

小鱼儿 2023-06-04 06:54 29阅读 0赞

## 前言 ##

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

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

话不多说，下面来看题。

**目录**

前言

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

2.斐波那契

3.求最大公约数

4.数组去重

5.删除重复的字符

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

7.字符串反向

8.字符串原位反转

9.判断是否是回文

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

11.连字符转成驼峰

12.最长公共前缀

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

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

15.岛问题：判断有几个岛

16.将数字12345678转化成RMB形式：12,345,678

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

18.宣讲会安排

19.汉诺塔问题

20.母牛生母牛问题

21.切割金条-贪心算法

--------------------

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

*  如果这个数是 2 或 3，一定是素数；
 *  如果是偶数，一定不是素数；
 *  如果这个数不能被3~它的平方根中的任一数整除，m必定是素数。而且除数可以每次递增2（排除偶数）

### 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)。

### 3.求最大公约数 ###

*  除数 在a和b的范围内，如果同时a和b处以除数的余等于0，就将此时的除数赋值给res；除数自增，不断循环上面的计算，更新res。

*  解法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数组。

### 5.删除重复的字符 ###

这一题的解法和上一题类似。

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

*  如果 b数组已经遍历完，a数组还有值 或 a\[i\] 的值 小于等于 b\[i\] 的值，则将 a\[i\] 添加进数组res，并 i++；
 *  如果不是上面的情况，则将 b\[i\] 添加进数组res，并 i++；

### 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

*  将函数添加到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.判断是否是回文 ###

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

eg：在一个未排序的数组中找出是否有任意两数之和等于给定的数。

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

这个题解得很巧妙，

1.  循环遍历数组，let subStract = num - arr\[i\];
2.  如果 differ\[subStract\] 里有值，则返回true；如果没有，将 differ\[arr\[i\]\] 置为 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.最长公共前缀 ###

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: \["flower","flow","flight"\]  
输出: "fl"

示例 2:

输入: \["dog","racecar","car"\]  
输出: ""

### 13.加油站问题-贪心算法 ###

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。  
要求：

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

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

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

String.prototype.trim1 = function(){
    	// return this.replace(/\s*/g,"");  // 清除所有空格
    	return this.replace(/(^\s*)|(\s*$)/g,"");  // 清除字符串前后的空格
    };
    console.log("  hello word ".trim1())  // "hello word"

### 15.岛问题：判断有几个岛 ###

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？

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

### 16.将数字12345678转化成RMB形式：12,345,678 ###

思路：将字符串切割成数组再反转，遍历数组，加入辅助数组，当数组长度为3的倍数，再向辅助数组加入 ","。

### 17.删除相邻相同的字符串 ###

### 18.宣讲会安排 ###

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

步骤：

1.  先按照会议的end时间升序排序；
2.  排除了因为正在进行会议而无法进行的会议（now > obj\[i\].start）；
3.  会议能举行，则 res++，并且更新目前时间now （now = obj\[i\].end;）。

### 19.汉诺塔问题 ###

把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思路：

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

结果：

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 右

### 20.母牛生母牛问题 ###

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

思路：

1.  因为新生的母牛，只有等到第四年才能生小母牛。所以前4年，只有原来的一头母牛每年生一头。
2.  第五年以后，除了有前一年的牛数量，还有三年前的牛可以生新的小牛。（最近3年内生的牛还不能生）

### 21.切割金条-贪心算法 ###

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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实现切割金条问题][js]

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

--------------------

算法问题先写到这，如果还有更多的面试题，也可以和我交流交流，相互学习呀！

[Javascript]: https://blog.csdn.net/weixin_40141473/article/details/102027271
[js]: https://blog.csdn.net/weixin_40141473/article/details/102313298