SZ 博客

忠于理想 忠于技术

0%

发表于 更新于 分类于 ， 阅读次数：

栈(Stack)

定义

栈是一种特殊的线性表，特殊之处在于它只允许在表的一端进行添加和删除操作。
先进后出

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Stack() {
  this.data = new Array();
  this.clear = function(){
    this.data = new Array();
  } 
  this.pop = function () {
    return this.data.pop();
  }
  this.push = function (d) {
    this.data.push(d);
  }
  this.getItem = function(){
    return this.data[this.data.length-1];
  }
}

应用

107.二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)
例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回其自底向上的层次遍历为：

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

实现

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
/*
* 方法: 迭代法
* 细节：层次遍历,跟随树维护一个节点深度数据
*/
var levelOrderBottom = function (root) {
  let DepthNode = function (node, depth) {
    this.node = node;
    this.depth = depth
  }
  let stack = [];
  let answer = [];
  if (root !== null) {
    let node = stack.push(new DepthNode(root, 0));
    while (stack.length) {
      let node = stack.pop();
      if (!Array.isArray(answer[node.depth])) {
        answer[node.depth] = new Array();
      }
      answer[node.depth].push(node.node.val);
      if (node.node.right) {
        stack.push(new DepthNode(node.node.right, node.depth + 1));
      }
      if (node.node.left) {
        stack.push(new DepthNode(node.node.left, node.depth + 1));
      }
    }
    return answer.reverse();
  } else {
    return [];
  }
};

发表于 更新于 分类于 ， 阅读次数：

链表(List)

定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

实现

1
2
3
4
function ListNode(value) {
  this.value = value;
  this.nextNode = null;
}

应用

236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7
     3
   /    \
  5      1
 / \    /  \
6   2  0    8
   / \
  7   4

示例 1:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

实现

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
38
39
40
41
42
43
44
45
46
47
/*
* 方法：记录父节点
* 细节：拿到子节点的同时给子节点赋值father属性记录回溯链表。
* 空间复杂度：On
* 时间复杂度：On
*/
var lowestCommonAncestor = function (root, p, q) {
  function setNodeList(node) {
    let list = [node];
    while (node && node.father) {
      list.unshift(node.father);
      node = node.father;
    }
    return list
  }

  let nodeStack = [root];
  let nodeListP = undefined;
  let nodeListQ = undefined;

  while (nodeStack.length) {
    let node = nodeStack.pop();
    if (node.right) {
      nodeStack.push(node.right);
      node.right.father = node;
    }
    if (node.left) {
      nodeStack.push(node.left);
      node.left.father = node;
    }
    if (node.val === q.val) {
      nodeListQ = setNodeList(node);
    }
    if (node.val === p.val) {
      nodeListP = setNodeList(node);
    }
    if (nodeListP && nodeListQ) {
      break;
    }
  }
  for (let i = 0; i < Math.min(nodeListP.length, nodeListQ.length); i++) {
    if (!nodeListP[i + 1] || !nodeListQ[i + 1] || nodeListP[i + 1].val !== nodeListQ[i + 1].val) {
      return nodeListP[i];
    }
  }
  return null;
};

发表于 更新于 分类于 ， 阅读次数：

队列(queue)

定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。
先进先出

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Queue() {
  this.data = new Array();
  this.clear = function(){
    this.data = new Array();
  }
  this.shift = function () {
    return this.data.shift();
  }
  this.push = function (d) {
    this.data.push(d);
  }
  this.getItem = function(){
    return this.data[0];
  }
}

应用

108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

实现

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 * 解法: 分治法 
 * 思路：搜索数组的中位作为根节点构建二叉树，原数组去掉中位数之后生成两个数组，继续寻找中位数作为子树的根节点。
 * 细节：采用一个队列来维护 数组在顺序 采用这个树顺序的数组，从根节点直接写入树，相对来说降低了setTreeNode方法的难度，但需要维护一个队列。
 */
var sortedArrayToBST = function (nums) {
  if (nums.length === 0) {
    return null;
  }
  // 一些节点操作方法
  function Node(start, end) {
    this.start = start;
    this.end = end;
  }
  function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
  }
  function setTreeNode(val, tree) {
    if (tree.left === null && tree.val > val) {
      tree.left = new TreeNode(val);
    }
    else if (tree.right === null && tree.val < val) {
      tree.right = new TreeNode(val);
    }
    else if (tree.left !== null && tree.val > val) {
      setTreeNode(val, tree.left);
    }
    else if (tree.right !== null && tree.val < val) {
      setTreeNode(val, tree.right);
    }
  }

  const len = nums.length;
  let lenList = [];
  let lenQueue = [new Node(0, len - 1)];

  while (lenQueue.length) {
    let node = lenQueue.shift();
    if (node.end - node.start > 1) {
      lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
      lenQueue.push(new Node(Math.round((node.end + node.start) / 2) + 1, node.end));
    } else if (node.end - node.start === 1) {
      lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
    }
    lenList.push(Math.round((node.end + node.start) / 2));
  }

  let tree = new TreeNode(nums[lenList[0]]);

  for (let i = 1; i < lenList.length; i++) {
    setTreeNode(nums[lenList[i]], tree);
  }
  return tree;
};

