C算法01：C语言常见算法

数组元素中出现次数最多

#import <Foundation/Foundation.h>

int max_count_num(int *arr,int len);

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int arr[9] = {2,3,4,2,3,4,4,4,4};
        int len = sizeof(arr) / sizeof(arr[0]);
        // 计算出现次数最多
        max_count_num(arr, len);
    }
    return 0;
}

int max_count_num(int *arr,int len) {
    // 定义次数存储数组
    int maxArr[len];
    // 数组初始化
    for(int i = 0; i < len; i ++) {
        maxArr[i] = 0;
    }
    
    // 对数组中的元素进行count
    for (int i = 0; i < len; i ++) {
        for (int j = 0; j < len; j ++) {
            if (arr[i] == arr[j]){
                maxArr[i]++;
            }
        }
//        printf("%d",maxArr[i]);
    }
    
    // 取出数组中元素的最大值
    int max = 0;
    for (int i = 0; i < len; i ++) {
        if (maxArr[0] < maxArr[i]) {
            max = i;
        }
    }
//    printf("最大次数下标：%d",max);
    printf("出现次数最多的元素为：%d，出现次数为：%d\n",arr[max],maxArr[max]);
    return 0;
}
======
出现次数最多的元素为：4，出现次数为：5

字符串去重

新开数组去重

#include <stdio.h>
#include <strings.h>

int main(int argc, const char * argv[]) {
    // 字符串
    char str[] = "abcabdAAVCBC";
    // 长度
    long len = strlen(str);
    // 新开数组
    char ret[30] = {0};
    // 新开数组有元素的下标
    int num = 0;
    for (int i = 0; i < len; i ++) {
        // 元素重复标志
        int flag = 0;
        // num 每增加1 代表数组添加一个元素
        for (int j = 0; j < num; j ++) {
            // 遍历数组，如果其中包含某个字符，则不去添加
            if (str[i] == ret[j]) {
                flag = 1;
            }
        }
        // 添加元素
        if (flag == 0) {
            ret[num] = str[i];
            num ++;
        }
    }
    printf("ret == %s\n",ret);
    
    return 0;
}
==========
ret == abcdAVCB

二叉树算法题

1. 已知某二叉树的前序遍历为 A-B-D-F-G-H-I-E-C,中序遍历为 F-D-H-G-I-B-E-A-C,请还原这颗二叉树。

解题思路：

从前序遍历中，我们确定了根节点为A，在从中序遍历中得出 F-D-H-G-I-B-E 在根节点的左边，C 在根节点的右边，那么我们就可以构建我们的二叉树雏形

那么剩下的前序遍历为 B-D-F-G-H-I-E，中序遍历为 F-D-H-G-I-B-E，B就是我们新的 根节点，从中序遍历中得出 F-D-H-G-I 在B的左边，E在B的右边，继续构建

那么剩下的前序遍历为 D-F-G-H-I，中序遍历为 F-D-H-G-I，D就是我们新的 根结点，从中序遍历中得出F在D的左边，H-G-I 在D的右边，继续构建

那么剩下的前序遍历为 G-H-I，中序遍历为 H-G-I，G 就是我们新的 根结点，从中序遍历中得出H在G的左边，I在G的右边，继续构建

结论：
前序(根左右)：A-B-D-F-G-H-I-E-C
中序(左根右)：F-D-H-I-G-B-E-A-C
后序(左右根)：F-H-I-G-D-EB-C-A
注：光有前序和中序是无法还原二叉树的

输出一个非负整数的位数

例如：

19 / 10 = 0
1099 / 10 = 1~9
….

分析：除以10其实就是将最后一位数去掉

// 传入一个非负整数，返回其位数
int numLen(unsigned int num) {
    int len = 0;
    while (num > 0) {
        num = num / 10;;
        len += 1;
    }
    return  len;
}

int main(int argc, const char * argv[]) {
    int num = 12345;
    int len = numLen(num);
    printf("%d 是个 %d 位数\n",num,len);
    
    return 0;
}
====
12345 是个 5 位数

给定一个非负整数num，反复将各个位上的数宇相加。直到结果为一位数。返回这个结果。

示例：

输入：num = 5
输出：5
输入：12345
输出：15

思路：

num / 10 可以去掉最后一位，num % 10 可以得到最后一位的 数

// 正整数的长度
int numLen(int num) {
    int len = 0;
    while (num > 0) {
        num = num / 10;
        len += 1;
    }
    return len;
}

// 求各个位数之和
int sumNum(int num) {
    int sum = 0;
    // 如果大于10
    if (num > 10) {
        int len = numLen(num);
        // 先加上最后一位
        sum += num % 10;
        for (int i = 0; i < len - 1; i ++) {
            // 去掉最后一位
            num = num / 10;
            // 得到最后一位的数并累加
            sum += num % 10;
        }
        return sum;
    }
    return num;
   
}

int main(int argc, const char * argv[]) {
    
    int num = 125;
    int sum = sumNum(num);
    printf("%d 各个数之和为：%d\n",num,sum);
    
    return 0;
}

=====
125 各个数之和为：8

斐波那契额数列：兔子数列

当前数是前两个数之和:

