02月

alogrithm analysis

发表于 2019-02-16 • 字数统计 309

定义：

如果存在正常数c和n0，使得当 N >= n0 时，T(N) <= f(N)，则记为 T(N) = O(f(N))
如果存在正常数c和n0，使得当 N >= n0 时，T(N) >= g(N)，则记为 T(N) = Ω(g(N))
T(N) = θ(f(N)) 当且仅当 T(N) = O(f(N)) 且 T(N) = Ω(g(N))
如果T(N) = O(f(N)) 且 T(N) != θ(f(N))，则记为 T(N) = o(f(N))

当我们说 T(N) = O(f(N)) 时候，我们保证 T(N) 是以不快于 f(N) 的速度增长，因此 f(N) 是 T(N) 一个上界

法则：

如果 T1(N) = O(f(N)) 且 T2(N) = O(g(N))，则：
- T1(N) + T2(N) = max(f(N) + g(N))
- T1(N) * T2(N) = O(f(N) * g(N))
如果 T(N) 是一个k次多项式，则 T(N) = θ(N^k)
对任意常数k，(logN)^k = O(N)

时间分析一般法则

for 循环：一次for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数
嵌套的for循环：相乘
顺序语句：相加
If、else语句：求MAX

对数

如果一个算法用常数时间O(1) 将问题的大小削减为其一部分（通常是二分之一），那么该算法就是 O(logN)

阅读全文 »

02月

algorithm

priority queue

发表于 2019-02-16 • 字数统计 134

priority queue

binary heap

堆是一棵完全填满的二叉树，，这样的树称为完全二叉树

数组实现：

对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元（2i+1），父亲在 i/2上

使操作快速执行的性质是堆序性（heap order）
在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或者等于）X中的关键字。

基本操作

insert
deleteMin

O(log N)

d-堆

阅读全文 »

02月

algorithm

stack queue and list

发表于 2019-02-16 • 字数统计 23

抽象数据类型

抽象数据类型（ADT）是一些操作集合。

表

stack

queue

阅读全文 »

02月

algorithm

stack queue and list

发表于 2019-02-16 • 字数统计 459

tree

一棵树是由N个节点和N - 1条边组成。

没有子节点的节点叫做树叶(leaf)
根节点为root
如果存在一个路径从n1到n2，则n1是n2的一位祖先（ancestor），n2是n1的一位后裔（descendant）
对于任意节点ni，ni的深度（depth）是从根到ni的唯一路径的长，ni的高度（height）是从ni到一片树叶的最长路径的长。因此根的深度为0，所有树叶的高度为0
先序遍历（preorder traversal），对节点的处理工作是在它诸多儿子节点被处理之前（pre）进行的。
后序遍历（postorder traversal），对节点的处理工作是在它诸多儿子节点被计算之后进行的
中序遍历（inorder traversal），左，节点，右

二叉树（binary tree）

平均二叉树的平均深度为 O(N^1/2)，二叉查找树深度平均值为 O(logN)
具有N个节点的二叉树都将需要N + 1个NULL指针（可以由 2N条边（满）减去 N-1条边（实际）来获得）

二叉查找树

对于树中的每一个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树种所有关键字值大于X的关键字值

复杂度

除了MakeEmpty外，其他操作基本都在 O(logN)

一棵树的所有节点的深度的和称为内部路径长

AVL

左-左、右-右：单旋转
右-左、左-右：双旋转

B-树

阶为M的B-树是一棵具有下类结构特性的树

树的根或者是一片树叶，或者其儿子数在2-M之间
除树根和树叶外，其他节点的儿子数在 M / 2 到 M 之间
所有树叶都在同一深度上

B-树的深度最多是logM/2(N)

阅读全文 »

02月

JavaScript

BOM

发表于 2019-02-15 • 字数统计 480

window对象定义属性和直接在全局环境中声明全局变量的区别：前者可以使用delete操作符删除，而后者不能
尝试访问未声明的变量会抛出错误，但是通过查询window对象，可以知道某个变量是否声明（var声明的变量）

frames

window
top
self
window.parent
window.frames[name] / window.frames[0]

窗口位置大小

