Jike Algo

上学期知识付费买的极客时间算法系列一直没来得及看，最近准备快速过一遍，在这里记录一下有用的知识点

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式：
```
 a[k]_address = base_address + k * type_size
```
但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变成：
```
 a[k]_address = base_address + (k-1)*type_size
```
对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令

C 语言的设计是从 0 开始，Java、Javascript 等高级语言都是借鉴 C 语言的设计
如果字符串是用链表存储的，如何判断字符串是否是回文的？
1. 快慢指针，一个走一步，一个走两步，找到中间节点
2. 走一步的慢指针在遍历的过程中，将 next 指向之前的指针节点
3. 从中间节点开始，左右两边的节点比对 value 值，然后分别指向 next 节点
4. 得到结果
如何实现浏览器的前进后退操作？

使用两个 Stack 来实现
如何用快排思想在 O(n) 内查找第 K 大的元素?

kth_element
如何优化快速排序？
1. 三数取中法
  
  我们取区间 head，middle 和 tail，取中间值作为 pivot
2. 随机法
  
  从区间中随机取一个数

二分查找的三个容易出错的地方

 def binary_search(arr, target):
     length = len(arr)
     head, tail = 0, length - 1
        
     while head <= tail:
         middle = head + (tail - head) / 2
         if arr[middle] == target:
             return middle
         if arr[middle] > target:
             head = middle + 1
         else:
             tail = middle - 1
        
     return -1

循环推出条件

注意是 head <= tail，而不是 head < tail
middle 的取值

(head + tail) / 2 这种写法是有问题的，有可能溢出
head 和 tail 的更新

head = middle + 1，tail = middle - 1，否则容易死循环

Java 中 HashMap 散列表的实现细节
1. HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
2. 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
3. HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
4. 散列函数
```
 int hash(Object key) {
     int h = key.hashCode()；
     return (h ^ (h >>> 16)) & (capitity - 1);
 }
```
  这里实现非常巧妙，hashCode 是32位的整数，h >>> 16 将高位移到低位，然后与低位异或，这样计算出来的整型值将“具有”高位和低位的性质，分布均匀，后面采用 & 而不是 %，因为 A % B = A & (B - 1)
经典平衡 BST 红黑树的特性
- 根结点是黑色的
- 每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
- 每个节点，从该节点到达其可达子节点的所有路径，都包含相同数目的黑色节点
利用两个堆来实现动态求中位数的方法

如果是静态数据的话，直接排序取中位数即可，如果是动态增加的，如果每次都重新排序取中间值，复杂度较高，不能接受

现在我们先将初始数据按增序排列好，将前 n/2（长度为奇数则为 n + 1 / 2）的数存在一个大根堆中，剩下的数存在一个小根堆中

这样，当总长度为奇数的时候，中位数就是大根堆的堆顶元素，偶数的时候为大根堆堆顶元素 + 小根堆堆顶元素 / 2

当新的元素到来的时候，如果小于大根堆堆顶元素，插入大根堆，反之，则插入小根堆，同时动态保证大根堆和小根堆元素数量比保持不变

其实 pct99 也可以这么去做，就把大根堆和小根堆的长度比由 5:5 变为 99:1
比 KMP 快 3-4 倍的字符串匹配算法 BM 算法 BM
Trie 中的 KMP AC 自动机

用位图来判断一个正整数是否存在

public class BitMap {
    private char[] bytes;
    private int nbits;
        
    public BitMap(int nbits) {
        this.nbits = nbits;
        this.bytes = new char[nbits/16 + 1];
    }

    public void set(int k) {
        if (k > nbits) return;

        int byteIndex = k / 16;
        int bitIndex = k % 16;
        bytes[byteIndex] |= (1 << bitIndex);
    }

    public boolean get(int k) {
        if (k > nbits) return false;
        int byteIndex = k / 16;
        int bitIndex = k % 16;
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;       
    }
}

Java 中 char 类型占 16 bit，也就是2个字节，则一个 char 类型可以表示16个整数是否存在

布隆过滤器

布隆过滤器基于的也是位图的思想，与位图用一个 bit 来判断是否存在不同，布隆过滤器用多个 hash 函数来判断，当 set 一个 item 的时候，用多个 hash 函数计算，将每一位设置为 1，在判断是否存在的时候，同样根据全部 hash 函数来计算，当全部的 bit 均为 1 的时候，我们认为存在，对于布隆过滤器来说，返回 false 的一定不存在，返回 true 的不一定存在

极客时间-算法

FEATURED TAGS

FRIENDS