一、快排
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) { //创建一个链表结点并赋值valstruct 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个结点处添加一个新结点，赋值valif (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; // 初始化returnSizeint** 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将格式化的字符串写入buffersprintf(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]的最大值。
