acwing基础算法笔记

🫥acwing基础算法笔记

<丘比特，大梦想>

那些不能杀死我们的，必将使我们变得强大       ——尼采

😏算法目录😏

1.快速排序

2.归并排序

3.二分查找

(1)整数二分

(2)浮点数二分

[TOC]

🐻前言

本篇文章主要针对在acwing算法课中的一些困惑和重要思路进行整理，从而便于复习提升。

1.快速排序

快速排序是一个比较经典的算法其主要是利用分冶的思想对总区间进行无限细分并对每个小区间进行调整,从而达到有序的目的。

具体实现及分析：

(1)算法基本结构

函数名称以及参数对象：

名称：函数接口的名字尽量与quick sort有关联缩写也好，要让人一读就能明白函数接口的意义

参数：因为这里来主要对数进行排序来演示所以参数就直接设置为整型指针，和左右边界下标.因为是传址调用直接更改数组并不需要返回什么参数所以就设为void

1
void my_qsort(int* arr，int l,int r)

算法主要模式：

主要实现方式是递归，值得注意的是在递归的时候要提前设好跳出条件，即将区间细分完或者子区间待细分序列只剩下一个数的时候就要进行跳出了，如若不然则会死递归导致栈溢出。所以综上我们递归的基准条件就已经确定了当递归传入区间中只有一个或0个的时候跳出。

简单来说就是当数组只有一个数或压根就是空的时候不用对数组进行排序了，因为他本来就是有序的

1
2
3
4
if(l >= r)
{
    return;//因为返回值是空类型所以并不需要返回什么具体的值
}

递归进行的主要操作：

递归基准条件已经确定了，那么就应该确定一下具体操作了，我们先从数据量较小的看起：

image-20230204172450628

然后咱们再把数据增加一下：

image-20230204174457344

仅仅是这点数据还是无法体现分治法的优点，下面我们加大亿点难度：

image-20230204175452424

1.选取基准值定义相关变量对应的值以及移动左右边界的临时变量：

一般选取最左边，最右边，以及中间值

1
2
3
int i = l - 1;//一开始要将临时变量指向数组外边，因为后边要利用do—while语句进行指向元素与基准值进行比较
int j = r + 1;//比较后确定了关系进行交换。
int x = arr[l + r >> 1]//这里选取中间值作为基准

2.区分区间不符合区间关系的进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while(i < j)//当指向左右的变量重合或者是交错的时候，就要跳出
{
    //确定指向左边的是不是小于基准值
    do
    {
        i++;//这便于理解上边的l - 1的操作了,因为上来就要移动。
	}while(arr[i] < x);
    //确定是不是大于基准值
    do
    {
        j++;
	}while(arr[j] > x);
    //判断是否未相遇或者是错过
    if(i < j)//因为前文已经进行了移动所以要对while条件在进行判断
    {
        //交换
        swap(arr[i],arr[j]);//c++库中特有的函数
	}
}

3.确定递归传入数据来执行递归操作

因为分治法是对区间不断细分的递归手段所以要确定好传入数据，以及对应递归区间的界限，因为是不断分为两块，所以要对所剩的两个区间分别进行细分所以要进行两次递归。

1
2
my_qsort(arr,l,j)//这里的j代表第一块区间的边界
my_qsort(arr,j+ 1,j)//这里的j+1代表右边界的起点

2.归并排序

其实归并排序的思想与上边的思想如出一辙，也是分治的思想将数组分成两个区间，无限细分成两个区间只剩下一个的时候对两个序列进行比较合并到临时数组中，然后在最后将数据一点一点读入原来数组。

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
36
37
38
39
40
41
42
43
//临时数组尽量开大点
const int N = 100010；
int tem[N] = {0};
void mer_sort(int * p,int l,int r)
{
    //确定基准值，中间
    mid = l + r >> 1;
    //进行细分区间
   //对从中间分开的区间分别进行细分
    mer_sort(p,l,mid);
    mer_sort(p,mid + 1,r);
    //设定移动的临时变量，以及重排列的变量
    int i = l;//每个区间的起始
    int j = mid + 1;
    int k = 0;//重排变量
    //开始比较存放，这时可以将两个区间看作两个单独的数组，所以这里的合并的条件就是边界问题了
    while(i <= mid && j <= r)
    {
        if(p[i] > p[j])
        {
            tem[k++] = p[j++];
		}
        else
        {
            tem[k++] = p[i++];
		}
	}
    //因为有可能有剩的所以要进行边界判断，然后进行拼接
    while(i <= mid)
    {
        tem[k++] = p[i++];
	}
    while(j <= r)
    {
        tem[k++] = p[j++];
	}
    //将tem的数从当前递归的左边界进行拼接
    for(i = l，j = 0;i <= r;i++,j++)
    {
        //进行读入
        p[i] = tem[j];
	}
}

