算法自解

（更新中……）

努力让自己熟练编程，关键代码，然后快速入门。

数据结构等各种知识点屡看屡忘的我，为以后整理的笔记……

以《算法全解》《挑战程序设计竞赛 算法与数据结构》等为基础

trick

二叉树——》递归比较好写
链表的话，想一想需不需要头结点

常用的数据结构

stack

入栈，如例：s.push(x);
出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素。
访问栈顶，如例：s.top()
判断栈空，如例：s.empty()，当栈空时，返回true。
访问栈中的元素个数，如例：s.size()。

queue

入队，如例：q.push(x); 将x 接到队列的末端。
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素，如例：q.front()，即最早被压入队列的元素。
访问队尾元素，如例：q.back()，即最后被压入队列的元素。
判断队列空，如例：q.empty()，当队列空时，返回true。
访问队列中的元素个数，如例：q.size()

输入输出与具体方法

(%与/的应用)

日期差值

输入两个日期：YYYYMMDD格式，得到两个日期之间的差值。

对于一个整数，%100：得到整数后两位 /100得到整数除后两位的。

// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。
//
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>

using namespace std;
bool issun(int year) {
    if ((year % 100 != 0 &&year % 4 == 0)||year%400==0) {//判断 闰年 的方法！！
        return true;
    }
    else{
        return false;
    }
}

int main()
{
    int a1, a2;
    int year1, year2, mon1, mon2, day1, day2;
    while(scanf("%d%d",&a1,&a2)!=EOF){
        //没有强调，需要保证前者早于后者。

        if (a1 > a2) {
            int tmp = a1;
            a1 = a2;
            a2 = tmp;
        }
        day1 = a1 % 100;//得到后两位
        a1 = a1 / 100;//得到除后两位的前面的数
        mon1 = a1 % 100;
        a1 = a1 / 100;
        year1 = a1 % 10000;//得到后四位
        day2 = a2 % 100;
        a2 = a2 / 100;
        mon2 = a2 % 100;
        a2 = a2 / 100;
        year2 = a2 % 10000;
        int days = 1;
        int mon[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
        int mons[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
        while (!(year1 == year2&&mon1 == mon2&&day1 == day2)) {
            day1++;

            if (issun(year1)) {
                if (day1 == mons[mon1] + 1) {
                    day1 = 1;
                    mon1++;
                }
            }
            else {
                if (day1 == mon[mon1] + 1) {
                    day1 = 1;
                    mon1++;
                }

            }
            if (mon1 == 13) {
                mon1 = 1;
                year1++;
            }
            days++;
        }
        printf("%d\n", days);

    }
    return 0;
}

进制转换

P进制转十进制y

int y=0,product=1;
while(x!=0){
    y=y+(x%10)*product;//y是结果，x%10为了得到个位数
    x=x/10;
    product=prodcut*P;//product的值会分别变成1，p,p^2,p^3,p^4…
}

十进制数y转换成Q进制数z

int z[40],num=0;
do{
    z[num++]=y%Q;//除基取余 得到最后一位数
    y=y/Q;
}while(y!=0);

这样z数组从高位z[num-1]到低位z[0]即为Q进制z,进制转换完成。

字符串

对于回文串的处理：1.根据对称性；2.利用for循环，从后向前遍历（逻辑性比较简单）

思路1.

假设字符串str的下标从0开始，由于“回文串”是正读和反读都一样的字符串，因此只需要遍历字符串的前一半（注意：不需要取到i==len/2)，如果出现字符str[i]不等于其对称位置str[len-1-i]，就说明这个字符串不是“回文串”；如果前一半的所有字符str[i]都等于对称位置 str[len-1-i],则说明这个字符串是回文串。

#include <cstdio>
#include <cstring>
const int maxn=256;
//判断字符串str是否是“回文串”
bool judge(char str[]){
    int len =strlen(str);//字符串长度
    for（int i=0;i<len/2;i++){//i枚举字符串的前一半
        if(str[i]!=str[len-1-i]){
            return false;
        }
        
    }
    return true;
}

