weixin_43688483的博客

原创 区间dp的总结

1、区间dp含义区间dp 常用dp[i][j] 来表示，含义是在区间[i,j]之间最大的…或是否可以成功。这里提供以下三个题来熟悉区间dp。2、经典区间dp问题，合并果子 现在设有n堆的果子，每堆果子根据果子数量的不同需要耗费不同的体力，现在想把这些果子有次序的合并为一堆，消耗的体力等于两堆果子的重量之和。现在求耗费的最小的体力数多少。比如 5 8 9 35+8=13 消费13体力 13 9 39+3=12 消费12体力 13 1213+12=25 消费25体力总体力消耗为 13

原创 基于自主web服务器的在线计算和huffman编码解码

1、项目背景 基于http协议的服务已经被广泛应用，做这个项目不仅可以复习所学的网络编程的知识，也可以加深对http协议的理解。2、项目目标 浏览器请求网页时服务器返回自己制作的网页，网页不存在返回404页面。可以实现在线的加减乘除运算和huffman的编码解码。3、项目分析  1、实现最基本的HTTP/1.0版本的web服务器，客户端能够使用GET、POST方法请求资源  2、服务器将客户请求的资源以html页面的形似呈现，并能够进行差错处理（如：客户请求的资源不存在时，服务器能够返回一个40

原创 windows下的文档搜索工具

1、项目背景 在windows下进行磁盘查找速度过慢（可以为文件建立索引来提高查找效率）。因此参考everything，借助于数据库，设计一个自己的文档搜索工具。2、everything原理 Everything并不扫描整个磁盘，只是读取磁盘上的USN日志，并建立索引，所以速度飞快。但因此缺点也明显： 1、只支持NTFS格式的分区，因为USN日志是NTFS专有的。在FAT、FAT32格式分区上无法使用Everything。 2、只索引文件名称、日期和大小，不索引文件内容和附加属性，而windo

原创 mysql中MVCC理解

1 事务隔离级别读未提交（脏读，不可重复读，幻读）读已提交（不可重复读，幻读）可重复读（幻读）–>但在mysql5.6版本之后，由于mysql的具有的间隙锁，解决了幻读问题串行化(安全级别高)，效率低，涉及加锁解锁操作。所以引入MVCC，不使用锁来实现大并发操作。2 MVCC MVCC即多版本并发控制，基本思想是在读已提交和可重复读这两个隔离级别下，为每次事务生成一个新版本的数据，随后在使用语句读数据时选择不同的版本的数据即可以实现对结果完整性的读取。可以提高并发的读写性能。 read

转载 多进程、多线程以及如何选择？

关于线程： 首先关于多线程多进程，看一张图： 基本上把线程，进程区别说清楚了提到线程，就不得不提线程同步的问题，我专门归纳了一篇文章： 线程同步常用方...

原创 Huffman树和Huffman的编码和解码,香农码和费诺码

文章目录1 、原理1.1 霍夫曼编码为什么huffman编码提高了效率？1.1 霍夫曼树2、代码(对26的英文字母编码)3、香农码和费诺码3.1香农码3.1费诺码1 、原理 Huffman编码是一种信源编码，而信源编码的含义是：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 Huffman编码是要实现前缀编码（任意一个码字都不是其他码字的前缀

原创 C/C++混合编程，extern“C“

文章目录1、C++使用C函数1、C++使用C函数//t2.h//注意这里不能加#include<stdio.h>，因为extern是C++的关键字#pragma onceextern "C" { int add(int, int); int sub(int, int);}//t3.c #include<stdio.h>int add(int a , int b){ return a + b;}int sub(int a, int b){ retu

原创 基数排序和希尔排序,堆排

文章目录1、基数排序2、希尔排序1、基数排序 基数排序是一种不进行比较的稳定的排序方法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。void radixsort(vector<int>& v, int n) //基数排序{ //找到最大的数，计算出分配次数 int maxv = *max_element(v.begin(), v.end()); int k = to_string(maxv).size(); //声明tmp数组，用于收集数据 vecto

