#### 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));
~~~
