数据结构和算法

数据结构

一、栈

栈是一种遵从后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端叫做栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

二、队列

队列是一种遵循先进先出原则的一组有序的项。队列在尾部添加元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

三、链表

链表储存有序的元素集合，但不同于数组，链表的每个元素由一个储存元素本身的节点和一个指向下一个元素的引用组成。

1. 单向链表

节点只有链向下一个节点的链接。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

2. 双向链表

节点的链接是双向的，一个链向下一个元素，另一个链向前一个元素。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        self.prev = None

3. 循环链表

最后一个元素指向下一个元素的指针不是引用null，而是指向第一个元素head。

4. 双向循环链表

有指向head元素的tail.next，和指向tail元素的head.prev。

数组和链表的区别

相同：
两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。

不同：
(1) 链表是链式的存储结构；数组是顺序的存储结构。
(2) 链表通过指针来连接元素与元素；数组则是把所有元素按次序依次存储。
(3) 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难。
(4) 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。

四、字典和散列表

1. 字典

以键-值形式储存元素，以遍历整个数据结构的方式获取值。

2. 散列表（HashMap）

以键-值形式储存元素，能够知道值的具体位置，因此能够快速检索到该值。

(1) 冲突版
HashMap数组每一个元素的初始值都是Null。调用 hashMap.put("apple", 0)，插入一个key为“apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置：

index = Hash('apple')

假定最后计算出的index是2，那么结果如下：

因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。

(2) 链表
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

(3) 线性探查
当想向表中某个位置加入一个新元素的时候，如果索引为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试index+2的位置，以此类推。

五、二叉树

1. 常见二叉树

(1) 二叉搜索树
二叉搜索树（Binary Search Tree）是二叉树的一种，但是它只允许你在左侧节点存储比父节点小的值，在右侧节点存储比父节点大或者等于父节点的值。

(2) 二叉平衡树
平衡二叉树，又称AVL树，指的是左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大，且左子树与右子树的高度差最大为1。因此，平衡二叉树满足所有二叉排序（搜索）树的性质。

class Solution:
    def IsBalanced_Solution(self, root):
        if not root:
            return True
        if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
            return False
        return self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)

    def maxDepth(self, root):
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

(3) 堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

在构造堆的基本思想就是：首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。 所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。

2. 二叉树遍历

(1) 中序遍历：左根右

res = []
def dfs(root):
    if not root: return
    dfs(root.left)
    res.append(root)
    dfs(root.right)

3-5-6-7-8-9-10-11-12-13-14-15-18-20-25

(2) 先序遍历：根左右

res = []
def dfs(root):
    if not root:return
    res.append(root)
    dfs(root.left)
    dfs(root.right)

11-7-5-3-6-9-8-10-15-13-12-14-20-18-25

(3) 后序遍历：左右根

res = []
def dfs(root):
    if not root:return
    res.append(root)
    dfs(root.left)
    dfs(root.right)

3-6-5-8-10-9-7-12-14-13-18-25-20-15-11

六、排序算法

1. 冒泡排序

(1) 比较相邻的两个元素，如果前一个比后一个大，则交换位置。
(2) 第一轮的时候最后一个元素应该是最大的一个。
(3) 按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

