算法笔记

第二章：C++快速入门

2.5 数组

• memset - 对数组中每一个元素赋相同的值 - 用于初始化 / 重置

  • memset(数组名,值,sizeof(数组名));

  • 一般初始化 0 或者 -1 ，因为memset使用的是按字节赋值，这样int类型的4个字节都会被赋成相同的值。

  • 若要对数组赋为其他数字 - 使用STL中的fill函数

• string.h头文件函数
  • strlen(字符数组);
    • 得到字符数组中第一个\0前的字符个数
  • strcmp(字符数组1,字符数组2);
    • 返回两个字符串大小比较结果，比较原则是按字典序 - <返回负整数 =返回0 >返回正整数
  • strcpy(字符数组1,字符数组2)；
    • 把字符数组2复制给字符数组1 - 包括结束符\0
  • strcat(字符数组1,字符数组2)
    • 把字符数组2拼接到字符数组1后
• sscanf & sprintf
  • string+ scanf / printf

2.7 指针

• 数组名作为函数参数，相当于指针传入，引用调用
  +* (a+i) == a[i]

  • q-p == &a[i] - &a[j] 相差距离

• 指针引用 - 引用别名

2.8 结构体

• 结构体内部可以定义自身的指针

• 结构体构造函数 - 初始化序列

• 结构体定义后直接申明的变量都是调用默认构造函数 - 跟C++构造函数一样的注意点

2.9 补充

• cin / cout 只有在string输出时才调用，一般多使用printf / scanf， 因为在输出大量数据时很容易超时

• 浮点数精度

const double eps = 1e-8;
const double Pi = acos(-1.0);

# define Equ(a,b) ((fabs((a)-(b)))<(eps))   // ==
# define More(a,b) (((a)-(b))>(eps))    // > 
# define Less(a,b) (((a)-(b))<(-eps))    // < 
# define More(a,b) (((a)-(b))>(-eps))    // >= 
# define More(a,b) (((a)-(b))<(eps))    // <= 

2.10 黑盒测试

while(scanf("%d %d",&a,&b) != EOF)
while(scanf("%s",str) != EOF)
while(gets(str) != NULL)

第四章 入门篇 - 算法初步

4.1 排序

4.1.1 选择排序

• n趟枚举选出依次最小元素

void selectSort(){
    for(int i = 1;i <= n; i++){ //进行n趟操作
        int k = i;
        for (int j =i; j <= n; j++){    //选出[i,n]中最小元素，下标为k
            if(A[j] < A[k])
                k = j;
        }
        int temp = A[i];
        A[i] = A[k];
        A[k] = temp;
    }
}

4.1.2 插入排序

• 序列分为有序与无序两部分，将无序部分一一插入有序部分合适位置处，进行n-1趟

int A[maxn], n;     //n为元素个数，数组下标为1-n
void insertSort(){
    for(int i = 2; i <= n; i++){    //进行n-1趟排序
        int temp = A[i], j = i;     //temp临时存放A[i]，j从i开始往前枚举
        while(j > 1 && temp < A[j-1]){  //只要temp小于前一个元素A[j-1]
            A[j] = A[j-1];      //则把A[j-1]后移一位
            j--;
        }
        A[j] = temp;
    }
}

4.1.3 排序题与sort函数应用

• 通常做题需要排序时直接调用C++的sort函数即可

  • C中的qsort涉及许多复杂指针操作

  • 规避了经典快排极端情况会出现O(n<sup>2</sup>)

• sort(首元素地址，尾元素地址的后一个地址 [，cmp比较函数] )

  • #include<algorithm>

  • using namespace std;

  • sort函数会原地修改传入序列

int a[6] = {5,6,4,1,3,2}
sort(a,a+4) //将a[0]~a[3]进行排序
sort(a,a+6) //将a[0]~a[5]进行排序

• 对非可比类型，比如类，结构体等，需要实现cmp比较函数

  • STL标准容器里vector，string，deque是可用sort的，而set，map本身有序（由红黑树实现不需排序）

  • 不填cmp参数，则默认对可比较类型进行从小到大排序

bool cmp(int a, int b){     // 实现int类型从大到小排序
    return a>b;     // 返回结果为True时，a在b前排序；否则b在a前排序
}

