KOwzb-CSDN博客

原创 C++图解前缀树（字典树）

字典树原理：字典数将相同前缀的单词做为共用的前缀，如果找不到这个前缀，则在另外一个结点上插入这个单词。并且在这个单词结尾的结点加上1。class Trie{private: bool isEnd; Trie *next[26];public: Trie() { isEnd=false; memset(next,0,sizeof(next)); } void Insert(string word) {

2021-05-16 14:40:39 277

原创 LeetCode 1059. 从始点到终点的所有路径（回溯）

1. 题目给定有向图的边 edges，以及该图的始点 source 和目标终点 destination，确定从始点 source 出发的所有路径是否最终结束于目标终点 destination，即：从始点 source 到目标终点 destination 存在至少一条路径如果存在从始点 source 到没有出边的节点的路径，则该节点就是路径终点。从始点source到目标终点 destination 可能路径数是有限数字当从始点 source 出发的所有路径都可以到达目标终点 destination

2021-05-07 22:12:37 781 1

原创零拷贝（Zero Copy）

一、零拷贝简介零拷贝指的是，从一个存储区域到另一个存储区域的copy任务没有CPU参与。零拷贝通常用于网络文件传输，以减少CPU消耗和内存带宽占用，减少用户空间（用户可以操作的内存缓存区域）与CPU内核空间（CPU可以操作的内存缓存区域及寄存器）的拷贝过程，减少用户上下文（用户状态环境）与CPU内核上下文（CPU内核状态环境）间的切换，提高系统效率二、传统拷贝方式DMA控制器Direct Memory Access，直接内存存取。ALU算术逻辑运算器发生4次空间切换（1、4、5、7），发

2021-05-06 20:34:18 2435

原创谈谈QUIC协议原理

QUIC，又名HTTP3，是近年来诞生的非常厉害的传输协议，它利用UDP解决了当前基于TCP协议的HTTP的许多问题，提升了在弱网环境下的网络通信体验。让我们来一探究竟！ 1.1 什么是QUIC？QUIC(Quick UDP Internet Connection)是谷歌推出的一套基于UDP的传输协议，它实现了TCP + HTTPS + HTTP/2的功能，目的是保证可靠性的同时...

2021-05-06 20:17:17 983 1

转载计算机中的高速缓存

1. 什么是缓存 2. 缓存的定义 3. 计算机中的高速缓存 3.1 高速缓存相关名词 3.2 计算机中的高速缓存存储器模型 3.3 计算机中有哪些缓存 3.4 硬件读取高速缓存的过程 4. 直接映射高速缓存 4.1 组选择 4.2 行匹配 4.3 字选择 4.4 模拟直接映射缓存 4.5 直接映射高速缓存的缺陷 5. 两..

2021-04-27 20:36:25 3013

原创设计模式C++实现（7）——观察者模式

观察者模式：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。它还有两个别名，依赖(Dependents)，发布-订阅(Publish-Subsrcibe)。可以举个博客订阅的例子，当博主发表新文章的时候，即博主状态发生了改变，那些订阅的读者就会收到通知，然后进行相应的动作，比如去看文章，或者收藏起来。博主与读者之间存在种一对多的依赖关系。下面给出相应的UML图设计。可以看到博客类中有一个观察...

2021-04-22 11:32:35 107

原创 KMP算法

一、问题描述给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。二、朴素算法最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：这个算法简单，不多说，附上代码#include<stdio.h>int Index_1(char s[],int

2021-04-21 15:06:41 111

原创设计模式C++实现（5）——原型模式

DP书上的定义为：用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象。其中有一个词很重要，那就是拷贝。可以说，拷贝是原型模式的精髓所在。举个现实中的例子来介绍原型模式。找工作的时候，我们需要准备简历。假设没有打印设备，因此需手写简历，这些简历的内容都是一样的。这样有个缺陷，如果要修改简历中的某项，那么所有已写好的简历都要修改，工作量很大。随着科技的进步，出现了打印设备。我们只需手写一份，然后利用打印设备复印多份即可。如果要修改简历中的某项，那么修改原始的版本就可以了，然后再复印。原始的那份手..

2021-04-18 22:48:43 100

原创设计模式C++实现（6）——建造者模式

建造者模式的定义将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示（DP）。《大话设计模式》举了一个很好的例子——建造小人，一共需建造6个部分，头部、身体、左右手、左右脚。与工厂模式不同，建造者模式是在导向者的控制下一步一步构造产品的。建造小人就是在控制下一步步构造出来的。创建者模式可以能更精细的控制构建过程，从而能更精细的控制所得产品的内部结构。下面给出建造者模式的UML图，以建造小人为实例对于客户来说，只需知道导向者就可以了，通过导向者，客户就能构造复杂...

2021-04-18 21:57:36 104

原创设计模式C++实现（4）——桥接模式

书上定义：将抽象部分与它的实现部分分离，使它们都可以独立地变化。考虑装操作系统，有多种配置的计算机，同样也有多款操作系统。如何运用桥接模式呢？可以将操作系统和计算机分别抽象出来，让它们各自发展，减少它们的耦合度。当然了，两者之间有标准的接口。这样设计，不论是对于计算机，还是操作系统都是非常有利的。下面给出这种设计的UML图，其实就是桥接模式的UML图代码如下：#include <iostream>using namespace std;class OS{publi.

2021-04-15 21:11:07 117

原创设计模式C++实现（3）——装饰模式

装饰模式：动态地给一个对象添加一些额外的职责。就增加功能来说，装饰模式相比生成子类更为灵活。有时我们希望给某个对象而不是整个类添加一些功能。比如有一个手机，允许你为手机添加特性，比如增加挂件、屏幕贴膜等。一种灵活的设计方式是，将手机嵌入到另一对象中，由这个对象完成特性的添加，我们称这个嵌入的对象为装饰。这个装饰与它所装饰的组件接口一致，因此它对使用该组件的客户透明。下面给出装饰模式的UML图。代码如下：#include <iostream>#include<string.

2021-04-15 20:31:11 132

原创 C++11新特性学习

什么是C+11C++11标准为C++编程语言的第三个官方标准，正式名叫ISO/IEC 14882:2011 - Information technology -- Programming languages -- C++。在正式标准发布前，原名C++0x。它将取代C++标准第二版ISO/IEC 14882:2003 - Programming languages -- C++成为C++语言新标准。C++11是对目前C++语言的扩展和修正， C++11不仅包含核心语言的新机能，而且扩展了C++的标准程

2021-04-15 19:19:28 334

原创二叉树的线索化

一、线索二叉树的引入二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。二、线索二叉树的构造线索二叉树的节点结构：线索二叉树的节点定义：enum PointTag{ LINK,//子树 THREAD,//线索};templat...

2021-04-11 14:16:13 510

原创 Linux下的进程概论与编程二（进程控制）

一、进程标识符1、每个进程都有非负的整形表示唯一的进程ID。几个典型进程的ID及其功能：2、除了进程ID，每个进程还有一些其他的标识符。下列函数返回这些标识符：#include <sys/types.h>#include <unistd.h>pid_t getpid(void); //返回值:调用进程的进程IDpid_t getppid(void); //返回值：调用进程的父进程IDuid_t getuid(void); //返回值：调用进程的实际用

2021-04-10 15:46:41 127

原创五种IO模型及设计模式

下面就分别来介绍一下这5种IO模型的异同。1.阻塞IO模型最传统的一种IO模型，即在读写数据过程中会发生阻塞现象。　　当用户线程发出IO请求之后，内核会去查看数据是否就绪，如果没有就绪就会等待数据就绪，而用户线程就会处于阻塞状态，用户线程交出CPU。当数据就绪之后，内核会将数据拷贝到用户线程，并返回结果给用户线程，用户线程才解除block状态。典型的阻塞IO模型的例子为：data = socket.read();如果数据没有就绪，就会一直阻塞在read方法。2.非阻塞IO模型

2021-04-09 20:56:23 982

原创搜索二叉树

二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树有个特点，最左的是最小的节点，最右的是最大的节点。当我们把二叉搜索树进行中序遍历的时候，它是进行排序后的结果，所以我们也把二叉搜索树叫做排序二叉树。接下来我们介绍二叉排序树的所有的算法：1.1搜索二叉树的结构首先我们来看它的结构，他的结构和二叉树类似，所以会有一

2021-04-08 12:41:34 464

原创浅析AVL树

1.为什么提出AVL树学习完搜索二叉树以后，我们应该想到一个问题，如果我们的搜索二叉树的趋向于单链的形式，类似于：2.二叉平衡树概念和结构为了解决上述问题，所以提出了一个概念，叫做二叉平衡树。二叉平衡树，相对于二叉搜索树，引入了一个叫做平衡因子的概念。平衡因子：平衡因子就是右子树的深度-左子树的深度。二叉平衡树的规则是：每一个节点的平衡因子的绝对值都要小于2。所以我们需要给一个平衡因子。二叉平衡树的结构：template<typename K,typena.

2021-04-08 10:55:55 179

原创机器学习实战教程（四）：朴素贝叶斯基础篇之言论过滤器

一、前言朴素贝叶斯算法是有监督的学习算法，解决的是分类问题，如客户是否流失、是否值得投资、信用等级评定等多分类问题。该算法的优点在于简单易懂、学习效率高、在某些领域的分类问题中能够与决策树、神经网络相媲美。但由于该算法以自变量之间的独立（条件特征独立）性和连续变量的正态性假设为前提，就会导致算法精度在某种程度上受影响。本篇文章将从朴素贝叶斯推断原理开始讲起，通过实例进行辅助讲解。最后，使用Python3编程实现一个简单的言论过滤器。二、朴素贝叶斯理论...

2021-04-07 17:07:38 537

原创 C++之类型萃取技巧

使用类型萃取的原因就是当你的顺序表是自定义类型，我们进行顺序表增容的时候，这个时候会出现一个问题，比如string类型，这个类型中有一个_buf与_ptr,当储存少于16个的时候这时会储存在_buf当中的，如果多于16个，那个会单独开辟空间，进行储存,这时拷贝的时候就是拷贝过去这个储存的地址而已，所以这样调用析构函数的时候，当增加容量的时候，这个时候会把储存string的那块空间进行释放。会造成数据丢失的问题。所以，在这里面我们提到一个类型萃取的技巧，可以把自定义类型和内置类型的区分开...

2021-04-06 23:05:01 201

原创 C++模板的那丢丢事儿

一、模板的引入首先，请你认真思考一个问题，如何编写一个通用的加法函数呢？1.对于我来说，首先第一反应是写一个宏函数来实现此功能，如：#define ADD(x,y) ((x) + (y))那么，这样写的缺点是什么呢？（1）它没有参数检测，这个原因致使它能够完成该要求，同时也造就了它致命的缺陷，不能进行参数检测，故安全性不高。（2）它不能像函数一样进行调试，而仅仅是在编译期间进行简单的参数替换，况且如果代码过长，会大幅增加代码量。（3）宏函数可能会有副作用，在不该替换的时候进行替换

2021-04-06 22:57:57 186

原创 map，multimap，unordered_map，unordered_multimap的详解

1，map简介map是STL的一个关联容器，它提供一对一的hash。第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)；map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的，后边我们会见识到有序的好处。比如一个班级中，每个学生的学号跟他的姓名就存在著一对一

2021-04-06 21:33:23 811

原创 LRU原理及其实现（C++）

LRU原理在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。但是如果让我们自己设计一个基于 LRU 的缓存，这样设计可能问题很多，这段内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的，我们需要把访问次序

2021-04-06 19:45:08 284

原创遗传算法

1、遗传算法理论的由来我们先从查尔斯·达尔文的一句名言开始：能够生存下来的往往不是最强大的物种，也不是最聪明的物种，而是最能适应环境的物种。你也许在想：这句话和遗传算法有什么关系？其实遗传算法的整个概念就基于这句话。让我们用一个基本例子来解释：我们先假设一个情景，现在你是一国之王，为了让你的国家免于灾祸，你实施了一套法案：你选出所有的好人，要求其通过生育来扩大国民数量。这个过程持续进行了几代。你将发现，你已经有了一整群的好人。这个例子虽然不太可能，但是我用它是想帮..

2021-03-29 22:05:06 1341

原创设计模式C++实现（2）——策略模式

软件领域中的设计模式为开发人员提供了一种使用专家设计经验的有效途径。设计模式中运用了面向对象编程语言的重要特性：封装、继承、多态，真正领悟设计模式的精髓是可能一个漫长的过程，需要大量实践经验的积累。最近看设计模式的书，对于每个模式，用C++写了个小例子，加深一下理解。主要参考《大话设计模式》和《设计模式:可复用面向对象软件的基础》两本书。本文介绍策略模式的实现。策略模式是指定义一系列的算法，把它们一个个封装起来，并且使它们可相互替换。本模式使得算法可独立于使用它的客户而变化。也就是说这些算...

2021-03-26 11:51:05 70

原创设计模式C++实现（1）——工厂模式

引出工厂模式的设计问题◆ 1.为了提高内聚（Cohesion）和松耦合（Coupling），我们经常会抽象出一些类的公共接口以形成抽象基类或者接口。这样我们可以通过声明一个指向基类的指针来指向实际的子类实现，达到了多态的目的。这里很容易出现的一个问题 n 多的子类继承自抽象基类，我们不得不在每次要用到子类的地方就编写诸如 new ×××;的代码。这里带来两个问题：客户程序员必须知道实际子类的名称（当系统复杂后，命名将是一个很不好处理的问题，为了处理可能的名字冲突，有的命名可能并不是具有很好的可读性和可记

2021-03-25 11:22:43 98

空空如也

空空如也