def bubble_sort(list):
    for i in range(len(list)-1,0,-1):
        for j in range(i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list

2. 选择排序

(1) 在未排序序列中找到最小元素，存放到排序序列的起始位置。
(2) 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。

def select_sort(list):
    length = len(list)
    for i in range(length):
        min = i
        for j in range(i,length):
            if list[j] < list[min]:
                min = j
        list[i],list[min] = list[min],list[i]
    return list

3. 插入排序

(1) 假设数列第一个元素为已排序数列，剩余数列为未排序。
(2) 将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的。

def insert_sort(list):
    length = len(list)
    for i in range(1,length):
        for j in range(i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list

4. 希尔排序

(1) 将整个待排序的列分割成为若干子序列。
(2) 分别进行直接插入排序。

def shell_sort(slist):
    gap = len(slist)
    while gap > 1:
        gap = gap // 2
        for i in range(gap, len(slist)):
            for j in range(i % gap, i, gap):
                if slist[i] < slist[j]:
                    slist[i], slist[j] = slist[j], slist[i]
    return slist

5. 归并排序

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

def merge_sort(array):
    def merge_arr(arr_l, arr_r):
        array = []
        while len(arr_l) and len(arr_r):
            if arr_l[0] <= arr_r[0]:
                array.append(arr_l.pop(0))
            elif arr_l[0] > arr_r[0]:
                array.append(arr_r.pop(0))
        if len(arr_l) != 0:
            array += arr_l
        elif len(arr_r) != 0:
            array += arr_r
        return array

6. 快速排序

快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

def quick_sort(list):
    if list == []:
        return []
    else:
        first = list[0]
        left = quick_sort([l for l in list[1:]if l < first])
        right = quick_sort([l for l in list[1:] if l > first])
        return left +[first] + right

7. 堆排序

它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

def heap_sort(array):
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child
            if heap[parent] >= heap[child]:
                break
            heap[parent], heap[child] = \
                heap[child], heap[parent]
            parent, child = child, 2 * child + 1

    heap, array = array.copy(), []
    for i in range(len(heap) // 2, -1, -1):
        heap_adjust(i)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        array.insert(0, heap.pop())
        heap_adjust(0)
    return array

七、LeetCode相关

1. Python

1 数字

import math
#向上取整
math.ceil(2.1)

#向下取整
math.floor(2.9)

#四舍五入
def round(n):
  return math.ceil(n) if (n - math.floor(n)) >= 0.5 else math.floor(n)

2 字符串

api	作用
len()	计算长度
capitalize(),lower(), upper()	大小写
center(s), ljust(s), rjust(s)	补全
count(s)	出现次数
find(s),lfind(s),rfind(s)	查找位置
split()	分割成列表
replace(old, new [, max])	替换字符串
strip(), lstrip(), rstrip()	去空格

#center(s), ljust(s), rjust(s)
'aaa'.center('b') #'baaab'

#capitalize(), lower(), upper()
'AAA'.lower() #'aaa'

#count()
'aaa'.count('a') #3

#find()
'abc'.find('a') #0

#split()
'a b c'.split() #['a','b','c']

3 列表

api	作用
len()	计算长度
append(x),insert(I,x),pop(i),remove(x)	增删
sort(reverse=False)	排序
reverse()	反转列表
max(),min()	最大最小
count()	计数
extend(l)	列表合并
index()	查找

#append(x), insert(i,x), pop(i), remove(x)
[1,2,3].append(4) #[1,2,3,4]
[1,2,3].insert(1,1.5) #[1, 1.5, 2, 3]
[1,2,3].pop(1) #[1,3]
['a','b','c'].remove('b') #['a', 'c']

#sort(reverse=False)
[1,2,3].sort(reverse=True) #[3,2,1]

#reverse()
[1,2,3].reverse() #[3,2,1]

#index
[1,2,3].index(2) #1

#count
[1,2,3].count(2) #1

#join
''.join(['a','b','c']) #abc

高阶函数

def f(x):
    return x * x
map(f, [1, 2, 3]) #[1,4,9]

from functools import reduce
def add(x, y):
    return x + y
reduce(add, [1, 3, 5]) #9

def is_odd(n):
    return n % 2 == 1
filter(is_odd, [1, 2, 4]) // [1]

4 字典

api	作用
dict.keys()	取键
dict.values()	取值

2. JavaScript

1 Array 数组常用方法

let a = [1, 2, 3]
a.splice(1, 1, 4, 5) // [2]
a // [1, 4, 5, 3]
["a", "b", "c"].slice(1,2)  // ["b"]

["a", "b", "c"].join('-')   // "a-b-c"
["a", "b", "c"].concat("d")   // ["a", "b", "c", "d"]

[3,1,2].sort((a,b) => a-b)  // [1, 2, 3]
["a", "b", "c"].reverse()   // ["c", "b", "a"]

push(), pop(), unshift(), shift()

[3, 10, 18, 20].some(val => val>18)   // true
[3, 10, 18, 20].every(val => val>18)    // false
[3, 10, 18, 20].filter(val => val>18)   // [20]

[1,2,3].forEach(val => val+1)   // undefined
[1,2,3].map(val => val+1)  // [2, 3, 4]

arr.reduce(callback,[initialValue])
[1, 2, 3].reduce(function(prev, cur, index, arr) {
    console.log(prev, cur, index, arr);
    return prev + cur;
},1)  // 7

[1,2,3].indexOf(2)  // 1

2 String 字符串常用方法

"hello".indexOf('h')  // 0
"hello".match("e")  // ["e", index: 1, input: "hello", groups: undefined]   String.match(regexp)
"hello".search("h") //0   String.search(regexp)

"hello".charAt(1)   // "e"
"hello".concat("world")   // "helloworld"
"hello".replace("o","ooo")  // "hellooo"

"abc".slice(1,2)  // "b"
"abc".split("") // ["a", "b", "c"]
"hello".substr(2,3) // "llo"
"hellow".substring(2,3) // "l"

toLowerCase(), toUpperCase()

3 Object

Object.keys({a:1,b:2})  // ["a", "b"]
Object.values({a:1,b:2})  // [1, 2]

3. 进制转换

3.1 十进制转二进制
十进制数除2取余法

3.2 二进制转十进制
把二进制数按权展开、相加即得十进制数。

3.3 二进制转八进制
3位二进制数按权展开相加得到1位八进制数。

3.4 八进制转成二进制
八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零。

3.5 二进制转十六进制
取四合一

3.6 十六进制转二进制
十六进制数通过除2取余法，得到二进制数，对每个十六进制为4个二进制，不足时在最左边补零。

3.7 十进制转八进制或者十六进制
间接法：把十进制转成二进制，然后再由二进制转成八进制或者十六进制。这里不再做图片用法解释。

直接法：把十进制转八进制或者十六进制按照除8或者16取余，直到商为0为止。

3.8 八进制或者十六进制转成十进制
把八进制、十六进制数按权展开、相加即得十进制数。

3.9 api

JavaScript

// 其他 to 十进制
Number.parseInt(x, radix)
// 十进制 to 其他
number.toString(radix)

Python

bin(x, radix) // 2进制
oct(x, radix) // 8进制
int(x, radix) // 10进制
hex(x, radix) // 16进制

4. 位操作

4.1 位操作

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

4.2 位操作常见场景

不用加减乘除做加法

sum1 = num1^num2 // 异或代表两数相加但不进位
sum2 = (num1&num2)<<1 // 进位值
return sum1 + sum2

不用加减乘除做乘法

// 数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2
a = 2
a >> 1 // 1
a << 1 //4

判断奇偶数

// 只要根据数的最后一位是 0 还是 1 来决定即可
a & 1 == 0

交换两数

a ^= b
b ^= a
a ^= b

交换符号

// 整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数
~a + 1

交换符号

// 正数右移 31 位得到 0，负数右移 31 位得到 -1
sign = a >> 31;
i == 0 ? a : (~a + 1)

统计二进制中 1 的个数

// 每计算一次二进制中就少了一个 1
count = 0
while(a){  
  a = a & (a - 1)
  count++
}