二分查找

这里没有用递归（事实上是可以用递归的），这里是动态改变left和right的值。注意传入参数为A[]

思想，只要left木有大于right，就接着找，but根据大于小于动态变化mid为right或者left

#include <stdio.h>
//A[]为严格递增序列，left为二分下界，right为二分上界，x为欲查询的数
//二分区间为左闭右闭的[left,right],传入的初值为[0,n-1]
int binarySearch(int A[],int left,int right,int x){
    int mid;//mid 为left和right中点
    while(left<=right){//不用递归，用while界定界限。
        mid=(left+right)/2;//取中点
        //有的时候会觉得(left+right)/2可能比较大，所以也可以用left+(right-left)/2
        if(A[mid]==x){
            return mid;
        }else if(A[mid>x]){
            //中间的数大于x
            right=mid-1;
        }else{//中间的数小于x
            left=mid+1;
            
        }
        
    }
    return -1;//查找失败

}
int main(){
    const int n=10;
    int A[n]={1,3,4,6,7,8,10,11,12,15};
    printf("%d%d\n",binarySearch(A,0,n-1,6),binarySearch(A,0,n-1,9));
    return 0;
}
输出3 -1；

排序

快排

注意，数组传 a[]或者*a

解析：1.递归程序。

结束标准：left>right

2.选定基准 a[left] 标兵 i和j

3.i和j比较换位。i和j相遇的条件：因为i和j分开运算，j先减，i后加，因为while小于的限制，i不可能超过j,

j停止的位置一定小于基准数（因为需要和i换）

i停止的位置可能大于基准数（和j换），可能=j（i,j条件的限制）

void quicksort(int a[],int left,int right){//x,起始点，y,长度 递归实现的快排，好像是这样的QAQ
    //注意对比和标程的区别
    int i,j,t,temp;
    if(left>=right)
        return;

    temp=a[left];//temp中存基准数
    i=left;
    j=right;
    //三个while，while中n次换位，while外一次换位
    while(i<j){//小于表明没有相遇
        //顺序很重要，要先从右往左找
        while(a[j]>=temp&&i<j)//注意这里也要标明i<j，反复左移
            j--;//找到基准右侧比基准小的数
        
        //再从左往右找
        while(a[i]<=temp&&i<j)//注意这里一定是小于等于
            i++;//找到基准左侧比基准大的数
        
        //交换两个数在数组中的位置，
        if(i<j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }

    }
    //最终将基准数归位。即基准数为最左边那个数，先把它右边的数大于它小于它的排好，再将基准数归位。
    a[left]=a[i];
    a[i]=temp;

    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}

冒泡排序&选择排序

冒泡和选择的区别：

选择循环a[i]和a[j]

冒泡循环a[j]和a[j+1]，外面大层是i