2.二分查找

二分重要的是找到那个分区的条件，即答案所处区间和答案不在的区间的分界。其实二分说简单也简单，说不简单，有时候你还真想不到。大家可能都做过猜数字这个小游戏，或者是数字炸弹，一般都是用二分法来猜的，因为这样能一下排除剩下的一半。

但是在编程中大家有时候根本不敢用，因为动不动就数组越界了。让人很崩溃。但是，今天我两个模板便能解决你的苦恼让你大呼过瘾。

例如：

image-20230204224940500

这题就是利用二分把左右边界找到：

如： 1，2，2，3，3，4

如果我要查找2的话那么就要返回1 ，2

如果4的话则5，5.

如果没有的话-1，-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
25
26
27
28
29
30
31
32
33
34
//判断是否符合某种能够缩小答案空间的条件
bool check(int x)……
int half_sort(int l,int r)//适合进行极致向右进行右边界查找
{
    while(l < r)//当两个重合的时候跳出
    {
        int mid = l + r >> 1;
        if(chaeck(x))//注意这是你自己画图判断答案区间的条件
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
	}
    return l;//因为会重合所以返回那个都一样
}
int half_sort1(int l,int r)
{
     while(l < r)//当两个重合的时候跳出
    {
        int mid = l + r >> 1;
        if(chaeck(x))//注意这是你自己画图判断答案区间的条件
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
	}
    return l;//因为会重合所以返回那个都一样
}

注意：其中的if条件根据自己理解进行调整，即预期区间缩小来确定

image-20230204231430373

二分虽好，可不要贪杯。

结语

愿诸君可以未来乘风破浪

展开全文 >>

leetcode经典题第一弹

😏简单但是出人意料的算法题

这个主要对我平常所做的oj题进行总结，并对方法进行归类。，并对算法进行评价。从而得到最目前水平上认为的最优解、

迟迟钟鼓初长夜，耿耿星河欲曙天

​ ——《长恨歌》

1.消失的数字

基本思路:

1.思路一（暴力）

创建一个元素个数为n + 1的数组以便记录数字是否出现，根据记录数组1/0的情况来判断。即遍历传入数组的同时开始记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    int  *p = (int *)malloc(sizeof(int) * (numsSize + 1));//动态开辟数组
    for(i = 0;i < numsSize + 1;i++)
    {
        p[i] = 0;//初始化动态数组
    }
    for(i = 0;i < numsSize;i++)
    {
        p[nums[i]]++;//对对应位置的数进行记录
    }
    for(i = 0;i < numsSize + 1;i++)
    {
        if(!p[i])
        {
            return i;
        }
    }
    free(p);
    p = NULL;
    return 0;
}

因为计算机记不住不智能，只能将动态开辟数组当作记录版，记录数字是否出现过。

2.排序后比较

即将数组先排成有序序列，因为是有序的所以要找出缺失的那个数字，就要用这个序列最大数从序列的最大开始比较如果比不上就会返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int cmp(const void * e1,const void * e2)//快排序的比较函数
{
    return *(int *)e1 - *(int *)e2;
}

int missingNumber(int* nums, int numsSize)
{
    int i = 0;
    qsort(nums,numsSize,sizeof(nums[0]),cmp);//对序列进行排序
    for(i = numsSize;i > 0;i--)//从最大的数开始一一对比
    {
        if(i != nums[i - 1])
        {
            return i;
        }
    }
    return 0;
}

但是这个算法的时间复杂度是O(n)

3.十分不可思议的算法

首先我们要了解到按位异或操作符的几个特性，即

1.第一个特性：相同为0相异为1

