SZ 博客

忠于理想 忠于技术

0%

发表于 分类于 阅读次数：

SVG Path 属性

<path> 标签

<path> 标签用来定义路径。

path元素的形状是通过属性d定义的，属性d的值是一个“命令+参数”的序列。字符结束后，解析器就会去读下一段命令。每一个命令都有两种表示方式，一种是用大写字母，表示采用绝对定位。另一种是用小写字母，表示采用相对定位（例如：从上一个点开始，向上移动10px，向左移动7px）。

因为属性d采用的是用户坐标系统，所以不需标明单位。

阅读全文 »

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

简介

对于是盒子的元素，如果没有特殊设置，其默认总是占独立的一行，宽度为浏览器窗口的宽度，在其前后的元素不管是不是盒子，都只能排列在它的上面或者下面，即上下累加着进行排列。HTML文档中的每个盒子都可以看成是由从内到外的四个部分构成，即内容区（content）、填充(padding)、边框(border)和空白边(margin)。 CSS 为四个部分定义了一系列相关属性，通过对这些属性的设置可以丰富盒子的表现效果。

阅读全文 »

发表于 分类于 阅读次数：

墨卡托投影坐标系（Mercator Projection）

墨卡托投影是一种“等角正切圆柱投影”，荷兰地图学家墨卡托（Mercator）在1569年拟定：假设地球被围在一个中空的圆柱里，其赤道与圆柱相接触，然后再假想地球中心有一盏灯，把球面上的图形投影到圆柱体上，再把圆柱体展开，这就是一幅标准纬线为零度（即赤道）的“墨卡托投影”绘制出的世界地图。
　　墨卡托投影在今天对于航海事业起着极为重要的作用，目前世界各国绘制海洋地图时仍广泛使用墨卡托投影，国际水路局（IHB）规定：“除特殊情况外，各国都要用墨卡托投影绘制海图”。国际水路局发行的《大洋水深总图》是把全世界分成24幅编辑的，在南北纬72度之间就是使用墨卡托投影绘成的。

投影原理

用一个平面包围成圆柱体，正好与地球相接，地球近似成正球体处理。从球内打射线，跟球面和圆柱面都有唯一的交点。如下图，从球内放置灯光，光线向外，跟球面交点为P，与外接圆柱面的交点为P1，P的经纬度分别为λ，φ。

反畸变处理

转换算法

设地球表面A点经纬坐标为（λ，Φ），对应的投影坐标为（x,y）,基准纬线设置为赤道，则R为地球半径；墨卡托投影方程式为：

参考 & 引用

https://www.cnblogs.com/DHUtoBUAA/p/6706642.html
https://blog.csdn.net/xiliuhu/article/details/52075408

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

babel入门

本文主要内容

一些babel基础知识、一个可工作的极简babel案例、一个简单的babel插件案例、以及对应的资源。

babel是什么

**本质上:**babel是一个JavaScript的编译器,输入一些code将这些code进行编译，输出一些code。
**主要工作:**将ES2015及更新版本解析成浏览器可执行的低版本代码，将jsx等自定义的编码规范解析成浏览器通用的代码。
**原理:**babel 利用 babylon 解析器进行语法解析。解析成 AST（抽象语法树）后，经过一定的规则对这个树进行处理后再生成新的语法树。最终新的语法树在生成对应的合法的 Javascript 语法。

阅读全文 »

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

ReactHook

简略记录版，本文仅提供一些基础内容作为学习和回忆之用，入门学习请查看React Hook官方文档

Hook 是 React 16.8 的新增特性。它可以让你在不编写 class 的情况下使用 state 以及其他的 React 特性。

阅读全文 »

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

层包(Pack)

图使用嵌套来表示层次结构。最里层表示叶节点的圆的大小用来编码定量的维度值。每个圆都表示当前节点的近似累计大小，因为有空间浪费以及变形；仅仅只有叶节点可以准确的比较。尽管 circle packing 不能高效的利用空间，但是能更突出的表示层次结构。

