- 博客(248)
- 资源 (6)
- 收藏
- 关注
RSS订阅原创 【滑动窗口】最大连续1的个数 III
文章摘要： 题目要求在一个二进制数组中找到连续1的最大个数，允许翻转最多k个0。通过滑动窗口算法，可以高效解决此问题。具体思路是：使用双指针维护一个窗口，记录窗口内0的个数。当0的个数超过k时，移动左指针直至窗口内0的个数不超过k。在此过程中，不断更新窗口的最大长度。最终，窗口的最大长度即为连续1的最大个数。此方法避免了直接翻转0的复杂性，通过记录0的个数来间接解决问题，时间复杂度为O(n)。
2025-05-10 09:16:32
464
原创 【网络编程】五、三次握手 && 四次挥手
本文详细介绍了TCP协议中的三次握手、通信过程以及四次挥手的机制。首先，三次握手通过客户端和服务端的SYN和ACK报文段建立连接，确保双方进入ESTABLISHED状态。接着，通信过程中，客户端和服务端通过send()和recv()函数进行数据传输，体现全双工通信特点。最后，四次挥手通过FIN和ACK报文段逐步关闭连接，客户端进入TIME_WAIT状态等待2MSL时间后释放连接，服务端在收到确认后直接进入CLOSED状态。整个过程确保了TCP连接的可靠性和有序性。
2025-05-10 09:15:18
717
原创 【滑动窗口】无重复字符的最长子串
本文介绍了如何找到字符串中不包含重复字符的最长子串的长度。首先通过暴力破解方法，利用哈希表统计字符出现的频次，判断子串是否重复，但该方法时间复杂度较高，容易超时。接着提出了优化的滑动窗口算法，通过双指针（left 和 right）动态调整窗口大小，避免重复遍历。当遇到重复字符时，移动 left 指针直到窗口内不再有重复字符，同时更新最大子串长度。该算法的时间复杂度为 O(n)，效率更高。代码实现中使用了哈希表记录字符频次，并通过滑动窗口机制确保窗口内字符唯一，最终返回最长子串的长度。
2025-05-09 07:39:01
973
原创 【网络编程】四、守护进程实现 && 前后台作业 && 会话与进程组
守护进程（daemon）是一种在后台运行的特殊进程，通常在系统启动时启动，并在系统关闭时终止。它不与用户交互，也没有控制终端，通常以超级用户权限运行，用于执行特定任务或提供服务，如网络服务、系统监控等。守护进程的关键特点是能在系统崩溃或重启后自动恢复，确保服务连续性。会话（session）是一个或多个进程组的集合，包含一个前台进程组和多个后台进程组。会话中的进程组可以通过 shell 命令进行前后台切换，作业可以通过 fg 和 bg 命令在前后台之间转换。前台进程组负责与用户交互，而后台进程组则在后台执行
2025-05-09 07:36:55
1067
原创 【滑动窗口】长度最小的子数组
暴力解法的思路比较简单，就是枚举所有的子数组，看看那些数组和满足要求的数组中长度最小的那个，那么无非就是套两层循环，用。 仔细想想，要是所有元素的值都是正的，那么在子数组中就不存在说遍历一个元素之后总和会变小的情况，也就是说， 切记，我们不要想着如何使用 “滑动窗口” 来解决问题，而是要思考，为什么要用 “滑动窗口”❓❓❓。 这样子通过双指针的移动，看起来就像是一个窗口在平移，所以才叫做 “滑动窗口”！ 首先我们不去管其它解法，就单单暴力解法来说，我们也得先了解它是怎么走的！
2025-05-08 08:46:48
866
原创 【卡特兰数】不同的二叉搜索树
的每个数依次插入二叉树，可以推断当确定了一个根节点之后，左右字数的节点个数就确定了！ 一般这类动态规划，找状态表示比较难，都是通过 “举例 + 抽象出相同的子问题” 来表示状态！ 难的是如何推导状态转移方程，因为它跟我们之前常见的状态转移方程不是很像。 而又因为二叉搜索树的左右子树个数问题其实是一个排列问题，就可以得到。 所以我们现在专门针对某个元素为根节点来研究一下会有多少。就相当于是没节点，其实这也属于一种二叉搜索树，所以。来说，我们可以按照以下规则来划分，分成不同的。 因此，我们只需要。
2025-05-07 22:56:35
1037
原创 【网络编程】二、UDP网络套接字编程详解
UDP相当于 TCP来说细节少了很多，所以我们先从简单的 UDP套接字编程下手，因为其涉及到的细节比较少，也很直接，就是面向报文，服务端拿到信息就直接丢给客户端，丢了也不管，无需我们关系太多细节，等我们把 UDP套接字编程稍微掌握了，其实 TCP的那套接口也是类似的，但是我们学 TCP的时候，需要去了解它的传输细节。 下面我们就从 UDP套接字编程开始，分为服务端和客户端，我们先讲服务端，客户端也就顺其自然了解了！
2025-05-07 22:52:38
1369
原创 【前缀和】矩阵区域和
那其实这道题我们就可以用之前学过的二维前缀和来解决，大体思路都是一样的，虽然我们给过模板，但是切记不要死记硬背，要理解模板是怎么来的！，但问题是，有可能这个区间的一部分是越界的，但是我们只要有效区间，所以我们需要做处理而不能单纯的让 x1 = 中心坐标 - k。之后，问题就和二维前缀和模板题是一样的了，根据状态表示，我们要求的区间 [x1, y1]，这样子一来一旦越界了，最后它们得到的值其实就是最后一行或者最后一列的坐标！语句进行判断的话，其实是比较麻烦的，所以我们这里借用最值函数 max()
2025-05-06 11:04:21
792
原创 【网络编程】一、socket编程详解
因特网上的每台计算机都有一个唯一的 IP地址，如果一台主机上的数据要传输到另一台主机，那么对端主机的 IP地址就应该作为该数据传输时的目的 IP地址。但仅仅知道目的 IP地址是不够的，当对端主机收到该数据后，对端主机还需要对该主机做出响应，因此对端主机也需要发送数据给该主机，此时对端主机就必须知道该主机的 IP地址。因此一个传输的数据当中应该涵盖其源IP地址和目的IP地址，目的 IP地址表明该数据传输的目的地，源 IP地址作为对端主机响应时的目的 IP地址。
2025-05-06 11:02:44
1053
原创 【多线程】九、常见的锁 && 读者写者问题
类型声明如下（注意在linux 2.6内核中，编译带读写锁数据类型时需要加参数，否则会编译错误）structint __lock;// 锁的状态// 读者数量// 读者的唤醒标志// 写者的唤醒标志// 等待读者的数量// 等待写者的数量// 用于存储读写锁的标志位// 当前写者的ID} __data;// 用于计算pthread_rwlock_t的大小// 用于内存对齐其中上述的 __flags。
2025-05-05 14:02:00
934
原创 【前缀和】和可被 K 整除的子数组
此外就是一些细节处理，比如哈希表我们对于一个特殊情况也就是 (sum % k + k) % k。，这样子无论是正数还是负数，得到的就是我们想要的正数结果了，这也是算法题经常遇到的问题！ 那么我们因为我们要求的区间，就是 (sum - x) % k = 0。的话，说明这时整个前缀和区间都是我们要求的，那么我们就需要对 0。，得到的其实是一个负数，这明显不是我们想要的，但是因为 c++ 其实很简单，因为得到了负数，我们只需要在 sum % k。正数】，得到的就是一个正数，如果我们多加了一个 k。
2025-05-04 10:52:22
522
原创 【多线程】八、线程池
线程池是一种多线程的并发模型，它包含了一组线程，用于执行多个任务，通常将任务存储在队列或者数组中，并通过一定的调度算法来实现任务的执行。线程池可以提高应用程序的性能，减少线程的创建和销毁所带来的开销，并能更好地控制并发线程的数量，从而避免因线程过多而导致系统性能下降的问题。加上一个或一个以上的线程实现，线程池中的线程可以从阻塞队列中获取任务进行任务处理，当线程都处于繁忙状态时可以将任务加入阻塞队列中，等到其它的线程空闲后进行处理。需要大量的线程来完成任务，且完成任务的时间比较短。
2025-05-04 10:50:54
652
原创 【前缀和】和为 K 的连续子数组
那么此时如果使用滑动窗口的话，会遗漏中间的一些情况，这都是因为滑动窗口的指针不会回退的原因，但如果要回退的话，时间复杂度就比较高了，所以这道题。，快速定位前面区间内一共有多少个满足要求的子数组，所以哈希表的结构我们设为 unordered_map<int, int> 首先看到连续子数组，我们会想到用滑动窗口来解决这道题，但其实这道题用滑动窗口的话只能暴力破解，因为这道题。 所以我们要换个思路，因为这道题也涉及到数组的连续和，所以可以考虑使用前缀和来解决这道题！位置处，那么我们要求就是从 [0, i]
2025-05-03 21:36:45
725
原创 【多线程】七、POSIX信号量 && 环形队列的生产者消费者模型
CAS是一种常见的原子操作，也称为“比较-交换”操作，是一种比较后数据若无改变则交换数据的一种无锁操作(乐观锁)。用于实现多线程或多进程并发访问共享资源的原子性操作。 CAS操作通常有三个参数：共享变量的内存地址、期望值和新值。CAS操作首先比较共享变量的值是否等于期望值，如果相等，则将共享变量的值替换为新值；如果不相等，则不执行任何操作。在这个过程中，CAS操作具有原子性，即其他线程或进程无法同时访问共享变量，从而避免了竞态条件和数据竞争等问题。 CAS。
2025-05-03 21:34:49
899
原创 【前缀和】除自身以外数组的乘积
因此需要进行两次遍历，第一次遍历用于求左部分的乘积，第二次遍历在求右部分的乘积的同时，再将最后的计算结果一起求出来。是类似的，只不过从之前的加法变成了乘法，具体的细节可以参考之前的笔记，同样还是用两个数组来分别记录前缀乘积和后缀乘积，最后由原数组来获取结果集！区间的元素乘积，所以可以很容易得到 front[i] = front[i - 1]*nums[i - 1]区间的元素乘积，很容易得到 back[i] = back[i + 1]*nums[i + 1]数组为前缀乘积数组，front[i]
2025-05-02 20:25:03
671
原创 【多线程】六、基于阻塞队列的生产者消费者模型
举个例子，生产者就是工厂，消费者就是我们日常消费的人，一般来说，我们是不会直接去工厂买东西的，而是到超市去买，超市就相对于是一个缓冲区，我们每次买东西的时候都会去超市买，超市一般都会储备比较多的货，所以消费者一般不需要去关心是否有货的问题； 要知道，其实这种模型是串行的方式通过阻塞队列的，所以其实相对于生产者直接向消费者投递资源、消费者直接向生产者拿资源来说其实效率不是高的很明显，而关键提高效率的要点在于生产者投放资源是需要消耗时间的，这段时间对于其它的生产者来说是不影响的可以继续投放，提高了效率；
2025-05-02 20:21:58
1243
原创 【前缀和】寻找数组的中心下标
那我们可以这样子，先求前缀和区间的元素和，然后再求后缀和区间的元素和，通过比较，看看两个区间是否相等，如果相等的话说明当前位置就是一个分界！ 此外，还有一个细节，就是我们要处理一些初始化问题，因为这里我们需要从数组下标为 0 开始遍历，那么我们就得初始化 front[0] 对于求前缀和区间来说我们并不陌生，但是这里需要注意一些细节，因为和前面前缀和模板题不同的是，这里的前缀和 front[i]减去左区间元素和，再减去当前元素，那么不就得到了右区间也就是后缀和区间的元素了吗，对不对！
2025-05-01 15:19:47
883
原创 【数据结构与算法】位图 && 布隆过滤器 && 海量数据问题处理 && 哈希切分
所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空，如果空了，自己挪过去也就皆大欢喜了。 我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。作者提出了布谷鸟过滤器。 而至于时间问题，查找某个数字的时候，位图也是通过某个数字的对应映射关系查找的，也就是通过哈希！之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。
2025-05-01 15:17:42
1029
原创 【前缀和】二维前缀和（模板题）
给你一个n行m列的矩阵A，下标从1开始，接下来有q次查询，每次查询输入4个参数x1y1x2y2。 请输出以(x1, y1)为左上角，(x2,y2)为右下角的子矩阵的和。 第一行包含三个整数nmq。 接下来n行，每行m个整数，代表矩阵的元素 接下来q行，每行4个整数x1y1x2y2，分别代表这次查询的参数。 输出 q行，每行代表一次查询的结果。
2025-04-30 14:37:35
681
原创 【数据结构与算法】跳表实现详解
skiplist是一种随机化的数据结构基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)大多数情况下，因为是实现上是概率问题），因为其性能匹敌红黑树且实现较为简单，因此在很多著名项目都用 skiplist来代替红黑树，例如LevelDBRocksDBRedis中的有序集合zset的底层存储结构就是用的 skiplist。 目前常用的 key-value数据结构有三种：哈希表、红黑树、skiplist哈希表：插入、查找最快，为 O(1)；如使用链表实现则可实现无锁；
2025-04-30 14:34:51
1000
原创 【前缀和】一维前缀和（模板题）
暴力解法这里就不说了，比较简单，就是一个普通的枚举，但是这种暴力解法的问题就是时间复杂度比较高，我们需要每次去查询的时候，需要从头开始计算区间的和，这是非常耗时的！区间的元素和，而又因为这段区间其实重复元素是很多的，我们可以用一个数组来记录下这些会发生重复的元素，而不用我们每次都去重新计算元素和，其实就是。 我们先想哈，之所以暴力破解时间复杂度高，其实就是因为。处下标，所以这里我们可以开辟虚拟位置，实际位置从 1。，怎么样，其实很简单吧，就是一个动态规划问题！个整数，表示 a1、a2、……
2025-04-29 10:26:06
494
原创 【数据结构与算法】哈希表实现：闭散列 && 开散列
中，元素关键码与其存储位置之间没有对应的关系，因此在。O(N)，平衡树中为树的高度，即log2n，搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素**。：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
2025-04-29 10:22:57
876
原创 【双指针】四数之和
这个大概操作和三数之和是一样的！但是有一些细节问题，就是直接是三个数与 target比较，现在要变成四个数！ 除此之外，我们四个数相加，对于这道题的数据来说是会发生溢出的，所以我们在相加的时候需要将它们的类型转化为long long类型以上才行，而对于类型转化表达式，我们只需要对其中一个变量进行类型转化，其它的三个变量会根据不同类型进行隐式类型转化的，也就是一个类型是 long long，其它类型是 int的话，最后相加的结果还是 long long！这样子就不会溢出了！
2025-04-26 15:02:41
674
原创 【多线程】五、线程同步 && 条件变量
/ 用于实现对条件变量的互斥访问// 一个底层的系统调用，用于实现线程等待和唤醒，它是一个用户空间和内核空间之间的交互接口，用于实现线程的同步和通信// 记录条件变量被唤醒的次数，包括所有线程的唤醒次数// 记录条件变量被唤醒的次数// 最后一次被唤醒的时间戳// 与条件变量相关联的互斥锁的指针/地址// 记录当前等待的线程数// 记录最后一次broadcast的时间戳} __data;// 指定条件变量的大小// 指定该类型的对齐方式。
2025-04-26 15:00:36
778
原创 【双指针】三数之和详解
我们本来就是要三元组的，那么相等了之后，不就两个数重合了吗，那就变成二元组了，这就不符合题意了，所以正确的是 while(left < right)的三个数，并且使用的是双指针，两个指针在左右两边开始遍历，这样子的话我们其实排序完就会有天然的 “平分” 情况，因为除了为全。，当然要做去重操作，相对应会比较复杂，难控制，所以这里我们不采用哈希的方法！移动的时候，判断结束条件是 while(left < right)，那么肯定会有负数的存在，所以我们相当于左右指针被。**的操作，也是这道题的关键！
2025-04-25 11:24:44
795
原创 【多线程】四、死锁
这些资源可能是共享的，如内存、硬盘等，或者是独占的，如打印机、数据库等。银行家算法的思想是为了避免出现“环路等待”条件，它采用安全性检查的方式来避免系统进入不安全状态，从而保证资源的安全分配。该算法把执行流和资源分别表示为图的顶点，用有向边表示执行流对资源的请求以及资源的分配。如果一个进程在一定时间内无法获取所需的资源，就会自动放弃这个请求，并释放已经占用的资源，从而避免死锁的发生。 是的，但是一般在大工程中，两个重复加锁的代码之间可能隔着很多行代码，导致疏忽的加锁，这都是有可能的，这都是。
2025-04-25 11:20:16
991
原创 【双指针】和为s的两个数字
输入一个递增排序的数组和一个数字target，在数组中查找两个数，使得它们的和正好是target。如果有多对数字的和等于target，则输出任意一对即可。
2025-04-24 17:34:26
276
原创 【多线程】三、线程互斥 && 互斥量操作 && 守卫锁 && 重入与线程安全
定义互斥锁对象 其中 pthread_mutex_tstruct{int __lock;// 锁的状态值，用于表示锁是否被占用。// 锁的计数器，用于支持可重入锁。// 锁的拥有者线程ID。/* KIND必须保持在结构中的这个位置，以保持二进制兼容性 */int __kind;// 锁的类型，包括PTHREAD_MUTEX_NORMAL（普通锁）、PTHREAD_MUTEX_RECURSIVE（可重入锁）等。// 锁的使用者数，用于支持可重入锁。
2025-04-24 17:32:47
1358
原创 【双指针】有效三角形的个数
这样子就能保证，大的边一定在后边，那我们只需要判断前面两个数是否大于第三个数，如果大于的话，反之用这个第三个数去和前面某一个数组合肯定也是大于另一个数的！这样子的话，我们只需要判断一次，并且不需要全部数据都去枚举！但是因为这道题的数据是无序的，如果我们不用排序的话，可能会稍微麻烦一些，为什么呢，因为我们得判断三条边，两两组合是否都大于第三边才算是构成三角形，这不也和枚举差不多吗？ 和上一道题一样，如果使用暴力破解也就是枚举的话，此时会超时，所以我们就要换一种方式来解决！
2025-04-23 15:17:06
611
原创 【多线程】二、pthread库 && 线程控制 && 线程分离 && __thread关键字 && 线程库封装
应用程序应该使用 POSIX线程库提供的函数来操作 pthread_t类型的值，而不是直接访问或修改它的内部成员。因此，虽然 pthread_t类型在定义时被 typedef为无符号长整型，
2025-04-23 15:15:30
783
原创 【双指针】盛最多水的容器
分别指向容器的左右两个端点，此时容器的容积为：v = (right - left) * min( height[left], height[right])，因此可得容积公式 ：v = (right - left) * min( height[left], height[right])，分别指向水槽板的最左端以及最右端，此时容器的宽度为 right - left。 枚举出能构成的所有容器，找出其中容积最大的值！，容积肯定就比之前小了！，但是因为宽度变小了，所以容积还是变小了！的话，此时短板高度还是 4。
2025-04-22 09:16:20
464
原创 【多线程】一、线程的概念与特点
我们已经将页表的工作原理这个坑填上了，接下来就是学习真正的多线程部分，而这部分的知识可能会与我们之前学的进程有些出入，但是在进程部分的知识大部分还是成立的，只不过我们之前讲的那种进程是比较特殊的，也就是单执行流进程，而从现在开始，一个进程就不再是单执行流了，而是多个执行流，也就是多线程！线程是操作系统中能够独立运行的最小单元，它是在进程内部创建的执行流，与同一进程中的其他线程共享进程资源。与进程不同的是，线程没有独立的地址空间和系统资源，线程的创建、撤销和切换都由操作系统内核完成。
2025-04-22 09:13:20
920
原创 【双指针】快乐数，你快乐了吗？！！
我们前面说过，双指针还是快慢指针，它们都不一定是语言级别上的指针，更多意义上表示的是一个指向，根据题目来，因为每一次都要拿这个数的每个位置上的数求平方和，那么也就说明，一次平方和，其实就是下一个位置，那我们就。来解决了，大家肯定都做过一道链表的判断环题目，用的就是快慢指针，通过快慢指针在环中的不断循环，加上其步伐的快慢，最后两个指针判断是否相等，相等说明就是相遇了，就达到是否在环内的目的！ 所以我们只需要用快慢指针，最后肯定快指针先到环内循环，而慢指针则后到环内，在。根据题目给的数据范围，也就是。
2025-04-21 08:53:03
687
原创 【进程信号拓展】SIG_CHLD 信号处理
函数清理僵尸进程，父进程可以阻塞等待子进程结束，也可以非阻塞地查询是否有子进程结束等待清理（也就是轮询的方式）。采用第一种方式，父进程阻塞了就不能处理自己的工作了；采用第二种方式，父进程在处理自己的工作的同时还要记得时不时地轮询一 下，程序实现复杂。信号的处理函数，这样父进程只需专心处理自己的工作，不必关心子进程了，子进程终止时会通知父进程，父进程在信号处理函数中调用 wait。信号，该信号的默认处理动作是忽略，父进程可以自定义 SIGCHLD。 其实，子进程在终止时会给父进程发 SIGCHLD。
2025-04-21 08:50:23
482
原创 【双指针】复写零，你会用双指针处理吗！
这里的暴力破解，其实也是算双指针做法，但是因为我们没有很好的利用双指针的特性，就会变成暴力破解的方式，但是这是一种比较好想到的解法，虽说时间复杂度达到了。 其实上面这种解法之所以变成了暴力破解，其实是因为我们没办法做到一次性的去往后移动那些元素，如果遇到比较棘手的样例比如说全0，那么时间复杂度是非常高的！ 但是上面的思想，也就是从后往前复写是正确的，如果我们是从前往后复写的话，那么就会导致后面元素先被覆盖就不见了！，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
2025-04-20 08:34:53
851
原创 【进程信号拓展】可重入函数 && 不可重入函数 && volatile关键字详解
不是的，我们目前大部分使用的接口都是不可重入函数，特别是 STL 中的容器有各种涉及插入、删除等操作，它们都是不可重入函数， 这是一种特性，是中性词，而不是问题！ 所以它不需要我们去解决，我们只需要理解它们的特性即可！
2025-04-20 08:31:19
1152
原创 【双指针】对撞指针 && 快慢指针 && 移动零
算法中的双指针，并不一定是指我们平常在c/c++使用的指针类型，更多时候其实是数组的下标等，因为它们也是有标识某个元素的功能，通常我们也就顺其自然地称其为“指针”！ 常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。
2025-04-19 20:50:30
802
c/c++实现高并发内存池
2025-01-25
嵌入式软件服务器开发的毕业实习总结：温湿度监测系统的设计与实现
2025-01-25
（校内课程设计）c/c++实现停车场管理系统
2025-01-25
c++实现在线版五子棋（包含Websocket++、JsonCpp、Mysql、c++11、BlockQueue阻塞队列、HTML / CSS / JS / AJAX等技术栈的使用）
2025-01-25
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人