倍增思想

倍增思想的核心是每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。在变化规则相同的情况下加速状态转移这里变化规则相同指的是:每次的变化规则必须相同变化规则必须满足结合律(加法,乘法)我们考虑一下计算2的10次方,怎样算比较快?最简单我们乘九次即可,但是每次只是乘2是不是太少了,如果乘以4,乘以8,那么计算的次数是不是就会少以些。我们可以先计算2*2,然后4*4,16*16,这样我们利用上一次计算的结果,步子越来越大,也就是我们向结果状态转移的速度越来越快,这就是倍增的基本思想。递...

生日悖论(Birthday paradox)

考虑一个问题,平均在多少人中才能找到一对相同生日?答案是23人。换一个角度,如果你进入了一个有着23个人的房间,房间里的人中会和你有相同生日的概率便不是50:50了,而是变得非常低。原因是这时候只能产生23种不同的搭配。根据下面概率公式,只有n=253时,能让某人生日与我相同的概率为1/2。$\begin{aligned} y=(1-\frac{1}{365})^n\end{aligned}$生日问题实际上是在问任何23个人中会有两人生日相同的概率是多少,也就是说没有特定人选。$\begi...

Boyer-Moore多数表决算法

问题陈述假设你有一个未排序的值列表。你想知道列表中是否存在该列表中一半以上元素的值。如果有则这个值是什么?尽可能高效地完成此任务。出现此问题的一个常见原因可能是容错计算。执行多个冗余计算,然后验证大多数结果是否一致。‘简单的解决方案简单的解决方案是哈希表。时间复杂度是O(N),空间复杂度是O(N)。Boyer-Moore多数表决算法首先检查该count值。如果计数等于0,则将设置candidate为当前元素的值。接下来,首先将元素的值与当前candidate值进行比较。如果它们相同,则增加...

Javascript 中的 RAII?

RAII 的全称是 “Resource Acquisition is Initialization” 1(资源获取即初始化),它是C++之父Bjarne Stroustrup提出的设计理念,目的是确保异常下的资源管理。换句话说,不管当前作用域以何种方式退出,都会执行资源释放等操作。C++中 RAII 应用很广,C++11 中的两种基本的锁类型,lock_guard 和 unique_lock ,通过对lock和unlock进行一次薄的封装,实现了自动unlock。std::lock_gu...

表驱动法(Table-Driven Approach)

表示原则:把知识叠入数据以求逻辑质朴而健壮。 ——《UNIX编程艺术》表驱动法是一种编程模式——从表里查找信息而不是使用逻辑语句。随着逻辑复杂性的增加,if/else 或switch中的代码将变得越来越肿,所以我们常说数据比程序逻辑更易驾驭。表驱动法就是将这些逻辑中的数据与逻辑分开,从而减少逻辑的复杂度。查表方式通常有如下几种:直接访问以一个月的天数为例,我们要写一串if/else 或者switch/case 来表达逻辑。 if(1 == iMonth) {iDays = 31;} ...