前言

算法用到的C语言范围在学习指针之前,尽可能寻找每个经典问题的最优解,也想借此做好笔记,方便回顾等等

最近去牛客网做了做入门题，我在138道基础题中见到好多新奇的解题思路，于是想把我见到的算法做个简单集合，由于时间有限，部分代码就直接转载了，超链接里有原网页

1.反向输出一个n位数

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
//思路一:
#include<stdio.h>
int main()
{
    int a,b,n;
    scanf("%d",&n);
    scanf("%d",&a);
    for(int i=0;i<n;i++)
	{
        b=a%10;
        a=a/10;
        printf("%d",b);
    }
    return 0;
}
/*当然也可以简化*/
#include<stdio.h>
int main()
{
    int a,n;
    scanf("%d",&n);
    scanf("%d",&a);
    for(int i=0;i<n;i++){
        printf("%d",a%10);
        a/=10;
    } 
    return 0;
}
//思路2:
#include<stdio.h>
int main(){
    int a,b,c,d;
    scanf("%1d%1d%1d%1d",&a,&b,&c,&d);
    printf("%d%d%d%d",d,c,b,a);
}

2.大小写转换（多组输入）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*scanf*/
#include <stdio.h>
int main()
{
    char a;
    while(scanf("%c\n",&a)!=EOF){
    printf("%c\n",a+32);
    }
    return 0;
}
/*getchar*/
#include <stdio.h>
int main()
{
    char ch;
    while((ch=getchar())!=EOF){
        if(ch>='A'&&ch<='Z'){
            ch+=32;
        }
        putchar(ch);
    }
}

3.判断字母

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main()
{
    char ch;
    while(scanf("%c",&ch)!=EOF){
        if(ch=='\n') continue;//也可用getchar();
        if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
}

4.四种排序

列举四种排序：

冒泡排序

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
    for (i = 0; i < n; ++i) {
        // 之前的循环已经将i个元素送到末尾，不需要再次比较，故减去，因为跟后一个元素比较，为了避免溢出，故减一
        for (j = 0; j < n - i - 1; ++j) {
            // 如果当前的元素比后一个元素小，就交换
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
//优化以后，加了一开关变量，因为当后面几轮的循环已经排好时，就没必要再判断了
    for (i = 0; i < n; ++i) {
        flag = 0;
        // 之前的循环已经将i个元素送到末尾，不需要再次比较，故减去，因为跟后一个元素比较，为了避免溢出，故减一
        for (j = 0; j < n - i - 1; ++j) {
            // 如果当前的元素比后一个元素小，就交换
            if (arr[j] > arr[j + 1]) {
                flag = 1;   // 有数据交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 没有数据交换，提前结束
        if (flag == 0) {
            break;
        }
    }
}
转载自博客园
作者Taltao

桶排序

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
    for(int i=0;i<50;i++)
    {
        scanf("%d",&array_stu[i]);
    }
    /*把50个学生的分数分别扔到对应的桶里面去*/
    for(int i=0;i<50;i++)
    {
        for(int j=1;j<100;j++)
        {
            /*如果分数跟桶的编号一样，就把这个桶的数据增加*/
            if(array_stu[i] ==j)
            {
                array_out[j] ++;
            }
        }
    }
    /*把排序后的数据输出*/
    for(int i=0;i<100;i++)
    {
        /*有些同学的分数是一样的,这里要格外注意*/
        while(array_out[i] > 0)
        {
            printf("%d\n",i);
            array_out[i]--;
        }
    }
    return 0;
}
转载自知乎
作者嵌入式Linux

选择排序

每一轮排好一个数放到最前或最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void selectSort(int arr[], int len)
{
	int min;
	int temp = 0;
	for (int i = 0; i < len - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[j]<arr[min])
				min = j;
		}
		temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}
转载自csdn
作者one of a king

插入排序

每一轮依次向后拿出一个数插入到前面已排好的序列中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insertSort(int arr[], int len)
{
	int temp = 0;
	int j = 0;
	for (int i = 1; i < len; i++)
	{
		j = i - 1;
		temp = arr[i];
		while(j >= 0 && arr[j]>temp)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
转载自csdn
作者one of a king

5.最值

如果只用求最值，就没必要排序了

1
2
3
4
5
max = a;
if(max < b)
max = b;
if(max < c)
max = c;

6.打印字符图案

图案太多了，如菱形，沙漏，箭形，空心三角形，X形等等。我认为利用好循环条件，什么时候输出空格，什么时候输出字符，具体在哪一个或者哪些位置输出是最重要的。

就举一个X形的例子

1
2
3
4
5
6
7
8
输入：
5
输出：
*   *
 * * 
  *  
 * * 
*   *

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        int i,j;
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(i==j||i+j==n-1){
                    printf("*");
                }else{
                    printf(" ");
                }
            }
            printf("\n");
        }
    }
}

