一、去重
我在前端面試過程中遇到去重算法的概率為百分之九十怒详，這里就總結(jié)下各種去重算法及其復(fù)雜度
1. new Set()
ES6中介紹了Set相關(guān)的概念弛秋，它可以實現(xiàn)數(shù)組和字符串去重的功能，代碼量非常少铺韧，一行代碼的事情
//數(shù)組去重
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以上
這里我就假設(shè)傳進(jìn)來的一定是一個合法的數(shù)組多矮，那些對入?yún)⒌男ｒ炦@里就不作處理了，直接寫邏輯代碼哈打。
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的第三個參數(shù)還是返回原數(shù)組塔逃，通過判斷這個數(shù)組的第n個元素的位置是不是原始位置來過濾重復(fù)數(shù)字。例如料仗，第一個1出現(xiàn)在0位置上湾盗，那么arr.indexOf(item) = 0 和index = 0 是匹配上的，第2個1出現(xiàn)在1位置上但是arr.indexOf(item) 還是等于0罢维，而此時的index = 1 那么這時候 arr.indexOf(item) 不等于 index淹仑，這樣重復(fù)的number就被過濾掉啦
3.object 對象屬性不重復(fù)
該方法速度最快，以空間換時間肺孵。不過需要注意的是匀借，該方法中判斷數(shù)組元素是否為對象的鍵值
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']
注意：這個方法返回的值為字符串了，這里注意要轉(zhuǎn)換下
或者是創(chuàng)建個對象和新數(shù)組
function unique3(arr){
const obj = {}
let arr = []
arr.forEach(item=>{
if(!obj[item]){
obj[item] = 1
arr.push(item)
}else { // else可要可不要平窘，要的話可以記錄下每個元素重復(fù)的次數(shù)
obj[item] += 1
}
})
return arr
}
只創(chuàng)建一個對象吓肋，遇到重復(fù)元素就刪除
function unique3(arr){
const obj = {}
for(let i =0;i<arr.length;i++){ //要動態(tài)改變length所以只能用for循環(huán)
const item = arr[i]
if(obj[item]){ //存在重復(fù)就刪除，且i--
obj[item] += 1
arr.splice(i,1) //
i--
}else {
obj[item] = 1
}
}
return arr
}
4. indexOf + 新數(shù)組
新增一個數(shù)組瑰艘，判斷這個新數(shù)組中是否存在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 + 新數(shù)組
思路和方法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.對象數(shù)組中id重復(fù)的去重
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矩陣的數(shù)組轉(zhuǎn)換為nxm的數(shù)組
將數(shù)組中每個元素中的第一位組成新數(shù)組中第一個元素均蜜，數(shù)組中每個元素的第二位組成新數(shù)組中的第二個元素.....直到最后一位
題目描述可能有點繞李剖，具體可以看看示例就能明白了
例如
示例一：arr = [ [1, 2, 3 ], [4, 5, 6 ],[7, 8, 9 ] ]，將arr轉(zhuǎn)換為 arr = [[1,4,7], [2,5,8],[3,6,9]]
示例二：arr = [ [1, 2, 3,4 ], [5, 6,7,8 ],[9,10,11,12 ] ]囤耳，將arr轉(zhuǎn)換為 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) {
//這里先定義一個新的空的數(shù)組篙顺，將新數(shù)組個長度先定義下
//兩種方法都可以
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 []})
//外層遍歷數(shù)組第一個元素的長度（這里隨便哪個元素都行，因為都是一樣的）
//里層遍歷數(shù)組長度
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))
最后輸出結(jié)果如圖
當(dāng)時一緊張腦子啥也沒想到充择，回來好好看了算法相關(guān)的題目德玫，將js相關(guān)的算法匯總下。
當(dāng)然上面的只是我想到的其中一種解題思路椎麦，肯定會有很多其他辦法也可以實現(xiàn)的宰僧。
三、螺旋矩陣
給定一個包含 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]
這題跟上面的點相似之處
四嘁捷、判斷一個整數(shù)是否是回文數(shù)凤类。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)普气。
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 谜疤。 從右向左讀, 為 121- 。因此它不是一個回文數(shù)现诀。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 夷磕。因此它不是一個回文數(shù)。
參考解答方案
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 個非負(fù)整數(shù) a1坐桩，a2，...封锉，an绵跷，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線成福，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)碾局。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水奴艾。
說明：你不能傾斜容器净当，且 n 的值至少為 2。
示例:
輸入: [1,8,6,2,5,4,8,3,7]
輸出: 49
參考解答方案
var maxArea = function(height) {
let max = 0//假設(shè)最大為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
};
六、最大公共前綴
編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴忽冻。
如果不存在公共前綴真朗，返回空字符串 ""。
示例 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 = ''//假設(shè)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
};
七、三數(shù)之和
給定一個包含 n 個整數(shù)的數(shù)組 nums振诬，判斷 nums 中是否存在三個元素 a，b衍菱，c 赶么，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組脊串。
注意：答案中不可以包含重復(fù)的三元組辫呻。
例如, 給定數(shù)組 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)
})
})
};
八琼锋、最大子序和
描述
給定一個整數(shù)數(shù)組 nums 放闺，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和缕坎。
示例
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大怖侦，為 6。
九谜叹、最接近的三數(shù)之和
給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標(biāo)值 target匾寝。找出 nums 中的三個整數(shù)，使得它們的和與 target 最接近荷腊。返回這三個數(shù)的和艳悔。假定每組輸入只存在唯一答案。
例如女仰，給定數(shù)組 nums = [-1猜年，2，1疾忍，-4], 和 target = 1.
與 target 最接近的三個數(shù)的和為 2. (-1 + 2 + 1 = 2).
十乔外、爬樓梯
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂一罩。
每次你可以爬 1 或 2 個臺階袁稽。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)擒抛。
例如：
輸入： 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]) //
}
}
}
//這是一個實現(xiàn)乘積的遞歸算法
function getCJ(n){
if(n=1){
return 1
}
return n*getCJ(n-1)
}
//2.在計算每一種組合內(nèi)部有多少排列方式
for (let n =0;n<arr.length;n++){
let item = arr[n]
//2.1當(dāng)組合中都是1或者都是2時候，只有1種排列方式
if(item.indexOf(0)>-1){
index +=1
//2.1當(dāng)組合中的1或者2只有1個的時候排列方式為 當(dāng)前數(shù)組元素相加的和
}else if((item.indexOf(1)>-1)){
index += item[0] +item[1]
}else{
//2.3最復(fù)雜的情況 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
