- 博客(45)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 stringstream分割字符与类型转换
stringstream分割字符与类型转换用法：#include <iostream>#include <sstream>#include <vector>using namespace std;int main(){ // string s; // getline(cin,s);/**********如果输入是以...
2018-08-12 19:37:11
1262
转载 循环队列实现
假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。 出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外 ，造成假溢出的现象。...
2018-08-10 14:34:56
11968
3
转载 Linux文件系统
分区是真正存放数据的地方，只有一份数据 目录是分区数据的逻辑映射，就像Windows系统中的快捷方式一样 分区的数据可以挂载到任意多个不同目录，这些目录就像不同名的快捷方式，都指向同样的分区数据 文件系统指文件存在的物理空间，linux系统中每个分区都是一个文件系统，都有自己的目录层次结构。linux会将这些分属不同分区的、单独的文件系统按一定的方式形成一个系统的总的目录层...
2018-08-09 16:46:22
1265
转载 手撕代码题
考题1：二分查找（递归与非递归）//递归方法int BinSearch(int Array[],int low,int high,int key/*要找的值*/) { if (low<=high) { int mid = (low+high)/2; if(key == Array[mid]) ...
2018-07-27 11:20:35
1303
转载 回溯法
判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。一般回溯的问题有三种：Find a path to success 有没有解Find all paths to success 求所有解求所有解的个数求所有解的具体信息Find the best path to success 求最优解理解回溯：给一堆选择, 必须从里面选一个. 选完之后我又有了新的一组选择. 回...
2018-06-09 14:28:03
1026
转载 KMP算法
给定目标字符串S，和模板字符串T，求S中是否包含T？T在S中的起始位置是多少？KMP的核心思想就是利用已有的匹配信息减少不必要的比较，当发生失配时候，i保持不动，j回溯到next【j】的位置，从而达到O(n)的复杂度来解决原本O(nm)复杂度的问题。（其中n是S串的长度，m是T串的长度。）前提知识：例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，”P...
2018-06-01 14:40:40
226
原创 剑指offer（树的算法题）
本文包含以下算法题：1.重建二叉树（面试题6）2.树的子结构（面试题18）3.二叉树的镜像（面试题19）4.从上往下打印二叉树（面试题23）5.二叉搜索树的后序遍历序列（面试题24）6.二叉树中和为某一值的路径（面试题25）7.二叉搜索树与双向链表（面试题27）8.二叉树的深度（面试题39）9.平衡二叉树（与上题相关）10.二叉树的下一个结点（面试题58）11.对称的二叉树（面试题59）12.把二...
2018-05-21 17:15:14
467
原创 剑指offer（链表的算法题）
本文包含链表的以下内容： 1、查找单链表中的倒数第k个结点（剑指offer，题15） 2、合并两个有序的单链表，合并之后的链表依然有序【出现频率高】（剑指offer，题17） 3、单链表的反转【出现频率最高】（剑指offer，题16） 4、从尾到头打印单链表（剑指offer，题5） 5、单链表中，取出环的起始点（剑指offer，题56） 6、判断两个单链表相交的...
2018-05-18 20:23:44
918
转载 位运算常见操作
原文链接地址：https://blog.csdn.net/u013074465/article/details/46686881一、位运算基本操作& 与 1 & 1 = 1；1 & 0 = 0；0 & 0 = 0 只有当两个位都为1时，结果为1| 或 1 | 1 = 1；1 | 0 = 1；0 | 0 = 0 只有...
2018-05-17 15:51:47
309
转载 剑指Offer（33 把数组排成最小数 ，34 丑数，40 数组中只出现一次的数字）
33.把数组排成最小数问题描述：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。 思路：先将整数数组转为字符串数组，然后字符串数组进行排序，最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义，不是比较a和b，而是比较ab与 ba。如果ab ...
2018-04-23 17:03:36
209
转载 大数据处理（位图，布隆过滤器）
位图法位图的基本概念是用一个位（bit）来标记某个数据的存放状态。海量数据排序 从最简单的情况说起，如果要对90个小于100的不重复的正整数排序。用位图的思想就是先申请一块100bit的空间，第一遍遍历所有的数，将出现的数字在位图中对应的位置置为1；第二遍遍历位图，依次输出值为1的位对应的数字。先且不说这种情况出现的频率不是很高，就仅这种情况，还是有很多其他的排序算法有它们自己的优势（不用额外...
2018-04-22 21:08:47
418
转载 图的问题
1.图的存储结构邻接矩阵 使用二维数组来存储图的边的信息和权重，如下图所示的4个顶点的无向图： 从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。 如果换成有向图，则如图所示的五个顶点的有向图的邻...
2018-04-21 16:48:15
559
转载 STL各容器对比
STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。STL容器分类： 顺序（序列）容器：vector, l...
2018-04-12 21:01:53
2042
转载 STL之map详解
STL的set和map都是基于红黑树实现的，和stack，queue都是基于deque一样，它们仅仅是调用了RBTree提供的接口函数，然后进行外层封装即可。set简介set是一种关联式容器，其特性如下：set以RBTree作为底层容器所得元素的只有key没有value，value就是key不允许出现键值重复所有的元素都会被自动排序不能通过迭代器来改变set的值，因为set的值就是键第五点需要做一...
2018-04-12 17:05:59
253
转载 STL之vector详解
1.vector的底层实现template<class _Ty, class _Ax> class vector : public _Vector_val<_Ty, _Ax> { // varying size array of valuespublic: /********/protected: poi...
2018-04-12 11:10:15
296
原创 大小堆以及TOP K问题
完全二叉树如上图所示，我们可以将完全二叉树的结点按照层序遍历的顺序储存在一个数组中，那么当完全二叉树中的某个结点位于array的i处时，其左子节点必位于2i+1处（i>=0），其右结点必位于array的2i+2处。这样我们就可以轻易的实现完全二叉树的存储。一般调整大小堆，从第一个非叶子节点位置开始，在数组中位size/2-1处，如上所示就是E。若将结点v的编号（秩）记作i（v...
2018-04-11 19:40:12
879
1
转载 字典树问题与AC自动机
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。字典树的核心就是空间换时间，空间消耗大，但是插入和查询有着很优秀的时间复杂度，利用字符串的公共前缀来避免无谓的字符串比较，降低查询时间。 Trie树的平均高度h为单词平均长度len，所以Trie树的查询复杂度为O（h）=O（len）字典树节点： ...
2018-04-10 18:50:51
731
转载 动态规划问题汇总
分治算法：将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解（子问题独立适合该方法）贪心算法：求局部最优，以得到全局最优（不一定是正确的，需要证明）动态规划：通过一些状态来描述一些子问题，然后通过状态之间的转移来求解（子问题重叠适合该方法）动态实质=分治算法+解决子问题数据冗余动态规划性质最优子结构性质：当一个问题的最优解中包含了子问题的最优解时，则称该问题具...
2018-04-08 20:40:58
746
转载 C++中数组的问题
数组的初始化：静态 int array[10] ; 定义了数组array，未初始化静态 int array[10]={1，2} ；定义并初始化了数组array动态 int *array =new int [10]; delete []array ; 分配了长度为10的数组array；动态 int *array =new int [10](1,2); delete []array ; 分配了长...
2018-04-07 17:28:19
667
转载 动态规划0-1背包问题
简单引入：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。动态规划中的三个概念：最优子结构，边界，状态转移公式；F(1)=1；F(2)=2；F(n)=F(n-1)+F(n-2) (n>=3);例如：F(10)=F(8)+F(9)为最优子结构；F(1)=1，F(2)=2为边界；F(n)=F(n-1)+F(n-2) (n>=3)...
2018-04-07 16:35:07
439
原创 C++面试常见问题
1. extern关键字的作用 extern置于变量或函数前，用于标示变量或函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义。它只要有两个作用：当它与“C”一起连用的时候，如：extern "C" void fun(int a,int b);则告诉编译器在编译fun这个函数时候按着C的规矩去翻译，而不是C++的（这与C++的重载有关，C++语言支持函数重载，C语言...
2018-04-01 17:05:35
59001
8
转载 数组，链表和哈希表比较
数组与链表的区别：（1）存储空间上： 链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据时，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。（2）长度的可变性： 链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。（3）查找效率：按序号查找时，数组可以随...
2018-03-31 19:11:06
5715
1
原创 哈希表总结（一致性哈希）
哈希表是一种通过哈希函数将特定的键映射到特定值的一种数据结构，他维护着键和值之间一一对应关系。散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后...
2018-03-31 17:08:00
467
原创 树的总结
（一）二叉树 相关复杂度：高度为k的二叉树最多有2^k-1，因此如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为log2n+1,其查找效率为O(log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。(对于二叉排序树，高度决定了查找效率) 1.二叉查找树（BST树）（1）若左...
2018-03-30 10:56:53
229
转载 二叉搜索树
参考：https://blog.csdn.net/yanxiaolx/article/details/51986428二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3. 任意节点的左、右子树也分别为二叉查找树。4. 没有...
2018-03-29 20:52:02
108
转载 二叉树的遍历
//也可以参考该文章：https://blog.csdn.net/guojz049/article/details/51597834定义二叉树结构体typedef struct BinaryTreeNode { TelemType data; struct BinaryTreeNode *Left; struct BinaryTreeNode *R...
2018-03-28 20:59:39
188
转载 XML常见问题
1.XML是什么？ XML 被设计用来传输和存储数据，其焦点是数据的内容。HTML 被设计用来显示数据，其焦点是数据的外观。XML即可扩展标记语言（Extensible Markup language），你可以根据自己的需要扩展XML。XML中可以轻松定义<books>, <orders>等自定义标签，而在HTML等其他标记语言中必须使用预定义的标签，比如<p...
2018-03-26 11:03:25
393
转载 数据库基本知识
SQL（Structured Query Language)结构化查询语言，是一种数据库查询和程序设计语言，用于存取数据以及查询、更新和管理关系数据库系统。Oracle Database，又名Oracle RDBMS，或简称Oracle。是甲骨文公司的一款关系数据库管理系统。MySQL是一个小型关系型数据库管理系统，采用了GPL（GNU通用公共许可证）。由于其体积小、速度快、总体拥有成本低，尤其是...
2018-03-22 09:52:45
287
转载 计算机网络
1.计算机网络漫谈：https://www.jianshu.com/p/c793a279f6982.面试常考题：https://www.nowcoder.com/discuss/19373.TCP/IP中的几个标识：SYN, FIN, ACK, PSH, RST, URG.SYN(synchronous建立联机) ACK(acknowledgement 确认) PSH(push传送) FIN(fi...
2018-03-18 20:23:55
392
转载 操作系统知识
同步I/O操作：导致请求进程阻塞，直到操作完成。异步I/O操作：不导致请求进程阻塞。（会立即返回，以通知方式告知）并发与并行并发的关键是你有处理多个任务的能力，不一定要同时。并行的关键是你有同时处理多个任务的能力。并发是一段时间内处理很多事情，并行是某一时刻同时做很多事情。进程是具有独立功能的程序，关于某个数据集合的一次运行过程。进程与程序的区别：1. 程序是静态...
2018-03-16 17:12:12
531
转载 C++中String常用函数总结
1.string类提取子串函数：s.substr();//返回s的全部内容s.substr(11);//从索引11往后的子串s.substr(5,6);//从索引5开始6个字符2.string类的查找函数： //查找成功时返回所在位置(第一个字符索引)，失败返回string::npos的值int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串...
2018-03-12 16:31:26
273
原创 C++中substr函数的注意点
注意：其中第一个参数为index，第二个参数为偏移量，并不是索引值#include<string>#include<iostream>using namespace std;int main(){string s("12345abcd");string a=s.substr(0,5); //获得字符串s中 从第0位开始的长度为5的字符串...
2018-03-11 15:54:53
1976
转载 有关链表问题
1.剑指offer中链表添加函数中为什么要用指向链表指针的指针（P50页） http://blog.csdn.net/shen_jz2012/article/details/50631317 2.链表结的结构和链表的各项操作模块函数点 http://blog.csdn.net/qq_41093451/article/details/791387883.关于链表中头指针和...
2018-03-10 18:34:35
141
转载 struct和typedef struct
转载：http://blog.csdn.net/zyh821351004/article/details/47961967 http://blog.csdn.net/shanshanhi/article/details/522681671 首先：//注意在C和C++里不同 在C中定义一个结构体类型要用typedef: typedef struct Student ...
2018-03-10 15:26:32
102
转载 哈希表简介
转载于：http://blog.csdn.net/u013752202/article/details/51104156顺序查表法假设现在有1000个人的档案资料需要存放进档案柜子里。要求是能够快速查询到某人档案是否已经存档，如果已经存档则能快速调出档案。如果是你，你会怎么做？最普通的做法就是把每个人的档案依次放到柜子里，然后柜子外面贴上人名，需要查询某个人的档案的时候就根据这个人的姓名来确定是否...
2018-03-08 15:31:55
182
转载 计数排序
转载于：http://blog.csdn.net/llzk_/article/details/53354071排序总归来说可分为两大类，比较排序与非比较排序。比较排序就是我们常用到的冒泡排序，插入排序，希尔排序，选择排序，堆排序，快速排序，归并排序。非比较排序不常用，但是在对一些特殊的情况进行处理时，它的速度反而更快。1、计数排序 排序原理：利用哈希的方法，将每个数据出现的次数都统计下来。哈希表...
2018-03-07 10:54:57
164
转载 C++中输入注意点(cin,cin.getline(),cin.get())
1.每次只读取一个单词（cin）：cin使用空白（空格，制表符和换行符）来确定字符串的结束位置，这意味着cin在获取字符数组输入时只读取一个单词，读取该单词后，cin将该字符串放到数组中，并自动添加空字符-"\0"，而不保存上述的结束符，会忽略上述结束符，cin可以重新读取一个单词。2.每次读取一行字符串输入（1）getline（）：每次只读取一行，通过回车键输入的换行符来确定输入结尾，但...
2018-03-06 16:28:04
730
转载 mid的计算方法
如果用mid=(low+high)/2，在运行二分查找程序时可能超时。原因是int类型最大表示范围是2147483647，如果输入的low和high都接近2147483647，两个数相加就会溢出，变成一个负数。所以如果想避免溢出，不能使用mid=(low+high)/2，应该使用mid=low+(high-low)/2。因为mid=(low + high)/2=(low + low + high ...
2018-03-04 09:57:22
2332
转载 快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。 每经过一趟快排，轴点元素都必然就位，也就是说，一趟下来至少有1个元素在其最终位置 快速排序使用分治策略...
2018-03-03 17:05:05
259
转载 归并排序
https://www.cnblogs.com/eniac12/p/5329396.html 归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。 归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭...
2018-03-03 14:54:36
183
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人