该模块利用层级布局的数据进行包布局[坐标计算](# 核心代码)。为层级布局数据添加[布局信息](# 布局信息)用于绘制图形。以及一些内置[API](# API)来设置或获取一些参数来辅助图形的坐标计算。

阅读全文 »

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

层级布局(Hierarchy)

一个好的层次结构可视化能促进快速的促进多尺度推理: 对单个单元的微观观察和对整体的宏观观察.

许多数据集从从本质上是嵌套结构的。例如一个[族谱结构](# 族谱结构)。
该模块实现了对层级结构的[基础数据计算](# 基础数据计算)。

该模块构建了一个[新的结构](# Node节点)来存储层级结构的一些[基本数据](# 基本数据)。以及一些[内置方法](# 内置方法)来进行层级间的计算。

阅读全文 »

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

哈希表(HashTable)

定义

哈希表是基于键值对的一种数据存储结构，key值不可以重复，value可以重复，后面添加的重复的key值的时候，会把之前key值对应的value给覆盖掉，JavaScript中的对象具有天然的哈希特性。

哈希表的常用方法：

  • put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
  • get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回 undefined。
  • remove(key)：如果映射中存在这个键，删除这个数值对。

设计

hash表的实现普遍基于数组，将给出key值映射到一个数组的一个地址,这里用一个hash函数来解决映射问题，hash函数存在两个问题，一个是性能问题，在大规模写入和查询时每次都会用到hash函数，另一个是冲突问题，key值可能是无限的，数组空间是有限的必然会出现多个key值对应同一个地址的情况，称为hash冲突。我们来看一个简单的hashTable设计。

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
function HashTable () {
    this.table = new Array(137);
    this.simpleHash = simpleHash;
    this.showAll = showAll;
    this.put = put;
    // this.get = get; 后面添加get
}
 
function simpleHash (data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
        // 获取 并 累加 key值 字符串中的每一个字符的 unicode 值
        total += data.charCodeAt(i);
    }

    // 对 数组长度 取余 映射到数组长度范围内
    return total % this.table.length;
}
 
function put (key, data) {
    var pos = this.simpleHash(key);
    this.table[pos] = data;
}
 
function showAll () {
    var n = 0;
    for (var i = 0; i < this.table.length; i++) {
        if (this.table[i] != undefined) {
            console.log(i + ': ' + this.table[i]);
        }
    }
}

运行一下代码测试：

1
2
3
4
5
6
const hash = new HashTable();
hash.put("Preshine","Preshine"),
hash.put("Clayton","Clayton"),
hash.showAll()// 8: Preshine 45: Clayton
hash.put("Raymond","Raymond"),
hash.showAll()// 8: Preshine 45: Raymond

这里发现 我往哈希表中put了两个不同的key值 ‘Clayton’和’Raymond’，但这时候后者把前者的值给覆盖了，而且在数组中的存储坐标也一致，说明发生了哈希碰撞。

下面我们就稍微改进下散列函数：

1
2
3
4
5
6
7
8
9
10
function betterHash (str, arr) {
    var H = 37;
    var total = 0;
    for (var i = 0; i < str.length; i++) {
        total += H * total + str.chatCodeAt(i);
    }
    total = total % arr.length;
 
    return parseInt(total);
}

为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。

这里定义了一个常量 H = 37;  这个质数37是一个比较好的数字适合我们的哈希算法来参与哈希键值运算，并且使生成的键值在哈希表中均匀分布。
并且加一个 get方法：

应用新的散列键值函数后 就没有发生 碰撞了。

1
2
3
4
5
const hash = new HashTable();
hash.put("Preshine","Preshine");
hash.put("Clayton","Clayton");
hash.put("Raymond","Raymond");
hash.showAll()// 22: Preshine 58: Clayton 99: Raymond

即使再高效的散列键值生成函数也是有可能发生碰撞了，处理碰撞方法有很多中，这里我介绍2种方法。

开链法

当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。即使两个键散列后的值相等，依然被保存在同样的位置，只不过它们在第二层数组中的位置不一样罢了，如图：

首先要初始化一下HashTable的数据存储结构:

1
2
3
4
5
function buildchains () {
    for (var i = 0; i < this.table.length; i++) {
        this.table[i] = [];
    }
}

下面给出put和get方法的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function put (key, data) {
    var pos = this.betterHash(key);
    var index = 0;
    if (!this.table[pos][index]) {
        this.table[pos][index] = key;
        this.table[pos][index + 1] = data;
    } else {
        index++;
        while (this.table[pos][index]) {
            index++;
        }
        this.table[pos][index] = key;
        this.table[pos][index + 1] = data;
 
    }
}

put的时候先算出哈希键值，然后在哈希表中查看是否有重复的哈希键值，如果没有重复的，则把值放入该位置，这时候数据是占用了数组的2个位置，是把key值存放之后，立即把值紧跟着存在后面；如果哈希键值有重复，则寻找到当前哈希键所在的哈希表的位置，然后在当前位置的数组中找到还没有利用的空间，然后把key值和value一起连续存储(其实就是JS数组的push()操作-_ - )。
这里的二维数组存储类似于一维数组中每个元素都是一个链表，Java中的HashTable类就是这样的存储结构。

get的时候就很简单了，就是一个把put过程取反的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function get (key) {
    var pos = this.betterHash(key);
    var index = 0;
    if (this.table[pos][index] === key) {
        return this.table[pos][index + 1];
    } else {
        index += 2;
        while (this.table[pos][index]) {
            index++;
        }
        this.table[pos][index] = key;
        this.table[pos][index + 1] = data;
 
    }
}

2.线性探测法
线性探测法属于一种更一般化的散列技术：开发寻址散列。当发生碰撞时，线性探测发检测散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存储数据。

如果数组的大小是待存储数据个数的1.5倍，那么使用开链法；如果数组的大小是待存储的数据的2倍及两倍以上，那么使用线性探测法。

采用线性探测法的时候，先给HashTable类初始化一个存储值的数组values = []; 存储键值使用table = [];

1
2
3
4
...
this.values = [];
...

上面分析了怎么存储数据之后，我们来重写下put和get方法：

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
function put (key, data) {
    var pos = this.betterHash(key);
    if (!this.table[pos]) {
        this.table[pos] = key;
        this.values[pos] = data;
    } else {
        while (this.table[pos]) {
            pos++;
        }
        this.table[pos] = key;
        this.values[pos] = data;
    }
}

function get (key) {
    var pos = -1;
    pos = this.betterHash(key);
    if (pos > -1) {
        for (var i = pos; this.table[pos]; i++) {
            if (this.table[pos] === key) {
                return this.values[pos];
            }
        }
    }
 
    return undefined;
}

照着前面的思路把数组给存进去之后，在拿的时候，只需要算出键的哈希值，在table中从pos坐标开始遍历，找到存储key值的坐标后直接用当前return values[pos];就拿到存入的数据了。

最后要注意哈希表哈希算法的计算复杂度和计算时间，哈希函数也正是哈希表的精髓所在。基于key-value数据结构存储的应用非常广泛，因为使用它非常方便，效率和很高，常见的有很多基于key-value存储的应用，比如redis数据库等。

实现

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
function HashTable() {
this.hashKey = 33;
this.hashLength = 137;
this.key = new Array(this.hashLength);
this.value = new Array(this.hashLength);
}
HashTable.prototype._showAll = function() {
for (let i = 0; i < this.hashLength; i++) {
if (this.key[i] !== undefined) {
console.log(`${i} ${this.key[i]}:${this.value[i]}`);
}
}
};
HashTable.prototype.hash = function(key) {
var index = 0;
for (var i = 0; i < key.length; i++) {
index += this.hashKey * index + key[i].charCodeAt();
}
index = index % this.value.length;
return parseInt(index);
};
HashTable.prototype.get = function(key) {
let index = this.hash(key);
while (this.key[index] !== undefined && this.key[index] !== key) index++;
return this.value[index];
};
HashTable.prototype.set = function(key, value) {
let index = this.hash(key);
while (this.key[index] !== undefined) index++;
this.key[index] = key;
this.value[index] = value;
};
HashTable.prototype.remove = function(key) {
let index = this.hash(key);
while (this.key[index] !== key) index++;
this.key[index] = undefined;
this.value[index] = undefined;
};

应用

由于js对象自带hash特性 而且hash应用其实非常多 这里就不特别举例了。

见705. 设计哈希集合

参考 & 引用

https://blog.csdn.net/PingZhi_6766/article/details/78025313

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

基本数据结构

回顾一波基本数据结构，做个整理。

目录

[队列](# 队列(queue))
[栈](# 栈(Stack))
[链表](# 链表(List))
[堆](# 堆(Heap))

阅读全文 »

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

堆(Heap)

定义

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

堆的常用方法：

  • 构建优先队列

  • 支持堆排序

  • 快速找出一个集合中的最小值（或者最大值）

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

堆和普通树的区别

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组，且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

来自数组的树

用数组来实现树相关的数据结构也许看起来有点古怪，但是它在时间和空间山都是很高效的。

我们准备将上面的例子中的树这样存储：

1
[ 10, 7, 2, 5, 1 ]

就这样！我们除了一个简单的数组以外，不需要任何额外的空间。

可以用堆做什么？

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：

  • shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
  • shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。

shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 **O(log n)**。

基于这两个原始操作还有一些其他的操作：

  • insert(value): 在堆的尾部添加一个新的元素，然后使用 shiftUp 来修复对。
  • remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆。
  • removeAtIndex(index): 和 remove() 一样，差别在于可以移除堆中任意节点，而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown()，如果与父节点比较发现无序则使用 shiftUp()。
  • replace(index, value)：将一个更小的值（最小堆）或者更大的值（最大堆）赋值给一个节点。由于这个操作破坏了堆属性，所以需要使用 shiftUp() 来修复堆属性。

上面所有的操作的时间复杂度都是 **O(log n)**，因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间：

  • search(value):堆不是为快速搜索而建立的，但是 replace() 和 removeAtIndex() 操作需要找到节点在数组中的index，所以你需要先找到这个index。时间复杂度：**O(n)**。
  • buildHeap(array):通过反复调用 insert() 方法将一个（无序）数组转换成一个堆。如果你足够聪明，你可以在 O(n) 时间内完成。
  • 堆排序：由于堆就是一个数组，我们可以使用它独特的属性将数组从低到高排序。时间复杂度：**O(n lg n)**。

堆还有一个 peek() 方法，不用删除节点就返回最大值（最大堆）或者最小值（最小堆）。时间复杂度 O(1) 。

注意：到目前为止，堆的常用操作还是使用 insert() 插入一个新的元素，和通过 remove()移除最大或者最小值。两者的时间复杂度都是**O(log n)**。其其他的操作是用于支持更高级的应用，比如说建立一个优先队列。

实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
const swapData = function (array, index_a, index_b) {
  let temp = array[index_a];
  array[index_a] = array[index_b];
  array[index_b] = temp;
}
const isNumber = function (obj) {
  return typeof obj === 'number' && !isNaN(obj)
}
function Heap(heapArray) {
  this.data = [];
  this.build(heapArray);
}
Heap.prototype.insetValue = function (value) {
  if (isNumber(value)) {
    this.data.push(value);
    this.shiftUp(this.data.length - 1);
  }
}
Heap.prototype.size = function () {
  return this.data.length;
}
Heap.prototype.isEmpty = function () {
  if (this.data.length === 0) {
    return true
  }
  return false;
}
Heap.prototype.getTop = function () {
  return this.data[0] === undefined ? null : this.data[0];
}
Heap.prototype.removeTop = function () {
  let value = undefined;
  if (this.data.length > 1) {
    let value = this.data[0];
    this.data[0] = this.data[this.data.length - 1];
    this.data.pop();
    this.shiftDown(0);
    return value;
  } else if (this.data.length === 1) {
    return this.data.pop();
  } else {
    return null;
  }
}
Heap.prototype.removeAtIndex = function (index) {
  let value = this.data[index];
  this.data[index] = this.data[this.data.length - 1];
  this.data.pop();
  if (this.data[index] > this.data[Math.floor((index - 1) / 2)]) {
    this.shiftUp(index);
  } else if (this.data[index] < this.data[index * 2 + 1]
    || this.data[index] < this.data[index * 2 + 2]) {
    this.shiftDown(index);
  }
  return value;
}
Heap.prototype.shiftUp = function (index) {
  let fatherIndex = Math.floor((index - 1) / 2);
  while (index >= 0) {
    if (this.data[fatherIndex] < this.data[index]) {
      swapData(this.data, fatherIndex, index);
      index = fatherIndex;
      fatherIndex = Math.floor((index - 1) / 2);
    }
    else {
      break;
    }
  }
}
Heap.prototype.shiftDown = function (index) {
  const len = this.data.length;
  let fatherIndex_1 = index * 2 + 1;
  let fatherIndex_2 = index * 2 + 2;

  while (fatherIndex_1 < len || fatherIndex_2 < len) {
    let swapFather = undefined;

    if (this.data[fatherIndex_2] === undefined
      || this.data[fatherIndex_1] > this.data[fatherIndex_2]) {
      swapFather = fatherIndex_1;
    } else {
      swapFather = fatherIndex_2;
    }
    if (this.data[index] < this.data[swapFather]) {
      swapData(this.data, swapFather, index);
      index = swapFather;
      fatherIndex_1 = index * 2 + 1;
      fatherIndex_2 = index * 2 + 2;
    } else {
      break;
    }
  }
}
Heap.prototype.build = function (heapArray) {
  for (let i = 0; i < heapArray.length; i++) {
    this.insetValue(heapArray[i])
  }
}
Heap.isHeap = function (heapArray) {
  const len = heapArray.length;
  for (let i = 0; (2 * i + 2) < len; i++) {
    if (heapArray[i] < heapArray[2 * i + 1] || heapArray[i] < heapArray[2 * i + 2]) {
      return false
    }
  }
  return true;
}

应用

1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
    最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例 ：

1
2
3
输入:[2,7,4,1,8,1]
输出：1
解释: 最终剩下的石头重量是 1

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  let stoneHeap = new Heap(stones);
  while (true) {
    let stoneFirst = stoneHeap.removeTop();
    if (stoneHeap.isEmpty()) {
      return stoneFirst;
      break;
    }
    let stoneSecond = stoneHeap.removeTop();
    let smallStone = stoneFirst - stoneSecond;
    if (smallStone !== 0) {
      stoneHeap.insetValue(smallStone);
    }
  }
};