打印出这样的数字：0 1 1 2 3 5 8 13 …

// 递归求和
int fibonaci(int i) {
    if (i == 0) {
        return 0;
    }
    if (i == 1) {
        return 1;
    }
    return fibonaci(i - 1) + fibonaci(i - 2);
}

int main(int argc, const char * argv[]) {
    // 斐波那契额数列
    for (int i = 0; i < 10; i ++) {
        printf("%d\t\n",fibonaci(i));
    }
    return 0;
}

=======
0	
1	
1	
2	
3	
5	
8	
13	
21	
34
....

求 n 的阶乘

问：求 1x2x3x4x…n ?

// 求 n! 传入一个无符号整型
double factorial(unsigned int i){
    if (i <=1 ){
        return 1;
    }
    return i * factorial(i-1);
}

int main(int argc, const char * argv[]) {
    int i = 5;
    printf("%d 的阶乘是：%f\n",i,factorial(i));
    return 0;
}

=====
5 的阶乘是：120.000000

汽水瓶

某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。
小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
数据范围：输入的正整数满足
1 ≤ n ≤ 100

注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。

示例1：
输入例子：
3
10
81
0
输出例子：
1
5
40
例子说明：
样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换
样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板

#import <Foundation/Foundation.h>

int main(int argc, char* argv[]) {
    NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
    // 定义空气水平为num，最多可喝到ret
    int num,ret;
    while (scanf("%d", &num) != EOF) { // 汽水瓶可以是0，这里跳出循环
        // 初始值
        ret = 0;
        if (num > 0) {
            // 如果空瓶 >= 3 那么一直可置换
            while (num >= 3) {
                // 汽水 = 汽水 + 空瓶3个换一瓶汽水
                ret = ret + num/3;
                // 空瓶3个换1个空瓶 + 剩余未置换的空瓶
                num = num/3 + num%3;
            }
            // 如果还剩2个空瓶，则还能置换一瓶汽水
            if (num == 2) {
                ret ++;
            }
            printf("%d",ret);
        }
    }
    [pool drain];
    return 0;
}

字符串去重

int main(int argc, const char * argv[]) {
    // 字符串
    char str[] = "abcabdAAVCBC";
    // 长度
    long len = strlen(str);
    // 数组
    char ret[30] = {0};
    int num = 0;
    for (int i = 0; i < len; i ++) {
        int flag = 0;
        // num 每增加1 代表数组添加一个元素
        for (int j = 0; j < num; j ++) {
            // 遍历数组，如果其中包含某个字符，则不去添加
            if (str[i] == ret[j]) {
                flag = 1;
            }
        }
        // 添加元素
        if (flag == 0) {
            ret[num] = str[i];
            num ++;
        }
    }
    printf("ret == %s\n",ret);
    
    return 0;
}

明明的随机数

明明生成了N个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。
数据范围： 1≤n≤1000 ，输入的数字大小满足 1≤val≤500

输入描述：
第一行先输入随机整数的个数 N 。
接下来的 N 行每行输入一个整数，代表明明生成的随机数。
具体格式可以参考下面的”示例”。

示例1：
输入例子：
3
2
2
1
输出例子：
1
2
例子说明：输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到500之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
2
2
1
所以样例的输出为：
1
2

c 语言实现：

#import <Foundation/Foundation.h>

int main(int argc, char* argv[]) {
    NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
    int n; // 个数
    int arr[1001]; // 数组
    int j,k;    //定义循环因子，嵌套双层循环
    while (scanf("%d", &n) != EOF) {
        // 生成随机数并添加到数组中
        for (int i = 0; i < n; i ++) {
            int r = rand()%1000;
            arr[i] = r;
        }
        // 冒泡排序
        for(j=0; j<n-1; j++)    //设置循环后界
        {
            for(k=0; k<n-j-1; k++)    //不断向后进行比较
            {
                if(arr[k]>arr[k+1])    //比较相邻的元素
                {
                    int temp=arr[k];    //三杯水交换法
                    arr[k]=arr[k+1];
                    arr[k+1]=temp;
                }
            }
        }

        /* 输出数组中每个元素的值 */
        for (int m = 0; m < n; m++ ){
        printf("Element[%d] = %d\n", m, arr[m] );
        }
    }
    [pool drain];
    return 0;
}

进制转换

16进制转10进制

#import <Foundation/Foundation.h>
#include<stdlib.h>

int main(int argc, char* argv[]) {
    char a[] = "1c";
    func(a);
    printf("%d\n",func(a));
    return 0;
}

int func(char a[]){
    // 长度
    long len = strlen(a);
    int i,j,num=0;
    for (i = 0; i < len; i ++) {
        if (a[i] == 'A')
            //pow() 函数用来求 x 的 y 次方的值。
            num += 10 * pow(16, len - i - 1); 
        else if (a[i] == 'B')
            num += 11 * pow(16, len - i - 1);
        else if (a[i] == 'C')
            num += 12 * pow(16, len - i - 1);
        else if (a[i]=='D')
            num += 13 * pow(16, len - i - 1);
        else if (a[i] == 'E')
            num += 14 * pow(16, len - i - 1);
        else
            num += i * pow(16, len - i - 1);
    }
    return num;
}