window.screenLeft & window.screenTop & window.screenX & window.screenY 不同浏览器行为不同
window.moveTo(x, y) & window.moveBy(x, y) 默认禁用
innerWidth & innerHeight & outerWidth & outerHeight，一般innerHeight代表视口区域，outerHeight代表浏览器区域
document.documentElement.clientHeight & document.documentElement.clientWidth
resizeTo(width, height) & resizeBy(width, height)

计时器

setTimeout & setInterval
clearTimeout & clearInterval

系统对话框

同步方法

alert
confirm
prompt

异步方法

find
print

location对象

即是 window 的属性，也是 document 的属性

属性

hash
host （带端口号）
hostname （不带端口号）
href （location.toString() 返回值）
pathname
port
protocol （协议，一般为’http:’或者’https:’）
search

方法

assign(url) 改变浏览器的位置（与直接修改location.href属性效果一样），同时会生成一条历史记录（改变其他属性也会）
replace(url) 改变浏览器位置，不生成历史记录，不能通过前进后退按钮回到前一个页面
reload(bool?) 重新加载当前页面，如果需要强制从服务器加载，需要传递参数true

navigator 对象

识别客户端浏览器的事实标准

几个重要的属性

onLine
plugins
registerProtocolHandler

screen 对象

浏览器窗口外部显示器的信息

几个重要的属性

availHeight
availWidth
availTop
availLeft
height
width

history 对象

保存着用户的上网历史记录，从打开的那一刻算起

go() 向前跳转（正数）或者向后跳转（负数）或者传入一个字符串，浏览器将跳转到最近的包含改字符串的历史
forward() 前进
back() 后退

阅读全文 »

02月

JavaScript

DOM

发表于 2019-02-15 • 字数统计 2038

节点层次

文档只有一个根节点，即document，html为其唯一的子节点

节点类型

一共具有12中节点类型，所有节点都继承自Node类型

Node.ELEMENT_NODE(1)
Node.ATTRIBUTE_NODE(2)
Node.TEXT_NODE(3)
Node.CDATA_SECTION_NODE(4)
Node.ENTITY_REFERENCE_NODE(5)
Node.ENTITY_NODE(6)
Node.PROCESSING_INSTRUCTION_NODE(7)
Node.COMMENT_NODE(8)
Node.DOCUMENT_NODE(9)
Node.DOCUMENT_TYPE_NODE(10)
Node.DOCUMENT_FRAGMENT_NODE(11)
Node.NOTATION_NODE(12)

属性

nodeType 上方12中之一
nodeName
nodeValue

对于元素节点，nodeName中保存的都是元素的标签名，nodeValue保存的始终是null

节点关系

每一个节点都保存着一个childNodes属性，保存着一个NodeList对象，指向子节点

NodeList通过下面属性访问

方括号
.item()

关系：

childNodes // NODE LIST
children // HTML COLLECTION
firstChild
lastChild
parentNode
previousSibling
nextSibling
element.compareDocumentPosition()
- 1 无关
- 2 居前
- 4 居后
- 8 包含
- 16 被包含

操作节点

hasChildNodes()
appendChild() 如果传进去appendChild的节点已经是文档的一部分，则将该节点从原来的位置转移到新位置
insertBefore(newNode, node) 第二个参数为参照节点
replaceChild(newNode, node) 第二个参数为移除的节点
removeChild(node) 跟上面一样，移除的节点还是归文档所有，只是在文档中已经没有其位置了
cloneNode(bool) 创建一个副本，bool表示是否深度复制
normalize() 找到空文本节点删除，找到相邻文本节点合并

Document类型

document为window的一个属性，因此可以当成全局变量访问

nodeType === 9
nodeName === ‘#document’
ownerDocument === null
子节点可能是一个DocumentType、Element、ProcessingInstruction 或者 Comment
document.documentElement为html元素
document.body保存body引用
document.head
document.doctype
document.compatMode
- CSS1Compat
- BackCompat
document.title
document.URL, document.domain, document.referrer 其中document.domain只能设置为URL中包含的域
document.readyState
- loading
- complete
document.charset & document.defaultCharset
document.importNode(node, bool) 可以传入ownerDocument不是当前文档的node，支持两个属性，一个为node，一个为是否深复制

