LiBK-铁甲依然在
0%

发表于 分类于

犀牛书3.91节中提到”一个值可以转换为另一个值，并不意味着这两个值是相等的“，比如undefined用在期待布尔值的地方，可以被转换成布尔值false，但undefined !== false。

JavaScript中的==运算符会涉及到一系列的隐式类型转换，有时候运行的结果会让初学者困惑。下面参考ECMA-262对==运算的内部执行逻辑进行分析。

表达式x == y，返回的结果为true或者false。其执行逻辑如下：

  1. 如果x和y的类型相同，那么执行x === y
  2. 如果x和y分别为null和undefined，那么返回true。
  3. 如果x是Number，y是String，那么执行x == ToNumber(y)，并返回结果。
  4. 如果x是String，y是Number，同上。
  5. 如果x是Boolean，那么执行ToNumber(x) == y，并返回结果。
  6. 如果y是Boolean，同上。
  7. 如果x是String/Number/Symbol之一，y是Object，那么执行x == ToPrimitive(y)，并返回结果。
  8. 如果y是String/Number/Symbol之一，x是Object，同上。
  9. 否则，返回false。

上述的执行逻辑有几点需要着重注意：

阅读全文 »

发表于 分类于

JavaScript是弱类型的语言，在很多情况下会涉及到隐式类型转换，这种类型转换在JavaScript引擎内部进行。通过参考ECMA-262，我们对几种常见的隐式类型转换在引擎内部的执行逻辑进行分析。

ToPrimitive( input [ , PreferredType ] )

这个抽象操作有一个参数input（表示需要进行类型转换的数据），还有一个可选参数PreferredType（表示期望转换成的类型）。

如果input是原始值，那么就直接返回输入本身。

如果input是对象，那么进行如下的操作：

阅读全文 »

发表于 分类于

文章开始之前，先来看个例子：

1
2
3
4
5
6
7
8
9
null == 0;//false
null > 0;//false
null < 0;//false
null >= 0;//true

undefined == 0;//false
undefined > 0;//false
undefined < 0;//false
undefined >=0;//false

之前的文章中深入解析过==运算符的执行逻辑，null == 0的结果为false是没有什么疑问的，但是后面的两行代码的结果就又让人困惑了。

接下来，就以x < y为例，参考ECMA-262来对关系比较运算符的执行逻辑进行分析：

阅读全文 »

发表于 分类于

概述

JavaScript对象到原始值转换的复杂性，主要原因在于某些对象类型有不止一种原始值的表示。比如，Date对象可以用字符串表示，也可以用时间戳表示。

因此JavaScript规范定义了多种对象到原始值的转换算法，不同的对象使用不同的转换算法。

对象到原始值转换算法

先来了解两个方法：

  • toString()方法

该方法的任务是返回对象的字符串表示。很多类都定义了自己特有的toString()版本，比如：

1
2
3
4
[1, 2, 3].toString()               // => '1,2,3'
/\d+/g.toString()                  // => '/\\d+/g'
(function(x) {f(x)}).toString()    // => 'function(x) {f(x)}'
(new Date(2020,0,1)).toString()    // => 'Wed Jan 01 2020 00:00:00 GMT+0800 (中国标准时间)'
  • valueOf()方法

这个方法的任务并没有太明确的定义，大体上可以认为它是把对象转换为代表对象的原始值（如果存在）。对象是复合值，且多数对象并不能真正通过一个原始值来表示，因此valueOf()方法默认情况下只返回对象本身，而非返回原始值。特例是Date对象，对valueOf方法进行了重写，返回的是1970.1.1至今的毫秒数：

1
(new Date(2020,0,1)).valueOf()      // 1577808000000

解释完 toString() 和 valueOf() 方法后，进一步解释对象到原始值的转换算法，JavaScript规范定义了三种对象到原始值的转换算法：

  • 偏字符串算法

    首先尝试 toString() 方怯。如果这个方位有定义且返回原始值，则JavaScript使用该原始值（即使这个值不是字符串）。如果 toString() 不存在，或者存在但返回对象， 则 JavaScript 尝试 valueOf () 方怯。如果这个方告存在且返回原始值 ，则 JavaScript 使用该值。否则，转换失败，报 TypeError。

  • 偏数值算法

    与偏字符串算法类似，只不过先尝试 valueOf() 方法，再尝试 toString() 方法。

  • 无偏好算法

    该算法不倾向于任何原始值类型，而是由类定义自己的转换规则。JavaScript内置类型除了Date类都实现了偏数值算法，Date类实现了偏字符串算法。