void xuanze(int *a){//由大到小
//  int *b=a;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){//注意这里是i+1
            if(a[i]<a[j]){
                int tmp=a[j];
                a[j]=a[i];
                a[i]=tmp;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
修正版
void maopao(int *a){
//  int *b=a;
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){//注意这里是n-i-1       
            if(a[j]<a[j+1]){//冒泡是j和j+1之间的关系
                int tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d",a[i]);
        printf("%s"," ");
    }
}
原版
void maopao(int *a){
//  int *b=a;
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i;j++){//注意这里是n-i
            //注意边界，第一次可能越界。思考怎么更改            
            if(a[j]<a[j+1]){//冒泡是j和j+1之间的关系
                int tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d",a[i]);
        printf("%s"," ");
    }
}

归并排序

先搞定递归的，日后再搞定非递归的。

（《算法笔记》）

堆

堆
【注：下面的代码可以AC，但是理论上，如果使用2i,2i+1表示堆，数组赋值从1开始，如果数组赋值从0开始，应该使用2i+1,2i+2表示孩子】

完全二叉树，左孩子2i位，右孩子2i+1位

树中每个节点的值都不小于（或不大于）其左右孩子节点的值。

完全二叉树一般用数组存储

这里是较小堆

增添是添到末尾，向上调整，注意边界条件，比上2时刻大于low；

删除是把末尾放在堆顶，向下调整，注意边界条件，*2小于high，需要比较左右孩子。

堆支持以下的基本操作:

• build:建立一个空堆；
• insert:向堆中插入一个新元素；【向上调整堆】
• update：将新元素提升使其符合堆的性质；
• get：获取当前堆顶元素的值；
• delete：删除堆顶元素；【向下调整堆】
• heapify：使删除堆顶元素的堆再次成为堆

标程（百练上对应题目AC代码）

PKU2017年夏令营机试题

定义一个数组，初始化为空。在数组上执行两种操作：

1、增添1个元素，把1个新的元素放入数组。

2、输出并删除数组中最小的数。

使用堆结构实现上述功能的高效算法。

输入

第一行输入一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入一个整数n，代表操作的次数。
每次操作首先输入一个整数type。
当type=1，增添操作，接着输入一个整数u，代表要插入的元素。
当type=2，输出删除操作，输出并删除数组中最小的元素。
1<=n<=100000。

输出

每次删除操作输出被删除的数字。

样例输入

2
5
1 1
1 2
1 3
2
2
4
1 5
1 1
1 7
2

样例输出

1
2
1

#include<stdio.h>
#include<queue>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int MAX=100000;
int heap[100000+5];
void downjust(int low,int high){//low为欲调整节点，high为最后一个元素节点
    //自上向下调整
    int j=low;
    int k=2*low;//得到孩子
    while(k<=high){//我写的是！=
//      int tmp=heap[k];
        if(k+1<high&&heap[k+1]<heap[k]){//左右比较，取最小
            k=k+1;}
        if(heap[k]<heap[j]){
            swap(heap[k],heap[j]);//注意swap方法
            j=k;
            k=k*2;
        }else{//如果不小于，则后面的也都大于了，可以不用比较了，直接break
            break;
        }
    }

}

void upjust(int low,int high){
    //自下向上调整
    int k=high/2;
    int j=high;
    while(k>=low){
        if(heap[j]<heap[k]){
            swap(heap[j],heap[k]);
            j=k;
            k=k/2;

        }else{
            break;
        }

    }
}



int main(){
    int m;
    int high=0;//high初始化为0
    scanf("%d",&m);//输入m组
    for(int i=0;i<m;i++){
        int n;
        scanf("%d",&n);
        memset(heap,0,sizeof(heap));//清空每次操作后的堆
        high=0;
        for(int j=0;j<n;j++){
            int op,num;
            scanf("%d",&op);//得到操作
                if(op==1){//如果是增添
                    scanf("%d",&num);
                    heap[high]=num;//添到末尾
                    upjust(0,high);//自下向上调整
                    high++;
                }else{
                    printf("%d",heap[0]);
                    printf("%s","\n");
                    heap[0]=heap[high-1];//得到最后一个数
                    downjust(0,high-1);//自上向下调整
                    high--;
                }
            

        }
    }

    return 0;
}

链表

二叉树

【有时间得写一写基本功能实现】

[C++实现（指针的用法和解析）和java实现]

基本结构（数组）

1.利用左孩子和右孩子分别是2i,和2i+1，轻松实现。

2.单纯构造node数组（from 《挑战程序设计语言》）

基本结构(链表)：

struct node{
    int data;
    node* lchild;//二叉树定义的每一个节点都是带指针的
    node* rchild;
}
//新建节点or插入节点，返回一个指针
node* newNode（int v){
    node* Node=new node;
    Node->data=v;
    Node->lchild=Node->rchild=NULL;
    return Node;
}
//二叉树的查找
void search(node* root,int x,int newdata){
    if(root==NULL){
        return;//空树
    }
    if(root->data==x){
        root->data=newdata;
    }
    search(root->lchild,x,newdata);//往左子树搜索x
    search（root->rchild,x,newdata);//往右子树搜索x
}
//二叉树的插入
void insert(node* &root,int x){
    if(root == NULL){
        root=newNode(x);
        return;
    }
    if(由二叉树的性质，x应该插在左子树){
        insert（root->lchild,x);
    }else{
        insert（root->rchild,x);
    }
}
//先序遍历
void preorder(node* root){
    if(root==NULL){
        return;
    }
   // printf中
    preorder(root->lchild);
    preorder(root->rchild);中左右
}