nodeList 和 HTMLCollection 区别
HTMLCollection 只包含元素节点，NodeList包含任何类型的节点
HTMLCollection 多了一个 namedItem() 方法，接受一个 id 或者 name

查找元素

getElementById()
getElementsByTagName() 不区分大小写
getElementsByName() 元素也支持这个方法，搜索起点为当前元素
querySelector() & querySelectorAll() 可以再document和element中使用，返回一个NodeList对象，但是底层实现类似于一组元素快照，而不是不断对文档进行搜索的动态查询。// 此处的 NodeList 不会动态更新
getElementsByClassName()
matchesSelector() 返回一个布尔值

获得的对象为HTMLCollection

方括号访问（数字或者字符串（name））
namedItem(name or id)
item(index)

特殊集合，都为HTMLCollection

document.anchors 带有name的a元素
document.forms 文档中所有form元素
document.images 文档中所有img元素
document.links 文档中所有带href特性的a元素
document.styleSheets 文档中的样式表，包含style标签定义的样式表

文档写入

document.write()
document.writeIn() ‘\n’
document.open()
document.close()

Element 类型

tagName === nodeName 标签名始终以大写表示
id、title、lang、dir、className
getAttribute()、setAttribute()、removeAttribute()
attributes –> namedNodeMap 拥有以下方法，保存着attr类型节点，可以通过specified查看是否定义了属性
- getNamedItem(name)
- removeNamedItem() 返回删除的attr节点，可以通过返回节点的nodeValue和nodeName来访问
- setNamedItem()
- item(pos)
classlist –> DOMTokenList
- add()
- contains()
- remove()
- toggle()
dataset 自定义属性
innerHTML html以及table等标签不支持innerHTML
outerHTML
innerText
outerText
insertAdjacentHTML()
- “beforebegin”
- “afterbegin”
- “beforeend”
- “afterend”
children
contains() 某一个节点是不是另一个节点的后代
document.createElement(name) 创建Element节点
.isSameNode() 判断对象是否相等
.isEqualNode() 判断是否同一引用

Text 类型

nodeType === 3
nodeName === ‘#text’
nodeValue 为文本
不支持子节点
data 文本
textContent
appendData()
deleteData(offset, count)
insertData(offset, count)
replaceData(offset, count, text)
splitText(offset) 分成两个文本节点
substringData(offset, count)
document.createTextNode()

DocumentFragment 类型

document.createDocumentFragment()

操作表格

Table：

caption
tBodies
tFoot
tHead
rows HTMLCollection
createTHead
createTFoot
createCaption
deleteTHead
deleteTFoot
deleteCaption
deleteRow(pos)
insertRow(pos)

TBody：

rows
deleteRow(pos)
insertRow(pos)

cells
deleteCell(pos)
insertCell(pos)

NodeList

NodeList
NamedNodeMap
HTMLCollection
DOMTokenList

元素遍历

childElementCount
firstElementChild
lastElementChild
previousElementSibling
nextElementSibling

焦点管理

document.activeElement
document.hasFocus() 返回布尔值

scrollIntoView

scrollIntoView(bool) true/default：顶部尽可能平齐， false：底部尽可能平齐

DOM子集模块

DOM2 级核心Core
DOM2 级视图View
DOM2 级事件Events
DOM2 级样式Style
DOM2 级遍历和范围 Traversal and Range
DOM2 级HTML

样式

支持style特性的HTML元素在JavaScript中都会有一个对应的style属性

其中，具有横杠的属性自动转换成驼峰式，float => cssFloat // float为JavaScript中的一个保留字
在标准模式下，所有度量值都必须要指定一个单位，否则会被忽略

style对象 extends CSSStyleDeclaration：

cssText
length 应用给元素css属性的数量，缩写会自动展开
removeProperty()
item(index) 可以通过for循环遍历属性

计算的样式

document.defaultView.getComputedStyle()，接受两个参数，第一个参数为元素，第二个参数为伪元素（如”:after”或者”::after”）

操作样式表

