2013年9月25日星期三

试试看 ？ 离奇古怪的javascript题目 - Aaron.

本邮件内容由第三方提供，如果您不想继续收到该邮件，可 点此退订 。
试试看 ？ 离奇古怪的javascript题目 - Aaron.  阅读原文»

来源地址：

http://dmitrysoshnikov.com/ecmascript/the-quiz/#q1

另一篇帖子 看看国外的javascript题目,你能全部做对吗?

http://www.cnblogs.com/aaronjs/p/3172112.html

答案都是自己总结的，毕竟是人肉解释器，解释不一定完全正确，如有不对欢迎大家指出！

题目1. 结果是什么？

typeof typeof(null)
  • “undefined”
  • SyntaxError
  • “string”
  • “object”
  • TypeError
答案

题目2. 下面的检测是否等价？

typeof foo == 'undefined'
typeof foo === 'undefined'
  • Yes
  • No
答案

题目3. 结果是什么？

100['toString']['length']
  • 100
  • 3
  • 1
  • 8
  • 0
  • SyntaxError

这个估计好多人想不通了

JavaScript 中所有变量都是对象，除了两个例外 null 和 undefined

false.toString(); // 'false'
[1, 2, 3].toString(); // '1,2,3'
function Foo(){}
Foo.bar = 1;
Foo.bar; // 1

一个常见的误解是数字的字面值（literal）不是对象。这是因为 JavaScript 解析器的一个错误， 它试图将点操作符解析为浮点数字面值的一部分。

2.toString(); // 出错：SyntaxError

例如以下这种就OK

true.toString()
"true"

false.toString()
"false"

01.toString()
"1"

0x20.toString()
"32"

true.toString()、false.toString()、02.toString()、 0x20.toString()都是可以的

我仔细查了下，网上大多给的解释

2.toString()出错是因为解释器读到“2. ”不知道这个“点”究竟该作为小数点还是“.”操作符， 或者也就是说在这里产生了一个“shift-shift conflit”

有很多变通方法可以让数字的字面值看起来像对象

2..toString(); // 第二个点号可以正常解析
2 .toString(); // 注意点号前面的空格
(2).toString(); // 2先被计算

访问100['toString']的length返回toString方法形参个数；

换个

(function(a,b){
//输出2
})['length']
fn = {
f : function(a,b,c){
//3
}
};

fn.f['length']

有长度属性的函数，这个长度就是用来计算多个参数的，

可以分解为

100['toString'].length

由于toString是个方法，所以它length属性返回的是toString的形参个数，而toString方法可以接收一个radix(基数)作为形参（比如：toString(2)，返回该数值的二进制，16则代表16进制），所以最终返回结果是1。

function toString( [radix : Number] ) : String

radix 可选项。为将数字值转换为字符串指定一个基数。此值仅用于数字。

所以当数字调用toString的时候，会有一个参数radix，其它的比如：Function、Array、String这些调用的话，结果会是 0

刚才上面的100['toString']['length']为什么不分解成100.toString.length？

这是是由于100后面的.是小数点之后是小数部分，从而导致语法错误

解决的方法也说了

红黑树并没有我们想象的那么难(上) - 捣乱小子  阅读原文»

红黑树并没有想象的那么难, 初学者觉得晦涩难读可能是因为情况太多. 红黑树的情况可以通过归结, 通过合并来得到更少的情况, 如此可以加深对红黑树的理解. 网络上的大部分红黑树的讲解因为没有「合并」. 红黑树的五个性质:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。

红黑树的数据结构

摘自 sgi stl 红黑树数据结构定义:

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;

struct _Rb_tree_node_base
{
typedef _Rb_tree_Color_type _Color_type;
typedef _Rb_tree_node_base* _Base_ptr;

_Color_type _M_color;
_Base_ptr _M_parent;
_Base_ptr _M_left;
_Base_ptr _M_right;

static _Base_ptr _S_minimum(_Base_ptr __x)
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}

static _Base_ptr _S_maximum(_Base_ptr __x)
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
};

template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;
_Value _M_value_field;
};

二叉搜索树的插入删除操作

在展开红黑树之前, 首先来看看普通二叉搜索树的插入和删除. 插入很容易理解, 比当前值大就往右走, 比当前值小就往左走. 详细展开的是删除操作.

二叉树的删除操作有一个技巧, 即在查找到需要删除的节点 X; 接着我们找到要么在它的左子树中的最大元素节点 M、要么在它的右子树中的最小元素节点 M, 并交换(M,X). 此时, M 节点必然至多只有一个孩子; 最后一个步骤就是用 M 的子节点代替 M 节点就完成了. 所以, 所有的删除操作最后都会归结为删除一个至多只有一个孩子的节点, 而我们删除这个节点后, 用它的孩子替换就好了. 将会看到 sgi stl map 就是这样的策略.

在红黑树删除操作讲解中, 我们假设代替 M 的节点是 N(下面的讲述不再出现 M).

红黑树的插入

插入新节点总是红色节点, 因为不会破坏性质 5, 尽可能维持所有性质.

假设, 新插入的节点为 N, N 节点的父节点为 P, P 的兄弟(N 的叔父)节点为 U, P 的父亲(N 的爷爷)节点为 G. 所以有如下的印象图:

rbtree0

插入节点的关键是:

  1. 插入新节点总是红色节点
  2. 如果插入节点的父节点是黑色, 能维持性质
  3. 如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质

插入算法详解如下, 走一遍红黑树维持其性质的过程:

第 0.0 种情况, N 为根节点, 直接 N->黑. over
第 0.1 种情况, N 的父节点为黑色, 这不违反红黑树的五种性质. over