1
2
3
int x = 3;
int y  = 3;
printf("%d", x ^ y)；//结果是0

2.第二个特性： 支持交换律

1
2
3
4
5
6
7
8
9
10
11
//请看下面一段代码
int a = 2；
int b = 0;
int c  = 3;
//请判断下面的表达式
printf("%d",a ^ b ^ c);
int x = c ^ a;
printf("%d",x ^ b);
//其实上边两个输出结果是一样的
//上边两个表达式其实在表义上并无不同
//将表达式进行替换交换可以发现x ^ b   =>  c ^ a ^ b => a ^ b ^c

知道了上述特性我们就不难想出既然按位异或可以对相同项进行消除那么，我们不妨将n从最高位进行递减操作并将每一个得到的数对已有数列进行异或操作最后剩下的就是缺失的。，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int missingNumber(int* nums, int numsSize)
{
    //接收异或结果的临时变量
    int x = 0;
    //循环调整变量
    int i= 0;
    for(i = numsSize;i > 0 ;i--)
    {
       if(!x)
       {
           x = nums[i - 1] ^ i;//因为一开始的x是具有0这个数值的所以要进行赋初始值
       }
       else
       {
           x ^= nums[i - 1] ^ i;//对数组数进行异或操作。
       }
        
    }
    return x;


}

![](D:\blog\source_posts\leetcode经典题第一弹\屏幕截图 2023-02-02 001552.png)

展开全文 >>

malloc-test

🐻动态内存开辟🐻

东风夜放花千树，更吹落，星如雨。

​ ————《青玉案.元夕》

《更吹落，星如雨》|插画|插画习作|狐狸狐狸鱼 - 原创作品 - 站酷 (ZCOOL)

[TOC]

✨前言

当所需空间是变化或者是不确定的时候，开辟数组这类的开辟明确固定内存空间的方法。总归是一定的限制。故我们就要对内存的动态需求有一定的响应和相应，所以接下来了解一下专门应对这种情况的机制->动态内存分配机制。

一、🫥动态内存开辟的相关函数

1.🤖[malloc](malloc - C++ Reference (cplusplus.com))和[free](free - C++ Reference (cplusplus.com))的使用

image-20230114223030797

函数作用分析：在对空间上开辟一块size字节大小的内存块，并返回此内存块的指针。

参数：size是要开辟的内存块所占的字节大小。

返回值：返回空指针，并进行强制转换。

注意：在使用这个函数的时候要进行强制类型转换，并用所开辟类型的指针接收。

使用基本规则: (需要开辟的数据类型指针)malloc(sizeof(期望数据类型) * 想要连续内存块所包含的)

同时在使用的时候值得注意的是，要了解这个函数调用返回规则。

  • 正常调用时，开辟成功会返回一个指向内存块的指针
  • 调用失败的时候，异或是空间不足则会返回NULL指针。
  • 如果是传入的是0，仍然会开辟，并返回有效指针

所以在调用完这个函数后要进行判空行为：

1
2
3
4
5
6
int * p = (int*)malloc(sizeof(int) * 10);
if(!p)
{
    perror("malloc");//这个函数得传入自定义信息当程序出现错误的时候将会将错误码解析后的结果放在自定义信息后边
    return 1;
}

image-20230118214333139

函数分析：是针对动态开辟得到的内存进行释放。归还给操作系统

参数分析：传入的应该是在堆上开辟的对应内存块的指针。

注意这个函数是跟malloc是成对出现的，一旦有malloc就一定要出现free来对空间进行释放。，但是对应动态开辟的指针不会变空，要进行手动置空，以防出现野指针。

所以就有以下范式：

1
2
3
int  p = (int*)malloc(sizeof(int)*3);
free(p);
p = NULL;

了解了这些，之后我们心中就会不禁生出疑惑为什么变量之类的就不需要我们释放而这种动态开辟的内存，需要我们主动进行销毁呢？

在解释这个问题之前我们要对内存空间要有更加深刻的了解。

image-20230119115652059

可见释放内存是一个优秀程序员在动态开辟后的必要操作。

