常考算法
排序算法：快速排序、归并排序、堆排序等。
查找算法：二分查找、哈希表查找等。
动态规划：解决最优化问题，如斐波那契数列、最长公共子序列等。
图论算法：最短路径（Dijkstra、Floyd-Warshall）、拓扑排序等。
字符串处理：KMP算法、正则表达式匹配等。
遍历方法总结
链式调用
- 数组的很多操作可以构成链式操作，类似这样的格式：…map().filter(…).sort(…).map(….)
- 链式操作就是对象方法返回类型是自身的。比如map是属于数组的方法，它返回数组，所以构成了链式操作
- 优势：语义清晰、思考方便，数据量小的时候很有用(<1W)
- 问题：性能、空间
递归
递归通常需要初始条件和递归表达式
阶乘：n! = n x (n-1) !
斐波那契：f(1) = 1, f(2) = 1，f(n) = f(n-1) + f(n-2), n>2
拷贝
push/pop/shift/unshift/splice：都在原始数据上进行修改
concat/slice/map/reduce：都会对原始数据进行浅拷贝
DOM结点的绝对位置
offsetLeft、offsetRight相对于offsetParent的位置
Element.getBoundingClientRect()相对于视窗的位置，受滚动的影响
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>递归</title>
</head>
<body>
<script>
// 阶乘
function factorial(n) {
if (n === 1) return 1
return n * factorial(n - 1)
}
// 斐波那契数列 1 1 2 3 5 8 13 21 34 55 89 144
function fibonacci(n) {
if (n === 1 || n === 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
// 从底端构造递归
function fibonacci1(n) {
let [a,b] = [1,1]
for(let i = 3; i <= n; i++) {
[a,b] = [b, a + b]
}
return b
}
// console.log('测试 fibonacci1=============');
// console.log(fibonacci1(10));
function fibonacci2(n) {
return Array(n - 2).fill(0).reduce(([a,b],_) => {
return [b, a + b]
}, [1,1])[1]
}
// console.log('测试 fibonacci2=============');
// console.log(fibonacci2(10));
// 递归实现深拷贝
function deepClone(obj) {
if (typeof obj !== 'object' || obj === null) return obj
// const newObj = Array.isArray(obj) ? [] : {}
// const newObj = obj instanceof Array ? [] : {}
// const newObj = obj.constructor === Array ? [] : {}
// const newObj = Object.prototype.toString.call([]) === '[object Array]' ? [] : {}
const newObj = new obj.constructor()
for(let key in obj) {
if(obj.hasOwnProperty(key)) {
newObj[key] = deepClone(obj[key])
}
}
return newObj
}
// 测试用例
function testDeepClone() {
console.log("测试普通对象:");
const obj1 = { a: 1, b: { c: 2 } };
const clonedObj1 = deepClone(obj1);
console.assert(obj1 !== clonedObj1, "对象应该是不同的引用");
console.assert(obj1.b !== clonedObj1.b, "嵌套对象也应该是不同的引用");
console.assert(obj1.b.c === clonedObj1.b.c, "嵌套对象的属性值应该相等");
console.log("测试数组:");
const arr1 = [1, 2, [3, 4]];
const clonedArr1 = deepClone(arr1);
console.assert(arr1 !== clonedArr1, "数组应该是不同的引用");
console.assert(arr1[2] !== clonedArr1[2], "嵌套数组也应该是不同的引用");
console.assert(arr1[2][0] === clonedArr1[2][0], "嵌套数组的元素值应该相等");
console.log("测试特殊对象（Date）:");
const date1 = new Date();
const clonedDate1 = deepClone(date1);
console.assert(date1 !== clonedDate1, "Date 对象应该是不同的引用");
console.assert(date1.getTime() === clonedDate1.getTime(), "Date 的时间戳应该相等");
// console.log("测试特殊对象（RegExp）:"); // 失败
// const reg1 = /hello/g;
// const clonedReg1 = deepClone(reg1);
// console.assert(reg1 !== clonedReg1, "RegExp 对象应该是不同的引用");
// console.assert(reg1.source === clonedReg1.source && reg1.global === clonedReg1.global, "RegExp 的属性和标志应该相等");
// console.log("测试循环引用:"); // 失败
// const obj2 = {};
// obj2.self = obj2;
// const clonedObj2 = deepClone(obj2);
// console.assert(obj2 !== clonedObj2, "对象应该是不同的引用");
// console.assert(clonedObj2.self === clonedObj2, "循环引用应该被正确处理");
console.log("所有测试通过！");
}
// testDeepClone();
// 深度比较
function deepCompare(a,b){
if (a === null || typeof a !== 'object' || b === null || typeof b !== 'object') {
return a === b
}
// Object.getOwnPropertyDescriptors 方法会返回对象自身的所有属性描述符，包括不可枚举的属性
const propsA = Object.getOwnPropertyDescriptors(a)
const propsB = Object.getOwnPropertyDescriptors(b)
if(Object.keys(propsA).length !== Object.keys(propsB).length) return false
return Object.keys(propsA).every(key => deepCompare(a[key],b[key]))
}
// 测试用例
function testDeepCompare() {
console.log("测试基本相等性:");
console.assert(deepCompare(1, 1), "1 应该等于 1");
console.assert(!deepCompare(1, 2), "1 不应该等于 2");
console.assert(deepCompare(null, null), "null 应该等于 null");
console.assert(deepCompare(undefined, undefined), "undefined 应该等于 undefined");
console.assert(!deepCompare(null, undefined), "null 不应该等于 undefined");
console.log("测试对象比较:");
const obj1 = { a: 1, b: { c: 2 } };
const obj2 = { a: 1, b: { c: 2 } };
const obj3 = { a: 1, b: { c: 3 } };
console.assert(deepCompare(obj1, obj2), "obj1 应该等于 obj2");
console.assert(!deepCompare(obj1, obj3), "obj1 不应该等于 obj3");
console.log("测试数组比较:");
const arr1 = [1, 2, [3, 4]];
const arr2 = [1, 2, [3, 4]];
const arr3 = [1, 2, [3, 5]];
console.assert(deepCompare(arr1, arr2), "arr1 应该等于 arr2");
console.assert(!deepCompare(arr1, arr3), "arr1 不应该等于 arr3");
// console.log("测试循环引用（此实现可能无法正确处理）:");
// const obj4 = {};
// obj4.self = obj4;
// const obj5 = {};
// obj5.self = obj5;
// 注意：此实现可能无法正确处理循环引用，因为它会陷入无限递归
// 这里我们假设它不会处理循环引用，并跳过这个测试
// console.assert(deepCompare(obj4, obj5), "循环引用对象应该相等（但这里不测试）");
console.log("所有测试通过！");
}
// testDeepCompare();
// DOM节点的绝对位置
function getLayout1(el) {
if (!el) return;
const layout = {
width: el.offsetWidth,
height: el.offsetHeight,
top: el.offsetTop,
left: el.offsetLeft
}
if(el.offsetParent) {
const parentLayout = getLayout1(el.offsetParent)
layout.top += parentLayout.top
layout.left += parentLayout.left
}
return layout
}
function getLayout2(el) {
if (!el) return;
let left = el.offsetLeft
let top = el.offsetTop
let p = el.offsetParent
while(p) {
left += p.offsetLeft
top += p.offsetTop
p = p.offsetParent
}
return {
width: el.offsetWidth,
height: el.offsetHeight,
top,
left
}
}
</script>
</body>
</html>