## 集合结构

集合是由一组无序且唯一(即不能重复)的项组成的。

    class MySet {
      items = {}
    add(element) {
    if (!this.has(element)) {
    this.items[element] = element
    return true
    }
    return false
    
    }
    delete(element) {
    if (this.has(element)) {
    delete this.items[element]
    return true
    }
    return false
    
    }
    has(element) {
    return element in this.items
    }
    clear() {
    this.items = {}
    }
    size() {
    return Object.keys(this.items).length
    }
    values() {
    return Object.values(this.items)
    }
    }
    let myset = new MySet()
    let arr = [1, 1, 2, 2, 5, 5, 8, 5]
    arr.forEach((item) => {
    myset.add(item)
    })
    console.log(myset.values()) //[1, 2, 5, 8]

### ES6的Set

    let s1 = new Set([1, 2, 3])
    let s2 = new Set([2, 3, 4])
    // 并集
    let myset = new Set([...s1, ...s2])
    console.log(myset) //{1, 2, 3, 4}
    // 交集
    myset = new Set([...s1].filter((item) => s2.has(item)))
    console.log(myset) //{2, 3}
    // 差集
    myset = new Set([...s1].filter((item) => !s2.has(item)))
    console.log(myset) //{1}

## 字典结构

字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。

    class ValuePair {
    constructor(key, value) {
    this.key = key
    this.value = value
    }
    }
    class Dictionary {
    table = {}
    toStr(item) {
    if (item === null) {
    return "NULL"
    } else if (item === undefined) {
    return "UNDEFINED"
    } else if (typeof item === "string" || item instanceof String) {
    return item
    }
    return JSON.stringify(item)
    
    }
    hasKey(key) {
    return this.table[this.toStr(key)] != null
    }
    set(key, value) {
    if (key != null && value != null) {
    const tableKey = this.toStr(key)
    this.table[tableKey] = new ValuePair(key, value)
      return true
    }
    
    return false
    
    }
    get(key) {
    const valuePair = this.table[this.toStr(key)]
    return valuePair == null ? undefined : valuePair.value
    }
    remove(key) {
    if (this.hasKey(key)) {
    delete this.table[this.toStr(key)]
    return true
    }
    return false
    
    }
    keys() {
    return this.keyValues().map((item) => item.key)
    }
    values() {
    return this.keyValues().map((item) => item.value)
    }
    keyValues() {
    return Object.values(this.table)
    }
    size() {
    return Object.keys(this.table).length
    }
    isEmpty() {
    return this.size() === 0
    }
    clear() {
    this.table = {}
    }
    forEach(cb) {
    const valuePair = this.keyValues()
    for (let i = 0; i < valuePair.length; i++) {
    cb(valuePair[i].key, valuePair[i].value)
    }
    }
    }
    let mymap = new Dictionary()
    mymap.set("name", "张三")
    mymap.set({ age: 18 }, "年龄")
    mymap.forEach((key, value) => {
    console.log(key, value)
    })

### 散列表

HashMap类，它是Dictionary类的一种散列表实现方式。散列算法的作用是尽可能快地在数据结构中找到一个值。

    class ValuePair {
    constructor(key, value) {
    this.key = key
    this.value = value
    }
    }
    class HashTable {
    table = {}
    toStr(item) {
    if (item === null) {
    return "NULL"
    } else if (item === undefined) {
    return "UNDEFINED"
    } else if (typeof item === "string" || item instanceof String) {
    return item
    }
    return JSON.stringify(item)
    
    }
    hashCode(key) {
    const tableKey = this.toStr(key)
    let hash = 5381
    for (let i = 0; i < tableKey.length; i++) {
    hash = hash * 33 + tableKey.charCodeAt(i)
    }
    return hash % 1013
    
    }
    set(key, value) {
    if (key != null && value != null) {
    const position = this.hashCode(key)
    this.table[position] = new ValuePair(key, value)
      return true
    }
    
    return false
    
    }
    get(key) {
    const valuePair = this.table[this.hashCode(key)]
    return valuePair == null ? undefined : valuePair.value
    }
    remove(key) {
    const hash = this.hashCode(key)
    const valuePair = this.table[hash]
    if (valuePair != null) {
    delete this.table[hash]
    return true
    }
    return false
    
    }
    }
    let mymap = new HashTable()
    mymap.set("name", "张三")
    mymap.set({ age: 18 }, "年龄")