换个角度来看，请设想这样一个场景，你是一个不释放内存的屑程序员，每天开辟一点每天开辟一点，公司的服务器内存就被占用一点，本来在你自己写程序的时候，程序结束了，就会将这段内存处理掉。但是在公司里，服务器可是一天都不敢关，每次到你负责的接口就泄露一点内存，到将来的某一天服务器崩了，一查是你的原因，那你觉得leader会怎么处理你呢。

你可能只能删库跑路了🥲：

程序员“删库跑路”，一己之力蒸发公司市值超10亿，300万商铺遭瘫痪 - 知乎

当然作为一个懂得是会主义核心价值观的新时代青年肯定是不能干出来这种事的吧🐼！？嗯，肯定的。😏

编程的第一法则：如果您的代码以某种莫名方式跑起来了，就不要再碰它了-表情包就找i表情

花开两朵，咱们各表一枝。回归正题，了解完了一些内存的基本区域储存规则，趁热打铁我们再来认识几个函数

2.realloc和calloc

image-20230119213653170

函数作用机制：

  • 如果相对于原来内存块有所减少那么，那么那些多出的部分就会进行释放。

  • 如果在增加时此块内存块后边有足够的空白内存，就会增加开辟，并将原来的地址进行返回

  • 若增加的时候此处内存块的后面没有足够的空白内存的话，这个函数则会找一个足够的部分将重设后的内存开辟在这个地方。并返回新开辟的内存空间的地址。

  • 因为返回的是空类型指针，所以要进行对应的强制类型转换，和接收对应。

  • 值得注意的是，指针传入的参数也可以是空指针，如果传入的是NULL的话，那就会在堆内存块任意找一个空内存，进行对应的开辟，作用相当于malloc。

  • image-20230124142909196

    应用示例：

1
2
3
4
5
6
7
8
9
10
11
12
//前文已经开辟了四十字节的动态空间p，下面是对其进行调整
//由之前的函数调用机制所以要用临时变量进行接收，同时要进行判空
int * ret = (int *)realloc(sizeof(int )*50);
if(ret)
{
    p = ret;//不为空所以可以进行赋值
}
else
{
    perror("realloc");//对错误信息进行打印
    return 1;
}

image-20230123174826752

函数作用分析：

在堆内存上动态开辟一个数组内存块并将数值初始化成0，然后对堆内存的地址进行返回。

参数分析：

num

所要开辟的元素个数

size

元素所需要占据的字节大小。

返回值:

因为返回值是空类型的指针，所以要经常进行指针类型的强制类型转换，因为，开辟失败会返回空类型的指针，所以在使用式用临时变量进行接收，而且进行判空，才能使用

使用范例：

1
int * p =  (int * )calloc(5,sizeof(int));

image-20230124193715342

二、调用时值得注意的误区

1.对空指针的误解引用

1
2
3
4
5
6
void test()
{
    int *p = (int *)malloc(INT_MAX/4);
    *p = 20;
    free(p);
}

乍一看可能没什么问题，但是考虑一下malloc的特点就可以明白，他会有两种情况：若开辟失败会返回空指针，那么下面的解引用操作就会对空指针进行操作，但是这种操作在编译器看来是非法的，因为这个空地址并无意义，没有指向，所以会报错。导致程序出错

2.动态空间的越界访问

请看下面的代码：

1
2
3
4
5
6
7
8
9
10
void test()
{
    int n =0;
    int *p = (int *)malloc(sizeof(int) * n);//四个整形大小边界
    int i= 0；
    for（i = 0;i <= n;i++)
    {
        p++;//因为p是起始位置的大小所以只能进行n - 1自增，但是当i= n是就进行了n次自增，会对为内存块的未使用内存非法访问。
	}
}

3.对非动态开辟内存进行释放

1
2
3
4
5
void test()
{
    int a = 0;
    free(a);//这个free  ok？
}

当然，众所周知的是free是通过堆内存地址对堆内存上的内存进行回收。对栈区的空间无法进行干涉，所以不能对非动态开辟的内存进行释放。

4. 只是对动态开辟的内存进行部分释放

1
2
3
int * p = (int *)malloc(sizeof(int) * 3);
p++;//使得原来指向起始位置的指针产生影响，使得指向下一个位置
free(p);//只是对动态内存进行部分释放，因为已经释放p指针已经变成了野指针了，不可访问所以未释放部分就会内存泄漏

