海屿文章列表

优先队列(Priority Queue)

简单介绍下优先队列,它不记录入队顺序,而是当前最大/最小的元素优先出队。我们可以用最大/最小堆来实现优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。这篇文章以Heapify的源码为例,简要介绍其实现。

优先队列的表示

我们用数组来表示二叉堆,并将根节点的索引置为 1。Heapify 中使用使用两个独立的类型数组(默认使用 Uint32Array )表示二叉堆。

heap-representations.png

在堆中,位置k的节点的父节点在位置k / 2;相反,位于位置k的节点的两个子节点位于位置2k2k +1。我们可以通过对数组索引执行简单的计算来上下移动。

    constructor(capacity = 64, keys = [], priorities = [],
        KeysBackingArrayType = Uint32Array,
        PrioritiesBackingArrayType = Uint32Array) {

        this.capacity = capacity;
        this._keys = new KeysBackingArrayType(capacity + ROOT_INDEX); // ROOT_INDEX = 1;
        this._priorities = new PrioritiesBackingArrayType(capacity + ROOT_INDEX);
        if (keys.length !== priorities.length) {
            throw new Error("Number of keys does not match number of priorities provided.");
        }
        if (capacity < keys.length) {
            throw new Error("Capacity less than number of provided keys.");
        }
        // copy data from user
        for (let i = 0; i < keys.length; i++) {
            this._keys[i + ROOT_INDEX] = keys[i];
            this._priorities[i + ROOT_INDEX] = priorities[i];
        }
        this.length = keys.length;
        for (let i = keys.length >>> 1; i >= ROOT_INDEX; i--) {
            this.bubbleDown(i);
        }
    }

插入或删除元素

插入或删除后都后需要重新调整堆的结构。插入时我们直接放在最后然后递归向上浮动到合适位置;删除时顶部空缺,我们先将最后一个节点换到顶部,然后将其下沉到合适位置。浮动的时间复杂度为O(log n)

上浮

  bubbleUp(index) {
        const key = this._keys[index];
        const priority = this._priorities[index];

        while (index > ROOT_INDEX) {
            const parentIndex = index >>> 1;   // 父元素索引
            if (this._priorities[parentIndex] <= priority) {
                break;  // 如果父元素优先级更小,则满足了堆的性质
            }
            // 否则将父元素沉下来
            this._keys[index] = this._keys[parentIndex];
            this._priorities[index] = this._priorities[parentIndex];

            index = parentIndex; // 重复下一级
        }

        // 至此找到了插入元素要放置的位置
        this._keys[index] = key;
        this._priorities[index] = priority;
    }

下沉

bubbleDown(index) {
        const key = this._keys[index];
        const priority = this._priorities[index];

        const halfLength = ROOT_INDEX + (this.length >>> 1);  // no need to check the last level
        const lastIndex = this.length + ROOT_INDEX;
        while (index < halfLength) {
            const left = index << 1;
            if (left >= lastIndex) {
                break;  // 到最后一个节点,无法继续下沉
            }

            // 选择左孩子
            let childPriority = this._priorities[left];
            let childKey = this._keys[left];
            let childIndex = left;

            // 如有右孩子,选择优先级最小的
            const right = left + 1;
            if (right < lastIndex) {
                const rightPriority = this._priorities[right];
                if (rightPriority < childPriority) {
                    childPriority = rightPriority;
                    childKey = this._keys[right];
                    childIndex = right;
                }
            }

            if (childPriority >= priority) {
                break;  // 如果孩子优先级更小,则满足了堆的性质
            }

            // 否则将子元素浮上去
            this._keys[index] = childKey;
            this._priorities[index] = childPriority;

            index = childIndex;
        }

        // 至此找到了插入元素要放置的位置
        this._keys[index] = key;
        this._priorities[index] = priority;
    }

在最后实现了下面三个生成器函数,让我们可以方便的获取优先队列中的值和优先级。

   * [Symbol.iterator]() {
        for (let i = 0; i < this.length; i++) {
            const priority = this._priorities[i + ROOT_INDEX];
            const key = this._keys[i + ROOT_INDEX];
            yield [key, priority];
        }
    }

    * keys() {
        for (let i = 0; i < this.length; i++) {
            yield this._keys[i + ROOT_INDEX];
        }
    }

    * priorities() {
        for (let i = 0; i < this.length; i++) {
            yield this._priorities[i + ROOT_INDEX];
        }
    }

参考文章

https://github.com/luciopaiva/heapify/blob/master/heapify.mjs
https://algs4.cs.princeton.edu/24pq/

《恋情的终结》书摘

唯一真正能持续的爱是能接受一切的,能接受一切失望,一切失败,一切背叛,甚至能接受这样一种悲哀的事实:最终,最深的欲望只是简单的相伴。


人若是动了感情,就并不要求一件事情有道理


they-say-love-is-blind-2-682x1024.jpg

倍增思想

倍增思想的核心是每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。

在变化规则相同的情况下加速状态转移