### ES6的Map

    let mymap = new Map()
    mymap.set("name", "张三")
    obj = { age: 18 }
    mymap.set(obj, "年龄")
    console.log(mymap)
    obj = null
    console.log(mymap)

WeakMap只能是对象为键：

    let mymap = new WeakMap()
    obj = { age: 18 }
    mymap.set(obj, "年龄")
    obj = null
    console.log(mymap)


JavaScript数据结构与算法(集合与字典)

在命令行下：`vi xxx` → 普通模式（主要操作：复制、粘贴、删除）。

普通模式下：`i 或 o` → 编辑模式（主要操作：编辑文本），ESC退出编辑模式，返回普通模式。

- i：当前光标前插入
- o：当前光标行的下一行插入

普通模式下：`: 或 /` → 命令模式，ESC退出命令模式，返回普通模式。

## 普通模式

### 移动光标

- ^：移动到行头，0 也可移动到行头
- $：移动到行尾
- w：向后移动到词头
- e：向后移动到词尾
- b：向前移动到词头
- gg：文档开头
- G（Shift + g）：文档末尾，3G 移动到第三行

### 复制

- yy：复制当前行，3yy 复制3行
- y^：复制光标位置到行首
- y$：复制光标位置到行尾
- yw：复制一个词（光标位置到空格）

### 剪切

- dd：剪切当前行，3dd 剪切3行
- dw：剪切一个词（光标位置到空格）
- x：剪切光标位置，相当于del
- X（Shift + x）：剪切光标前一个位置，相当于Backspace

### 粘贴

- p：粘贴

### 替换

- r：替换光标位置
- R（Shift + r）：依次替换

### 撤销和重做：

- u - 撤销
- Ctrl + r - 重做

## 命令模式

### 文件操作

- :w 保存
- :q 退出
- :wq 保存并退出
- :q! 不保存强制退出

### 设置

- :noh 取消高亮显示
- :set nu 显示行号，:set nonu 关闭行号

### 查找

- /pattern：向前搜索指定模式
- n：跳转到下一个搜索结果
- N：跳转到上一个搜索结果

### 替换

- :s/old/new/g 替换当前行所有匹配的字符串
- :%s/old/new/g 全局替换 old 为 new


Vim文本编辑器学习笔记

## 需求

如果传入的字符串是回文字符串，则返回 true，否则返回 false。

回文 palindrome，指在忽略标点符号、大小写和空格的前提下，正着读和反着读一模一样，例如：上海自来水来自海上。

## 代码实现

    function palindrome(str) {
      // 去除空格，字母转小写
      str = str.replace(' ', '').toLowerCase()
      // 去除非字母数字
      if (str.match(/[^0-9a-z]/)) {
        while (str.match(/[^0-9a-z]/)) {
          str = str.replace(/[^0-9a-z]/, '')
        }
      }
    // 回文检查
    let newStr = ''
    for (let i = str.length - 1; i >= 0; i--) {
    newStr += str[i]
    }
    return str == newStr
    }


JavaScript回文检查器（freeCodeCamp项目）

## 简介

PHPWord 是一个用纯 PHP 编写的库，它提供了一组用于写入和读取不同文档文件格式的类。