总结

  1. 对象转换为布尔值

    所有对象都转换为true，不需要用到前面所说的三种算法，像空数组、new Boolean(false)这样的包装对象。

  2. 对象转换为字符串

    JavaScript会首先使用偏字符串算法将它转换为一个原始值，然后将得到的原始值再转换为字符串

  3. 对象转换为数值

    JavaScript会首先使用偏数值算法将它转换为一个原始值，然后再将得到的原始值再转换为数值。

    这里看一个例子：

    1
    2
    3
    Number([])     // => 0
    Number([99])   // => 99
    Number({})     // => NaN

    Number()会使用偏数值算法，先尝试 valueOf() ，由于 Array类继承了默认的valueOf方法，该方法不返回原始值，因此在尝试将数组转换为数值时，最终会调用 toString() 方法。先将 [] 和 [99] 转换为字符串，再将字符串转换为数值。Array定义了自己特有的toString()方法，[] 和 [99] 分别会被转换成空字符串和 ’99‘，再转换成数值0和99。而普通对象调用toString()方法后，会被转换成 [object Object]，再转换成数值就是NaN。

发表于 分类于

历史原因

既然有了null，为什么还设计了undefined，有以下两个历史原因

  1. null的类型被设计成一个对象，在JavaScript中数据类型分为基本类型和引用类型两大类，对象属于引用类型，JavaScript的设计者Brendan Eich觉得表示”无”的值最好不是对象。
  2. JavaScript的最初版本没有包括错误处理机制，发生数据类型不匹配时，往往是自动转换类型或者默默地失败。Brendan Eich觉得，如果null自动转为0，很不容易发现错误。

两者含义的区别

  1. null表示“没有对象”，即此处没有值。Number()作用于null返回0。
  2. undefined表示“缺少值”，即此处应该有一个值，但是还没有定义，或者定义了还没有初始化。Number()作用于undefined返回NaN。
阅读全文 »

发表于 分类于

风格

JavaScript中分号的书写有两种风格：

  • 使用明确的分号标记语句结束，即便这些分号并非必需
  • 尽可能省略分号，只有在极少数情况下才用

一些细节

  1. JavaScript并非任何时候都把换行符当作分号，只是在不隐式添加分号就无法解析代码的情况下才这么做。

    1
    2
    3
    4
    5
    6
    7
    let a
    a
    =
    3
    console.log(a)
    // 上面代码将被解析成如下代码
    let a; a = 3; console.log(a)

  2. 根据上面所述，如果语句以（ 、 ［、／ 、 ＋ 或 － 开头，就有可能被解释为之前语句的一部分 。 实践中以／、＋和－开头的语句极少， 但以 （和［ 开头的语句则并不鲜见， 至少在某种JavaScript 编程风格下经常会看到 。 有的程序员 喜欢在所有这种语句前面都防御性地添加一个分号 ，这样即使它前面的语句被修改 ，删掉了之前末尾的分号，也不会影响当前语句： 

    1
    2
    let x = a
    ;[x, x+1, x+2].forEach(console.log)

  3. 这三种情况，在其后续没有分号时，换行符必定被解析成分号，而不考虑后续的代码能不能被解析成当前语句的一部分：

    • return、throw、yield、break和continue语句，这些语句后的换行符必定会被解释称分号
    • ++ 和 – 操作符
    • 箭头函数的 => 符号

发表于 分类于

二叉搜索树（Binary Search Tree）

二叉树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。支持对数据的快速查找、插入和删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @description: 二叉搜索树节点
 * @param {*} val
 * @param {*} left
 * @param {*} right
 * @return {*}
 */
function BSTNode (val = 0, left = null, right = null) {
  this.val = val
  this.left = left
  this.right = right
}
/**
 * @description: 二叉搜索树
 * @param {*} root
 * @return {*}
 */
