一、快排
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]的最大值。
![[译] 教你如何用 Flutter 的 GestureDetector 构建自定义滑块](https://img-blog.csdnimg.cn/img_convert/9619864ab5dcb1e2cf0b0e83065810b9.webp?x-oss-process=image/format,png)