struct node {
    int x,y;
}ssd[10];

bool cmp(node a, node b){   //实现对结构体的排序
    return a.x > b.x    // True则ab，false则ba  - 一级排序
}
bool cmp(node a, node b){   // 二级排序
    if(a.x != b.x)  return a.x > b.x;   //x不等时按x从大到小排序
    else return a.y < b.y;  //x相等时按y从小到大排序
}

• 排序题sort应用与相关Tricks

  • 按string字典序大小排序：使用strcmp(s1,s2) - 返回值>0或<0

  • 并列排名，eg. 1、2、2、4：

    • 直接设置一个变量记录或定义结构体时将排名项加入结构体中；

    • 之后先排序，后修改结构体内的排名值：a[0]=1，遍历剩余元素，若分数等于上个元素分数，则排名值相同，否则等于下标+1

// strcmp(s1,s2)应用
bool cmp(student a, student b){
    if(a.score != b.score)  return a.score > b.score;
    else return strcmp(a.name, b.name) < 0;     //名字字典序小的在前
}

// 并列排名问题 1 - 需要存储
stu[0] = 1;     //有序数组
for(int i = 1; i<n; i++){
    if(stu[i].score == stu[i-1].score)
        stu[i].rank = stu[i-1].rank;
    else stu[i].rank = i + 1;
}

// 并列排名问题 2 - 直接输出
r = 1;
for(int i  = 0;i < n;i++){
    if(i>0 && stu[i].score != stu[i-1].score )
        r = i+1;
    //  输出信息 or stu[i].rank = r;
}

4.2 散列

4.2.1 散列定义与整数散列

• 常见散列函数：直接定址法（恒等变换&线性变换） 平方取中法 除留余数法（mod常为素数）

  • 哈希冲突：开放定址法（线性探查&平方探查） 拉链法

  • map（C++11中unordered_map）

4.2.2 字符串hash初步

• 非整数key映射整数value（初步暂时不讨论冲突，只讨论转化成唯一的整数）
  • 二维坐标点映射整数（0<x,y<R）- H(P) = x * R + y 唯一映射
• 字符串hash

  • 字符串由A~Z构成 - 将其看成26进制，转换成十进制整数映射：26^len-1 最大表示整数

  • 若有A~Za~z构成 - 则将其看成52进制，处理方法与上一致

  • 若出现数字，则有两种处理方法：

    • ① 与上一样，化为62进制

    • ② 若是只出现在特定位置，比如最后一位，则可以用拼接的方式：将前面的字母映射为十进制，拼接上后续数字

// A~Z
int hashFunc(char S[], int len){
    int id = 0;
    for(int i = 0; i < len; i++){
        id = id * 26 + (S[i]-'A')
    }
    return id;
}

// A~Za~z
int hashFunc(char S[], int len){
    int id = 0;
    for(int i = 0; i < len; i++){
        if(S[i]<='Z' && S[i]>='A')      // Z~a之间在ascll上不是相连的
            id = id * 52 + (S[i]-'A');
       else if(S[i]<='z' && S[i]>='a')
            id = id * 52 + (S[i]-'a') + 26;
    }
    return id;
}

// 假设A~Z且最后一位是数字
// A~Z
int hashFunc(char S[], int len){
    int id = 0;
    for(int i = 0; i < len; i++){
        id = id * 26 + (S[i]-'A');
    }
    id = id*10 + (S[i]-'0');
    return id;
}

4.3 递归

• 分治 & 递归

• 递归式 & 递归边界

4.4 贪心

• 简单贪心：当前局部最优来获得全局最优 - 贪心的证明思路一般使用反证+数学归纳法，证明比想到更难，若是想到时自己暂时也无法举出反例，则一般来说是正确的

• 区间贪心：

  • 区间不相交问题：给出N个开区间，选择尽可能多的开区间，使得两两之间没有重合。 - 贪心策略：先按左端点大小排序（右端点大小），总是选择最大左端点（最小右端点）

  • 区间最小点：给出N个开区间，选择最少的点，使得各区间都有点分布 - 与上述贪心策略相反，就是区间相交问题

  • 贪心解决最优化问题 - 思想希望由局部最优求解全局最优 - 适用问题需具有最优子结构性（即一个问题最优解能由其子结构最优解求得） - 贪心解决问题范围有局限性

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 110;
struck Inteval {
    int x,y;    // 开区间左右端点
} I[maxn];

