算法笔记 03 —— 算法初步（上）

本系列为胡凡编著的算法笔记当中代码部分的精简版整理，笔者也在同时准备Leetcode刷题和实习面试，希望为有一定编码和数据结构基础的同学提供一份系统型的参考，以方便遗忘时的算法查阅、期末复习总览以及C++学习参照。

目录

01 排序

Ⅰ选择排序

Ⅱ 插入排序

Ⅲ sort排名

02 散列（hash）

Example 01

03 递归

Example 02: 使用递归求解 n 的阶乘

Example 03: 求 Fibonacci 数列的第 n 项

Example 04: 输出 1~n 这 n 个整数的全排列

Example 05: n 皇后问题

附：词汇解释

01 排序

Ⅰ选择排序

//选择排序：选择最小
//for i [0, n]
//for j [i, n]
//flag
//swap

void selectSort(){
    for(int i=1; i<=n; i++){ //i [1, n]
        int flag = i;
        for(int j=i; j<=n; j++){ //j [i, n]
            if(A[j] < A[flag]){
                flag = j;
            }
        }
        
        int temp = A[i];
        A[i] = A[flag];
        A[flag] = temp;  
    } 
}

Ⅱ 插入排序

//插入排序:向后移动
//for i [2, n]
//for j [i, 1)
//flag

void insertSort(){
    for(int i=2; i<=n; i++){ //i [2, n]
        int flag = A[i];
        for(int j=i; j>1; j--){ //j [2, i]
            if(A[j-1] > flag){
                A[j] = A[j-1];
            }
        }
        
        A[j] = flag;
    }
}

Ⅲ sort排名

//sort排名
//struct
//cmp
//rank=i+1

struct Student{
    char name[10];
    char id[10];
    int score;
    int rank;
}stu[10000];

//成绩排序
bool cmp(Student a, Student b){
    if(a.score != b.score){
        return a.score > b.score;
    }else{
        return strcmp(a.name, b,name) < 0;
    }
}

//计算排名
stu[0].rank = 1; //i 0
for(int i=1; i<n; i++){ //i [1, n-1]
    if(stu[i].score == stu[i-1].score){
        stu[i].rank = stu[i-1].rank;
    }else{
        stu[i].rank = i + 1; //序号加一
    }
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Student{
    char id[20];
    int score;
    int local_number; //班级号
    int local_rank; //班级排名
}stu[10010];

bool cmp(Student a, Student b){
    if(a.score != b.score) return a.score > b.score;
    else return strcmp(a.id, b.id) < 0;
}

int main(){
    int n, k;
    int num = 0; //总人数
    
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        //班级输入
        scanf("%d", &k);
        for(int j=0; j<k; j++){
            scanf("%s %d", stu[num].id, &stu[num].score);
            stu[num].local_number = i;
            num++;
        }
        
        //班级排名 local_rank
        sort(stu+num-k, stu+num, cmp);
        stu[num-k].local_rank = 1; //j num-k
        for(int j=num-k+1; j<num; j++){ //j [num-k+1, num]
            if(stu[j].score == stu[j-1].score){
                stu[j].local_rank = stu[j-1].local_rank;
            }else{
                stu[j].local_rank = j+1-(num-k); //序号加一
            }
        }
    }
    
    //全校排名 r
    printf("%d\n", num);
    sort(stu, stu+num, cmp);
    int r = 1; //i 0
    for(int i=1; i<num; i++){ //i [1, num]
        if(stu[i].score == stu[i-1].score){
            printf("%s %d %d %d\n", stu[i].id, r, 
                   stu[i].local_number, stu[i].local_rank);
        }else{
            r = i + 1; //序号加一
            printf("%s %d\n", stu[i].id, r, 
                   stu[i].local_number, stu[i].local_rank);
        }
    }
    
    return 0;
}

02 散列（hash）

设定一个 bool 型数组 hashTable[100010]，其中 hashTable[x] = true 表示正整数 x 在 N 个正整数中出现过，而 hashTable[x] = false 表示正整数 x 在 N 个正整数中没有出现过。

注：hashTable数组需要初始化为 false，表示初始状态下所有数都未出现过。

//整数hash
//hashTable[maxn]

#include <cstdio>
const int MAXN = 100010;

//以空间换时间
//将输入的数作为数组下标来对该数进行统计
bool hashTable[MAXN] = {false};

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    
    int x;
    for(int i=0; i<N; i++){
        scanf("%d", &x);
        hashTable[x] = ture;
    }
    
    for(int i=0; i<M; i++){
        scanf("%d", &x);
        if(hashTable[x] == true){
            printf("Yes.\n")
        }else{
            printf("No.\n")
        }
    }
    
    return 0;
}

什么是散列？

将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素，其中，把这个转换函数称为散列函数 H，也就是说，如果元素在转换前为 key，那么转换后就是一个整数 H(key)。

什么是散列函数？

直接定址法：H(key) = key、H(key) = a * key + b

除留余数法：H(key) = key % mod

//字符串hash
//除留余数法

