- 博客(217)
- 收藏
- 关注
RSS订阅原创 五种IO模型：同步阻塞I/O、同步非阻塞I/O、同步I/O复用模型、同步信号驱动I/O、异步I/O模型
阻塞、非阻塞、多路IO复用，都是同步IO，异步必定是非阻塞的，所以不存在异步阻塞和异步非阻塞的说法。换句话说，只有用户线程在操作IO的时候根本不去考虑IO的执行，全部都交给CPU去完成，而自己只等待一个完成信号的时候，才是真正的异步IO。异步过程中进程触发IO操作以后，直接返回，做自己的事情，IO交给内核来处理，完成后内核通知进程IO完成。同步：执行一个操作之后，进程触发IO操作并等待(也就是我们说的阻塞)或者轮询的去查看IO操作(也就是我们说的非阻塞)是否完成，等待结果，然后才继续执行后续的操作。
2023-03-18 22:01:10
850
1
原创 LeetCode 【数据结构与算法专栏】【链表】
刷题笔记链表leetcode专栏leetcode 203 移除链表元素leetcode 707 设计链表leetcode 206 翻转链表leetcode 24 两两交换链表中的节点leetcode 19 删除链表的倒数第 N 个结点leetcode 160 链表相交leetcode 142 环形链表 IIleetcode 328 奇偶链表leetcode 234 回文链表leetcode 21 合并两个有序链表leetcode 2 两数相加leetcode 430 扁平化多级双向链表leetcode 13
2022-12-31 23:42:02
804
1
原创 LeetCode 【数据结构与算法专栏】【数组】
刷题笔记数组leetcode专栏leetcode 704 二分查找leetcode 27 移除元素leetcode 26 删除有序数组中的重复项leetcode 80 删除有序数组中的重复项 IIleetcode 283 移动零leetcode 75 颜色分类leetcode 215 数组中的第K个最大元素leetcode 167 两数之和 IIleetcode 11 盛最多水的容器leetcode 125 验证回文串leetcode 345 反转字符串中的元音字母leetcode 844 比较含退格的字符
2022-12-31 23:32:03
755
原创 C++面向对象特性——多态
多态性（ polymorphism ）是面向对象设计语言的基本特征之一。仅仅是将数据和函数捆绑在一起，进行类的封装，使用一些简单的继承，还不能算是真正应用了面向对象的设计思想。多态性是面向对象的精髓。多态性可以简单地概括为“一个接口，多种方法”。通常是指对于同一个消息、同一种调用，在不同的场合，不同的情况下，执行不同的行为。虚函数就是在基类中被声明为virtual，并在一个或多个派生类中被重新定义的成员函数。// 类内部 class 类名 {virtual 返回类型 函数名(参数表) {
2022-12-27 13:29:13
677
原创 LeetCode 【算法专栏】 【图】
图相关算法有关BFS和DFS求有权图的单源最短路径算法(Dijkstra算法)求有权图的多源最短路径算法(Floyd算法)Prim算法leetcode 1584 连接所有点的最小费用(prim+priority_queue)Kruskal算法实现思想（并查集）leetcode 1584 连接所有点的最小费用(Kruskal UnionFind)拓扑排序Topologicalsortleetcode 133 克隆图(DFS + DeepCopy + ShadowCopy)leetcode 547 省份数量(
2022-11-16 23:18:39
281
1
原创 【数据结构】B树（B-树）和B+树
分裂的方法：取一个新结点，在插入key后的原结点，从中间位置（⌈m/2⌉）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新结点中，中间位置（⌈m/2⌉）的结点插入原结点的父结点。若被删除关键字所在结点删除前的关键字个数 = ⌈m/2⌉-1，且与此结点相邻的右（或左）兄弟结点的关键字个数 >= ⌈m/2⌉，则需要调整该结点、右（或左）兄弟结点、及其双亲结点（父子换位法），以达到新的平衡。B树，又称为多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。
2022-08-23 16:19:41
3733
1
原创 leetcode 394 字符串解码 【栈】
编码规则为k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数k，例如不会出现像3a或2[4]的输入。输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。输入s=“2[abc]3[cd]ef”s中所有整数的取值范围为[1,300]输入s=“abc3[cd]xyz”输入s=“3[a]2[bc]”输入s=“3[a2[c]]”...
2022-07-19 22:16:37
91
原创 leetcode 241 为运算表达式设计优先级【递归，回溯】
给你一个由数字和运算符组成的字符串expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。生成的测试用例满足其对应输出值符合32位整数范围，不同结果的数量不超过104。输入expression=“2-1-1”...
2022-07-19 21:20:44
135
原创 leetcode50 Pow(x, n) 递归题目
实现pow(x,n)，即计算x的整数n次幂函数。解释2^-2=1/2^2=1/4=0.25。时间复杂度O(n)的代码超时，有测试用例跑不过。输入x=2.00000,n=10。输入x=2.00000,n=-2。时间复杂度O(logn)的代码。输出1024.00000。输出0.25000。...
2022-07-18 09:05:05
113
原创 剑指 Offer 33. 二叉搜索树的后序遍历序列
题目输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。输入[1,6,3,2,5]输入[1,3,2,6,5]
2022-07-17 22:59:59
147
原创 Catch That Cow POJ 3278 (BFS问题)
问题链接http://poj.org/problem?id=3278摘自王道笔试指南#include <iostream>#include <string>#include <vector>#include <queue>using namespace std;const int MAXN = 100001;vector<bool> inq(MAXN, false);struct Status{ int loc; i
2022-02-19 21:45:57
445
原创 PAT 1076 Forwards on Weibo
https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736#include <iostream>#include <vector>#include <queue>using namespace std;const int MAXN = 1010;struct Node { int v; int layer; Node(int _v, in
2022-02-17 17:59:07
458
原创 0-1背包问题—— 动态规划，二维dp和一维dp
刷题笔记0-1背包问题动态规划0-1背包问题动态规划有关于动态规划可以解决0-1背包问题的证明，即证明原问题的最优解包含子问题的最优解，可以采用反证法来证明。（教材上有）dp数组的定义以及含义：首先采用二维dp，我们需要同时考虑value和weight两个变量。dp[i][j] 表示从下标为[1-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。（为了回溯结果方便，物品下标编号从1到n）dp状态转移公式：对于第i个物品，决策只有两种，一种是第i个物品放入背包x[i] = 1，这时dp[i
2022-01-14 12:54:40
1232
原创 0-1背包问题——暴力搜索、回溯法和剪枝限界
刷题笔记动态规划0-1背包问题回溯法和剪枝限界动态规划0-1背包问题回溯法和剪枝限界运用回溯法解题通常包含以下三个步骤：1、针对所给问题，定义问题的解空间；2、确定易于搜索的解空间树；3、以深度优先的方式搜索解空间树，并在搜索过程中用剪枝函数避免无效搜索0-1背包问题，对于每一个物品只有两种决策，一种是该物品装入背包，x[i] = 1，另一种是该物品不装入背包，x[i] = 0。所以对于物品编号1-n所形成的解空间树的高度是n+1(包含叶子节点)。叶子节点最下面一层节点的数量是2^n，表示该问
2022-01-14 11:23:41
1342
原创 LeetCode 【数据结构与算法专栏】【贪心】
刷题笔记贪心算法leetcode专栏leetcode 455 分法饼干leetcode 376 摆动序列leetcode 53 最大子数组和leetcode 122 买卖股票的最佳时机 IIleetcode 55 跳跃游戏leetcode 45 跳跃游戏 IIleetcode 1005 K次取反后最大化的数组和leetcode 134 加油站leetcode 135 分发糖果leetcode 860 柠檬水找零leetcode 406 根据身高重建队列leetcode 452 用最少数量的箭引爆气球leet
2022-01-11 11:23:41
185
原创 leetcode 哈希表相关算法刷题笔记
刷题笔记hash table 算法leetcode专栏leetcode 242 有效的字母异位词leetcode 383 赎金信leetcode 49 字母异位词分组leetcode 138 复制带随机指针的链表leetcode 1002 查找共用字符leetcode 349 两个数组的交集leetcode 350 两个数组的交集IIleetcode 202 快乐数leetcode 1 两数之和leetcode 15 三数之和leetcode 18 四数之和leetcode 454 四数相加IIhash
2022-01-06 19:26:35
436
原创 LeetCode 【数据结构与算法专栏】【二叉树】
刷题笔记二叉树算法leetcode专栏leetcode 94 二叉树的中序遍历leetcode 144 二叉树的前序遍历leetcode 145 二叉树的后序遍历leetcode 102 二叉树的层序遍历leetcode 107 二叉树的层序遍历IIleetcode 119 二叉树的右视图leetcode 637 二叉树的层平均值leetcode 429 N叉树的层序遍历leetcode 515 在每个树行中找到最大值leetcode 116 填充每个节点的下一个右侧节点指针leetcode 117 填充每
2022-01-05 17:19:27
448
1
原创 LeetCode 【数据结构与算法专栏】【回溯算法】
leetcode 77 组合给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。示例 1：输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3],[1,4], ]示例 2：输入：n = 1, k = 1 输出：[[1]]提示：1 <= n <= 201 <= k <= n来源：力扣（LeetCode）链接：https:/
2022-01-03 23:17:28
712
原创 剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例 1：输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3方法一：将数组进行排序，需要O(nlogn)的时间，然后再用两个指针扫描一遍数组即可。这里排序的时候，刚开始直接用的sort函数，之后尝试自己写了一个简单的快排逻辑。int Partition(vector<
2021-07-25 02:10:38
105
原创 操作系统——存储器管理习题和笔记
摘自：计算机操作系统第四版什么是对换技术？对换，指的是把内存中暂时不能运行的进程或者暂时不用的数据和程序换出到外存上，以便腾出足够的内存空间，再把已具有运行条件的进程或进程所需要的程序和数据换入内存。为什么要引入对换？对换可分为哪几种类型？一方面，在内存中的某些进程由于事件尚未发生而被阻塞运行，但它却占用大量的内存空间，甚至有时出现内存中的所有进程都被阻塞，而无可运行之进程。迫使CPU停下来等待的情况。另一方面，又有着许多作业，因为内存的空间不足，一直驻留在外存上，而不能进入内存运行，这显然是对系
2021-02-16 00:58:47
1005
原创 进程同步与互斥——相关问题汇总（源码+伪代码）
问题描述：某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：cobegin参观者进程i:{ //进门 //参观 //出门}coend请添加必要的信号量和P、V（或wait()、signal()）操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。问题分析：//错误的解法，该题中提到了只有一个出入口，就是只有一个门，可以是出，也可以入，每次只能一个人过semaphore out = 1;semaph
2021-02-15 18:25:01
7619
1
原创 进程同步与互斥——吸烟者问题源码实现（cigarette smoker’s problem）
问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟， 抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复(让三个抽烟者轮流地抽烟)。问题分析:1)关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上
2021-02-13 17:21:11
1836
原创 进程同步与互斥——哲学家就餐问题源码实现（dining philosopher’s problem）
哲学家就餐问题哲学家就餐问题（dining philosopher’s problem）是一个著名的并发问题，它由Dijkstra提出来并解决。这个问题之所以出名，是因为它很有趣，引人入胜，但其实用性却不强。可是，它的名气让我们在这里必须讲。实际上，你可能会在面试中遇到这一问题，假如老师没有提过，导致你们没有通过面试，你们会责怪操作系统老师的。因此，我们这里会讨论这一问题。假如你们因为这个问题得到工作，可以向操作系统老师发感谢信，或者发一些股票期权。这个问题的基本情况是：假定有5位“哲学家”围着一个
2021-02-13 16:19:33
2520
原创 进程同步与互斥——读者/写者问题源码实现（reader-writer lock）
摘自：操作系统导论读者——写者锁另一个经典问题源于对更加灵活的锁定原语的渴望，它承认不同的数据结构访问可能需要不同类型的锁。例如，一个并发链表有很多插入和查找操作。插入操作会修改链表的状态（因此传统的临界区有用），而查找操作只是读取该结构，只要没有进行插入操作，我们可以并发的执行多个查找操作。读者—写者锁（reader-writer lock）就是用来完成这种操的。typedef struct _rwlock_t { sem_t lock; // binary semaph
2021-02-13 15:41:01
1826
原创 进程同步与互斥——生产者/消费者（有界缓冲区）问题源码实现
摘自：操作系统导论第一次尝试第一次尝试解决该问题时，我们用两个信号量empty和full分别表示缓存区空或者满。put()和get()函数，下面是我们尝试解决生产者/消费者问题的代码。int sem_wait(sem_t* s) //请求一个单位的资源{ decrement the value of semaphore s by one wait if value of semaphore s is negative}int sem_post(sem_t* s) //释放一个单位
2021-02-13 15:05:30
3573
1
原创 进程同步与互斥——信号量（实现锁、条件变量）
摘自：操作系统导论我们现在知道，需要锁和条件变量来解决各种相关的、有趣的并发问题。多年前，首先认识到这一点的人之中，有一个就是Edsger Dijkstra。他出名是因为图论中著名的“最短路径”算法，因为早期关于结构化编程的论战“Goto语句是有害的”，还因为他引入了名为信号量的同步原语，正是这里我们要学习的。事实上，Dijkstra及其同事发明了信号量，作为与同步有关的所有工作的唯一原语。你会看到，可以使用信号量作为锁和条件变量。信号量的定义信号量是有一个整数值的对象，可以用两个函数来操作它。在PO
2021-02-13 15:01:06
2133
原创 进程同步与互斥——理发师问题源码实现（sleeping barber problem）
理发师问题描述：（1）理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子（2）如果没有顾客，理发师便在理发椅上睡觉（3）一个顾客到来时，它必须叫醒理发师（4）如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开问题分析：1、对于理发师问题而言，是生产者-消费者（有界缓冲区）模型的一种。其中理发师和顾客之间涉及到进程之间的同步问题，理发师是生产者，顾客是消费者，生产者生产的速度（理发师理发的速度），和消费者消费的速度（顾客来到理发店的时间），这两者肯定是不同的
2021-02-13 12:27:42
9507
11
原创 设置线程锁属性，用mutex实现两个进程对同一数据进行处理
Q1：通过设置线程锁属性，用mutex实现两个进程各加2千万，最终实现4千万。#ifndef __HEAD_H__#define __HEAD_H__#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/stat.h>#include <unistd.h>#include <sys/types.h>#include <diren
2021-02-07 23:31:36
290
原创 《算法第四版》：第一章 Union-Find 算法
union-find算法动态连通型性：问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数pq可以被理解为“p和q是相连的”。我们假设相连是一种对等关系，则它具有：自反性对称性传递性对等关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤序列中所有无意义的整数对（两个整数均来自同一个等价类中）。换句话说，当程序从输入中读取了整数对p q时，如果已知的所有整数对都不能说明p和q是相连的，那么将这一对整数写入到输出中
2021-01-08 00:39:11
200
原创 The abstract data type about graph
timestamp : 2020.12.31 status: unfinished#include <iostream>#include <fstream>#include <sstream>#include <vector>#include <map>using namespace std;typedef int vertextype;typedef int weight;typedef int index;struct
2020-12-31 00:04:37
104
原创 未排序数组中累加和为给定值的最长子数组系列问题
摘自：程序员代码面试指南给定一个无序数组arr，其中元素可正、可负、可0。给定一个整数K，求arr所有的子数组中累加和为K的最长数组长度。解答：s(i)代表子数组arr[0…i]所有元素的累加和，那么子数组arr[j…i]（0 <= j <= i < arr.length）的累加和为s(i) - s(j-1)。原问题解法只遍历一次arr，具体过程为：1、设置变量sum = 0，表示从0位置开始一直加到i位置所有元素的和。设置变量len = 0，表示累加和为K的最长子数组长度。设置
2020-12-14 22:08:23
276
原创 leetcode 111 二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。参考二叉树的最大深度，传送门：https://blog.csdn.net/CLZHIT/article/details/111118994参考来自微信公众号代码随想录的文章：二叉树的最小深度解法一：递归解法求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。class Solution {public: int minDepth(T
2020-12-13 21:51:42
145
原创 剑指offer34 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。此题的解法和思路和leetcode 113 路径之和是相同的：移步：https://blog.csdn.net/CLZHIT/article/details/103935351/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left
2020-12-13 20:50:27
99
原创 leetcode 145 二叉树的后续遍历
给定一个二叉树，返回它的 后序 遍历。解法二：非递归形式采用两个栈实现后续遍历的过程，具体流程如下：1、申请一个栈，记为sck1，将头节点压入栈sck1中。2、从sck1中弹出的节点记为tmpNode，然后依次将tmpNode的左孩子和右孩子节点压入sck1中。3、在整个过程中，每次从sck1中pop出的节点都放入sck2中。4、不断重复步骤2和步骤3，直到sck1为空，过程停止。5、从sck2中依次弹出节点并存储，其结果就是后续遍历的结果。class Solution {public:
2020-12-13 19:25:41
77
原创 leetcode 92 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。解法一：递归实现，省略解法二：非递归实现1、申请一个新的栈stack，初始化时，令遍历tmpNode = root。2、先把tmpNode节点压入栈中，再对以tmpNode节点为头结点的整颗子树来说，依次把左边界压入栈中，即不停地令tmpNode = tmpNode->left，然后重复步骤2。3、不断重复步骤2，发现tmpNode为空，此时从stack中弹出一个节点，记为node，收集node的值，并让tmpNode = tmpNo
2020-12-13 18:35:03
138
原创 leetcode 559 N叉树的最大深度
给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree实例一：输入：root = [1,null,3,2,4,null,5,6]输出：3实例二：输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10
2020-12-13 17:58:32
86
原创 leetcode 217 存在重复元素
给定一个整数数组，判断是否存在重复元素。如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。示例 1:输入: [1,2,3,1]输出: true示例 2:输入: [1,2,3,4]输出: false示例 3:输入: [1,1,1,3,3,4,3,2,4,2]输出: true链接：https://leetcode-cn.com/problems/contains-duplicate解法一：class Solution {publ
2020-12-13 16:04:30
102
原创 leetcode 104 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/解法一：采用递归实现：1、递归函数的参数和返回值：参数就是传入树的根节点，返回值为这颗树的深度。2、终止条件，如果遇到NULL节点，则返回03、单层递归逻辑，对于根节点，先求左子树的深度，再求右子树的深度，最后取左右子树深度的最大数值加1，就是整
2020-12-13 15:33:44
96
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人