algorithm-extra-note

持续更新ing，本文用于记录学习算法中一些很细碎的知识点。

蔡基姆拉尔森计算公式

用于计算几月几号是星期几。

假设星期为 w,年份为 y,月份为 m,日期为 d。
$w =(d+2m+3(m +1)/5 +y +y/4-y/100 +y/400)$ %7

然后把计算出来的 w 加上 1 就是真正的星期几了

注意每年的 1,2 月要当成上一年 13,14 月计算，上述的除法均为整除。

数论基础

整除

定义:设a,b属于Z，a不等于0，如果存在q属于Z使得b= aq,那就说b可被a整除，记做a|b，且称b是a的倍数,a是b的约数(也称为除数、因数)。

带余数除法

设a,b是2个正整数且b不等于0，则存在唯一整数q和r，使a =qb+r,0<r<|b|。这个式子叫做带余数除法，并记余数r=a modb。例如 13 mod5= 3,10mod 2=0。当r =0的时候，就出现了整除，是a的约数。

(a+b)%n=(a%n+b%n)%n
(a*b)%n=((a%n)*(b%n))%n

排序算法对比

下图来自清华大学出版的《算法》书

快速幂

核心思想：利用二进制来加速运算

代码如下：

#define ll long long 
ll qpow(int base, int power) {
	ll result = 1;
	while (power > 0) {
		if (power & 1)			
			result *= base;     
		power >>= 1;			
		base *= base;           
	}
	return result;              
}

Boyer-Moore 投票算法

摩尔投票算法（Boyer-Moore Majority Vote Algorithm）是一种用于查找数组中出现次数超过一半的主要元素的高效算法。它的核心思想是通过消除不同的元素对来找到主要元素，这个算法的时间复杂度为 O(n)，其中 n 是数组的长度。下面是该算法的基本原理：

初始化两个变量 candidate 和 count，其中 candidate 用于保存候选主要元素，count 用于记录候选主要元素出现的次数。初始时，candidate 可以是任何数组中的元素，而 count 初始化为0。
遍历数组中的每个元素：

如果 count 等于0，将当前元素设置为候选主要元素 candidate，并将 count 设置为1。
如果count不等于0，检查当前元素是否等于candidate：
- 如果相等，将 count 递增1，表示找到了一个与候选主要元素相同的元素。
- 如果不相等，将 count 递减1，表示找到了一个与候选主要元素不同的元素。

在遍历完成后，candidate 变量中存储的元素就是数组中的主要元素。

这个算法的核心思想在于消除不同元素对，最终剩下的元素就是主要元素，因为主要元素的出现次数超过一半。算法的优点是只需要进行一次遍历，具有较低的时间复杂度和空间复杂度。

摩尔投票算法适用于大多数寻找主要元素的问题，例如，查找出现次数超过一半的元素，查找众数等。它是一个高效的算法，通常用于解决此类问题。

int majorityElement(vector<int>& nums) {
    int candidate=nums[0],count=0;
    for(int num:nums){
        if(candidate==num){
            count++;
        }else{
            count--;
            if(count<0){
                candidate=num;
                count=1;
            }
        }
    }
    return candidate;
}

Charles's Castle

algorithm-extra-note