纯C代码模板

一、快排

void QuickSort(int *a,int left,int right){
	if(left>right) 
    return;
    else{
    
    int low = left,high = right;
    int pivot = a[low];
	while(low<high){
		while(a[high] >= pivot && low < high){
        high--;}
		a[low] = a[high];  //必须先动a[low]
		while(a[low] <= pivot && low < high){ 
        low++;}
		a[high] = a[low];
	}
	a[low] = pivot;
	QuickSort(a,left,low-1);
    QuickSort(a,low+1,right);
    }
}

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a, const void *b){
	return *(int *)a - *(int *)b;//升序
//	return *(int *)b - *(int *)a;//降序
}

int main()
{
	int n,s[10000];
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d",&s[i]);
	qsort(s, n, sizeof(s[0]), cmp);
	for(int i=0;i<n;i++)
		printf("%d ",s[i]);
	return 0;
 } 

二、二分查找

int search(int* nums, int numsSize, int target) {
    int left = 0,right = numsSize-1,middle = 0;
    while(left<=right){
        middle=(left + right)/2;
        if(nums[middle]>target)
        right = middle-1;
        else if(nums[middle]<target)
        left=middle+1;
        else if(nums[middle]==target)
        return middle;
    }
    return left; //返回应该插入的地方
}

三、取数值各个位上的单数操作

leetcode 202快乐数

//对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
//n=191  sum=1+81+1=83
int getSum(int n) {
    int sum = 0;
    while(n){
    sum =sum + (n % 10) * (n % 10);
    n=n/10;
    }
    return sum;
}

三、进制转换

// 翻转字符串中指定范围的字符
void reverse(char* s, int start, int end) {
    for (; start < end; start++, end--) {
       char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
    }
}
// 先用flag表示最后要不要加负号
//  数值各个位上单数操作
//  最后翻转一下即可
char* convertToBase7(int num) {
    if(num==0) return "0";
    int flag=1;
    if(num<0) flag=0;
    num=num>0?num:-num;
    char *ret=(char*)malloc(sizeof(char)*32);
    int pos=0;
    while(num>0){
        ret[pos++]=num%7+'0';
        num/=7;
    }
    if(flag==0) ret[pos++]='-';
    reverse(ret,0,pos-1);
    ret[pos]='\0';
    return ret;
}

四、单链表的各种操作 

#define MAX(a, b) ((a) > (b) ? (a) : (b))
typedef struct ListNode{   //定义单链表结点
    int val;
    struct ListNode*next;
}ListNode;


typedef struct  {             //定义单链表，指明头指针和结点数
    struct ListNode *head;
    int size;
}LinkedList;

struct ListNode *ListNode_Creat(int val) {  //创建一个链表结点并赋值val
    struct ListNode * node = (struct ListNode *)malloc(sizeof(struct ListNode)*1);
    node->val = val;
    node->next = NULL;
    return node;
}

LinkedList* LinkedList_Create() {    //创建一个链表，初始为空
    LinkedList * obj = (LinkedList *)malloc(sizeof(LinkedList));
    obj->head = ListNode_Creat(0);  
    obj->size = 0;
    return obj;
}

int LinkedList_Get(LinkedList* obj, int index) {    
     //找到链表中第index个结点，第0个即头结点
    if (index < 0 || index >= obj->size) {
        return -1;
    }
    struct ListNode *cur = obj->head;
    for (int i = 0; i <= index; i++) {
        cur = cur->next;
    }
    return cur->val;
}

void LinkedList_Add_At_Index(LinkedList* obj, int index, int val) {
    //在第index个结点处添加一个新结点，赋值val
    if (index > obj->size) {
        return;
    }
    index = MAX(0, index); //index为负值或0时意为在头节点后插入
    obj->size++;
    struct ListNode *pred = obj->head;
    for (int i = 0; i < index; i++) {
        pred = pred->next;
    }
    struct ListNode *toAdd = ListNode_Creat(val);
    toAdd->next = pred->next;
    pred->next = toAdd;
}