5.对一块动态内存空间多次进行释放

1
2
3
4
5
6
void test()
{
    int * p = (int * )malloc(sizeof(int) * 3);
    free(p);//第一次释放对传入指针的内存空间进行变化使得内存空间释放，也就让p的地址变成了非法访问空间了
    free(p);//传入的是非法地址，无法对非法空间进行访问以及改变，所以报错。
}

6.忘记释放动态内存空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void test()
{
    int * p = (int *)malloc(sizeof(int) * 3);
    //进行判空
    if(p)
    {
        *p  =10;
	}
    
}//因为函数调用结束了栈帧中的临时变量就会销毁以至于没有指针记录空间在堆区上的位置无法回收
//这个导致的后果是内存泄露，是一个十分严重的后果
int main()
{
    test();
    return 0;
}

内存泄漏:即内存因为未知原因消失，了其中对堆区内存的不释放就是一个主要原因，因为不对这个空间进行释放就会一直占用着这块内存使得你再申请空间的时候，编译器对这块空间就会忽视，使得能用的空间变得越来越少，不但占用，最后致使崩溃。

一定要注意：内存一定要适时释放。

三、一些程序谬误笔试题以及解析

1.

1
2
3
4
5
6
7
8
9
10
11
void GetMemory(char *p)
{
	p = (char *)malloc(100);
}
void Test(void)
{
    char *str = NULL;
    GetMemory(str);
    strcpy(str, "hello world");
    printf(str);
}

请问调用上边的函数会有什么结果？

分析：

我们先从test函数主体开始读，开始理解首先前两句的意图是创建一个预期指针用GetMemory来创建内存空间并且存放，所以接下来我们放眼到局部，GetMemory内部定义可以看到参数是字符指针，不要一看是指针类型参数就当成实参，因为实参和形参只是相对而言的，针对同一个变量才有意义，但是，在这里可以看见，这个函数的意图是为了对传入指针的内容进行更改，但是p 只是Test函数中str指针的一份临时拷贝，并不能更改其中内容，所以出了GetMemory，p就会销毁，更改的是实参 开辟的内存地址就也不会被str记住。所以str还是空指针，输出只能是空。

2.

1
2
3
4
5
6
7
8
9
10
11
char *GetMemory(void)
{
    char p[] = "hello world";//在栈帧中创建临时数组，一旦出了函数就会销毁此块栈帧空间，地址指向空间就会进行释放
    return p;//返回也无法正确访问这块内存
}
void Test(void)
{
    char *str = NULL;
    str = GetMemory();
    printf(str);//打印结果   错误
}

请问调用上边的函数会有什么结果？

分析：

这道题虽然与上道题不尽相似，但是上文是利用动态开辟的堆区空间，而这个只是在栈桢空间创建的临时数组空间，并不能通过记住地址在任何地方将进行访问。出了函数定义空间就无法发挥作用，如果访问的话则是野指针。所以Test函数中的str得到的是无效内存空间的地址。编译器无法通过。

3.

1
2
3
4
5
6
7
8
9
10
11
12
Void GetMemory2(char **p, int num)//因为传的是二级指针所以其中的解引用更改会对相应的指针进行修改。
{
	*p = (char *)malloc(num);//动态开辟内存块
}
void Test(void)
{
    char *str = NULL;
    GetMemory(&str, 100);
    strcpy(str, "hello");//会将整个字符串复制到动态开辟的空间连带着‘\0'
    printf(str);//所以输出时就可以直接输出到'\0'
    //打印hello
}

4.

1
2
3
4
5
6
7
8
9
10
11
void Test(void)
{
    char *str = (char *) malloc(100);
    strcpy(str, "hello");
    free(str);
    if(str != NULL)
    {
        strcpy(str, "world");
        printf(str);
    }
}

本题考查点即动态开辟后指针的状况，要了解到free的基本调用机制，并不会将对应的动态指针置空，只会将指向的那个内存块给释放掉，所以，他的本来意图的判空就是为了检测指针。只不过如果不进行置空的话，就会出现野指针的情况。，更改意见：在free后边，进行置空即可。

后记

键盘敲烂年薪三十万，兄弟们必拿下

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家