中序：左中右 后序：左右中

//层序
void LayerOrder（node* root）{ //BFS
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        if(now->lchild!=NULL) q.push(now->lchild);
        if(now->rchild!=NULL) q.push(now->rchild);
    }

层次遍历如何逐层遍历,(求树高非递归）
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/comments/61294

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        int num = 0;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty()){
            int n = que.size();
            for(int i = 0;i < n;++i){
                TreeNode *cur = que.front();
                if(cur->left != NULL)
                    que.push(cur->left);
                if(cur->right != NULL)
                    que.push(cur->right);
                que.pop();
            }
            num++;
        }
        return num;
    }
};

求树高（递归）
https://www.cnblogs.com/tsj816523/p/10690704.html

int h(BTree *bt)
{
    if(bt->lchild==NULL&&bt->rchild==NULL)
        return 1;
    if(bt->lchild!=NULL&&bt->rchild==NULL)
        return 1+h(bt->lchild);
    if(bt->lchild==NULL&&bt->rchild!=NULL)
        return 1+h(bt->rchild);
    return 1+max(h(bt->rchild),h(bt->lchild));
}

遍历的非递归实现

思想：

vector<int> proorder(Node* root){
    //根左右
    vector<int> res;
    if(NULL==root){
        return res;
    }
    stack<Node*> s;
    s.put(root);
    while(!s.empty()){
        Node * node=s.top();
        s.pop();
        res.push_back(node_val);
        if(node->left){
            s.push(node->left);
        }
        if(node->right){
            s.push(node->right);
        }
    }
    reverse(res.begin(),res.end());//倒转方法
    return res;
}

叶子节点路径

二叉树根到叶子节点每一条路径【求二叉树是否存在和值为N的路径】

#include <iostream>
#include <cstdio>
using namespace std;
struct node{
    int x;
    node* left=NULL;
    node* right=NULL;
}


int count=0;
void sum(node* current,int result){
    //int data=-1;
    int data=current->x;
    newres=result*10+data;
    
    if(current->left!=NULL){
       
        sum(current->left,newres);
        
    }
    if(current->right!=NULL){
        sum(current->right,newres);      
        
    }
    if(current->rigth==NULL&&current->left==NULL){
         count+=newres;
        return;
    }
}

dfs&bfs&dijiesiqula算法

快排 bfs dfs 图算法【算法课本、书】 dijiesiqula算法

void dfs(G){
    for(G的每一个顶点u){
        if(vis[u]==false){
            vis[u]=true;
            dfs(u);
           
        }
    }        
}
void bfs(){
    queue q;
    while(q非空){
        取出q的队首元素u进行访问
        for(从u出发可达的所有顶点v){
            if(v没被访问过)
                加入队列
        }
    }
}
//循环n次
void Dijkstra(G，d[],s){
    for(循环n次){
        u=使d[u]最小还未被访问的顶点；
        记u已被访问；
        for（从u出发能到达所有顶点v){
            if(v未被访问&&以u为中介点能使s到顶点v距离更优){
                优化d[v]
            }
        }
    }
    
}

void Dijkstra(int s){
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1;MIN=INF;
        //找没有被访问过的点中，d(离源点距离)最小的，令u为那一个点
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                 MIN=d[j];
            }
        }
        if(u==-1)return;//没有找到
        vis[u]=true;
        //对找到的那个点临接的每一个未被访问过的点，更新d值
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
                d[v]=d[u]+G[u][v];
            }  
        }
    }
}

并查集（最小生成树）

【回顾博客上的那篇文章】https://www.jianshu.com/p/25b08412e313

G题 networking

动态规划