算法由浅入深（二）

[kekobin]

栈内存与堆内存 、浅拷贝与深拷贝

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。

堆

• 定义

堆数据结构是一种树状结构。
它的存取数据的方式，与书架与书非常相似。我们不关心书的放置顺序是怎样的，只需知道书的名字就可以取出我们想要的书了。
好比在 JSON 格式的数据中，我们存储的 key-value 是可以无序的，只要知道 key，就能取出这个 key 对应的 value。

堆与栈比较

• 堆是动态分配内存，内存大小不一，也不会自动释放。
• 栈是自动分配相对固定大小的内存空间，并由系统自动释放。
• 栈，线性结构，后进先出，便于管理。
• 堆，一个混沌，杂乱无章，方便存储和开辟内存空间。

栈内存与堆内存

let a1 = 0; // 栈内存
let a2 = "this is string" // 栈内存
let a3 = null; // 栈内存
let b = { x: 10 }; // 变量 b 存在于栈中，{ x: 10 } 作为对象存在于堆中
let c = [1, 2, 3]; // 变量 c 存在于栈中，[1, 2, 3] 作为对象存在于堆中

引用类型发生复制

let a = { x: 10, y: 20 }
let b = a;
b.x = 5;
console.log(a.x); // 5

浅拷贝与深拷贝

上面讲的引用类型的复制就是浅拷贝，复制得到的访问地址都指向同一个内存空间。所以修改了其中一个的值，另外一个也跟着改变了。

深拷贝：复制得到的访问地址指向不同的内存空间，互不相干。所以修改其中一个值，另外一个不会改变。

深拷贝的的复制过程

let a = { x: 10, y: 20 }
let b = JSON.parse(JSON.stringify(a));
b.x = 5;
console.log(a.x); // 10
console.log(b.x); // 5

深拷贝方式

数组

arr.slice(0)
arr.concat()
[...arr]
JSON.parse(JSON.stringify(arr)) // 这种方式在数据量大时有性能问题

对象

一、对象的循环

//  循环 copy 对象
let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let obj2 = copy2(obj)
function copy2(obj) {
    let cObj = {};
    for(var key in obj){
      cObj[key] = obj[key]
    }
    return cObj
}
obj2.name = "king2"
console.log(obj) // {id: "0", name: "king", sex: "man"}
console.log(obj2) // {id: "0", name: "king2", sex: "man"}

二、JSON.parse 与 JSON.stringify

var obj1 = {
    x: 1, 
    y: {
        m: 1
    },
    a:undefined,
    b:function(a,b){
      return a+b
    },
    c:Symbol("foo")
};
var obj2 = JSON.parse(JSON.stringify(obj1));
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 1, y: {m: 1}}
obj2.y.m = 2; //修改obj2.y.m
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 2, y: {m: 2}}

可实现多维对象的深拷贝。

注意：进行JSON.stringify() 序列化的过程中，undefined、任意的函数以及 symbol 值，在序列化过程中会被忽略（出现在非数组对象的属性值中时）或者被转换成 null（出现在数组中时）。

三、es6 扩展运算

let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let {...obj4} = obj
obj4.name = "king4"
console.log(obj) //{id: "0", name: "king", sex: "man"}
console.log(obj4) //{id: "0", name: "king4", sex: "man"}

• 只能对一维对象进行深拷贝。

四、Object.assign()
Object.assign() 只能实现一维对象的深拷贝。

var obj1 = {x: 1, y: 2}, obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 1, y: 2}

obj2.x = 2; // 修改 obj2.x
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 2, y: 2}

var obj1 = {
    x: 1, 
    y: {
        m: 1
    }
};
var obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: {m: 1}}
console.log(obj2) // {x: 1, y: {m: 1}}

obj2.y.m = 2; // 修改 obj2.y.m
console.log(obj1) // {x: 1, y: {m: 2}}
console.log(obj2) // {x: 1, y: {m: 2}}

通用深拷贝方法

简陋版