原创 设计模式（结构型） -- 适配器模式，代理模式，装饰器模式

 定义：将一个类的接口转换为客户希望的另一个接口，使得原本由于接口不兼容而不能在一起工作的那些类可以一起工作。例如，我们使用for_each()来遍历数组class MyPrint {public: void operator()(int v1, int v2){ cout << v1 + v2 << endl; }};int main(){ vector<int> v; for (int i = 0; i < 10; i++) v.pu

原创 设计模式 简单工厂--工厂--抽象工厂

文章目录1、简单工厂2、工厂3 抽象工厂4 参考1、简单工厂 我们假设使用工厂生产苹果，香蕉，梨子，这里我们将苹果，香蕉，梨子都抽象为水果，然后使用一个静态的工厂函数去生产水果，代码很好理解，但不符合开闭原则。比如，当我们又需要生产西瓜的时候，需要修改工厂的源码，增加对if…else…的判断。#if 1#include<iostream>using namespace std;//简单工厂模式，不符合开闭原则，不算在23种设计模式中//抽象水果class AbstractFru

原创 设计模式(行为型)命令模式， 观察者模式

文章目录1、定义2、简单实现1、定义 观察者模式主要是是定义对象间的一种一对多（变化）的依赖关系，以便当一个对象(Subject)的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。 而我们设计程序有两个基本原则，开闭原则和依赖倒置原则，开闭原则是对源代码地更改时不建议的，而对原始程序进行模块添加是建议的（策略模式）。而依赖倒置原则是要求具体的类要依赖于抽象类，借助于抽象类地接口，实现具体的类或功能。 现在有大量的关于设计模式的书，讲的都挺不错，但基本上都是使用java语言的，是使用c++语言

原创 leetcode 200. 岛屿数量 dfs,bfs,unique find

文章目录dfsbfsunique find给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。 思路：这个图刚开始给我的感觉是和leetcode 547. 朋友圈的解法是一样的，直接将leetcode 547.的代码复制过来不对，检查原因是leetcode 547.是求图上的连通分量，比如如下数据：[[1,1,1], [1,1,0], [0,0

原创 leetcode 547. 朋友圈三种解法 dfs,bfs,union find

文章目录dfsbfsunique findunique find朴素写法unique find优化 班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N∗NN * NN∗N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j]=1M[i][j] = 1M[i][j]=1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出

原创 摩尔投票算法解决leetcode 169， 229

文章目录1、leetcode 1691.1其他方法1.2 摩尔投票2、leetcode 2292.1 其他方法2.2 摩尔投票1、leetcode 169给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1.1其他方法 思路：对于这个题，常见的方法时使用hashmap对数据每个元素进行统计，然后计算除每个元素的个数，最后进行提取就ok，这个方法需要二外的空间。 还有一种方法是直接对其

原创 在数组中找到重复次数出现最多的数，不使用额外空间

题目：在数组中找到重复次数出现最多的数? 至少两种方法. 其中一种空间复杂度要求O(1)1、第一种方法是使用map来对数组进行出现的元素的次数进行记录。 map<int,int> mp; mp[v[i]]++。要使用额外空间。2、第二种方法 我们考虑先对元素进行排序（使用快排，冒泡…都可以），然后使用count来记录现在的元素和下一个元素个数，在使用一个pair记录当前最大元素的值和个数，进行动态更新，有点像动态规划。pair<int, int> fun1(vector&

原创 判断二叉树是否对称 递归，非递归（bfs）

文章目录1、递归2、非递归请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。1、递归 我开始想的是产生一个镜像的树，然后递归的判断这两个数是否相等，但是这样很麻烦。题解是我们只需传进去两个一样的树，判断左子树是否等于右子树如果一个二叉树是对称的，则假设有两个这样的树，1树的左节点等于2树的右节点1树的右节点等于2树的左节点*class Solution {public: bool equal(TreeNode*pRoot,Tre

原创 leetcode 买卖股票的最佳时机3 4

文章目录123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV123. 买卖股票的最佳时机 III给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 思路：第一眼，就是要使用动态规划去做，我们可以设dp1表示第1次买入的最低价格dp1=min(dp1,prices[i])dp1表示第1次买入的最低价格 dp1=min(dp1,

转载 LaTex符号大全

原创 Leetcode 115. 不同的子序列

文章目录1.1 思路11.2 状态压缩2.1 思路22.2 状态压缩 给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）题目数据保证答案符合 32 位带符号整数范围。 思路1：对于这种给定两个字符串的问题，类似于编辑距离和求最大公共子串，都可以采用动态规划。我们都可以设dp[i][j]dp[i][

原创 不使用“+”,“-”,“×”,“÷”实现四则运算

文章目录1、加法2、减法3、乘法4、除法1、加法思路： & 按位与运算：相同位的两个数字都为1，则为1；若有一个不为1，则为0。两个数相与，并左移一位：相当于求得进位1&1=1 将1左移一位变成了10，相当于拿到了进位。 ^ 按位异或运算：相同位置不同则为1，相同则为0。相当于每一位相加，而不考虑进位。第一步 异或——无进位相加得result1 (a^b)第二步 与运算+左移一位——>求得进位result2 （a&b）<<1第三步 result =

原创 C++特殊类设计1 单例模式

文章目录1、饿汉2、饱汉 一个类只能创建一个对象，即单例模式，该模式可以保证系统中该类只有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。单例模式有两种实现模式：饱汉，饿汉1、饿汉 饿汉模式就是说不管你将来用不用，程序启动时就创建一个唯一的实例对象。 思路：简单来说，就是将类的构造函数，拷贝构造函数，赋值运算符重载私有，随后定义一个静态的类对象，再给出一个静态的类对象的获取方法。class Singleton{public: static Singleton* GetIns

原创 C++ 类型转换

文章目录1、static_cast2、const_cast3、reinterpret_cast4、dynamic_cast1、static_cast 静态转化static_cast 全部用于明确定义达到转换，包括编译器允许我们所做的不用强制类型转换的安全转换和不太安全但清楚定义的转换。简单来说等价与c语言的隐式转换。void main(){ int a = 10; double d = 12.34; a = static_cast<int>(d); //用于替换C中隐式转换 /

原创 C++多态 虚函数表 函数指针

C++多态虚函数表1、多态2、虚函数表2.1 单继承中的虚函数表2.2 函数指针和虚函数表2.3 多继承中的虚函数表2.4虚函数表的不安全性1、多态 多态是在不同继承关系的类对象，去调用同一函数，产生了不同的行为。简而言之就是用父类型别的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。那么在继承中要构成多态还有两个条件： 1、 必须通过基类的指针或者引用调用虚函数 2、 被调用的函数必须是虚函数，且派生类必须对基类的虚函数进行重写。例如以下代码：class Person {p

原创 同步互斥，同步异步，以及高级IO笔记1

文章目录1 同步互斥，同步异步2 高级IO笔记11 同步互斥，同步异步 这段时间学到高级IO，发现IO分为同步和异步，又想起之前学过的同步互斥，就想总结一下。 先说同步和异步，主要关注的是在网络通信背景下的消息通信机制。我们知道IO主要分为两个过程，等和拷贝，同步是在调用者在发起起一个调用后，在没有得到结果之前，该调用就不返回，动等待这个调用的结果。异步则是相反，调用在发出之后，这个调用就直接返回了，所以没有返回结果; 换句话说，当一个异步的过程调用发出后，调用者不会立刻得到结果; 而是在调用发出后，

原创 位图和布隆过滤器

文章目录1、位图1.1 位图模拟实现2、布隆过滤器2.1 模拟实现1、位图 位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。可以用来1. 快速查找某个数据是否在一个集合中 2. 排序 3. 求两个集合的交集、并集等 4. 操作系统中磁盘块标记。 其内在的数据结构其实就是连续的二进制的数组。0代表数组中该下标元素不存在，0代表存在。 在系统中，只要加入<bitset>头文件，就可以使用位图。#include<iostream&g

原创 C++ 仿函数和lambda表达式

文章目录1 、 仿函数lambda表达式1 、 仿函数仿函数的定义： 仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。template<typename T>struct comp{ bool operator()(T in1, T in2) cons

原创 C++ 11 线程库笔记 mutex锁 原子操作

文章目录1、线程函数1.1 线程传参1.2 ：如果是类成员函数作为线程参数时，必须将this作为线程函数参数。2、mutex锁3、原子操作1、线程函数 C++11的多线程必须包含< thread >头文件，同时，而且在原子操作中还引入了原子类的概念。 一些相关函数thread() 构造一个线程对象，没有关联任何线程函数，即没有启动任何线程。thread[] 构造一个线程数组，没有关联任何线程函数，即没有启动任何线程。thread(fn,args，…) 构造一个线程对象，并关联线程函

原创 c++ 智能指针笔记2 shared_ptr的循环引用和删除器 weak_ptr

文章目录1、shared_ptr1.1 shared_ptr模拟2、weak_ptr3、 循环引用4、 shared_ptr删除器1、shared_ptr shared_ptr和uinque_ptr的最大区别是，shared_ptr可以拷贝构造和赋值，而又为了避免多个智能指针管理一个普通指针，造成多起delete的问题，shared_ptr会维护一个引用计数，只有当这个计数等于0的时候才会真正的删除空间，其他的只是对引用计数的++和–。即 1、如果引用计数是0，就说明自己是最后一个使用该资源的对象

原创 c++ 智能指针笔记1 auto_ptr unique_ptr scoped_ptr

文章目录1、auto_ptr1.1、模拟实现，vc版本1.2、模拟实现，vs版本2、unique_ptr1、auto_ptr 智能指针形如其名，智能（可以自主删除在堆上开辟的空间），指针（可以和普通指针一样，可以由 * ， -> 操作）。在内部，其实就是一个对象。 auto_ptr时最早的智能指针，最早是c98中的vc版本，再到vs版本，在还有boost库里的各种智能指针。我们首先介绍他的基本用法，然后进行模拟。 我们要注意，从C ++ 11开始不推荐使用此类智能指针。推荐使用 unique

原创 三角形最小路径和 2种方法 动规

文章目录1、自顶向下2、从下到上 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。1、自顶向下对于给定的一组数据，[ [2], [3,4], [6,5,7], [4,1,8,3] ]， 我们用图形表示其转移流程右边是最终转移的结果，由此我们可以得到状态转移方程：    dp[i][j]=triangle[i][j]+min(dp[i−1][j],dp[

原创 C++ 异常 笔记

文章目录1、概念1、概念 异常是一种处理错误的方式，当一个函数发现自己无法处理的错误时就可以抛出异常，让函数的直接或间接的调用者处理这个错误。 throw: 当问题出现时，程序会抛出一个异常。这是通过使用 throw 关键字来完成的。 catch: 在您想要处理问题的地方，通过异常处理程序捕获异常.catch 关键字用于捕获异常，可以有多个catch进行捕获。 try: try 块中的代码标识将被激活的特定异常,它后面通常跟着一个或多个 catch 块。 先简单展示一个代码double D

原创 最长公共子序列和最长重复子数组动规

文章目录1 最长公共子序列2 最长重复子数组1 最长公共子序列 定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。 思路：动规

原创 C++ 右值引用

文章目录1、右值引用介绍1.1 move函数2、右值作用1、右值引用介绍 我们首先按确定什么是右值：C++ 中一个被广泛认同的说法，那就是可以取地址的、 有名字的就是左值，反之，不能取地址的、没有名字的就是右值C++11对右值进行了严格的区分：    C++语言中的纯右值，比如：a+b, 100   将亡值。比如：表达式的中间结果、函数按照值的方式进行返回。引用，常引用和右值引用的区别int main(){ int a = 10; int &b = a; //int &a

原创 leetcode 买卖股票问题 1 2

文章目录1、121. 买卖股票的最佳时机1.1 动规1.2 差分1、121. 买卖股票的最佳时机  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。1.1 动规 思路：状态转移方程dp[i]=max(dp[i−1],prices[i]−minprice[i]) dp[i]=max(dp[i-1],prices[i]-minprice[i])dp[

原创 数组的最大子序和 动态规划

文章目录1、动态规划2、动态规划优化1、动态规划  给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。思路：首先，给出状态转移方程：dp[i]=max(dp[i−1],dp[i−1]+nums[i])dp[i]=max(dp[i-1],dp[i-1]+nums[i]) dp[i]=max(dp[i−1],dp[i−1]+nums[i])dp[i]表示以num[i]结尾的最大子段和。其要么是num[i]num[i]num[i],要么是dp[i−1]

原创 Floyd弗洛伊德算法和解决 leetcode 743. 网络延迟时间

文章目录1 Floyd弗洛伊德算法2 leetcode 743. 网络延迟时间1 Floyd弗洛伊德算法 Floyd算法是求解图上多源最短路径问题的，意思是可以求出每一个顶点到其他顶点的最短路径，和我们之前讲的Bellman-ford算法原理其实是一样的，也是一种动态规划问题，状态转移方程是dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])dp[i][j]=min(dp[i][j],dp[i][

原创 Bellman-ford算法和解决 leetcode 743. 网络延迟时间

文章目录1、Bellman-ford算法原理2、leetcode 743. 网络延迟时间1、Bellman-ford算法原理  Bellman-ford算法是一种在图上求解单源最短路径算法，顾名思义，是由Bellman和ford创立。上图是Bellman，动态规划INT_MIN的创始人！！！！！！！！！！！！！具体地说：Bellman-ford算法是一种动态规划算法，而Dijkstra算法是一种贪心算法。Bellman算法的时间复杂度更高O(EN)O(EN)O(EN)，空间复杂度为O(N)O(N)

原创 位操作符的总结 Brian Kernighan算法

文章目录1 Brian Kernighan 算法2 判断一个数字n的比特位中1的个数2 leetcode231. 2的幂3 201. 数字范围按位与4 不创建临时变量，交换两个数字1 Brian Kernighan 算法  这个算法的意思是，对任何一个数 nnn，n&(n−1)n\&(n-1)n&(n−1)的结果是nnn的比特位最右端的1变为0的结果。例如，n=12,n−1=11,11&12=8n=12,n-1=11,11\&12=8n=12,n−1=11,11&

原创 剪绳子 /整数拆分 4种解法

文章目录1 递归2 带备忘录的递归3 动态规划4 贪心（数学方法） 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。思路：我们设f(n)f(n)f(n)是将n拆分后的所能得到的最大值，则f(n)=max(1∗f(n−1),2∗f(n−2),...)f(n)=max(1*f(n-1),2*f(n-2),...)f(n)=max(1∗f(n−1),2∗f(n−2),...),我们也可以画出他的递归树则我们设resresres为最大值，则res=ma

原创 单调队列解决滑动窗口最大值

文章目录1 单调队列2 leetcode239 滑动窗口最大值1 单调队列 单调队列，顾名思义，是维护一个单调递增的或单调递减的队列，比较容易地想到可以使用deque来维护这个单调队列，这是因为deque可以在头尾进行插入和删除。这里我们可以维护一个单调递减的队列。插入元素时，将队列中所有比它小的元素删除即可。这里我们只封装push，pop，getmax这三个方法，如下，就可以看出为什么是一个单调递减队列。数组元素是：[1,3,-1,-3,5,3,6,7]class MonotonicQueue