常见算法题
ALEX CODE PARK 2020-02-17
JavaScript
ES6
算法
# 数组去重
# 双层循环
function unique(arr) {
let res = [];
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < res.length; j++) {
if (arr[i] === res[j]) {
break;
}
}
// 意味着 res全部扫描完都没有该元素
if (j == res.length) {
res.push(arr[i]);
}
}
return res;
}
let test1 = [1, 1, "a", "a"];
console.log(unique(test1));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
错误写法:
function unique(arr) {
let res = [];
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < res.length; j++) {
if (arr[i] === res[j]) {
// 无法推入第一个数
if (j == res.length) {
res.push(arr[i]);
}
break;
}
}
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# indexOf 简化内层
利用 indexOf 找不到元素会返回-1
function unique(arr) {
let res = [];
for (var i = 0; i < arr.length; i++) {
let cur = arr[i];
if (res.indexOf(cur) === -1) {
res.push(cur);
}
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 排序后去重
先排序后比较当前元素与前一个元素,性能优于 indexof
留意该代码对边界的处理 十分巧妙
function unique(arr) {
let res = [];
let pre;
let sorted = arr.concat().sort();
for (let i = 0; i < sorted.length; i++) {
// !i 处理第一个元素
if (!i || pre !== sorted[i]) {
res.push(sorted[i]);
}
// 下次循环之前先将这次的值赋给pre 实现与上一个元素比较
pre = sorted[i];
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# filter
API:filter((item,index,arr)=>{})
function unique(arr) {
let res = arr.filter((item, index, arr) => {
return arr.indexOf(item) == index;
});
return res;
}
1
2
3
4
5
6
2
3
4
5
6
# Object
我们可以发现,是有问题的,因为 1 和 '1' 是不同的,但是这种方法会判断为同一个值,这是因为对象的键值只能是字符串,所以我们可以使用 typeof item + item
拼成字符串作为 key 值来避免这个问题
function unique(arr) {
let obj = {};
let res = arr.filter((item, index, arr) => {
// return obj.hasOwnProperty(item) ? false : (obj[item] = true);
return obj.hasOwnProperty(typeof item + item)
? false
: (obj[typeof item + item] = true);
});
return res;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# ES6
- Set
[...new Set(arr)];
1
- Map
!myMap.has(a) && myMap.set(a, 1)
包含隐式转换
function unique(arr) {
let myMap = new Map();
return arr.filter(item => !myMap.has(a) && myMap.set(a, 1));
}
1
2
3
4
2
3
4
# 特殊类型比较
- NaN:
NaN === NaN //false
使用typeof NaN //number
的特性 - 对象:
JSON.stringify
# 排序算法
# 冒泡排序
当前项与后项比较 根据结果决定是否交换位置
ES6 解构赋值可用来交换位置[a,b] = [b,a]
function comp(arr, index) {
let temp;
let preI = index;
let nextI = index + 1;
if (arr[preI] > arr[nextI]) {
temp = arr[preI];
arr[preI] = arr[nextI];
arr[nextI] = temp;
}
console.log(arr);
return arr;
}
function bubble(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i; j++) {
arr = comp(arr, j);
}
}
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 插入排序
- 先摸第一项
- 从第二项依次向后抓牌
- 和手里牌比较 两种插入情况
- 比当前牌大 插入当前的后一位
- 比全部都小 插入第一位
⚠️**splice(i,0,'a')
会插入在 i 前面**
function insert(arr) {
let handle = [];
handle.push(arr[0]);
for (let i = 1; i < arr.length; i++) {
for (let j = handle.length - 1; j >= 0; j--) {
if (arr[i] > handle[j]) {
handle.splice(j + 1, 0, arr[i]);
break;
}
if (j === 0) {
handle.unshift(arr[i]);
}
}
}
return handle;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 快速排序
- 先取出中间值
- 将原数组剩下的元素依次与中间值比较 小放左 大放右
- 递归
- 返回 拼接数组
⚠️**splice(i,1)
返回值是数组 取得元素需跟[0]
**
function quick(ary) {
if (ary.length <= 1) return ary;
let midIndex = Math.floor(ary.length / 2);
let mid = ary.splice(midIndex, 1)[0];
let left = [],
right = [];
for (let i = 0; i < ary.length; i++) {
let item = ary[i];
item < mid ? left.push(item) : right.push(item);
}
return quick(left).concat(mid, quick(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13