# 反转二叉树
var obj = {
'id': '4',
'left': {
'id': '2',
'left': {
'id': '1',
'left': null,
'right': null
},
'right': {
'id': '3',
'left': null,
'right': null
}
},
'right': {
'id': '7',
'left': {
'id': '6',
'left': null,
'right': null
},
'right': {
'id': '9',
'left': null,
'right': null
}
}
}
console.log(obj);
function invertTree(root) {
if (root !== null) {
var temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
}
return root
};
invertTree(obj)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 排序
# 冒泡排序
//思路：先比较一轮一次，然后用for循环比较一轮多次，然后再加for循环比较多轮多次
//从大到小排序
//比较轮数
function bubbleSort(arr){
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
//每轮比较次数，次数=长度-1-此时的轮数
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
} //end if
}//end for 次数
} //end for 轮数
return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 选择排序
function selectSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
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
# 插入排序 (打牌)
function insertSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex+1] = arr[preIndex]
preIndex--;
}
arr[preIndex+1] = current
}
return arr;
}
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
# 希尔排序
var arr = [3, 2, 4, 7, 1, 5, 9, 6, 8];
var gops = [5, 3, 1];
for(var g=0; g<gops.length;g++) {
for(var i=gops[g]; i<arr.length; i++){
var temp=arr[i];
for(var j=i; j>=gops[g] && arr[j-gops[g]]>temp;j-=gops[g]){
arr[j] = arr[j-gops[g]];
}
arr[j] = temp
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 快速排序
function quickSort(arr) {
if (arr.length == 0) {
return [];
}
var pivot = arr[0];
var lesser = [];
var greater = [];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
lesser.push(arr[i])
} else {
greater.push(arr[i])
}
}
return quickSort(lesser).concat(pivot,quickSort(greater));
}
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
# 数组去重
const arr = [];
// 生成[0, 100000]之间的随机数
for (let i = 0; i < 100000; i++) {
arr.push(0 + Math.floor((100000 - 0 + 1) * Math.random()))
}
// ...实现算法
console.time('test');
arr.unique();
console.timeEnd('test');
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# indexOf
Array.prototype.unique = function () {
const newArray = [];
this.forEach(item => {
if (newArray.indexOf(item) === -1) {
newArray.push(item)
}
})
return newArray;
}
Array.prototype.unique = function() {
return this.filter((item,index)=>{
return this.indexOf(item) === index
})
}
test1: 3766.324951171875ms
test2: 4887.201904296875ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# sort
Array.prototype.unique = function () {
const newArray = [];
this.sort();
for (let i = 0; i < this.length; i++) {
if (this[i] != this[i + 1]) {
newArray.push(this[i])
}
}
return newArray;
}
test: 4300.39990234375ms
Array.prototype.unique = function () {
const newArray = [];
this.sort();
for (let i = 0; i < this.length; i++) {
if (this[i] != newArray[newArray.length-1]) {
newArray.push(this[i])
}
}
return newArray;
}
test1: 121.6259765625ms
test2: 123.02197265625ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# hash
- 无法区分隐式类型转换成字符串后一样的值，比如 1 和 '1'
- 无法处理复杂数据类型，比如对象（因为对象作为 key 会变成 [object Object]）
- 特殊数据，比如 'proto'，因为对象的 proto 属性无法被重写
Array.prototype.unique = function () {
const newArray = [];
const tmp = {};
for (let i = 0; i < this.length; i++) {
if (!tmp[typeof this[i] + JSON.stringify(this[i])]) {
tmp[typeof this[i] + JSON.stringify(this[i])] = 1;
newArray.push(this[i]);
}
}
return newArray;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# Map
Array.prototype.unique = function () {
const tmp = new Map();
return this.filter(item => {
return !tmp.has(item) && tmp.set(item, 1)
})
}
1
2
3
4
5
6
2
3
4
5
6
# includes
Array.prototype.unique = function () {
const newArray = [];
this.forEach(item => {
if (!newArray.includes(item)) {
newArray.push(item);
}
});
return newArray;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9