发表于 更新于 分类于 ， 阅读次数：

基本算法

电子竞技(coding)，菜是原罪。除了多敲别无他法。准备在LeetCode刷题，这里记录一些基本算法的思想，解题思路，以及一些经典题目的解。一些题目的答案在这里将持续更新。这些记录和总结可能更适于我自己理解和记忆，如果有疑问强烈建议查看文末的[参考及引用](# 引用 & 参考)。

阅读全文 »

发表于 分类于 阅读次数：

type-check-plus

简介

type-check-plus是一个JavaScript库用于检测输入的值是否符合定义。
例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const objValue = {
    name: 'barChart',
    title: 'population growth',
    yAxisName:'Growth rate',
    xAxisName:'Years',
    color:'green',
    values: [0.13,0.14,0.12,0.15,0.17]，
}；
const objDefine = {
    name: 'string',
    title: '?string',
    yAxisName:'?string',
    xAxisName:'?string',
    color:'?color',
    values: numbser[]',
}
check(objValue, objDefine) // true

背景

我们开发了一个快速构建可视化大屏程序的PAAS平台，该平台支持用户采用一些拖拽修改的方式快速生成大屏引用。因此需要对用户输入的数组进行合法性检测，剔除异常数据保留正确数据。

由于npm的type-check字段被占用，并且npm已有的相关库并不能满足我们的需要，所以决定自己开发一个变量类型检测库，命名为type-check-plus。

阅读全文 »

发表于 更新于 分类于 阅读次数： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
async function async1() {
    console.log("async1 start");
    await  async2();
    console.log("async1 end");
}
async function async2() {
    console.log( 'async2');
}
console.log("script start");
setTimeout(function () {
    console.log("settimeout");
},0);
async1();
new Promise(function (resolve) {
    console.log("promise1");
    resolve();
}).then(function () {
    console.log("promise2");
});
console.log('script end');
阅读全文 »

发表于 分类于 ， 阅读次数：

变量

1
2
3
4
5
6
7
$nav-color: # F90;
nav {
  $width: 100px;
  width: $width;
  color: $nav-color;
  border: 1px solid $highlight-color;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@mixin rounded-corners($normal) { // 混合器 引用这个变量重用大段代码
  -moz-border-radius: $normal;
  -webkit-border-radius: $normal;
  border-radius: $normal;
}
notice {
  background-color: green;
  border: 2px solid # 00aa00;
  @include rounded-corners(5px);
}
===============================================================
.notice {
  background-color: green;
  border: 2px solid # 00aa00;
  -moz-border-radius: 5px;
  -webkit-border-radius: 5px;
  border-radius: 5px;
}

提示

  1. 变量作用域为块级
  2. 中划线 与 下划线 不敏感 例：$link-color与$link_color指向同一个变量
  3. $nav-color: # F90; !default 如果这个变量接下来被声明赋值了，那就用它声明的值，否则就用这个默认值。

嵌套

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
# content {
  article {
    h1 { color: # 333 }
    p { margin-bottom: 1.4em }
  }
  aside { background-color: # EEE }
  a {
    color: blue;
  &:hover { color: red }   // 父选择器  
  }
  h1, h2, h3 {margin-bottom: .8em} // 群组选择器嵌套
  ~ article { border-top: 1px dashed # ccc } // 选择所有跟在content后的同层article元素
  > section { background: # eee } // 子组合选择器 只会选择content下紧跟着的子元素
  dl > {
    dt { color: # 333 }
    dd { color: # 555 }
  }
  nav + & { margin-top: 0 }
}

nav { 
  border: { // 嵌套属性
  style: solid;
  width: 1px;
  color: # ccc;
  }
}

编译后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# content article h1 { color: # 333 }
# content article p { margin-bottom: 1.4em }
# content aside { background-color: # EEE }
# content a { color: blue; }
# content a:hover { color: red; }
# content h1 { margin-bottom: .8em }
# content h2 { margin-bottom: .8em }
# content h3 { margin-bottom: .8em }
# content ~ article { border-top: 1px dashed # ccc }
# content > footer { background: # eee }
# content dl > dt { color: # 333 }
# content dl > dd { color: # 555 }
nav + # content { margin-top: 0 
nav {
  border-style: solid;
  border-width: 1px;
  border-color: # ccc;
}

导入

css有一个特别不常用的特性，即@import规则，它允许在一个css文件中导入其他css文件。然而，后果是只有执行到@import时，浏览器才会去下载其他css文件，这导致页面加载起来特别慢。

sass也有一个@import规则，但不同的是，sass的@import规则在生成css文件时就把相关文件导入进来。这意味着所有相关的样式被归纳到了同一个css文件中，而无需发起额外的下载请求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 嵌套导入
aside {
  background: blue;
  color: white;
}
// blue-theme.scss

===========================================
.blue-theme {@import "blue-theme"}
===========================================
.blue-theme {
  aside {
    background: blue;
    color: # fff;
  }
}

提示

但在下列三种情况下会生成原生的CSS@import，尽管这会造成浏览器解析css时的额外下载：

注释

1
2
3
4
body {
  color: # 333; // 这种注释内容不会出现在生成的css文件中
  padding: 0; /* 这种注释内容会出现在生成的css文件中 */
}

参考

https://www.sass.hk/