function deepClone(obj) {
	var toString = Object.prototype.toString;
	var o = toString.call(obj) === '[object Array]' ? [] : {};

	if (typeof obj !== 'object') return obj;

	for (var i in obj) {
		o[i] = typeof obj[i] === 'object' ? deepClone(obj[i]) : obj[i]
	}

	return o;
}

但上面的深拷贝方法遇到循环引用，会陷入一个循环的递归过程，从而导致爆栈。如：

var obj1 = {
    x: 1, 
    y: 2
};
obj1.z = obj1;
var obj2 = deepClone(obj1);

终极版

function deepClone(obj, parent = null){ 
  let result; // 最后的返回结果

  let _parent = parent; // 防止循环引用
  while(_parent){
    if(_parent.originalParent === obj){
      return _parent.currentParent;
    }
    _parent = _parent.parent;
  }
  
  if(obj && typeof obj === "object"){ // 返回引用数据类型(null已被判断条件排除))
    if(obj instanceof RegExp){ // RegExp类型
      result = new RegExp(obj.source, obj.flags)
    }else if(obj instanceof Date){ // Date类型
      result = new Date(obj.getTime());
    }else{
      if(obj instanceof Array){ // Array类型
        result = []
      }else{ // Object类型，继承原型链
        let proto = Object.getPrototypeOf(obj);
        result = Object.create(proto);
      }
      for(let key in obj){ // Array类型 与 Object类型 的深拷贝
        if(obj.hasOwnProperty(key)){
          if(obj[key] && typeof obj[key] === "object"){
            result[key] = deepClone(obj[key],{ 
              originalParent: obj,
              currentParent: result,
              parent: parent
            });
          }else{
            result[key] = obj[key];
          }
        }
      }
    }
  }else{ // 返回基本数据类型与Function类型,因为Function不需要深拷贝
    return obj
  }
  return result;
}

• 推荐在循环对象属性的时候，使用for...in,在遍历数组的时候的时候使用for...of。
• for...in循环出的是key，for...of循环出的是value
• 作用于数组的for-in循环除了遍历数组元素以外,还会遍历自定义属性

递归

基本上，所有的递归问题都可以用递推公式来表示，比如:

f(n) = f(n-1) + 1; 
// 其中，f(1) = 1 

为什么使用递归 ？递归的优缺点 ？

• 优点：代码的表达力很强，写起来简洁。
• 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

什么样的问题可以用递归解决呢 ？

一个问题只要同时满足以下 3 个条件，就可以用递归来解决。

• 问题的解可以分解为几个子问题的解。何为子问题 ？就是数据规模更小的问题。
  比如，前面讲的电影院的例子，你要知道，自己在哪一排的问题，可以分解为前一排的人在哪一排这样一个子问题。
• 问题与子问题，除了数据规模不同，求解思路完全一样
  比如电影院那个例子，你求解自己在哪一排的思路，和前面一排人求解自己在哪一排的思路，是一模一样的。
• 存在递归终止条件
  比如电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是 f(1) = 1，这就是递归的终止条件。

递归常见问题及解决方案

• 警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。
• 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。

如何实现递归 ？

1. 递归代码编写
   写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

2. 递归代码理解
   对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。
   理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

看一个多叉树的例子

叶子结点：就是深度为 0 的结点，也就是没有孩子结点的结点，简单的说就是一个二叉树任意一个分支上的终端节点。
数据结构格式，参考如下代码：

const json = {
  name: 'A',
  children: [
    {
      name: 'B',
      children: [
        {
          name: 'E',
        },
        {
          name: 'F',
        },
        {
          name: 'G',
        }
      ]
    },
    {
      name: 'C',
      children: [
        {
          name: 'H'
        }
      ]
    },
    {
      name: 'D',
      children: [
        {
          name: 'I',
        },
        {
          name: 'J',
        }
      ]
    }
  ]
}

我们如何获取根节点的所有叶子节点个数呢 ？

递归代码如下：

function getLeafCount(treeJson) {
  if (!treeJson.children) {
    return 1;
  } else {
    let count = 0;

    for (let i in treeJson.children) {
      count += getLeafCount(treeJson.children[i])
    }
    return count;
  }
}