document.styleSheets & styleOrLinkElement.sheet
CSSStyleSheet extends StylesSheet

disabled 可写，是否禁用样式表
href 样式表的href，style标签的为null
media 当前样式表支持的所有媒体类型的集合，如果是空列表，表示适合所有媒体类型的集合
cssRules 包含的规则
insertRule(rule:str, index)
deleteRule(index)

元素大小

offsetHeight // border-box
offsetWidth
offsetTop 与offset parent 之间的距离
offsetLeft
offsetParent

clientHeight padding-box
clientWidth
clientTop
clientLeft
scrollHeight 没有滚动条下元素总高度，即所有内容的高度 // padding-box
scrollWidth
scrollTop 设置此可以改变元素的滚动位置
scrollLeft

getBoundingClientRect() // border-box
返回相对于视口的 left right top bottom

特殊集合

HTMLCollection：一般为以下方法获得：
动态改变

getElementsByTagName
getElementsByClassName
element.children
document.anchors 带有name的a元素
document.forms 文档中所有form元素
document.images 文档中所有img元素
document.links 文档中所有带href特性的a元素

NodeList:
不会动态改变

getElementsByName
querySelectorAll
element.childNodes

DOMTokenList:
动态改变

element.classList

NamedNodeMap:
动态改变

element.attributes

StyleSheetList

document.styleSheets 文档中的样式表，包含style标签定义的样式表

遍历

DOM的遍历是要给深度优先的算法

NodeIterator

const ni = document.createNodeIterator(root, whatToShow, filter)
// NodeFilter.FILTER_ACCEPT
// NodeFilter.FILTER_SKIP
// NodeFilter.SHOW_ELEMENT
// filter:
function filter(node) {
  return node.nodeName.toLowerCase() === 'section' ? NodeFilter.ACCEPT : NodeFilter.SKIP
}

// usage
ni.nextNode()
ni.previousNode()

TreeWalker

用法与NodeIterator差不多，增加了下面的功能

parentNode
firstChild
lastChild
nextSibling
previousSibling

NodeFilter.SKIP 跳过某个节点 NodeFilter.REJECT 跳过一整个子树
可以通过修改currentNode 来修改遍历的起点

Range

1	const range = document.createRange()

方法：

selectNode()
selectNodeContent()

Event

事件是利用侦听器来预定一些文档或浏览器窗口发生的一些特定的交互瞬间，这个模型称为观察者模型

事件流

事件流描述的是从页面中接收事件的顺序。
IE的事件流是事件冒泡流，网景的是事件捕获流

DOM2规定的时间流包括三个阶段：事件捕获阶段、处于目标阶段以及事件冒泡阶段。

规范要求，捕获阶段不会涉及事件目标

处理程序

addEventListener(eventType, callback, caption? or option?)
option = {
  capture: bool,
  once: bool,
  passive: bool, // never call preventDefault
}

event object

type
eventPhase：1.捕获阶段 2.处于目标 3.冒泡阶段
bubble：是否冒泡
defaultPrevented：是否已经阻止默认行为
currentTarget
target
preventDefault()，只有cancelable为true的事件才可以使用
stopPropagation()
trusted：浏览器生成的为true，开发者通过JavaScript创建的为false
stopImmediatePropagation() 取消事件的进一步捕获或者冒泡，同时阻止任何事件处理程序被调用

兼容性

event || window.event
event.target || window.event.srcElement
event.stopPropagation || window.event.cancelBubble = true
event.preventDefault || window.event.returnValue = false

事件类型

UI事件：load、unload、abort（用户停止下载）、error（JavaScript运行错误）、select、resize、scroll
焦点事件：blur、focus、focusin、fucusout（后两个支持冒泡）
鼠标事件：click、dbclick、mousedown、mouseenter、mouseleave、mousemove、mouseout、mouseover、mouseup
滚轮事件：mousewheel（包含clientX、clientY、pageX、pageY、screenX、screenY等）
文本事件
键盘事件
合成事件
变动事件

根据DOM2规范，应该在document上触发onload事件而不是window上