//二十六进制转十进制
int hashFunc(char S[], int len){
    int id = 0;
    for(int i=0; i<len; i++){
        id = id * 26 + (S[i] - 'A');
    }
    return id;
}

//五十二进制转十进制
int hashFunc(char S[], int len){
    int id = 0;
    for(int i=0; i<len; i++){
        if(S[i] >= 'A' && S[i] <= 'Z') //S[i] [0, 25]
            id = id * 52 + (S[i] - 'A');
        if(S[i] >= 'a' && S[i] <= 'z') //S[i] [26, 51]
            id = id * 52 + (S[i] - 'a' + 26);
    }
    return id;
}

//二十六进制转十进制 + 个位整数
int hashFunc(char S[], int len){
    int id = 0;
    for(int i=0; i<len-1; i++){
        id = id * 26 + (S[i] - 'A');
    }
    id = id * 10 + (S[len-1] - '0');
    return id;
}

Example 01

给出 N 个字符串（由恰好三位大写字母组成），再给出 M 个查询字符串，问每个查询字符串在 N 个字符串中出现的次数。

//hashTable[maxn]
//除留余数法

#include <cstdio>
const int MAXN = 100;
char S[MAXN][5], temp[5];
int hashTable[26*26*26 + 10] = {0};

//二十六进制转十进制
int hashFunc(char S[], int len){
    int id = 0;
    for(int i=0; i<len; i++){
        id = id * 26 + (S[i] - 'A');
    }
    return id;
}

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    
    //输入数据
    int id;
    for(int i=0; i<N; i++){
        scanf("%s", S[i]);
        id = hashFunc(S[i], 3);
        hashTable[id]++;
    }
    
    //查询数据
    for(int i=0; i<M; i++){
        scanf("%s", temp)
        id = hashFunc(temp, 3);
        printf("%d", hashTable[id]);
    }
    
    return 0;
}

03 递归

递归 = 递归边界 + 递归式

Example 02: 使用递归求解 n 的阶乘

//阶乘
//递归边界：n==1
//递归算式：Func(n-1) * n

#include <stdio.h>

int Func(int n){
    if(n == 1) return 1;
    else return n * Func(n - 1);
}

int main(){
    int n;
    scanf("%d", &n);
    
    int num = Func(n);
    printf("%d", num);
    
    return 0;
}

Example 03: 求 Fibonacci 数列的第 n 项

//Fabonacci
//递归边界：n==0 || n==1
//递归算式：Func(n-1) + Func(n-2)

#include <stdio.h>

int Func(int n){
    if(n == 0) return 1;
    else if(n == 1) return 1;
    else return Func(n - 1) + Func(n - 2);
}

int main(){
    int n;
    scanf("%d", &n);
    
    int num = Func(n);
    printf("%d", num);
    
    return 0;
}

Example 04: 输出 1~n 这 n 个整数的全排列

//全排列
//递归边界：index == n+1
//递归算式：generateP(index + 1)
//hashTable[MAXN]

#include <cstdio>
const int maxn = 11;
int n;
int P[maxn], hashTable[maxn] = {false};

void generateP(int index){
    if(index == n + 1){ //递归边界
        //遍历输出
        for(int i=1; i<=n; i++){
            printf("%d", P[i]);
        }
        printf("\n");
        return;
    }
    
    //遍历填数
    for(int x=1; x<=n; x++){
        if(hashTable[x] == false){
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1); //递归式
            hashTable[x] = false;
        }
    }
}

int main(){
    n = 3;
    generateP(1);
    return 0;
}

Example 05: n 皇后问题

//方法一：暴力法
//for i [1, n]
//for j [i+1, n]
//abs
//flag

int count = 0;
void generateP(int index){
    if(index == n + 1){
        //遍历判断
        bool flag = true;
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                if(abs(i-j) == abs(P[i]-P[j]))
                    flag = false;
            }
        }
        
        if(flag == ture) count++;
        return; //这里要返回
    }
    
    for(int x=1; x<=n; x++){
        if(hashTable[x] == false){
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);
            hashTable[x] = false; //这里要改回false
        }
    }
}

//方法二：回溯法
//for pre [1, index)
//abs
//flag

int count = 0;
void generateP(int index){
    if(index == n + 1){
        count++;
        return;
    }
    
    for(int x=1; x<=n; x++){
        if(hashTable[x] == false){
            
            //回溯判断
            bool flag = true;
            for(int pre=1; pre<index; pre++){
                if(abs(index - pre) == abs(x - P[pre])){
                    flag = false;
                    break;
                }
            }
            
            if(flag == true){
                P[index] = x;
                hashTable[x] = true;
                generateP(index + 1);
                hashTable[x] = false;
            }
        }
    }
}

附：词汇解释

merge 合并、simultaneously / ˌsaɪm(ə)lˈteɪniəsli / 同时地、generate 产生，引起、testee / tesˈti / 应考人、registration / ˌredʒɪˈstreɪʃ(ə)n / 登记，注册、nondecreasing 不下降的、interval / ˈɪntərv(ə)l / 间隔，间隙、partition 分裂，分治