bool cmp(Inteval a, Inteval b){
    if(a.x != b.x) return a.x > b.x;
    else return a.y < b.y;
}

int main(){
    int n;
    while(scanf("%d", &n), n != 0){
        for(int i = 0; i<n; i++)
            scanf("%d%d",&I[i].x, &I[i].y);
        sort(I, I+n ,cmp);  //区间端点排序
        
        //ans记录不相交区间个数，lastX几里路上一个被选中区间的左端点
        int ans = 1, lastX = I[0].x;
        for(int i =1; i<n; i++){
            if(I[i].y <= lastX){        //如果该区间右端点在lastX左边，表示没有重合
                lastX = I[i].x;     //以I[i]作为新选中区间
                ans++;  //不相交区间个数+1
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

4.5 二分

4.5.1 二分查找（整数二分）

• 基于有序序列查找算法，查找第一满足条件的位置，时间复杂度O(logⁿ)

  • mid = left+(right-left)/2（避免int越界），[left,mid-1]，[mid+1,right]；

  • 临界条件：1、查找到 2、left>right

  • 二分条件：1、循环left，相等时就是需要的值直接返回即可 2、二分初始区间为[0,n]

  • ①：序列中是否存在满足条件的元素 ②：寻找有序序列第一个满足某条件元素位置

// 序列中是否存在满足条件的元素 
int binarySearch(int A[], int left, int right, int x){
    int mid;    // mid为left和right中点
    while(left <= right){
        mid = left+ (right - left) / 2;
        if(A[mid] == x) return mid;
        else if(A[mid] > x)
            right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

// 寻找有序序列第一个满足某条件元素位置
int solve(int left, int right){     //左闭右闭写法
    int mid;
    while(left < right){        // 若左开右闭，则 left+1<right
        mid = left + (right - left)/2;
        if( 条件成立 ){
            right = mid;
        } else left = mid +1;       // 若左开右闭，则 left=mid
    }
    return left;    // 左开右闭，return right
}

4.5.2 二分法拓展

• ① 二分法 - 罗尔定理求方程根 eg.f(x)=x²-2=0 求在[left,right]范围方程根

• ② 二分答案：二分法查找结果

  • eg. 给N根木棒，切割希望得到至少K段长度相等的木棒，请问切割最长长度是多少。（切分长度越长，得到的段数越少 - 线性有序）

  • 相当于问：一个有序序列中，满足k>=K的最后一个元素位置 - 满足k<K的第一个元素位置(递减序列)，利用上述模板即可解决

4.5.3 快速幂

• 求幂朴素做法 O(n)：aⁿ=a * a * a..... 一共进行n次乘法

• 快速幂基于二分思想，亦称二分幂，即将幂部分/2拆分，如此只需要进行logⁿ次乘法 O(logⁿ)
  • 递归写法：n/2每次

    • if n = 奇数：aⁿ = a * aa^n-1

    • if n = 偶数：aⁿ = a^n/2 * a^n/2

    • 为了加快运算，奇偶判断使用位运算：if(n&1)

  • 迭代写法：将n化为二进制，二进制第i位上有数，化为a^2i-1

    • eg. a¹¹ = a²³ * a²¹ * a²⁰

    • 步骤①：n&1判断二进制末尾是否=1，ans是则乘以a

    • 步骤②：a=a²，n>>=1，只要n大于0，则继续步骤①；结果ans返回

// 快速幂递归写法
typedef long long LL;
LL binaryPow(LL a, LL b){
    if(b == 0) return 1;
    if(b & 1) return a * binaryPow(a,b-1);
    else{
        LL mul = binaryPow(a,b/2)     // 不能同时调用两个binaryPow，时间复杂度指数倍
        return mul * mul;
    }
}

// 快速幂迭代写法
LL binaryPow(LL a, LL b){
    LL ans = 1;
    while(b > 0){
        if(b & 1)
            ans = ans * a;
        a = a* a;
        b >>= 1;
    }
    return ans;
}

4.6 two pointers

4.6.1 what‘s two pointers

原文：https://www.cnblogs.com/ymjun/p/12171132.html