- 博客(24)
- 收藏
- 关注
RSS订阅
原创 动态规划之0-1背包
前言从今天开始陆续给大家讲一下动态规划中十分重要的一个问题——背包问题，主要有三种具体的类型，0-1背包、完全背包、多重背包。这三种背包问题是使用动态规划思想的十分重要且典型的问题，在面试和笔试中出现的频率很高，强烈建议大家掌握。今天这篇博客先进行预热，给大家讲一下0-1背包。在此之前先放一个链接：【动态规划】01背包问题，这篇博客是我到现在为止看到的讲0-1背包问题最好的博客，我也是看了这篇博客后渐渐理解了背包问题，因此建议大家看一下这篇博客，当然了，也希望大家看完之后也可以赏光一下本人的这篇博客，顺便
2020-08-18 11:29:17
244
原创 智能指针入门
智能指针简介相信各位使用C++编程的小伙伴都有过内存泄漏的困惑，确实，C++因为没有Java的垃圾回收机制，当程序员不能很好的管理自己所申请的内存时很容易出现内存泄漏的问题。不过虽然在语法机制上面C++有如此缺憾，但仍然给我们这种粗心大意的程序员提供了一个弥补错误的工具——智能指针模板类。首先看下列代码。void remodel(string& str){ string * ps = new string(str); ... return;}如代码所示，指针ps为局部变量，当函数返回
2020-08-29 20:53:01
133
原创 动态规划之完全背包、多重背包
前言上一篇博客刚讲了01背包，本章所要讲的完全背包和多重背包和01背包属于同一问题，它们三个的解决思想和数学模型相同，唯一不同的是约束。因此没看过01背包的建议一定先看一下01背包，另外在这里同样给大家推荐两篇博客：完全背包、多重背包。好，下面进入正题。完全背包场景我们仍使用01背包的场景，马上我们就会发现这两个其实是同一问题：同样是这档节目，给嘉宾发一个购物车，然后准备一些商品，但每个商品不再只有一个，而是无限个，在1分钟的时间内嘉宾可以随意往购物车中装任意商品任意个数，只要购物车装的下，然后购
2020-08-18 12:38:04
238
原创 线程间同步经典问题——哲学家就餐、消费者生产者、睡眠的理发师、读者写者
线程间同步经典问题——哲学家就餐、消费者生产者、睡眠的理发师、读者写者哲学家就餐消费者生产者睡眠的理发师读者写者哲学家就餐https://github.com/kfcyh/threads/tree/master/philosopher消费者生产者https://github.com/kfcyh/threads/tree/master/producer_consumer睡眠的理发师https://github.com/kfcyh/threads/tree/master/barber读者写者ht
2020-05-24 16:37:07
379
原创 c++多线程之condition_variable
c++多线程之同步实现——std::mutex类线程同步简介互斥锁mutex线程同步简介之前讲过使用thread创建线程，实际中经常出现几个线程共享数据互相合作完成某项工作，也就是说有若干个线程对同一块数据进行读写，这时候会出现几种情况。几个线程读取同一块数据，不对数据进行写操作：这时几个线程之间可以同时访问该数据，不需要进行互斥。一个或若干个线程对数据进行读操作，一个或若干个线程对数据进行写操作：一块数据是不允许同时进行读和写操作的，因为这样操作的结果是不可预见的，比如线程t1对变量a进行读操作
2020-05-24 15:26:09
1608
原创 c++多线程之模版类lock_guard和unique_lock
c++多线程之模版类lock_guard和unique_lock简介lock_guardunique_lock简介之前讲解互斥锁mutex中提到，mutex的上锁lock()和解锁unlock()操作必须成对使用，一旦我们在一个线程中获取一个mutex锁后忘记在线程结束时解锁，那么这个锁将一值处于上锁状态，导致其他需要获取这个锁的线程一直处于阻塞状态从而饿死。为了避免大家犯这种低级错误，也为了更好更灵活的使用互斥锁，c++退出了模板类lock_guard和unique_lock。下面给大家具体讲解一下。
2020-05-23 16:47:56
338
原创 c++多线程之互斥锁mutex
c++多线程之互斥锁mutex互斥锁mutex简介调用lock()调用try_lock()互斥锁mutex简介mutex只有两种状态，即上锁( lock )和解锁( unlock )，它具有原子性和唯一性，简单解释就是：原子性：一个互斥锁同一时间只有一个线程可以对其进行上锁。唯一性：当一把互斥锁被上锁后，在它被解锁前不能被其他线程锁定。下面我们具体看一下mutex类。我们只需掌握它三个接口即可。void lock()上锁，若此时锁被其他线程拥有则阻塞直到锁被释放void
2020-05-22 10:47:50
1512
原创 c++多线程之std::thread类的使用
c++多线程之std::thread类的使用构造函数c++中封装了用于创建线程的类thread，它需要包含头文件include<thread>include <thread>include<thread>，我们来看一下thread中的几个重要接口。构造函数1.默认构造函数std::thread t()构造空的线程对象2.初始化构造函数std::thread t(&f,arg)构造执行函数f的线程对象，arg代表函数f的参数列表
2020-05-18 18:06:57
854
原创 排序算法之快速排序详解
排序算法之快速排序简介原理枢纽元的选取分割策略代码实现性能分析简介今天介绍排序算法中最重要的快速排序，顾名思义，快速排序之所以能在历史的长河中脱颖而出以“快速”两字命名，就是因为经多年实践证明它是已知最快的泛型排序算法。并且到目前为止还没有哪个算法能撼动其位置。所以它的重要性是不言而喻的，是我们一定要熟悉并掌握的排序算法。原理前不久我们刚讲过归并排序（归并排序），快速排序同归并排序一样，也...
2020-05-04 19:45:31
326
原创 排序算法之归并排序
排序算法之归并排序原理代码实现性能分析原理今天介绍另一种十分高效的排序算法——归并排序。其通过将两个有序的表合并成一个有序表进行排序，过程是取两个待合并数组AAA和BBB，一个待输出数组CCC，以及计数器ActrActrActr、BctrBctrBctr、CctrCctrCctr，计数器初始位置于其数组首地址，然后将ActrActrActr和BctrBctrBctr指向值中的最小值赋予Cctr...
2020-05-03 18:06:15
383
原创 排序算法之堆排序
排序算法之堆排序简介之前讲过简单选择排序，它是通过nnn次遍历，每次选出最小值，从而完成排序，因为没有保存每次遍历的结果，所以在每次遍历时都要遍历剩余的所有元素，因此操作次数较多，那我们可不可以在每次选择最小元素的同时，根据比较结果对其他元素进行调整，使其最小值始终处于某个位置，这样每次选择最小值时就不用进行多余的操作，从而提高了效率。下面我们就介绍这样一种排序算法——堆排序。简介堆排序是采...
2020-05-03 12:06:40
114
原创 数据结构之优先队列——二叉堆
数据结构之优先队列（堆）简介二叉堆的结构性质我们之前已经讲过好几种数据结构，其中讲到队列时我们说过队列经常用于打印机作业，此时打印机安排打印作业是按照作业加入打印机的先后顺序进行的。但这未必是最好的做法，例如，现有一项后来插入的特别重要的作业，需要优先打印，此时再按照“先来后到”的原则就不合适了，这种情况在日常生活和工作中十分多见，这时就需要用到今天我们讲的一种十分重要且常用的数据结构——优先队...
2020-05-02 11:43:39
445
原创 排序算法之希尔排序
排序算法之希尔排序简介代码讲解性能分析简介之前介绍的几种排序算法，简单选择排序、直接插入排序，它们的时间复杂度都是O(n2)O(n^2)O(n2)。实际上在早期很长一段时间内，普遍认为排序算法的效率不会高于O(n2)O(n^2)O(n2)，直到希尔排序算法的出现才打破了这一认知。希尔排序是第一批冲破二次时间界(O(n2)O(n^2)O(n2))的算法之一。它通过比较相距一定距离的元素来排序，各...
2020-04-30 16:07:07
1515
原创 排序算法之直接插入排序
排序算法之直接插入排序简介代码讲解性能分析简介直接插入排序是插入排序的一种。它思想是将一个新的数据插图到已经排好序的有序表中，然后得到一个新的有序表。因为思想和代码很简单，我们仍然直接通过代码进行讲解。代码讲解首先提供代码：struct SqList{ int r[MAXSIZE + 1]; //r0用作哨兵 int length;};void insertsort(SqLi...
2020-04-30 10:50:52
105
原创 排序算法之简单选择排序
排序算法之简单选择排序简介代码实现性能分析排序算法和查找算法一样是最常用最重要的算法之一，排序算法有交换排序、插入排序、选择排序和归并排序等，本专栏给大家介绍一些以上排序算法中的经典算法，今天先给大家介绍第一种——简单选择排序。本文完整代码见kfc/sort简介简单选择排序是选择排序的一种，选择排序原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从...
2020-04-28 11:31:44
524
原创 查找算法之散列表查找（哈希表）
查找算法之散列表查找（哈希表）简介哈希表查找步骤哈希函数构造方法处理冲突代码实现性能分析之前介绍的几种查找算法，无论是有序表查找还是平衡二叉树（二叉查找树），都需要进行元素间的比较或遍历，因此效率最高也只是O(logn)，那有没有不需要进行元素间的比较或遍历直接就能查找到所需数据的算法呢？还真有！那就是通过关键字key进行查找的算法——散列表查找，我们通常称为哈希表。简介查找算法的效率在很大...
2020-04-25 18:17:03
498
原创 平衡二叉树之AVL树
平衡二叉树之AVL树简介之前有篇文章讲二叉排序树（动态查找二叉排序树），二叉排序树是用于动态查找的数据结构，但在文章结尾中也说明了普通的二叉排序树的查找效率是不确定的，这主要取决于二叉排序树是否平衡，为了充分发挥二叉排序树的查找效率我们通常使用平衡的二叉排序树——平衡二叉树，常用的平衡二叉树主要有两种——AVL树和红黑树。今天我们主要介绍AVL树。简介AVL树的平衡条件为：其每个节点的左子...
2020-04-24 13:11:11
339
原创 动态查找之二叉排序树
二叉排序树简介建立之前讲过二分、插值和斐波那契查找方式，这三种查找算法是针对有序线性表的，但有序表的插入和删除操作比较复杂，它需要移动插入和删除元素之后的所有元素。那有没有即可以高效的查找又可以高效的插入和删除呢？有，二叉排序树就可以实现。下面介绍一下二叉排序树。简介二叉排序树又称二叉查找树，它若不为空则具有如下性质：若左子树不为空，则左子树上所有节点的值均小于它根节点的值；若右子树不...
2020-04-22 21:32:35
1623
原创 静态查找之有序表查找——二分查找、插值查找、斐波那契查找
查找算法之二分查找（折半查找）概念原理概念原理二分查找又称折半查找，是有序查找算法的一种，即查找的序列必须是递增或递减的。它的原理类似于猜1至100中的任意数字，比如我们猜数字27，如果我们按顺序猜的话需要27次，如果随机猜的话，次数无法保证，可能很少也可能很多，我们按照这种方式猜，我们先猜中间数100/2=50，发现大了，我们再猜1至50的中间数50/2=25，发现小了，再猜25至50中间数...
2020-04-20 12:24:28
248
原创 数据结构之二叉树——概念原理及代码实现
数据结构之树——重点概念和原理树的简介二叉树树的简介之前已经写过几篇关于数据结构的文章，分别是链表、栈和队列。其中链表采用链式存储结构，栈和队列既可以使用链式存储也可以使用顺序存储（数组），而这些结构有一个共同的特性，看下图从逻辑上讲，无论是链式存储还是顺序存储，这些结构在非空得情况下，每个节点最多只有一个前驱和一个后继，也就是说它们一对一的。而今天所讲的树属于非线性结构，树在非空的情况下...
2020-04-04 16:46:09
396
原创 C++类的使用——关于构造函数的定义与注意事项
关于构造函数的定义与注意事项默认构造函数带参数的构造函数拷贝构造函数(copy constructor和copy assignment operator)总结构造函数是类必备的成员函数，它进行着类的数据成员的初始化工作。如果我们没有定义构造函数，那声明类的对象时会调用系统自动生成的默认构造函数，这个函数什么也不做，通常这样做是有风险的，因为在声明对象时如果不对对象内的数据成员初始化的话，它们的值...
2020-03-29 20:58:51
1568
1
原创 数据结构之队列——概念原理及代码实现
数据结构之队列简介简介今天讲另一种常用的数据结构——队列。队列存储数据的结构类型和栈相同（如果不了解栈可以去看我另一篇专讲栈的文章），不同的是栈只在栈顶插入（压栈）和删除（出栈）数据，而队列在队首删除（出队）数据，在队尾插入（入队）数据。所以队列的入队和出队顺序相同（这一点和栈相反），它是一种先进先出FIFO（First In First Out)的数据结构。如下图所示。...
2020-03-28 20:34:31
359
原创 数据结构之栈——概念原理及代码实现
数据结构之栈栈的简介顺序栈顺序栈类声明顺序栈各接口实现测试链栈链栈类声明链栈类实现测试总结栈的简介今天给大家介绍另一种常用的数据结构——栈。（注意，栈从不同的角度定义有不同的定义，从内存分配的角度定义是指变量由系统分配内存，今天讲的是一种数据结构）它是一种先进后出的结构即FILO(first in last out)。如下图所示，数据的插入（压栈）删除（出栈）都从栈顶操作。栈通常具有以下接...
2020-03-27 20:18:41
267
原创 数据结构—链表及其迭代器的封装
数据结构—链表及其迭代器的封装链表简介代码实现节点定义封装链表类链表类声明链表类各操作定义封装迭代器类迭代器类声明迭代器类定义测试代码链表简介链表是采用链式存储方式实现的一种逻辑上类似于数组的数据结构，其元素之间的逻辑顺序是连续的，但在内存中的物理存储顺序是不连续的，因此不能使用下标的方式读取元素。为了实现数据元素的各种操作，我们把各元素封装成一个结构体——节点（下文都使用此称谓），每个节点内...
2020-03-26 17:49:06
727
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人