void LinkedList_Add_At_Head(LinkedList* obj, int val) {//头插
    LinkedList_Add_At_Index(obj, 0, val);
}

void LinkedList_Add_At_Tail(LinkedList* obj, int val) {//尾插
    LinkedList_Add_At_Index(obj, obj->size, val);
}

void LinkedList_Delete_At_Index(LinkedList* obj, int index) {
    //删除第index位置的结点
    if (index < 0 || index >= obj->size) {
        return;
    }
    obj->size--;
    struct ListNode *pred = obj->head;
    for (int i = 0; i < index; i++) {
        pred = pred->next;
    }
    struct ListNode *p = pred->next;
    pred->next = pred->next->next;
    free(p);
}

void LinkedList_Free(LinkedList* obj) {
    //释放一个链表的所有空间
    struct ListNode *cur = NULL, *tmp = NULL;
    for (cur = obj->head; cur;) {
        tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(obj);
}

五、 翻转字符串中指定范围的字符

// 翻转字符串中指定范围的字符
void reverse(char* s, int start, int end) {
    for (; start < end; start++, end--) {
       char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
    }
}

六、暴力字符串匹配

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    for (int i = 0; i + m <= n; i++) {
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (haystack[i + j] != needle[j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            return i;//返回第一个字符串匹配处的下标
        }
    }
    return -1;
}

七、strlen  strcmp   isdigit  C语言实现

int mystrlen (char*s){
char *start=s;
char *end=s;
while(*end!='\0') end++;
return end-start;
}

int my_strcmp(char* arr1, char*arr2)
{
	while (*arr1 == *arr2)//遍历arr1和arr2数组,判断字符串元素是否相同
	{
		if (*arr1 == '\0')//其中任意一个字符串来到'\0'说明两个字符串内容都相同，返回		
			return 0;
		arr1++;//将arr1与arr2加一找到下一个字符进行比较
		arr2++;
	}
	return *arr1 - *arr2;//若字符串元素出现不同，则返回两元素相减的值
}

int myisdigit(char c){
return  c>='0'&&c<='9';
}

八、 math.h部分函数实现

#include <stdio.h>
double myabs(double x){  //绝对值
    if(x>0) return x;
    return  (-x);
}
int myshang(double x){ //向上取整
    if(x>0) {
       return ((int)x)+1;
    }
    else return (int)x;
}
int myxia(double x){  //向下取整
    if(x>0) {
       return ((int)x);
    }
    else return (int)x-1;
}
int myround(double x){  //四舍五入
    if(x>0) {
        if(x>myxia(x)+0.5) return  myshang(x);
        return myxia (x);
    }
    else{
        if(x>myshang(x)-0.5) return myshang(x);
        return myxia (x);
    }
}
double mypow(double x,int y){  //x的y次方
     double sum=x;
      while((y-1)){
          sum*=x;
          y--;
      }
      return sum;

}
signed main(){
    double n;
    scanf("%lf",&n);
    printf("%.2f ",myabs(n));
    printf("%d %d ",myxia(n),myshang(n));
    printf ("%d ",myround(n));
    printf("%.2f",mypow(n,5));
    return 0;
}

九、取最大公约数/最小公倍数/互质

//最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

最小公倍数为
a/gcd(a,b)*b
最大公约数是1，就是互质

十、判断素数

#include<stdio.h>
int isprime(int n){
    int mybool=1;
    if(n<2) mybool=0;
    for(int i=2;i<=n/i;i++)
     if(n%i==0)  mybool=0;
    return mybool;
}
int main(){
    int n;
    scanf("%d",&n);
    int myb=isprime(n);
    if(myb==1) printf("Yes");
    else printf("No");
    return 0;
}

十一、螺旋矩阵

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//用来顺时针旋转，一开始是行不变，列往右；然后行往下，列不变
然后行不变，列往左；然后行往上，列不变

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrixColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }//空矩阵处理

    int rows = matrixSize, columns = matrixColSize[0];
    int visited[rows][columns];
