汇源果汁吖！

一点小记录

0%

啊哈！算法

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 10k 阅读时长 ≈ 9 分钟

前言

我基础太差了。就从最简单，能看下去的这本书开始吧

排序

桶排序

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
a[i]=0; //初始化为0
for(i=1;i<=5;i++) //循环读入5个数 {
  scanf("%d",&t); //把每一个数读到变量t中
  a[t]++; //进行计数 }
  for(i=0;i<=10;i++) //依次判断a[0]~a[10]
    for(j=1;  j<=a[i];j++) //出现了几次就打印几次
      printf("%d ",i);
      getchar();getchar(); //这里的getchar();用来暂停程序，以便查看程序输出的内容 //也可以用system("pause");等来代替
  return 0;
}

冒泡排序

冒泡排序的基本思想是:每次比较两个相邻的元素，如果它们的顺序错误就把它们交换 过来。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main()
{
int a[100],i,j,t,n;
scanf("%d",&n); //输入一个数n，表示接下来有n个数 for(i=1;i<=n;i++) //循环读入n个数到数组a中
        scanf("%d",&a[i]);
        //冒泡排序的核心部分
for(i=1;i<=n-1;i++) //n个数排序，只用进行n-1趟 {
for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数，想一想为什 么到n-i就可以了。
{
if(a[j]<a[j+1]) //比较大小并交换
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
} }
for(i=1;i<=n;i++) //输出结果 printf("%d ",a[i]);
        getchar();getchar();
return 0; }

pic

快速排序

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
return;
temp=a[left]; //temp中存的就是基准数 i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右往左找 while(a[j]>=temp && i<j)
j--; //再从左往右找
        while(a[i]<=temp && i<j)
            i++;
//交换两个数在数组中的位置 if(i<j)//当哨兵i和哨兵j没有相遇时 {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
} }
//最终将基准数归位
a[left]=a[i];
    a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程 }
int main() {
int i,j,t; //读入数据 scanf("%d",&n); for(i=1;i<=n;i++)
scanf("%d",&a[i]); quicksort(1,n); //快速排序调用
//输出排序后的结果 for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    getchar();getchar();
return 0; }

pic

我们来回顾一下本章三种排序算法的时间复杂度。桶排序是最快的，它的时间复杂度是 O(N+M);冒泡排序是 O(N 2);快速排序是 O(NlogN)。\

栈、队列、链表

队列

“先进先出”(First In First Out，FIFO)原则。

队列将是我们今后学习广度优先搜索以及队列优化的 Bellman-Ford 最短路算法的核心 数据结构。所以现在将队列的三个基本元素(一个数组，两个变量)封装为一个结构体类型， 如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
struct queue
{
int data[100];//队列的主体，用来存储内容 int head;//队首
int tail;//队尾 };
int main() {
struct queue q; int i; //初始化队列 q.head=1; q.tail=1; for(i=1;i<=9;i++) {
//依次向队列插入9个数 scanf("%d",&q.data[q.tail]); q.tail++;
}
while(q.head<q.tail) //当队列不为空的时候执行循环 {
//打印队首并将队首出队 printf("%d ",q.data[q.head]); q.head++;
//先将新队首的数添加到队尾 q.data[q.tail]=q.data[q.head]; q.tail++;
//再将队首出队
q.head++; }
    getchar();getchar();
return 0; }

栈

入栈的操作 是 top++;s[top]=x(;假设需要入栈的字符暂存在字符变量 x 中)，其实可以简写为 s[++top]=x;

判断回文：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <string.h>
int main()
{
    char a[101],s[101];
    int i,len,mid,next,top;
gets(a); //读入一行字符串 len=strlen(a); //求字符串的长度 mid=len/2-1; //求字符串的中点
top=0;//栈的初始化 //将mid前的字符依次入栈 for(i=0;i<=mid;i++)
        s[++top]=a[i];
//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标 if(len%2==0)
        next=mid+1;
    else
next=mid+2;
//开始匹配 for(i=next;i<=len-1;i++)
{
        if(a[i]!=s[top])
            break;
        top--;
}
//如果top的值为0，则说明栈内所有的字符都被一一匹配了 if(top==0)
        printf("YES");
    else
        printf("NO");
    getchar();getchar();
return 0; }