项目地址：[https://github.com/PHPOffice/PHPWord](https://github.com/PHPOffice/PHPWord)

## 使用

    // 引入PHPWord类库
    require '../vendor/autoload.php';
    use \PhpOffice\PhpWord\PhpWord;
    // 创建Word文档
    $phpWord = new PhpWord();
    // 设置默认字体和字号
    $phpWord->setDefaultFontName('宋体');
    $phpWord->setDefaultFontSize(14); //四号字体
    // 定义一级标题样式
    $phpWord->addTitleStyle(1, ['size' => 16, 'bold' => true]); //三号字体
    // 添加段落
    $section = $phpWord->addSection();
    $section->addText('添加文本', ['size' => 18, 'bold' => true], ['alignment' => 'center', 'spaceAfter' => 240]);
    $section->addTitle('添加标题', 1);
    $section->addText('添加文本', null, ['spaceAfter' => 240]);
    // 添加表格
    $table = $section->addTable(['borderSize' => 7.5, 'cellMargin' => 100, 'layout'=> 'fixed']);
    $table->addRow();
    $table->addCell(1200, ['valign' => 'center'])->addText("列1", ['size' => 10.5,'bold' => true],['alignment'=>'center']);
    $table->addCell(2600,['valign' => 'center'])->addText("列2", ['size' => 10.5,'bold' => true],['alignment'=>'center']);
    $table->addCell(2600,['valign' => 'center'])->addText("列3", ['size' => 10.5,'bold' => true],['alignment'=>'center']);
    $table->addCell(2600,['valign' => 'center'])->addText("列4", ['size' => 10.5,'bold' => true],['alignment'=>'center']);
    $table->addRow();
    $table->addCell(null, ['width'=>500])->addText("行A", ['size' => 10.5,'alignment' => 'both']);
    $cell = $table->addCell();
    $cell->addText("行B", ['size' => 10.5,'alignment' => 'both']);
    $cell->addLink('https://www.baidu.com/', 'https://www.baidu.com/',array('color' => '0000FF','size' => 10.5, 'underline' => \PhpOffice\PhpWord\Style\Font::UNDERLINE_SINGLE));
    $info = '<w:br />行C';
    $cell = $table->addCell();
    $textrun = $cell->addTextRun();
    $textrun->addText('PMID：',['size'=>10.5]);
    $textrun->addLink('https://www.baidu.com/', '百度', array('color' => '0000FF','size' => 10.5, 'underline' => \PhpOffice\PhpWord\Style\Font::UNDERLINE_SINGLE));
    $table->addCell()->addText("行D", ['size' => 10.5,'alignment' => 'both']);
    // 保存文档
    $objWriter = \PhpOffice\PhpWord\IOFactory::createWriter($phpWord, 'Word2007');
    $objWriter->save('hello.docx');


利用PHPWord不使用模板纯代码生成Word

算法复杂度分为时间复杂度和空间复杂度。**时间复杂度**是指程序要执行的次数，而非执行时间；而**空间复杂度**是指算法执行过程中大概所占用的最大内存空间。计算机资源最重要的是时间和空间(即寄存器)资源，因此复杂度分为时间和空间复杂度。

## 大O表示法

大O时间复杂度表示法：T(n)=O(f(n))。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

常见的大O数量级函数：
f(n)名称1常数log(n)对数n线性n*log(n)对数线性n²平方n³立方2ⁿ指数![](https://thumbsnap.com/i/NuYwjTK7.jpg)
## 列表常用操作性能

按索引取值和赋值（v=a[i]，a[i]=v），由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)。

列表增长：lst.append(v)，执行时间是O(1)；lst= lst+[v]，执行时间是O(n+k)，其中 k 是被加的列表长度。

4种生成n个整数列表的方法：

from timeit import Timer def t1(): lst = [] for i in range(1000): lst = lst + [i] def t2(): lst = [] for i in range(1000): lst.append(i) def t3(): lst = [i for i in range(1000)] def t4(): lst = list(range(1000)) time1 = Timer("t1()", "from __main__ import t1") print("concat:\t\t{} seconds".format(time1.timeit(1000))) time2 = Timer("t2()", "from __main__ import t2") print("append:\t\t{} seconds".format(time2.timeit(1000))) time3 = Timer("t3()", "from __main__ import t3") print("comprehension:\t{} seconds".format(time3.timeit(1000))) time4 = Timer("t4()", "from __main__ import t4") print("list range:\t{} seconds".format(time4.timeit(1000)))

可以看到，4种方法运行时间差别挺大的，列表连接（+）最慢，中间的是append和列表推导式，List range最快。

## 字典常用操作性能

与列表不同，字典是根据键值（key）找到数据项，而列表是根据索引（index）。最常用的取值和赋值，其性能均为O(1)。另一个重要操作contains(in)是判断字典中是否存在某个键值（key），这个性能也是O(1)。

更多Python数据类型操作复杂度可参考官方文档：[https://wiki.python.org/moin/TimeComplexity](https://wiki.python.org/moin/TimeComplexity)


Python数据结构与算法

这里是 aboss.top 的自留地。写了十几年野路子代码，攒了些摸爬滚打的经验，做成系列课程慢慢讲；也留了一小块地方，记记代码之外的胡思乱想。