【前端面试】七、算法-递归、拷贝等

目录

1.常考算法

2.遍历方法

3.链式调用

4.递归

5.拷贝和比较

---

1.常考算法

1. 排序算法：快速排序、归并排序、堆排序等。

2. 查找算法：二分查找、哈希表查找等。

3. 动态规划：解决最优化问题，如斐波那契数列、最长公共子序列等。

4. 图论算法：最短路径（Dijkstra、Floyd-Warshall）、拓扑排序等。

5. 字符串处理：KMP算法、正则表达式匹配等。

2.遍历方法

3.链式调用

• 数组的很多操作可以构成链式操作，类似这样的格式：…map().filter(…).sort(…).map(….)
• 链式操作就是对象方法返回类型是自身的。比如map是属于数组的方法，它返回数组，所以构成了链式操作
• 优势：语义清晰、思考方便，数据量小的时候很有用(<1W)
• 问题：性能、空间

4.递归

• 条件：递归通常需要初始条件和递归表达式
• 阶乘：n! = n x (n-1) !   

     // 阶乘
    function factorial(n) {
      if (n === 1) return 1
      return n * factorial(n - 1)
    }

• 斐波那契：f(1) = 1, f(2) = 1，f(n) = f(n-1) + f(n-2), n>2 

     // 斐波那契数列 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));

• DOM结点的绝对位置

offsetLeft、offsetRight相对于offsetParent的位置
Element.getBoundingClientRect()相对于视窗的位置，受滚动的影响

 // 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
      }
   }

5.拷贝和比较

push/pop/shift/unshift/splice：都在原始数据上进行修改

concat/slice/map/reduce：都会对原始数据进行浅拷贝

    // 递归实现深拷贝
    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();