小猫钓鱼

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
struct queue
{
    int data[1000];
    int head;
    int tail;
};
struct stack
{
    int data[10];
int top; };
int main() {
    struct queue q1,q2;
    struct stack s;
    int book[10];
    int i,t;
//初始化队列
q1.head=1; q1.tail=1;
q2.head=1; q2.tail=1;
//初始化栈
s.top=0; //初始化用来标记的数组，用来标记哪些牌已经在桌上 for(i=1;i<=9;i++)
book[i]=0;
//依次向队列插入6个数 //小哼手上的6张牌 for(i=1;i<=6;i++) {
        scanf("%d",&q1.data[q1.tail]);
q1.tail++; }
//小哈手上的6张牌 for(i=1;i<=6;i++) {
        scanf("%d",&q2.data[q2.tail]);
q2.tail++; }
while(q1.head<q1.tail && q2.head<q2.tail ) //当队列不为空的时候执行循环 {
t=q1.data[q1.head];//小哼出一张牌 //判断小哼当前打出的牌是否能赢牌 if(book[t]==0) //表明桌上没有牌面为t的牌
{
//小哼此轮没有赢牌
q1.head++; //小哼已经打出一张牌，所以要把打出的牌出队 s.top++;
s.data[s.top]=t; //再把打出的牌放到桌上，即入栈 book[t]=1; //标记桌上现在已经有牌面为t的牌
} else {
//小哼此轮可以赢牌 q1.head++;//小哼已经打出一张牌，所以要把打出的牌出队 q1.data[q1.tail]=t;//紧接着把打出的牌放到手中牌的末尾 q1.tail++;
while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾 {
book[s.data[s.top]]=0;//取消标记 q1.data[q1.tail]=s.data[s.top];//依次放入队尾 q1.tail++;
s.top--; //栈中少了一张牌，所以栈顶要减1
} }
t=q2.data[q2.head]; //小哈出一张牌 //判断小哈当前打出的牌是否能赢牌 if(book[t]==0) //表明桌上没有牌面为t的牌 {
//小哈此轮没有赢牌
q2.head++; //小哈已经打出一张牌，所以要把打出的牌出队 s.top++;
s.data[s.top]=t; //再把打出的牌放到桌上，即入栈 book[t]=1; //标记桌上现在已经有牌面为t的牌
} else {
//小哈此轮可以赢牌 q2.head++;//小哈已经打出一张牌，所以要把打出的牌出队 q2.data[q2.tail]=t;//紧接着把打出的牌放到手中牌的末尾 q2.tail++;
while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾 {
book[s.data[s.top]]=0;//取消标记
q2.data[q2.tail]=s.data[s.top];//依次放入队尾 q2.tail++;
s.top--;
} }
}
if(q2.head==q2.tail)
{
printf("小哼win\n"); printf("小哼当前手中的牌是"); for(i=q1.head;i<=q1.tail-1;i++)
printf(" %d",q1.data[i]); if(s.top>0) //如果桌上有牌则依次输出桌上的牌 {
printf("\n桌上的牌是"); for(i=1;i<=s.top;i++)
printf(" %d",s.data[i]); printf("\n桌上已经没有牌了");
} else
} else {
printf("小哈win\n"); printf("小哈当前手中的牌是"); for(i=q2.head;i<=q2.tail-1;i++)
printf(" %d",q2.data[i]); if(s.top>0) //如果桌上有牌则依次输出桌上的牌 {
printf("\n桌上的牌是"); for(i=1;i<=s.top;i++)
printf(" %d",s.data[i]); printf("\n桌上已经没有牌了");
} else
}
    getchar();getchar();
return 0; }

链表

Code：下面来设置头指针并设置新创建结点的*next 指向空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h> //这里创建一个结构体用来表示链表的结点类型 struct node
{
int data;
    struct node *next;
};
int main() {
struct node *head,*p,*q,*t; int i,n,a;
scanf("%d",&n);
head = NULL;//头指针初始为空 for(i=1;i<=n;i++)//循环读入n个数 {
scanf("%d",&a); //动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node)); p->data=a;//将数据存储到当前结点的data域中 p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空 if(head==NULL)
head=p;//如果这是第一个创建的结点，则将头指针指向这个结点 else
q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点 q=p;//指针q也指向当前结点
}
//输出链表中的所有数 t=head; while(t!=NULL)
{
printf("%d ",t->data);
t=t->next;//继续下一个结点 }
    getchar();getchar();
return 0; }