function BinarySearchTree (root = null) {
  this.root = root
}
查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @description: 查找数据是否存在二叉搜索树中
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.search = function (root, val) {
  if (!root) {
    return false
  }
  if (val === root.val) {
    return true
  } else if (val < root.val) {
    return this.search(root.left, val)
  } else {
    return this.search(root.right, val)
  }
}
插入
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
/**
 * @description: 在二叉树中插入节点
 * @param {*} root
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.insert = function (root, val) {
  if (!root) {
    return new BSTNode(val)
  }

  if (val < root.val) {
    if (root.left === null) {
      root.left = new BSTNode(val)
    } else {
      this.insert(root.left, val)
    }
  } else if (val > root.val) {
    if (root.right === null) {
      root.right = new BSTNode(val)
    } else {
      this.insert(root.right, val)
    }
  }

  return root
}
删除
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
/**
 * @description: 删除二叉树中的节点
 * @param {*} root
 * @param {*} val
 * @return {*}
 */
BinarySearchTree.prototype.delete = function (root, val) {
  const getMinNode = (cur) => {
    while (cur.left !== null) {
      cur = cur.left
    }
    return cur
  }

  if (!root) {
    return null
  }

  if (root.val === val) {
    if (!root.left) {
      root = root.right
    } else if (!root.right) {
      root = root.left
    } else {
      // 如果左子树和右子树同时不为空，则用右子树的最小节点覆盖要删除的节点
      // 然后再将右子树的最小节点删除
      let minNode = getMinNode(root.right)
      root.val = minNode.val
      root.right = this.delete(root.right, minNode.val)
    }
  } else if (root.val < val) {
    root.right = this.delete(root.right, val)
  } else {
    root.left = this.delete(root.left, val)
  }
  return root
}

发表于 分类于

快速排序

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
/*
 * @Description: quickSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function partition (arr, left, right) {
  let random = Math.floor(Math.random() * (right - left + 1)) + left
  let povit = arr[random]

  ;[arr[random], arr[left]] = [arr[left], arr[random]]
  while (left < right) {
    while (left < right && arr[right] >= povit) {
      right--
    }
    if (left < right) {
      arr[left++] = arr[right]
    }
    while (left < right && arr[left] < povit) {
      left++
    }
    if (left < right) {
      arr[right--] = arr[left]
    }
  }
  arr[left] = povit
  return left
}
function quickSort (arr, left = 0, right = arr.length - 1) {
  if (!arr || arr.length < 2) {
    return
  }
  if (right > left) {
    let index = partition(arr, left, right)
    quickSort(arr, left, index - 1)
    quickSort(arr, index + 1, right)
  }
}

发表于 分类于

问题描述

给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，等于K的元素放到数组的中间

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * @Description: 荷兰国旗问题
 * @Author: libk
 * @Github: https://github.com/libk
 */
function nethFlag (arr, num) {
  let less = -1
  let greater = arr.length
  let i = 0

  while (i < greater) {
    if (arr[i] < num) {
      [arr[i], arr[less + 1]] = [arr[less + 1], arr[i]]
      i++
      less++
    } else if (arr[i] === num) {
      i++
    } else {
      [arr[i], arr[greater - 1]] = [arr[greater - 1], arr[i]]
      greater--
    }
  }
  return arr
}

发表于 分类于

归并排序

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
/*
 * @Description: mergeSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function mergeSort (arr) {
  if (arr === null || arr === undefined || arr.length <= 1) {
    return arr
  }
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid, arr.length)
  mergeSort(leftArr)
  mergeSort(rightArr)
  merge(arr, leftArr, rightArr)
}

function merge (arr, left, right) {
  let i = 0
  let iL = 0
  let iR = 0

  while (iL < left.length && iR < right.length) {
    arr[i++] = (left[iL] < right[iR]) ? left[iL++] : right[iR++]
  }

  while (iL < left.length) {
    arr[i++] = left[iL++]
  }
  while (iR < right.length) {
    arr[i++] = right[iR++]
  }
}

用归并排序的思想解决小和问题

阅读全文 »