mouseleave与mouseenter：首次移动到/离开元素范围触发，不冒泡！，移动到后代元素上不会触发
mouseout与mouseover：首次移动/离开元素范围触发，移动到后代元素上触发

mousewheel包含一个wheelDelta属性

阅读全文 »

02月

JavaScript

函数防抖和节流

发表于 2019-02-08 • 字数统计 146

function debounce(func, wait, immediate = true) {
  let timer = 0

  return function(...args) {
    if (timer) {
      clearTimeout(timer)
    } else {
      if (immediate) {
        func.apply(func, args)
      }
    }

    timer = setTimeout(() => {
      timer = 0
      if (!immediate) {
        func.apply(func, args)
      }
    }, wait)
  }
}

function getNow() {
  return + new Date()
}


function throttle(func, wait) {
  let [now, previous, timer, remainTime] = [0, 0, 0, 0]

  const later = (...params) => setTimeout(() => {
    func.apply(func, params)
    previous = now
    timer = 0
  }, remainTime)

  return function(...params) {
    now = getNow()
    // if if's the first time
    if (!previous) {
      previous = now
    }

    remainTime = wait - (now - previous)
    // if there is not a timer, then create it
    if (!timer) {
      timer = later(...params)
    }
  }
}

阅读全文 »

02月

JavaScript

事件循环

发表于 2019-02-08 • 字数统计 162

Node-loop

Tasks, microtasks, queues and schedules

   ┌───────────────────────────┐
┌─>│           timers          │
│  └─────────────┬─────────────┘
│  ┌─────────────┴─────────────┐
│  │     pending callbacks     │
│  └─────────────┬─────────────┘
│  ┌─────────────┴─────────────┐
│  │       idle, prepare       │
│  └─────────────┬─────────────┘      ┌───────────────┐
│  ┌─────────────┴─────────────┐      │   incoming:   │
│  │           poll            │<─────┤  connections, │
│  └─────────────┬─────────────┘      │   data, etc.  │
│  ┌─────────────┴─────────────┐      └───────────────┘
│  │           check           │
│  └─────────────┬─────────────┘
│  ┌─────────────┴─────────────┐
└──┤      close callbacks      │
   └───────────────────────────┘

await 可以使用任何 “thenable”，即任何带有 then 方法的对象，即使它不是真正的 Promise

进程是cpu资源分配的最小单位（是能拥有资源和独立运行的最小单位）

线程是cpu调度的最小单位（线程是建立在进程的基础上的一次程序运行单位，一个进程中可以有多个线程）

js_singlethread_eventloop

浏览器渲染页面过程与页面优化

https://www.html5rocks.com/zh/tutorials/internals/howbrowserswork/

阅读全文 »

02月

JavaScript

数字储存

发表于 2019-02-08 • 字数统计 1871

在JavaScript中如果在控制台中输入0.1+0.2会出现什么结果？正常来说结果是等于0.3的，令人惊讶的是，输出的结果却是：0.30000000000000004，究竟是什么原因使得JavaScript中0.1 + 0.2 !== 0.3，这就需要从JavaScript存储Number类型开始说起。

阅读全文 »

02月

JavaScript

regular expression

发表于 2019-02-05 • 字数统计 999

正则表达式

元字符及其作用

字符	作用
\	转移字符，将下一个字符标记为特殊字符，如：\n表示换行符
^	匹配字符串的开始位置，如果设置了Multiple属性，它也匹配’\n’，’\r’之后的位置，如: /^b/匹配以b为开始的字符串（bus…）
$	匹配字符串的结束位置，如果设置了Multip属性，它也匹配’\n’，’\r’之前的位置，如： /e$/匹配以e结束的字符串(apple…)
{n}	匹配前面字符（表达式）n次，如：/o{2}/匹配foo中的oo，不匹配box中的o
{n,}	至少匹配前面字符（表达式）n次（即 >= n)，如：/o{4,}/匹配coooool中的o
{n,m}	匹配前面字符（表达式）最少n次，最多m次（即 n <= x <= m），如：/o{2,3}/匹配coooool中前3个o（非贪婪模式下匹配前两个o）

| 匹配前面字符（表达式）零次或多次，相当于{0,}，如：/co*l/ 将匹配cool或cl