第 1 种情况, N,P,U 都红(G 肯定黑). 策略: G->红, N,P->黑. 此时, G 红, 如果 G 的父亲也是红, 性质又被破坏了, HACK: 可以将 GPUN 看成一个新的红色 N 节点, 如此递归调整下去; 特俗的, 如果碰巧将根节点染成了红色, 可以在算法的最后强制 root->红.

rbtre01

第 2 种情况, P 为红, N 为 P 右孩子, U 为黑或缺少. 策略: 旋转变换, 从而进入下一种情况:

rbtree02

第 3 种情况, 可能由第二种变化而来, 但不是一定: P 为红, N 为红. 策略: 旋转, 交换 P,G 颜色, 调整后, 因为 P 为黑色, 所以不怕 P 的父节点是红色的情况. over

rbtree03

红黑树的插入就为上面的三种情况. 你可以做镜像变换从而得到其他的情况.

红黑树的删除

假设 N 节点见上面普通二叉树删除中的定义, P 为 N 父节点, S 为 N 的兄弟节点, SL,SR 分别是 S 的左右子节点. 有如下印象图:

rbtree04 N 没有任何的孩子!

删除节点的关键是:

  1. 如果删除的是红色节点, 不破坏性质
  2. 如果删除的是黑色节点, 那么这个路径上就会少一个黑色节点, 破坏了性质. 故删除算法就是通过重新着色或旋转, 来维持性质

删除算法详解如下, 走一遍红黑树维持其性质的过程:

第 0.0 情况, N 为根节点. over
第 0.1 情况, 删除的节点为红. over
第 0.2 情况, 删除节点为黑, N 为红. 策略: N->黑, 重新平衡. over

第 1 情况, N,P,S,SR,SL 都黑. 策略: S->红. 通过 PN,PS 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0 开始继续调整. 为什么要这样呢? HANKS: 因为既然 PN,PS 路径上的黑节点数量相同而且比其他路径会少一个黑节点, 那何不将其整体看成了一个 N 节点! 这是递归原理.

rbtree05

第 2 情况, S 红, 根据红黑树性质 P,SL,SR 一定黑. 策略: 旋转, 交换 P,S 颜色. 处理后关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始, 进入下一个情况:

rbtree06

第 2.1 情况, S,SL,SR 都黑. 策略: P->黑. S->红, 因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5. over. 将看到, sgi stl map 源代码中将第 2.1 和第 1 情况合并成一种情况, 下节展开.

rbtree07

第 2.2.1 情况, S,SR 黑, SL 红. 策略: 旋转, 变换 SL,S 颜色. 从而又进入下一种情况:

rbtree08
第 2.2.2 情况, S 黑, SR 红. 策略: 旋转, 交换 S,P 颜色, SR->黑色, 重新获得平衡.

rbtree09

上面情况标号 X.X.X 并不是说这些关系是嵌套的, 只是这样展开容易理解. 此时, 解释三个地方:

  1. 通过 N 的黑色节点数量多了一个
  2. 通过 SL 的黑色节点数量不变
  3. 通过 SR 的黑色节点数量不变

红黑树删除重新调整伪代码如下:

// 第 0.0 情况, N 为根节点. over
if N.parent == NULL:
return;

// 第 0.1 情况, 删除的节点为红. over
if color == RED:
return;

// 第 0.2 情况, 删除节点为黑, N 为红, 简单变换: N->黑, 重新平衡. over
if color == BLACK && N.color == RED:
N.color = BLACK;

// 第 1 种情况, N,P,S,SR,SL 都黑. 策略: S->红. 通过 N,S 的黑色节点数量相同了, 但会比其他路径多一个, 解决的方法是在 P 上从情况 0 开始继续调整.
if N,P,S,SR,SL.color == BLACK:
S.color = RED;

// 调整节点关系
N = P
N.parent = P.parent
S = P.paernt.another_child
SL = S.left_child
SR = S.right_child
continue;

// 第 2 情况, S 红, 根据红黑树性质 P,SR,SL 一定黑. 旋转, 交换 P,S 颜色. 此时关注的范围缩小, 下面的情况对应下面的框图, 算法从框图重新开始.
if S.color == RED:
rotate(P);
swap(P.color,S.color);

// 调整节点关系
S = P.another_child
SL = S.left_child
SR = S.right_child

// 第 2.1 情况, S,SL,SR 都黑. 策略: P->黑. S->红, 因为通过 N 的路径多了一个黑节点, 通过 S 的黑节点个数不变, 所以维持了性质 5. over
if S,SL,SR.color == BLACK:
P.color = BLACK;
S.color = RED;
return

// 第 2.2.1 情况, S,SR 黑, SL 红. 策略: 旋转, 变换 SL,S 颜色. 从而又进入下一种情况:
if S,SR.color == BLACK && SL.color == RED:
rotate(P);
swap(S.color,SL.color);

// 调整节点关系
S = SL
SL = S.left_child
SR = S.right_child

// 第 2.2.2 情况, S 黑, SR 红. 策略: 旋转, 交换 S,P 颜色.
if S.color == BLACK && SR.color == RED:
rotate(P);
swap(P.color,S.color);
return;

总结

所以, 插入的情况只有三种, 删除的情况只有两种. 上面的分析, 做镜像处理, 就能得到插入删除的全部算法, 脑补吧. 从上面的分析来看, 红黑树具有以下特性: 插入删除操作都是 0(lnN), 且最多旋转三次.

下节中会重点展开 sgi stl map 的源代码.

参考文档: wikipedia

捣乱 2013-9-25

http://daoluan.net

时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)