这里利用了字符位置的特殊性，对角线就是字符输出的位置

如果想通过上下镂空金字塔拼接，太过麻烦，所以思路要尽可能简单易行

7.最大公约数与最小公倍数

最大公约数：

1
2
3
4
while(a&&b){
        if(a>b) a%=b;
        else b%=a;
    }

最小公倍数：

我们都知道（我可不知道。。。）两个数的乘积等于这两个数的最大公约数和最小公倍数的积

那么结果就显而易见了

8.素数个数

要判断一堆数中有几个素数，要知道如何判断一个数是素数

一开始我们会想判断n是否能被2到n-1的整数整除，但还有优化的余地，如果一个质数大于根号n，而n可以除尽它，那么n必然也可以除尽一个更小的质数。因此我们可以判断n是否能被2到√n间的整数整除

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
#include <stdio.h>
int main()
{
    int a=0;
    int count = 0;
    while(~scanf("%d",&a))
    {
        int i=0;
        int j=0;
        for(i=2;i<=a;i++)
        {
            for(j=2;j<=sqrt(i);j+=1)
            {
                if(i%j == 0)
                {
                    break;
                }
            }
            if(j>sqrt(i))
            {
                printf("%d ",i);
                count++;
            }
        }
    }
    printf("\n");
    printf("%d",a-count-1);
    return 0;
}

9.有序序列判断

有序包括正序，逆序以及一连串相等的数字，反过来想，无序就是正序和逆序都出现了，所以可以这样写：

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>
int main()
{
    int n;
    scanf("%d",&n);
    int arr[50];
    int flag1=0;
    int flag2=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    for(int i=0;i<n-1;i++)
    {
        if(arr[i]>arr[i+1])
            flag1=1;
        else if(arr[i]<arr[i+1])
            flag2=1;
    }
    if(flag1&&flag2)
        printf("unsorted");
    else
        printf("sorted");
    return 0;
}

10.有序插入一个数

如果有n个数，可以从第（n-1）个数开始比大小，原数大就往后放，空出一个位置，到下一轮如果原数小，就可以把输入的数放到原来留出的空位了（当然也可以正着来）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
int main()
{
    int n;
    int a[55];
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    int x;
    scanf("%d",&x);
    for(i=n;i>0;i--){
        if(a[i-1]>x){
            a[i]=a[i-1];
        }else{
            a[i]=x;
            break;
        }
    }
    if(i==0) a[i]=x;
    for(i=0;i<=n;i++){
        if(i==n) printf("%d\n",a[i]);
        else printf("%d ",a[i]);
    }
}

11.删除序列指定数字

可以让指定数字小于零，小于零就跳过输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int main(){
    int n,x;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&x);
    for(int j=0;j<n;j++)
        if(x==a[j])
            a[j]=-1;
    for(int k=0;k<n;k++){
        if(a[k]<0)
            continue;
        printf("%d ",a[k]);
    }
    return 0;
}

12.矩阵元素定位

用二维数组很方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
    int a[15][15];
    int i,j;
    int n,m;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d%d",&n,&m);
    printf("%d\n",a[n-1][m-1]);
}

13.简单动态规划和迭代

动态规划是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

下面是一个经典的走台阶的问题

有n个台阶，小明一次可走1个台阶或2个台阶，问有几种走法

我们可以试着找找规律：

台阶数 1 2 3 4 5 6 … n
子结构 f(1) f(2) f(3) f(4) f(5) f(6) … f(n)
跳法 1 2 1+2=3 2+3=5 3+5=8 5+8=13 … f(n)=f(n-1)+f(n-2)

因此我们发现解法数满足f(n)=f(n-1)+f(n-2)，这不就是是斐波那契数列么

下面是动态规划的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
int main()
{
    int n,i;
    scanf("%d",&n);
    int a[n];
    a[0]=1;
    a[1]=2;
    for(i=2;i<n;i++)
    {
        a[i]=a[i-2]+a[i-1];
    }
    printf("%d\n",a[n-1]);
}

当然，数组记录了多个结果，我们可以用迭代(就是可以不断地用旧的值得到新的值，直到我们想要的得到的结果)，只记三个结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
int main()
{
    int a = 0;
    int b = 1;
    int c = 1;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        c=a+b;
        a=b;
        b=c;
    }
    printf("%d",c);
    return 0;
}