//visited用来判断是不是访问过了，用来缩小边界
    memset(visited, 0, sizeof(visited));
    int total = rows * columns;
    int* order = malloc(sizeof(int) * total);
    *returnSize = total;
//order是一个要求返回的一维数组
    int row = 0, column = 0;
    int directionIndex = 0;
    for (int i = 0; i < total; i++) {
        order[i] = matrix[row][column];
        visited[row][column] = true;
        int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
        if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
            directionIndex = (directionIndex + 1) % 4;
        }
        row += directions[directionIndex][0];
        column += directions[directionIndex][1];
    }
    return order;
}

十二、leetcode二维数组返回问题

#define IN 
#define OUT
// 定义框架
#define __________FRAME_START__________
#define __________FRAME_END__________

// 输入参数：intervals是数组指针，常规用法
// 输入参数：intervalsSize是数组行数，常规用法
// 输入参数：intervalsColSize是数组列数指针，我又不去改它列数，为什么要指针而不是整型，求指教，划为迷惑用法
// 输出参数：returnSize是返回数组行数，此处指定方便平台编译，可以理解，因此默认需要手动初始化，也就是印证了上面Note的说法，常规用法
// 输出参数：returnColumnSizes是返回列数的数组指针
int** merge(IN int** intervals, IN int intervalsSize, IN int* intervalsColSize, OUT int* returnSize, OUT int** returnColumnSizes){
  
    __________FRAME_START__________

    int row = 0; // 定义行列，二维数组肯定会用到
    int col = 0;
    *returnSize = 0; // 初始化returnSize

    int** ret = (int**)malloc(sizeof(int*)*intervalsSize );
    // 在堆空间分配二维数组，所以用malloc方法，不能在栈空间直接定义数组，不然无法返回
    // 定义返回数组的二级指针，元素个数为行数，我一般把二维数组看成一个顺序表，每个结点是一个数组
    // 若用returnColumnSizes = (int**)malloc(sizeof(int*)*intervalsSize );方法定义，不创建新指针变量虽不报错但输出结果会有问题
    for (row = 0; row < intervalsSize; row++)
    {
        ret[row] = (int*)malloc(*intervalsColSize * sizeof(int)); // 为每个结点分配一个数组空间，元素个数为列数

    } // 此时返回的二维数组创建完毕
    *returnColumnSizes = (int*)malloc(sizeof(int)*intervalsSize ); 
    // 为神秘的returnColumnSizes指针变量初始化分配一段空间
    // 元素个数为行数，每个元素用来存放该行的列数

    __________FRAME_END__________

   

十三、同构哈希

十四、sprintf 

#include <stdio.h>

int main() {
    char buffer[50];
    int a = 10;
    float b = 20.5;
    
    // 使用sprintf将格式化的字符串写入buffer
    sprintf(buffer, "整数是: %d, 浮点数是: %.2f", a, b);
    
    // 输出buffer的内容
    printf("%s\n", buffer);
    
    return 0;
}

 十五、字符串模拟加法

//多少进制加法都是这个模板
char * addBinary(char * a, char * b){
    int carry = 0;
    int lena = strlen(a);
    int lenb = strlen(b);
    int len  = fmax(lena, lenb);
    int i    = lena - 1;
    int j    = lenb - 1;
    char *res = (char*)malloc(sizeof(char) * (len + 2)); /* 长度可能是更长的字符串加1 */
    int k = len + 1;
    res[k--] = '\0'; /* 添加结束符 */

    /* 模拟加法处理 */
    while (i >= 0 || j >= 0 || carry > 0) {
        carry += (i >= 0) ? a[i--] - '0' : 0;     //记录a当前位的值
        carry += (j >= 0) ? b[j--] - '0' : 0; 
        res[k--] = carry % 2 + '0';              //3取余是1，
        carry /= 2;                                //进位
    }
    return res + k + 1;  //注意最后停止在哪里
}

随便记机

数组篇

 二分查找：

注意while中是小于等于，等于时要进行判断，不然会忽略只有一个值且是目标值的情况

注意更新值是middle要是边界值减一或者加一，不然只有一个值是不会跳出循环

数组移除元素

用一个count记录目前返回数组的计数就行，注意最后数组元素个数具体是什么

有序数组的平方（快排）

先平方再快排就行，快排注意点：

三个while里面都是小于,同时low和high移动时都是小于等于或者大于等于移动

长度最小的子数组（和大于目标值的子数组的最小长度）

滑动窗口，从左到右，从下标零开始先找到满足目标值的子数组，记录目前最小长度。然后左边界尽可能地在满足大于目标值的情况下往右边划，记录目前最小长度。最少划一次后然后不满足了，然后右边界往右划直到满足，记录目前最小长度。重复此操作直到右边划到头。

链表篇

树篇

111.求二叉树的最小深度

贪心篇

455分发饼干

先排序，然后双指针比较即可

376摆动序列

用一个trend记录上升还是下降，上升为1，下降为0，初始trend为100保证初始一定记录

53最大子序列：

从头开始，记录一个当前sum和最大result，遇见负数也sum计数加值，遇见正数自然会更新result，如果sum计数到负值了，令sum=0从头开始计数sum。result一定是保存当前最大值，初始化为INT_MIN(导致一定会记录到第一个负数，然后后续会记录到最大的负数)

122买卖股票的最佳时机Ⅱ：

比如有三天。第一天买第二天卖同时第二天买第三天卖，即3-2+2-1=3-1。跟第一天买第三天卖一样。因此只要能赚钱，就可以日抛，只需要找到整个周期中日抛为正的差值，然后加起来就行

55跳跃游戏：

用一个cover来记录当前能达到的下标范围，达到终点即可返回。在迭代的过程中不断更新该cover的实际范围。 

45跳跃游戏2

与I不同的是这里一定可以保证到达终点，因此局部最优可以为找到当前位置i到j使cover最大的j，然后更新i=j,count+1；最后当cover可以到达时，cover+1即可结束。

1005K次取反后最大化的数组

排序数组，先统计数组负值数量count，取count和K最小的把数组的负值翻转，如果K大于count，排序数组，把k-count用来翻转最小的那个元素，K-count为偶数相当于不变，最后求和数组。

字符串篇

58.最后一个单词的长度

因为是最后一个单词，所以可以把字符串翻转，这样转换到了前面。

然后把开头第一个单词前面的空格删

然后计算第一个单词的长度即可

844.比较含退格的字符

strcmp函数的实现还有删除#的操作，注意返回的是一个新字符串数组

524. 通过删除字母匹配到字典里最长单词

注意字典是一个二维数组，每次取出一行就行，记为q

当前p,q字母相等时下标都加加，当不等时p下标++，直到为两者其一为空，q为空就是匹配到了，更新当前最长单词，如果长度相同，比较字典序。

1309. 解码字母到整数映射

判断属于哪种解码，然后对应位怎么处理即可

动态规划篇

509斐波那契数

递归法，动态规划法（使用dp数组），迭代法

70爬楼梯

每次你可以爬 1 或 2 个台阶， dp[i]=dp[i-1]+dp[i-2]

746使用最小花费爬楼梯

每次你可以爬 1 或 2 个台阶，加上花销，dp[i]=fmin(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

62不同路径

先初始化第一行和第一列都是1，递推公式： f[ i ] [j ] = f[i - 1][ j ] + f[ i ] [ j - 1];

63不同路径2

先初始化第一行和第一列都是0，然后检查第一行第一列是否有障碍物，把没有障碍物的地方初始化为1，递推公式仍然是f[ i ] [j ] = f[i - 1][ j ] + f[ i ] [ j - 1]，先检查ij位置是否有障碍物即可

343整数拆分

两层遍历，外层是i，内层是j从1到i-1，dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));//内层每次更新dp[i]

300最长递增子序列

dp[i]表示以nums[i]为结尾的最长子序列数目，然后对于j<i,如果nums[j]<nums[i]，那么dp[i]=dp[j]+1，那么在一个i中，遍历所有的小于i的j，取dp[i]的最大值。