一、去重
我在前端面试过程中遇到去重算法的概率为百分之九十，这里就总结下各种去重算法及其复杂度
1. new Set()
ES6中介绍了Set相关的概念，它可以实现数组和字符串去重的功能，代码量非常少，一行代码的事情
//数组去重
const arr = [1,1,2,2]
function unique1(arr){
return [...new Set(arr)] //[1,2]
}
//或者
function unique1(arr){
return Array.from(new Set(arr)) //[1,2]
}
//补充 字符串去重
[...new Set('aabbccs')].join('') //'abcs'
2. filter + indexOf 过滤
indexOf有兼容性问题,支持ie8以上
这里我就假设传进来的一定是一个合法的数组，那些对入参的校验这里就不作处理了，直接写逻辑代码。
function unique2(arr){
return arr.filter((item,index,arr)=>arr.indexOf(item) == index)
}
console.log(fn([1,1,2,2,3]))//[1,2,3]
这个方法利用了filter的第三个参数还是返回原数组，通过判断这个数组的第n个元素的位置是不是原始位置来过滤重复数字。例如，第一个1出现在0位置上，那么arr.indexOf(item) = 0 和index = 0 是匹配上的，第2个1出现在1位置上但是arr.indexOf(item) 还是等于0，而此时的index = 1 那么这时候 arr.indexOf(item) 不等于 index，这样重复的number就被过滤掉啦
3.object 对象属性不重复
该方法速度最快，以空间换时间。不过需要注意的是，该方法中判断数组元素是否为对象的键值
function unique3(arr){
const obj = {}
arr.map(item=> obj[item] = item)
return Object.keys(obj)
}
console.log(unique3([1,1,2,2,3])) //['1','2','3']
注意：这个方法返回的值为字符串了，这里注意要转换下
或者是创建个对象和新数组
function unique3(arr){
const obj = {}
let arr = []
arr.forEach(item=>{
if(!obj[item]){
obj[item] = 1
arr.push(item)
}else { // else可要可不要，要的话可以记录下每个元素重复的次数
obj[item] += 1
}
})
return arr
}
只创建一个对象，遇到重复元素就删除
function unique3(arr){
const obj = {}
for(let i =0;i<arr.length;i++){ //要动态改变length所以只能用for循环
const item = arr[i]
if(obj[item]){ //存在重复就删除，且i--
obj[item] += 1
arr.splice(i,1) //
i--
}else {
obj[item] = 1
}
}
return arr
}
4. indexOf + 新数组
新增一个数组，判断这个新数组中是否存在item元素，不存在就push,存在就忽略
function unique4(arr){
const newArr = []
arr.forEach(item=>{
newArr.indexOf(item) === -1 ? newArr.push(item):null
})
return newArr
}
console.log(unique4([1,1,2,2,3])) //[1,2,3]
5. includes + 新数组
思路和方法4一样，只是使用方法由indexOf改为includes
function unique5(arr){
const newArr = []
arr.forEach(item=>{
!newArr.includes(item) ? newArr.push(item):null
})
return newArr
}
console.log(unique5([1,1,2,2,3])) //[1,2,3]
6.对象数组中id重复的去重
const repeatArr = [
{ id: 1, a: 1 },
{ id: 2, a: 2 },
{ id: 3, a: 3 },
{ id: 1, a: 4 },
];
const newArr = repeatArr.reduce((arr, cur) => {
const ids = arr.map(item => item.id);
return ids.includes(cur.id) ? arr : [...arr, cur];
}, []);
console.log(newArr); // -> [ { id: 1, a: 1}, {id: 2, a: 2}, {id: 3, a: 3} ]
二、将mxn矩阵的数组转换为nxm的数组
将数组中每个元素中的第一位组成新数组中第一个元素，数组中每个元素的第二位组成新数组中的第二个元素.....直到最后一位
题目描述可能有点绕，具体可以看看示例就能明白了
例如
示例一：arr = [ [1, 2, 3 ], [4, 5, 6 ],[7, 8, 9 ] ]，将arr转换为 arr = [[1,4,7], [2,5,8],[3,6,9]]
示例二：arr = [ [1, 2, 3,4 ], [5, 6,7,8 ],[9,10,11,12 ] ]，将arr转换为 arr = [[1,5,9], [2,6,10],[3,7,11],[4,8,12]]
参考解答方案
let arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13,14, 15, 16],
[17,18, 19, 20],
]
function coverFun(arr) {
//这里先定义一个新的空的数组，将新数组个长度先定义下
//两种方法都可以
let newArr = Array.apply(null,{length:arr[0].length})
.map((item,i)=>{return []})
// let newArr = Array.from({length:arr[0].length})
// .map((item,i)=>{return []})
//外层遍历数组第一个元素的长度（这里随便哪个元素都行，因为都是一样的）
//里层遍历数组长度
for (let i = 0; i < arr[0].length; i++) {
for (let j = 0; j < arr.length; j++) {
newArr[i].push(arr[j][i])
}
}
return newArr
}
console.log(coverFun(arr))
最后输出结果如图
当时一紧张脑子啥也没想到，回来好好看了算法相关的题目，将js相关的算法汇总下。
当然上面的只是我想到的其中一种解题思路，肯定会有很多其他办法也可以实现的。
三、螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
例如输入
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
这题跟上面的点相似之处
四、判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
参考解答方案
var isPalindrome = function(x) {
if((x+'').indexOf('-') >-1){
return false
}
let str = String(x)
str = str.split('').reverse().join('')
if(str === String(x) ){
return true
}else {
return false
}
};
五、盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
参考解答方案
var maxArea = function(height) {
let max = 0//假设最大为0
for(let i= 0;i<=height.length-1;i++){
for(let j=1+i;j<=height.length-1;j++){
if(Math.min(height[i],height[j])*Math.abs(i-j)>max)
max = Math.min(height[i],height[j])*Math.abs(i-j)
}
}
return max
};
六、最大公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
参考解答方案
var longestCommonPrefix = function(strs) {
if(strs.length ===0){
return ''
}else if(strs.length ===1){
return strs[0]
}
let index = ''//假设index是公共字符串
for(let i = 0;i<strs[0].length;i++){
let comStr = strs[0].charAt(i)
for(let j = 1; j<strs.length;j++){
if(strs[j].charAt(i)!==comStr){
return index
}
}
index += comStr
}
return index
};
七、三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
参考解答方案
var threeSum = function(nums) {
let arr = []
for(let i=0;i<nums.length;i++){
for(let j = 1;j<nums.length;j++){
for(let c=2;c<nums.length;c++){
if((nums[i]+nums[j]) === -nums[c]&& i!==j &&i!==c&&j!==c){
arr.push([nums[i],nums[j],nums[c]])
}
}
}
}
let a = arr.map(item=>{
return item.sort().join(',')
})
let lastArr = [...new Set(a)]
return lastArr.map(item=>{
return item.split(',').map(item=>{
return Number(item)
})
})
};
八、最大子序和
描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
九、最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
十、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
例如：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
var climbStairs = function(n) {
let arr = [],index=0
//1.首先先算出有多少1和2的组合
for( let i = 0; i <= n; i++ ){
for( let j = 0; j<=n;j++){
if(i*1 + 2*j === n){ //i 个1， j个2
arr.push([i,j]) //
}
}
}
//这是一个实现乘积的递归算法
function getCJ(n){
if(n=1){
return 1
}
return n*getCJ(n-1)
}
//2.在计算每一种组合内部有多少排列方式
for (let n =0;n<arr.length;n++){
let item = arr[n]
//2.1当组合中都是1或者都是2时候，只有1种排列方式
if(item.indexOf(0)>-1){
index +=1
//2.1当组合中的1或者2只有1个的时候排列方式为 当前数组元素相加的和
}else if((item.indexOf(1)>-1)){
index += item[0] +item[1]
}else{
//2.3最复杂的情况 m个1和n个2的情况(m,n>=2) 排列方式 有(m+n)!/(m!*n!)种
index += getCJ(item[0]+item[1])/(getCJ(item[0])*getCJ(item[1]))
}
}
return index
};
console.log(climbStairs(7)) //21