这里变化规则相同指的是:

  • 每次的变化规则必须相同
  • 变化规则必须满足结合律(加法,乘法)

我们考虑一下计算2的10次方,怎样算比较快?
最简单我们乘九次即可,但是每次只是乘2是不是太少了,如果乘以4,乘以8,那么计算的次数是不是就会少以些。我们可以先计算2*2,然后4*416*16,这样我们利用上一次计算的结果,步子越来越大,也就是我们向结果状态转移的速度越来越快,这就是倍增的基本思想。

递归快速幂,先计算a的n/2次方,然后平方;如果n是奇数,那么就先计算a的n-1次方,再乘上a;递归出口是a的0次方为1。

int qpow(int a, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

加速区间操作

稀疏表(Sparse Table)主要用来求解RMQ(Range Minimum/Maximum Query)区间最大/最小值查询问题。即给定一个数组,动态查询数组任意区间范围内的最小值。

我们使用倍增的思想预处理数据,定义一个二维数组 f,对于范围内的所有ST[i][j]表示被查询数组
$[j, j+2^i - 1]$区间的最小值。

我们首先初始化ST[0][j] = a[j],然后在长度为2的每个数组子范围中找到最小值,随后长度翻倍为4,依此类推。

img
img

在计算这个ST数组时,我们可以使用动态规划重用状态。

$ST[i][j]=min \left\{\begin{aligned} ST[i][j-1] \\ ST[i+2^j-1][j-1]\end{aligned}\right. $

img
例如:ST[2][3] = min(ST[1][3], ST[1][5])

查询时我们先计算 $k = \left \lfloor\log_2 (r-l+1) \right \rfloor$ 然后将区间拆分为[r, k-1]和[k, l],然后再ST数组上查找即可。

预处理的复杂度为O(nlogn),之后查询只需要O(1)时间。稀疏表的主要缺点是输入数组无法更改。任何更改都将需要新的预计算来恢复数据结构。如果需要在变化的数组中回答最小或最大范围查询,则最好使用段树。

const int MAXN = 105000;
const int MAXLOG = 20;

int n;
int a[MAXN];
int table[MAXLOG][MAXN];

void buildSparseTable() {
  for (int i = 0; i <= logs[n]; i++) {
    int curLen = 1 << i; // 2^i
    for (int j = 0; j + curLen <= n; j++) {
      if (curLen == 1) {
        table[i][j] = a[j];
      } else {
        table[i][j] = min(table[i - 1][j], table[i - 1][j + (curLen / 2)]);
      }
    }
  }
}

int getMin(int l, int r) {
  int p = logs[r - l + 1];
  int pLen = 1 << p; // 2^p
  return min(table[p][l], table[p][r - pLen + 1]);
}

此外LCA,和后缀数组都能应用到倍增思想。

为何二倍增

假设为K增,那么相关系数$ \log_2N $就变成了$(k-1)\log_kN$(因为预处理时要向后取用(k-1)个已知结果才能将范围扩大为原来的k倍),显然这个函数是单调递增的,所以只有在k为2时复杂度最低。

参考文章

http://adilet.org/blog/sparse-table/
https://oi-wiki.org/ds/sparse-table/
https://zhuanlan.zhihu.com/p/95902286
https://wenku.baidu.com/view/33219414a6c30c2259019e54.html

生日悖论(Birthday paradox)

考虑一个问题,平均在多少人中才能找到一对相同生日?

答案是23人。

换一个角度,如果你进入了一个有着23个人的房间,房间里的人中会和有相同生日的概率便不是50:50了,而是变得非常低。原因是这时候只能产生23种不同的搭配。根据下面概率公式,只有n=253时,能让某人生日与我相同的概率为1/2。
$\begin{aligned} y=(1-\frac{1}{365})^n\end{aligned}$

生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少,也就是说没有特定人选
$\begin {aligned} y=1-\dfrac {365!}{365^{n}\left( 365-n\right) !}\end{aligned}$

比较这两者曲线,第二种的增长非常快:

v2-b8a148d4e4221cf34b22aa28281d0e24_720w.jpg

#include<stdio.h>  
int main()  
{  
    int T,n,i;   
    scanf("%d",&T);  
    int k=0;  
    while(T--)  
    {  
        scanf("%d",&n);  
        double p=1.0;  
        int num=0;  
       for(i=0;; i++)  
       {  
          p=p*(1-(double)i/n);  
           num++;  
          if(1.0-p>=0.5)  
            break;  
       }  
        printf("Case %d: %d\n",++k,num-1);  
    }  
    return 0;
}
  

应用

Pollard’s Rho整数因子分解算法

假设 𝑵 是一个能被分解为 𝒒 ∗ 𝒓 的数 ( 𝑵 = 𝒒 ∗ 𝒓 且 𝒒 ≠ 𝒓 )
我们的目标是找到 𝑵 的其中一个因子 𝒒 或 𝒓 (另外一个因子可以通过除 𝑁 来得到 )

最传统的方法是试除法

let N = 29;                    
let flag = 1;                   
if(N % 2 == 0) flag = 0;                 //首先测试 N 是否是偶数
else for(let i = 3;i * i < N;i += 2){    //与刚才不同的是,我们先从 3 开始,每次增加 2,一直
                                         //到根号下 N 为止。这样我们的测试就在奇数中展开
    if(N % i == 0){            
        flag = 0;
        break;                 
    }
}

我们随即地从[1,N]中选择一个数,这个数是 p 或者 q 的可能性是非常小。但是我们可以转换角度,不再只选取一个整数,我们能够选取 k 个数,然后在这k个数中寻找是否存在a − b 能够整除 𝑁。这样我们就将概率从我们可以将可能性从 1/𝑁 提高到 √1/𝑁
做差之后等于p或q,只有两个还是太少了,我们可以还可以更进一利用最大公约数gcd(|a - b| ,N) > 1,满足这个条件的就多了𝑞,2𝑞,3𝑞,4𝑞,……,(𝑟 − 1)𝑞,𝑟,2𝑟,3𝑟,4𝑟,……,(𝑞 − 1)𝑟一共有𝑞 + 𝑟 − 2 个数,到现在我们只需要大约 $N^(1/4) $ 个数。

在实际计算时,我们不预先生成随机数,而是一个一个地生成并检查连续的两个数。

// 随机数生成
function g (x, prime) {
  return (Math.pow(x, 2) + 1) % prime
}

// 最大公约数
function gcd (a, b) {
  if (!b) return a;
  return gcd(b, a % b)
}

function pollardRho (prime) {
  let x = 2;
  let y = 2;
  let d = 1;

  while (d === 1) {
    x = g(x, prime);  //x runs once
    y = g(g(y, prime), prime); ; //y runs twice as fast

    d = gcd(Math.abs(x - y), prime);

    if (d === prime) return;
    if (d !== 1 && !isNaN(d)) return d;
  }
}

哈希碰撞

我们以CRC16 为例,哈希值是17位,2 ^ 8 = 256 个项目的集合中,哈希冲突的机率就会达到约为50%。
这里是CRC16-CRC64的测试 1

安全的Hash标准的输出长度选为160比特是出于这种考虑。

参考文章

http://www.math.umbc.edu/~campbell/NumbThy/Class/Programming/JavaScript/
https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html
https://wenku.baidu.com/view/c3e3657b27284b73f24250d5.html

Boyer-Moore多数表决算法

问题陈述

假设你有一个未排序的值列表。你想知道列表中是否存在该列表中一半以上元素的值。如果有则这个值是什么?尽可能高效地完成此任务。

出现此问题的一个常见原因可能是容错计算。执行多个冗余计算,然后验证大多数结果是否一致。‘

简单的解决方案

简单的解决方案是哈希表。时间复杂度是O(N),空间复杂度是O(N)。

Boyer-Moore多数表决算法

首先检查该count值。如果计数等于0,则将设置candidate为当前元素的值。接下来,首先将元素的值与当前candidate值进行比较。如果它们相同,则增加count1。如果它们不同,则减少count1。

candidate = 0
count = 0
for value in input:
  if count == 0:
    candidate = value
  if candidate == value:
    count += 1
  else:
    count -= 1

最终 candidate 即为众数,该算法空间复杂度是O(1)。

我们用下面一组数据来理解,我们把 5 看成 -1 ;0 看成 +1 ,只要不同就相互抵消,相同的元素相加,多的一方一定会把另一方抵消掉。下面是计算过程:

[5, 5, 0, 0, 0, 5, 0, 0, 5]

[1, 2, 1, 0, 1, 0, 1, 2, 1]  // count 取值

[5, 5, 5, 5, 0, 0, 0, 0, 0]  // candidate 取值

推广

每次删除三个不相同的数,最后留下的可能是出现次数超过1/3的数,这个思想可以推广到出现次数超过1/k次的元素有哪些。需要注意的是最后还需要再遍历一遍结果,判断次数最多和次多的是不是超过了⌊ n/3 ⌋次。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int i : nums) {
            if (m == i) {
                ++cm;
            } else if (n == i) {
                ++cn;
            } else if (cm == 0) {
                m = i;
                cm = 1;
            } else if (cn == 0) {
                n = i;
                cn = 1;
            } else {
                --cm;
                --cn;
            }
        }
        cm = cn = 0;
        for (int i : nums) {
            if (i == m)
                ++cm;
            else if (i == n)
                ++cn;
        }
        vector<int> res;
        const int N = nums.size();
        if (cm > N / 3)
            res.push_back(m);
        if (cn > N / 3)
            res.push_back(n);
        return res;
    }
};

并行计算

Finding the Majority Element in Parallel

以 [1, 1, 1, 2, 1, 2, 1, 2, 2] 为例,我们可以将其拆开。

分组1:
[1, 1, 1, 2, 1]
candidate = 1
count = 3

分组2:
[2, 1, 2, 2]
candidate = 2
count = 2

可以将第1部分的结果视为与[1,1,1]相同,而将第2部分的结果视为与[2,2]。

参考文章:

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html