Code:插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型 struct node
{
int data;
struct node *next;
};
int main() {
struct node *head,*p,*q,_t; int i,n,a;
scanf("%d",&n);
head = NULL;//头指针初始为空 for(i=1;i<=n;i++)//循环读入 n 个数 {
scanf("%d",&a); //动态申请一个空间，用来存放一个结点，并用临时指针 p 指向这个结点
p=(struct node _)malloc(sizeof(struct node)); p->data=a;//将数据存储到当前结点的 data 域中 p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空 if(head==NULL)
head=p;//如果这是第一个创建的结点，则将头指针指向这个结点 else
q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
q=p;//指针 q 也指向当前结点
}
scanf("%d",&a);//读入待插入的数 t=head;//从链表头部开始遍历 while(t!=NULL)//当没有到达链表尾部的时候循环 {
if(t->next->data > a)//如果当前结点下一个结点的值大于待插入数，将数插入到中间 {
用来存放新增结点
p=(struct node \*)malloc(sizeof(struct node));//动态申请一个空间，
p->data=a; p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
t->next=p;//当前结点的后继指针指向新增结点
break;//插入完毕退出循环 }
t=t->next;//继续下一个结点 }
//输出链表中的所有数 t=head; while(t!=NULL)
{
printf("%d ",t->data);
t=t->next;//继续下一个结点 }
getchar();getchar();
return 0; }

模拟链表

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int main()
{
    int data[101],right[101];
int i,n,t,len; //读入已有的数 scanf("%d",&n); for(i=1;i<=n;i++)
    scanf("%d",&data[i]);
len=n;
//初始化数组right for(i=1;i<=n;i++) {
    if(i!=n)
        right[i]=i+1;
    else
        right[i]=0;
} //直接在数组data的末尾增加一个数 len++; scanf("%d",&data[len]);
//从链表的头部开始遍历 t=1;
while(t!=0)
{
if(data[right[t]]>data[len])//如果当前结点下一个结点的值大于待插入数，将 {
right[len]=right[t];//新插入数的下一个结点标号等于当前结点的下一个结
right[t]=len;//当前结点的下一个结点编号就是新插入数的编号
break;//插入完成跳出循环 }
    t=right[t];
}
//输出链表中所有的数 t=1;
while(t!=0)
{
    printf("%d ",data[t]);
    t=right[t];
}
getchar();
    getchar();
    return 0;
}

枚举

计算 xxx+xxx=xxx，x=[1-9]：

1

炸弹人

火柴棍等式

数的全排列

万能的搜索

深度优先搜索

Code：

1
2
3
4
5
6
7
void dfs(int step){
  判断边界
  尝试每一种可能for(i=1;i<=n;i++>){
    继续下一步dfs(step+1])
  }
  返回
}

迷宫

广度优先排序

层层递进

用队列存储已经走过的点

解决炸弹人问题

炸弹人会出现在无法到达的地点以至于结果错误。
利用广度优先枚举出炸弹人可以到达的地方
也可以使用深度优先

宝岛探险

Floodfill 漫水填充法

水管工游戏

图的遍历

时间戳：顶点被访问的顺序

深度与广度优先究竟是啥

深度遍历主要思想：
以一个未被访问过的顶点作为起始顶点，
沿当前顶点的边走到未被访问过的顶点，
当没有未被访问过的顶点时，则返回上一个顶点，
继续试探访问别的顶点，直到所有顶点都被访问过。

广度遍历主要思想：
以一个未被访问过的顶点作为起始顶点，
访问其所有相邻的顶点，然后对每个相邻的顶点，
再访问他们相邻的所有未被访问过的顶点，直到所有顶点都被访问

城市地图-图的优先遍历

存图方法

  • 图的邻接矩阵表示法 – 二维数组
  • 邻接表

最少转机-图的广度优先遍历

队列

最短路径

只有五行的算法-Floyd-Warshall

不能解决‘负权回路’的图

Dijksstr 算法-通过边实现松弛

单源最短路径

基本思想：
每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有顶点的最短路径

边数 M < 顶点数 N^2 –>稀疏图 –>可用邻接表
边数 M > 顶点数 N^2 –>稠密图

Bellman-Ford 解决负权边

Bellman-Ford 队列优化