| 匹配前面字符（表达式）一次或多次，相当于{1,}，如：/co+l/ 将匹配cooool（中间o个数大于1即可）
? | 匹配前面字符（表达式）零次或一次，相当于{0,1},如：/jsx?/ 将匹配js或者jsx
? | ?字符还可以放在其他限制符(前面 *,+,?,{n},{n,},{n,m})后面，表示非贪婪匹配（即尽量少匹配字符，如：/co+/匹配coooool匹配到cooooo，而/co+?/匹配coooool匹配到co），默认为贪婪匹配
(pattern) | 括号()，匹配里面的子表达式，并获取匹配结果（捕获），称为捕获组，后续可以使用\1，\2等表示括号内内容，如：/(bili)\1/ 可以匹配bilibili 。需要注意：\1与前面括号捕获到的内容是完全相同的，而不只是符合匹配模式(pattern)。
(?:pattern) | 匹配括号内表达式pattern，但是不获取匹配结果，称为非捕获组，如：/cit(?:y|ies)/匹配city或者cities。
(?=pattern) | 正向肯定预查，匹配任何其后符合pattern模式的字符串。这个一个非捕获组，（预查不消耗字符，即下一次匹配从预查前面匹配到的地方开始匹配，而不是pattern的位置开始匹配）。如：/dis(?=able)/匹配disable中的dis
(?!pattern) | 正向否定预查，匹配任何其后不符合pattern模式的字符串。与(?=)类似，是一个非捕获组
(?<=pattern) | 反向肯定预查，匹配任何前面字符符合pattern模式的字符串。
(?<!pattern) | 反向否定预查，匹配任何前面字符吧符合pattern模式的字符串。
. | 匹配出换行符之外任意字符，若要匹配所有字符，可以使用类似/(.|\n|\r)/的形式
[xyz] | 字符集合，匹配x、y、z中任意一个字符。也可以使用缩写[0-9a-zA-Z]。如：/[0-9]+/将匹配一个或多个数字
[^xyz] | 负值字符集合，匹配不是x、y、z的任意一个字符。也可以使用上述的缩写形式。
x | y | 匹配x或者y，如/apple|pear/将匹配apple或者pear，而/appl(e|es)/将匹配apple或者apples
\w | 匹配[0-9a-zA-Z_]（包括下划线）
\W | 匹配[^0-9a-zA-Z]
\b | 匹配单词边界（即\w与\W之间的边界）
\B | 匹配非单词边界
\d | 匹配一个数字[0-9]
\D | 匹配一个非数字[^0-9]
\s | 匹配空白字符，包括空格，换行符，回车符，制表符
\S | 匹配非空白字符
\un | n为4个16进制表示的Unicode字符。

优先度

正则表达式从左到右进行计算

运算符	描述
\	转义
(),(?:),(?=),(?!),(?<=),(?<!),[]	括号
*,+,?,{n},{n,},{n,m}	限定符
\|	或操作

使用正则表达式的函数

正则方法

exec() 返回一个数组，没匹配到返回null。
test() 返回一个Boolean值

String方法

match() 加g与不加g返回不一样
- 不加g的情况下，跟exec返回的相同，加了g的情况下返回匹配的数组
search() 返回匹配的第一个字符index
replace()
split()

阅读全文 »

priority queue

binary heap

d-堆

抽象数据类型

表

stack

queue

tree

二叉树（binary tree）

二叉查找树

复杂度

AVL

B-树

frames

窗口位置大小

导航

计时器

系统对话框

location对象

navigator 对象

screen 对象

history 对象

节点层次

节点类型

节点关系

操作节点

Document类型

查找元素

文档写入

Element 类型

Text 类型

DocumentFragment 类型

操作表格

NodeList

元素遍历

焦点管理

scrollIntoView

DOM子集模块

样式

计算的样式

操作样式表

元素大小

特殊集合

遍历

NodeIterator

TreeWalker

Range

Event

事件流

处理程序

event object

兼容性

事件类型

正则表达式

元字符及其作用

优先度

使用正则表达式的函数

正则方法

String方法