#### 1\. 數組去重和排序的多種實現算法
**數組去重**
[https://blog.csdn.net/weixin\_42412046/article/details/81459294](https://blog.csdn.net/weixin_42412046/article/details/81459294)
* indexOf / includes
* 雙循環
* 先排序，在相鄰比較（基于正則）
~~~javascript
let ary = [12, 23, 12, 15, 25, 23, 25, 14, 16];
ary.sort((a, b) => a - b);
let str = ary.join('@') + '@';
let reg = /(\d+@)\1*/g;
ary = [];
str.replace(reg, (n, m) => {
m = Number(m.slice(0, m.length - 1));
ary.push(m);
});
console.log(ary);
~~~
* 對象鍵值對
* Set
~~~javascript
let ary = [12, 23, 12, 15, 25, 23, 25, 14, 16];
ary = [...new Set(ary)];
console.log(ary);
~~~
**數組排序**
* 冒泡排序
~~~javascript
function bubble(ary){
let temp=null;
// 外層循環I控制比較的輪數
for(let i=0;i<ary.length-1;i++){
// 里層循環控制每一輪比較的次數J
for(let j=0;j<ary.length-1-i;j++){
if(ary[j]>ary[j+1]){
// 當前項大于后一項
temp=ary[j];
ary[j]=ary[j+1];
ary[j+1]=temp;
}
}
}
return ary;
}
let ary = [12,8,24,16,1];
ary=bubble(ary);
console.log(ary);
~~~
* 插入排序
~~~javascript
function insert(ary){
// 1.準備一個新數組，用來存儲抓到手里的牌，開始先抓一張牌進來
let handle=[];
handle.push(ary[0]);
// 2.從第二項開始依次抓牌，一直到把臺面上的牌抓光
for(let i=1;i<ary.length;i++){
// A是新抓的牌
let A=ary[i];
// 和HANDDLE手里的牌依次比較（從后向前比）
for(let j=handle.length-1;j>=0;j--){
// 每一次要比較的手里的牌
let B=handle[j];
// 如果當前新牌A比要比較的牌B大了，把A放到B的后面
if(A>B){
handle.splice(j+1,0,A);
break;
}
// 已經比到第一項，我們把新牌放到手中最前面即可
if(j===0){
handle.unshift(A);
}
}
}
return handle;
}
let ary = [12,8,24,16,1];
ary=insert(ary);
console.log(ary);
~~~
* 快速排序
~~~javascript
function quick(ary){
// 4.結束遞歸（當ARY中小于等于一項，則不用處理）
if(ary.length<=1){
return ary;
}
// 1.找到數組的中間項，在原有的數組中把它移除
let middleIndex=Math.floor(ary.length/2);
let middleValue=ary.splice(middleIndex,1)[0];
// 2.準備左右兩個數組，循環剩下數組中的每一項，比當前項小的放到左邊數組中，反之放到右邊數組中
let aryLeft=[],
aryRight=[];
for(let i=0;i<ary.length;i++){
let item=ary[i];
item<middleValue?aryLeft.push(item):aryRight.push(item);
}
// 3.遞歸方式讓左右兩邊的數組持續這樣處理，一直到左右兩邊都排好序為止（最后讓左邊+中間+右邊拼接成為最后的結果）
return quick(aryLeft).concat(middleValue,quick(aryRight));
}
let ary = [12,8,15,16,1,24];
ary=quick(ary);
console.log(ary);
~~~
#### 2.數組扁平化的N種實現方案
~~~javascript
let arr = [
[1, 2, 2],
[3, 4, 5, 5],
[6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10
];
//=>使用ES6中提供的 Array.prototype.flat 處理
// arr = arr.flat(Infinity);
//=>把數組直接變為字符串即可（數組TOSTRING之后，不管你有多少級，最后都會變為以逗號分隔的字符串，沒有中括號和所謂的層級了），相當于直接的扁平化了
// arr = arr.toString().split(',').map(item => {
// return Number(item);
// });
//=>JSON.stringify也可以扁平化數組
// arr = JSON.stringify(arr).replace(/(\[|\])/g, '').split(',').map(item => Number(item));
//=>基于數組的some方法進行判斷檢測：驗證數組中的某一項有沒有符合函數中提供的規則的
// while (arr.some(item => Array.isArray(item))) {
// arr = [].concat(...arr);
// }
//=>自己遞歸處理
~ function () {
function myFlat() {
let result = [],
_this = this;
//=>循環ARR中的每一項，把不是數組的存儲到新數組中
let fn = (arr) => {
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (Array.isArray(item)) {
fn(item);
continue;
}
result.push(item);
}
};
fn(_this);
return result;
}
Array.prototype.myFlat = myFlat;
}();
arr = arr.myFlat();
~~~
#### 3.阿里面試題之斐波那契數列
請實現一個fibonacci \[?f?b??nɑ?t?i\] 函數，要求實現以下的功能：
斐波那契數列為：\[1,1,2,3,5,8,13,21,…\]
fibonacci(0) -> 1
fibonacci(4) -> 5
……
~~~javascript
function fibonacci(count) {
function fn(count, curr = 1, next = 1) {
if (count == 0) {
return curr;
} else {
return fn(count - 1, next, curr + next);
}
};
return fn(count);
}
~~~
#### 4.字節跳動經典算法題
~~~javascript
/*
* 輸入一個正數N，輸出所有和為N的連續正數序列
* 例如：輸入15
* 結果：[[1,2,3,4,5],[4,5,6],[7,8]]
*/
function createArr(n,len){
let arr=new Array(len).fill(null),
temp=[];
arr[0]=n;
arr=arr.map((item,index)=>{
if(item===null){
item=temp[index-1]+1;
}
temp.push(item);
return item;
});
return arr;
}
function fn(count){
let result=[];
//=>求出中間值
let middle=Math.ceil(count/2);
//從1開始累加
for(let i=1;i<=middle;i++){
//控制累加多少次
for(let j=2;;j++){
//求出累加多次的和
let total=(i+(i+j-1))*(j/2);
if(total>count){
break;
}else if(total===count){
result.push(createArr(i,j));
break;
}
}
}
return result;
}
~~~
==========================================
解答
~~~
// let ary = [12, 23, 12, 15, 25, 15, 25, 14, 16];
/*相鄰項的處理方案*/
// ary.sort((a,b)=>a-b);
// ary=ary.join('@')+'@';
// let reg=/(\d+@)\1*/g,
// arr=[];
// ary.replace(reg,(val,group1)=>{
// // arr.push(Number(group1.slice(0,group1.length-1)));
// arr.push(parseFloat(group1));
// });
// console.log(arr);
/*拿數組中的每項向新容器中存儲，如果已經存儲過了，把當前項干掉*/
/*let obj={};
for(let i=0;i<ary.length;i++){
let item=ary[i];
if(typeof obj[item]!=='undefined'){
ary[i]=ary[ary.length-1];
ary.length--;
i--;
continue;
}
obj[item]=item;
}
obj=null;
console.log(ary);*/
/* SET */
// let arr = Array.from(new Set(ary));
// console.log(arr);
/*拿出當前項和后面的內容進行比較*/
/*for(let i=0;i<ary.length-1;i++){
let item=ary[i],
args=ary.slice(i+1);
if(args.indexOf(item)>-1){
//包含：我們可以把當前項干掉
// splice刪除
// 1. 原來數組改變，這樣如果i繼續++，則會產生數組塌陷
// 2. 性能不好：當前項一旦刪除，后面項索引都要變
// ary.splice(i,1);
// i--;
//賦值為null，后續filter一次
// ary[i]=null;
//用最后一項替換
ary[i]=ary[ary.length-1];
ary.length--;
i--;
}
}
// ary=ary.filter(item=>item!==null);
console.log(ary);
*/
/*數組扁平化*/
/*let arr = [
[1, 2, 2],
[3, 4, 5, 5],
[6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10
];*/
/*ES6方法直接實現*/
// arr=arr.flat(Infinity);
/*轉換為字符串*/
// arr=arr.toString().split(',').map(item=>parseFloat(item));
// arr=JSON.stringify(arr).replace(/(\[|\])/g,'').split(',').map(item=>parseFloat(item));
/*循環驗證是否為數組*/
// while (arr.some(item => Array.isArray(item))) {
// arr = [].concat(...arr);
// }
/*(function () {
function myFlat() {
let result = [],
_this = this;
//=>循環ARR中的每一項，把不是數組的存儲到新數組中
let fn = (arr) => {
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (Array.isArray(item)) {
fn(item);
continue;
}
result.push(item);
}
};
fn(_this);
return result;
}
Array.prototype.myFlat = myFlat;
})();
arr = arr.myFlat();*/
// console.log(arr);
/*斐波那契數列*/
/*function fibonacci(n){
if(n<=1) return 1;
let arr=[1,1];
//=>即將要創建多少個
let i=n+1-2;
while(i>0){
let a=arr[arr.length-2],
b=arr[arr.length-1];
arr.push(a+b);
i--;
}
return arr[arr.length-1];
}*/
/*
function fibonacci(count) {
function fn(count, curr = 1, next = 1) {
if (count == 0) {
return curr;
} else {
return fn(count - 1, next, curr + next);
}
};
return fn(count);
}
*/
/*
* 輸入一個正數N，輸出所有和為N的連續正數序列
* 例如：輸入15
* 結果：[[1,2,3,4,5],[4,5,6],[7,8]]
*/
function createArr(n,len){
let arr=new Array(len).fill(null),
temp=[];
arr[0]=n;
arr=arr.map((item,index)=>{
if(item===null){
item=temp[index-1]+1;
}
temp.push(item);
return item;
});
return arr;
}
function fn(count){
let result=[];
//=>求出中間值
let middle=Math.ceil(count/2);
//從1開始累加
for(let i=1;i<=middle;i++){
//控制累加多少次
for(let j=2;;j++){
//求出累加多次的和
let total=(i+(i+j-1))*(j/2);
if(total>count){
break;
}else if(total===count){
result.push(createArr(i,j));
break;
}
}
}
return result;
}
console.log(fn(4));
console.log(fn(5));
console.log(fn(10));
console.log(fn(15));
~~~