在每实施一次松弛操作后，就会有一些顶点已经求得其最短路径，但每次还要判断是否需要松弛，浪费了时间。

==

每次仅对最短路估计值发生变化了的顶点的所有出边执行松弛操作。

使用队列优化的 bellman Ford 算法的关键之处在于，只有那些在前一遍松弛中改变了最短路程估计值的顶点\才可能引起他们连接点最短路程估计值发生改变。

神奇的树

开启树之旅

树其实是不包含回路的连通无向图。指任意两个节点中有且只有一条路径的无向图。

特性：

  1. 一棵树中的任意两个结点有且仅有唯一的一条路径连通
  2. 一棵树如果有 n 个节点，那么它一定恰好有 n-1 条边。
  3. 在一棵树中加一条边将会构成一个回路。

根又叫根结点，一棵树有且只有一个根结点。根结点有时候也称为祖先。如果一个节点没有子节点，那么这个节点称为叶节点。没有父节点的节点称为根节点。如果一个节点既不是根节点，也不是叶节点，则称为内部节点。深度是指从根到这个节点的层数（根为第 1 层）。

二叉树

二叉树是一种特殊的树，二叉树的特点是每个节点最多有两个儿子，左边的叫左儿子，右边的叫右儿子，或者说每个节点最多有两颗子树，更加严格的递归定义是二叉树要么为空，要么由根节点，左子树和右子树组成，而左子树和右子树分别是一棵二叉树。

二叉树中还有两种特殊的二叉树，叫做满二叉树和完全二叉树。

  • 如果二叉树中每个内部节点都有两个儿子，这样的二叉树叫做满二叉树。满二叉树，所有的叶节点都有同样的深度。

    满二叉树的严格的定义是一颗深度为 h 且有 2 的 h 次方减一个节点的二叉树。

  • 如果一棵二叉树除了最右边位置上有一个或几个叶节点缺少外，其他是丰满的，那么这样的二叉树就是完全二叉树。

    严格的定义是，若设二叉树的高度为 h，除除 h 层外其他各层的节点数都达到最大个数，第 h 层从右往左连续缺若干个节点。则这个二叉树就是完全二叉树。

如果完全二叉树的一个父节点编号为 k，那么他做儿子的编号就是 2k，右儿子的编号就是 2k+1。
如果已知儿子（左儿子或右儿子）的编号是 x，那么它父节点的编号就是 x/2。
如果一颗完全二叉树有 n 个节点，那么这个完全凹凸处的高度为 log2 n，简写为 log n。即最多有 logo n 层节点。

完全二叉树的最典型应用就是堆。

堆-神奇的优先队列

堆是一种特殊的完全二叉树，如果所有父节点都比子节点小，我们称为最小堆，如果所有父节点都比子节点大，这样的完全二叉树称为最大堆。

擒贼先擒王-并查集

并查集也称为不相交集数据结构。

更多精彩算法

镖局运镖-图的最小生成树

要想让有 n 个顶点的图联通，那么至少需要 n-1 条边。

先选择最短的边，然后选择次短的边，直到选择了 n-1 条边为止。

再谈最小生成树

将图中所有的顶点分为两类树顶点（已被选入生成树的顶点）和非速顶点（还未被选入生成树的顶点），首先选择任意一个顶点加入生成树，你可以理解为生成树的根，接下来要找出一条边添加到生成树，这需要枚举每一个树顶点到每一个非树顶点所有的边，然后找到最短边加入到生成树，照此方法重复操作 n-1 次，直到将所有的顶点都加入生成树中。

重要城市-图的割点

在一个无向连通图中，如果删除某个顶点后图不再连通（即任意 2 点之间不能相互到达），我们称这样的顶点为割点/割顶

关键道路-图的割边

割边也成为桥，即在一个无向连通图中，如果删除某条边后图不再连通。

二分图最大匹配

二分图的定义：如果一个图的所有顶点可以被分为 x 和 y 两个集合，并且所有边的两个顶点恰好一个属于集合 x，另一个属于集合 y，即每个集合内的顶点没有边相连，那么此图就是二分图。

判断一个图是否为二分图也非常简单，首先将任意一个顶点着红色，然后将其相邻的顶点着蓝色，如果按照这样的着色方法，可以将全部顶点着色的话，并且相邻的顶点着色不同，那么该图就是二分图。

Donate comment here.

欢迎关注我的其它发布渠道