- 博客(45)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 两种洗牌算法
两种洗牌算法#pragma once#include<vector>class Shuffle {public: //某一个元素放在第i个位置上的概率为： //(n-1)/n * (n-2)/(n-1) *...* (i+1)/(i+2) * 1/(i+1) //=1/n void shuffle1(std::vector<int>&nums) { for (int i = nums.size() - 1; i >= 0; --i) { std
2020-09-28 10:56:44
307
原创 模板为什么必须定义在头文件
这是由C++编译器的性质决定的。C++采用了分离式编译的方法，.h头文件仅仅是在预处理阶段进行展开的，真正进行的是对.cpp文件的编译。编译器在编译时，看到模板并不会进行任何操作，而是在模板实际使用时（实例化），才会进行代码生成。如果模板定义放在.h头文件中，模板实现放在.cpp文件中，编译时可以看到模板的声明，但找不到定义，因此会成为外部符号，而在链接时，必然无法找到模板的实现（该外部符号的对应符号），导致链接失败。而如果模板定义在.h头文件中，则可以在编译时就找到模板的定义，进行代码生成。...
2020-09-24 20:04:23
2295
4
原创 最大回文子串(中心点扩展与Manacher算法)
最大回文子串问题描述中心点扩展算法思想源码Manacher算法思想源码问题描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: “babad”输出: “bab”注意: “aba” 也是一个有效答案。示例 2：输入: “cbbd”输出: “bb”题目来源：5. 最长回文子串 - 力扣（LeetCode）中心点扩展算法思想选择一个中心点，向两边扩展，直至不符合回文串要求；时间复杂度：O(n2)；空间复杂度：O(1)；源码
2020-08-29 20:58:01
299
原创 排序算法——冒泡排序
描述基本思想：循环地利用比较交换的操作，将第i大的元素归位；平均时间复杂度：O(n2)，最好时间复杂度：O(n)，最坏时间复杂度：O(n2)；空间复杂度：O(1)源码//冒泡排序void BubbleSort(vector<int>& nums) { for (int i = nums.size()-1; i >= 0;--i) { bool flag = true; for (int j = 0; j < i; ++j) { if (nums
2020-08-28 20:00:35
119
原创 排序算法——归并排序（递归与非递归）
描述基本思想：将已有序的子序列合并，得到完全有序的序列；一种常见的方法是将数据等分为二份，分别进行递归排序，之后对这两组有序的数据再进行一次排序即可；基于递归的归并排序比较简单，只需要自上而下进行排序即可；而非递归版本的归并排序则需要自下而上进行排序；时间复杂度：O(nlogn)，空间复杂度：O(n)；归并排序为稳定排序算法；此外，归并排序可用于求解逆序对；源码#pragma once#include<vector>#include<algorithm>cl
2020-08-28 19:57:10
1254
原创 二叉树遍历的三种实现方式
二叉树遍历的三种实现方式中序遍历基于递归实现非递归实现之stack非递归实现之线索树先序遍历基于递归实现非递归实现之stack非递归实现之线索树后序遍历基于递归实现非递归实现之stack非递归实现之线索树中序遍历基于递归实现 //递归版本中序遍历（左 中 右） void inorderTraversal1(TreeNode* tree,std::vector<int>& vec) { if (tree == NULL) return; inorderTraversal1(
2020-08-27 14:05:42
219
原创 排序算法——快排系列2（C++）
描述1）基于递归的排序容易造成栈溢出，因此这里提供一种快排的非递归版本；2）由于使用到了stack数据结构以存储需要快排的数据段，因此也存在内存溢出的风险；3）如果希望避免内存溢出，可以考虑混合式排序，即在STL中的sort函数，是一种混合排序（自省式排序）——如果递归深度过深，采用堆排序；如果当前排序元素过少，则使用插入排序（插入排序在数组相对有序的情况下，性能比快排好）；否则是使用三数取中快排；源码 //三数取中，将中值放在first上 void swapThreeMedian(int&a
2020-08-27 13:23:15
115
原创 C++简单实现HashMap
实现说明线程不安全；2倍扩容，方便使用位运算计算桶位置；但存在极端情况下的弊端；不支持将链表转为红黑树源码#pragma once#include<string>//Hash函数int Hash(int key) { return key;}//线程不安全容器//2倍扩容，方便计算//不支持链表转为红黑树class HashMap { class Node { public: const int key; int val; const int
2020-08-22 12:38:31
1825
原创 C++11实现基于链表的自旋锁队列LockFreeLinkedQueue
C++11实现基于链表的无锁队列LockFreeLinkedQueue 无锁队列实现原理源码测试代码运行结果码云链接无锁队列无锁队列一般指的是通过CAS操作来保证队列的线程安全性问题，而不会使得线程陷入到内核，以避免用户态与内核态的切换开销；实现原理采用链表，实现基于自旋锁CAS的无界队列自旋锁方式，对head/tail自旋为NULL 表示成功获取自旋锁：2.1. 在push函数中，对tail成功CAS为Exclude 表示当前线程获取tail自旋锁成功，并设置tail的next节点为push
2020-08-21 13:28:27
2065
1
原创 C++11实现基于循环数组的自旋锁队列LockFreeArrayQueue
C++11实现基于循环数组的无锁队列LockFreeArrayQueue 无锁队列实现原理源码测试代码运行结果无锁队列无锁队列一般指的是通过CAS操作来保证队列的线程安全性问题，而不会使得线程陷入到内核，以避免用户态与内核态的切换开销；实现原理本文采用循环数组，实现无锁队列；自旋锁方式，对front/rear自旋为Exclude 表示成功获取自旋锁：1.1. 在push函数中，对rear成功CAS为Exclude 表示当前线程获取rear自旋锁成功，并需要判断当前数组是否已满，如果已满，则解锁
2020-08-21 11:07:24
2879
2
原创 《Redis设计与实现》学习笔记
《Redis设计与实现》学习笔记第一部分 数据结构与对象第二章、简单动态字符串SDS第三章、链表（双向无环链表）第四章、字典（hash表实现）第五章、跳跃表第六章、整数集合第七章、压缩列表第八章、对象第二部分 单机数据库的实现第9章 数据库第10章 RDB持久化第11章 AOF持久化第12章 事件第13章 客户端第14章 服务器第三部分 多机数据库的实现第15章 复制第16章 Sentinel第17章 集群第四部分 独立功能的实现第18章 发布和订阅第19章 事务第20章 Lua脚本第21章 排序第22章
2020-08-20 20:44:29
237
原创 C++寻找两个链表的交点
算法思想链表明确无环下 findIntersectWithoutRing这种情况，只需要使用两个指针进行一次遍历就可以了。注：可以假想成两个链表彼此相连，即list2连到list1后面，list1连在list2后面；链表可能有环 findIntersect首先需要判断两个链表是否有环，环的入口，以及不重复节点的数量；当两个链表其中一个无环，另一个有环时，必然没有交点；当两个链表都有环，且环的入口不一致时，需要判断是否为同一个环；如果是同一个环，则返回其中一个环入口，否则，必然没有交点；其它
2020-08-16 14:25:32
431
原创 最大公约数与最小公倍数
#pragma once#include<algorithm>using namespace std;//求最大公约数//辗转相除法int GCD(int n, int m) { if (n < m) swap(n, m); while (m != 0) { int tmp = n % m; n = m; m = tmp; } return n;}//求最小公倍数int LCM(int n, int m) { return n * m / GCD(n,
2020-08-16 12:46:53
162
原创 排序算法——桶排序、计数排序与基数排序（C++）
桶排序基本思想先扫描得到待排序数组中的最大值maxVal与最小值minVal，假设桶的个数为k，则代表则将[minVal, maxVal]均分为k个范围，每个范围中的元素各自放入对应的桶中。如此桶之间必然是有序的，桶内使用排序算法进行排序，最后按序收集所有桶的元素，即完成桶排序；复杂度时间复杂度总的时间复杂度为 O(n)+O(k)O(n/klog(n/k)) = O(n+nlog(n/k))当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶
2020-08-16 10:12:36
919
原创 排序算法——插入排序与希尔排序（C++）
插入排序基本思想插入排序插入排序的基本思想是：将一个待排数据插入到已经排序的数据中的适当位置，如果迭代。希尔排序希尔排序（Shell Sort）又称为“缩小增量排序”。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。复杂度插入排序平均时间复杂度：O(n2)，
2020-08-15 12:29:23
148
原创 C++实现大数加法和乘法
#pragma once#include<iostream>#include<vector>#include<assert.h>#include<algorithm>using namespace std;class BigNumber {private: //判断是否为数字 bool isNumber(const string& number) { int index = 0; if (number[index] == '-
2020-08-13 20:25:21
461
原创 最小生成树MST
最小生成树MST最小生成树是在一张无向连通图中，找到一棵树，使得其边的代价之和最小。注：可能存在多个最小生成树。两种算法Kruskal核心思想以边为展开，将图中的最小代价边尝试加入集合tree中，并且该边不能与集合tree中的边形成环，如此迭代，最终得到的集合tree为MST。因此可以采用并集查的方式实现Kruskal算法Prim核心思想以点为展开，将图中的最小代价边的终点尝试加入集合visited中，并边的起点from已在集合visited中，终点to不在集合visited中。这里，可以采用
2020-08-12 10:14:03
196
原创 C++11实现CountDownLatch以及CyclicBarrier
#pragma once#include<assert.h>#include<mutex>#include<atomic>#include<condition_variable>//用于一组线程等待另外count个线程执行任务结束//一次性的class CountDownLatch {private: //计数 std::atomic<int> count; std::mutex mx; std::condition_v
2020-08-05 18:19:28
1031
原创 C++实现strcpy、memcpy以及memmove函数
#pragma once#include<string>//需要保证src为C风格字符串//dest缓冲中可以完全放下src//存在内存重叠问题char* strcpy1(char* dest, const char* src) { if (dest == nullptr || src == nullptr) return nullptr; if (dest == src) return dest; char* dst = dest; while ((*dst++ = *src
2020-08-05 12:31:21
291
原创 C++的string简单实现（拷贝、移动）
#pragma once#include<vector>using namespace std;class String {private: char* data;public: String(const char* str = NULL); String(const String& other); String(String&& other); String& operator=(const String& other); Stri
2020-08-05 12:13:06
1329
原创 质数判断的两种方式
#include<math.h>using namespace std;//简单方法，质数无法被1和自身以外的数整除bool isPrime1(int n) { if (n < 2) return true; int sn = sqrt(n); for (int i = 2; i <= sn; ++i) if (n % i == 0) return false; return true;}//...,6x-1,6x+1,6x+2,6x+3,6x+4,6x+5
2020-08-04 21:30:16
1156
原创 多线程循环打印ABC
#include<thread>#include<mutex>#include<condition_variable>#include<iostream>#include<vector>std::mutex mx;std::condition_variable cond1, cond2, cond3;int cnt = 0;void func1() { while (true) { std::unique_lock<
2020-08-04 20:15:19
166
原创 LRU与LFU缓存替换算法C++实现
LRU与LFU缓存替换算法C++实现LRU实现实现原理讨论源码LRU实现实现原理源码Dqueue版本list版本LRU实现实现原理数据结构unordered_map+Dqueue;unordered_map的键为key，值为Node*，方便快速存取数据；Dqueue双端队列，快速删除、插入Node*；讨论简单的LRU是存在缺点的，比如有某一次缓存操作是完全随机的，但是LRU缓存中替换为了这一次随机的访问数据（指的是，只有这一次被访问，接下来不会被访问），导致缓存被污染；因此也有对LRU的
2020-08-04 19:34:42
400
原创 3种插值算法C++代码实现
最近邻插值算法//最近邻插值Vec3b INTER_NEAREST(double row, double col, const Mat& img) { int r = int(row + 0.5); int c = int(col + 0.5); Vec3b vec3b; if (r < 0 || r >= img.rows || c < 0 || c >= img.cols) vec3b[0] = vec3b[1] = v
2020-08-03 19:51:39
7794
1
原创 直方图计算C++代码实现
//计算直方图vector<vector<int>> CalHistgram(const Mat& img) { vector<vector<int>>histogram(256); for (int i = 0; i < histogram.size(); ++i) histogram[i].resize(3); for (int row = 0; row < img.rows; row++)
2020-08-03 19:40:08
2453
原创 C++内存对齐的原则
内存对其规则1、数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的整数倍开始；2、结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存储；(struct a里存有struct b,b里有char,int ,double等元素,那b应该从8的整数倍开始存储)3、收尾工作:结构体的总
2020-08-03 10:03:50
477
原创 C++11的多种单例模型实现
C++的多种单例模型实现单例概念单例的懒汉实现单例的饿汉实现有问题的双重检查锁问题源码以上代码的问题原因基于atomic的双重检查锁源码说明参考单例概念单例模式确保某个类只有一个实例，而且自行实例化并向整个系统提供这个实例。单例的懒汉实现1）利用C++11的static线程安全性class Instance {public: static Instance& getInstance() { static Instance instance; return instance;
2020-08-02 16:00:41
221
原创 排序算法——快排系列1（C++）
描述1）这里只实现了三数取中快排quickSort；时间复杂度为O(nlogn)2）在STL中的sort函数，是一种混合排序（自省式排序）——如果递归深度过深，采用堆排序；如果当前排序元素过少，则使用插入排序（插入排序在数组相对有序的情况下，性能比快排好）；否则是使用三数取中快排；3）基于快排思想，快速选择第rank个最小的元素quickSelect；时间复杂度为O(n);源码#pragma once#include<vector>class QuickSort {priva
2020-08-02 13:18:47
167
原创 C++实现KMP算法
#pragma once#include<vector>#include<string>class KMP {private: std::vector<int> getNext(const std::string& p) { if (p.size() < 1) return {}; std::vector<int>next(p.length()); next[0] = -1; int i = 0, k = -1;
2020-08-02 12:52:26
136
原创 排序算法——堆排序（C++）
#pragma once#include<vector>//调整堆void maxHeapify(std::vector<int>& nums, int cur, int size) { while ((2 * cur + 1) < size) { int left = 2 * cur + 1; int right = 2 * cur + 2; int larger = left; if (right<size && nu
2020-08-02 12:05:36
88
原创 C++实现最大堆
#pragma once#include<vector>#include<assert.h>//最大堆template<typename T>class Heap {public: Heap(int size=0):data(size){} bool isEmpty() { return last == 0; } void push(int val) { if (data.size() <= last) data.push_b
2020-08-02 12:04:06
324
原创 C++的volatile关键字理解
C++的volatile关键字1）volatile语义是易变的，该修饰的变量可能会突然地、出乎意料地被改变；2）禁止编译器优化；如使得被修饰变量需要每次从内存中读取。因为编译器优化过程，认为这个变量没有被更改的可能性的时候，就会优化成每次从CPU寄存器中读取，导致中断函数的改变对于其是不可见的。3）在多线程下，变量的可见性不能保证。因为多线程变量的可见性的导致原因是CPU为优化导致的多核下的指令乱序。比如CPU的store buffer。某个CPU核在改某一个变量时，为加速，会将其先放在store
2020-08-02 10:41:43
171
原创 pure virtual method called错误简记
pure virtual method called错误简记错误1错误源码运行结果说明原因错误1错误源码运行结果说明原因错误1错误源码class Base {public: virtual void foo() = 0; Base() { call_foo(); } void call_foo() { foo(); }};class Derived : Base { void foo() { }};int main() {Derived d;}
2020-08-02 10:28:27
583
原创 C++实现循环阻塞队列CycleBlockingQueue
C++实现循环阻塞队列CycleBlockingQueue描述源码CycleBlockingQueue.h描述1）循环阻塞队列采用生产者消费者模式；2）循环阻塞队列内部采用了vector数组（也可使用链表）管理缓冲，并预先分配size+1的空间；3）关于与之前博客中的线程池连用，需要扩展相应的函数接口；源码CycleBlockingQueue.h#pragma once#include<vector>#include<mutex>#include<condi
2020-08-02 09:54:57
390
原创 C++实现读写锁ReadWriteLock
C++实现读写锁ReadWriteLock描述使用示例源码ReadWriteLock.h描述1）读写锁基本思想：写者之间互斥、写者和读者之间互斥，而读者之间并不需要互斥2）读写锁分为两种：读者优先和写者优先；读者优先，即当前只要可读，就是可进入的；写者优先，读者需要看看当前是否有写者要读，如果有，则等待至没有写者正在写或者需要写的情况；使用示例#include"ReadWriteLock.h"#include<iostream>#include<vector>#i
2020-08-02 09:44:38
3361
原创 C++11实现信号量semaphore
C++11实现信号量semaphore描述源码semaphore.h描述1）信号量是一种线程/进程间同步的一种手段，可以用来管理有限资源的访问；2）互斥锁主要用来进行互斥的，而信号量则是主要用来同步的；3）从使用上来说，互斥锁的lock和unlock必须在同一个线程；而信号量的wait和signal可以在不同的线程；典型的线程同步代码如下所示：#include"semaphore.h"#include<thread>#include<iostream>semaph
2020-08-02 09:25:28
3556
原创 直方图均衡化C++代码实现
//直方图均衡化void equHistogram(const Mat& src,Mat& dst) { assert(src.cols == dst.cols && src.rows == dst.rows); vector<int>histogram(255); //计算直方图 for (int row = 0; row < src.rows; ++row) { const unsigned char*
2020-08-01 17:56:50
1532
原创 直方图规格化C++代码实现
//直方图规格化void specifyHistogram(const Mat& src, const Mat& dst,Mat& out) { assert(src.cols == dst.cols && src.rows == dst.rows); assert(src.cols == dst.cols && out.rows == out.rows); vector<double>src_hist(255);
2020-08-01 17:56:13
660
原创 《TCP/IP详解卷一》学习笔记
《TCP/IP详解卷一》学习笔记第1章 概述第3章 IP:网际协议第6章 ICMP：internet控制报文协议第7/8章 Ping/Traceroute程序第9/10章 IP路由第11章 UDP: 用户数据包协议第12章 多播和广播第14章 DNS：域名系统第15章 TFTP：简单文件传送协议第17章 TCP：传输控制协议第18章 TCP连接建立与终止第19章 TCP的交互数据流第20章 TCP成块数据流第21章 TCP的超时与重传第22章 TCP的持续定时器第23章 TCP的保活定时器第1章 概述1
2020-08-01 15:10:21
643
原创 《Linux内核设计与实现》学习笔记
《Linux内核设计与实现》学习笔记第三章 进程管理第四章 进程调度第五章 系统调用第六章 内核数据结构第七章 中断和中断处理第十章 内核同步方法第11章 定时器和时间管理第12章 内存管理第13章 虚拟文件系统第14章 块I/O层第15章 进程地址空间第16章 页高速缓存和页写回第16章 其它第三章 进程管理1、内核线程和普通的进程相比，没有独立的地址空间；2、进程退出，而未被wait时，占用内核栈、thread_info结构和task_struct结构第四章 进程调度1、CFS公平调度器，将任
2020-08-01 15:01:59
309
深度学习论文推荐1.rar
2019-08-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人