- 博客(56)
- 收藏
- 关注
RSS订阅原创 排序代码
目录1、插入排序2、冒泡排序3、选择排序4、希尔排序5、快排（2路）6、堆排序7、归并排序1、插入排序template <typename T>void insertSort(vector<T>& v){ if( v.empty() ) return; for( size_t i=1;i<...
2018-08-28 21:29:06
665
原创 指针常量和常量指针
1、指针常量——指针类型的常量（int *const p）本质上一个常量，指针用来说明常量的类型，表示该常量是一个指针类型的常量。在指针常量中，指针自身的值是一个常量，不可改变，始终指向同一个地址。在定义的同时必须初始化。用法如下：int a = 10, b = 20;int * const p = &a;*p = 30; // p指向的地址是一定的，但其内容可以修改2、...
2018-08-22 10:53:04
77574
55
转载 归并排序
转载：归并排序算法基本思想归并排序采用的是分治算法的思想，其中最重要的操作就是归并操作。主要思想是，将数组平分为A，B两部分，分别将A,B两部分排好序，然后再合并，对A排序的时候，也是同样的思路，将A分为两份，同样先分别排序，再合并。一直递归下去，直到不能再分解为止。网上看到一张图很好的解释了这个过程：归并算法过程.png再用动画展示一下这个过程： 归并过程...
2018-08-07 22:42:11
198
原创 剑指Offer——滑动窗口的最大值
题目描述给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,...
2018-08-05 10:02:54
617
原创 剑指Offer——构建乘积数组
题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。方法一如果能使用除法，可以求出A[0]*...*A[n-1]的乘积结果记为product，则每个B[i] = product / A[i]。但是不能使用除法，比较简单的办法就...
2018-07-31 17:45:27
271
原创 死锁
目录一、什么是死锁二、死锁的必要条件三、死锁的处理方法1、死锁预防2、死锁避免（1）进程启动拒绝（2）资源拒绝分配（银行家算法）3、死锁检测和死锁恢复死锁检测死锁恢复一、什么是死锁所谓死锁是指多个并发进程，各自持有资源又都等待别的进程释放所拥有的资源，在未改变这种状态之前不能向前推进，这种状态称为死锁，死锁产生的根本原因是系统资源不足。二、死锁的...
2018-07-29 20:52:12
4453
原创 剑指Offer——和为S的连续正数序列
题目描述小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!输出描述输出所有和为S的连续正数序列...
2018-07-28 21:11:30
146
转载 C语言运算符优先级
转自: http://blog.csdn.net/huangblog/article/details/8271791 C语言运算符优先级 优先级 运算符 名称或含义 使用形式 结合方向 说明 1 [] ...
2018-07-28 19:44:04
1647
原创 剑指Offer——不用加减乘除做加法
题目描述写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。输入为num1和num2方法不能用+-*/，那么只能用位运算来进行计算，可以把二进制像十进制加法一样，按位相加，满2进1，然后可以发现：按位相加时，0和1相加等于1，0和0、1和1相加等于1，与^运算的结果相同，因此可以使用^运算得到相加结果（不考虑进位情况下）记为sum = num1 ^ n...
2018-07-27 20:16:59
544
原创 进程的状态及转换
进程是计算机中已运行程序的实体。程序本身只是指令的集合，进程才是程序的真正运行。用户下达运行程序的命令后，就会产生进程。同一个程序可以产生多个进程（一对多关系），以允许用户运行统一程序，却不会互相冲突。进程需要一些资源才能够完成工作，如CPU使用时间、存储器、文件以及I/O设备，且为依序逐一进行，也就是任何时间内仅能运行一项进程。进程通常有如下5种状态，其中前3种是进程的基本状态：就绪...
2018-07-27 17:27:29
4144
原创 硬链接和软链接的区别
参考：https://www.ibm.com/developerworks/cn/linux/l-cn-hardandsymb-links/index.html 硬链接我们知道文件都有文件名与数据，这在 Linux 上被分成两个部分：用户数据 (user data) 与元数据 (metadata)。用户数据，即文件数据块 (data block)，数据块是记录文件真实内容的地方；而元数...
2018-07-26 21:17:46
183
1
原创 剑指Offer——平衡二叉树
题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。（一般来说，平衡二叉树既是平衡的树，又是二分搜索树。但此题只要求判断是不是平衡的）节点的结构一般如下：struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ...
2018-07-25 09:15:19
216
原创 剑指Offer——左旋转字符串
题目描述汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！思路可以看出，如果需要将str左移n位，其实就是将str的前n个字符挪到str的尾部，所以...
2018-07-23 21:22:44
679
转载 C++显式构造函数
如果C++类的其中一个构造函数有一个参数，那么在编译的时候就会有一个缺省的转换操作：将该构造函数对应数据类型的数据转换为该类对象。如下面的例子：#include <iostream>using namespace std;class B{public: int data; B(int _data):data(_data){} //explicit...
2018-07-23 16:41:03
4149
原创 剑指Offer——把数组排成最小的数
题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。方法输入为 vector<int> numbers， 输出为string。可已将numbers中的int通过to_string函数变为string，然后对修改后的string进行排序（此时...
2018-07-22 19:55:28
130
原创 HTTP首部
HEEP首部字段四种类型HTTP 首部字段根据实际用途被分为以下 4 种类型：通用首部字段（ General Header Fields） 请求报文和响应报文两方都会使用的首部。 请求首部字段（ Request Header Fields） 从客户端向服务器端发送请求报文时使用的首部。 补充了请求的附加内容、 客户端信息、 响应内容相关优先级等信息。 响应首部字段（ R...
2018-07-22 10:53:37
128
原创 对面向对象的理解
面向对象是基于万物皆对象这个哲学观点，在现实生活中的任何物体都可以归为一类事物，而每一个个体都是一类事物的实例。把一个对象抽象成类，具体上就是把一个对象的静态特征和动态特征抽象成属性和方法，也就是把一类事物的算法和数据结构封装在一个类之中，程序就是多个对象和互相之间的通信组成的。面向对象有三大特性：封装、继承和多态。封装封装将一类事物的属性数据和处理该数据的方法抽象成一个整体，以实现独...
2018-07-22 09:59:02
222
原创 剑指Offer——丑数
题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。方法一首先想到的是如果一个数是丑数，那么它应该可以分解成一个丑数与2或3或5的积，所以可以将已经得到的丑数进行存储，如果i满足下述的条件，则i是丑数：i能够整除2且i/2也是丑数 i能够整除3...
2018-07-21 22:09:28
169
原创 TIME_WAIT的意义
上图为TCP连接释放过程，在服务器A收到服务器B发送的FIN+ACK后，会向B发送ACK，进入到TIME_WAIT阶段，等待2MSL（MSL：Max Segment Lifetime，最长报文段寿命，报文段在网络中能够存活的最长时间）。TIME_WAIT的意义（1）可靠地实现TCP全双工连接的终止为了保证A发送的最后一个ACK报文段能够到达B。A给B发送的ACK可能会丢失，B收...
2018-07-20 21:50:11
4580
原创 进程间通信
进程通信的应用场景 数据传输：一个进程需要将它的数据发送给另一个进程，发送的数据量在一个字节到几兆字节之间。 共享数据：多个进程想要操作共享数据，一个进程对共享数据的修改，别的进程应该立刻看到。 通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）。 资源共享：多个进程之间共享同样的资源。为了作到这一点，需要...
2018-07-20 15:57:16
762
原创 内存的页面置换算法
请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。在请求分页系统中，只要求将当前需要的一部分页面装入内存，以便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过雕爷功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。页面置换算法的主要目标是使页...
2018-07-20 11:15:13
10492
1
原创 剑指Offer——最小的k个数
题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。方法一可以利用快排中partition的思想（快排详细分析可以参考快速排序算法）随机选中一个数字，在第一次partition之后，得到此时排列中该数字的位置index，位于index左边的值均小于等于该数字，位于index右边的值均大于等于该数字；当index > ...
2018-05-14 22:50:17
149
原创 剑指Offer——数组中出现次数超过一半的数字
题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。方法一最先想到的是对数组记性排序，然后遍历数组找出出现次数超过数组长度的一半的数。该方法的时间复杂度就是排序用的时间，即最快的排序算法的时间复杂度O(nlogn)。class Sol...
2018-05-09 13:16:25
135
原创 剑指Offer——序列化二叉树
题目描述请实现两个函数，分别用来序列化和反序列化二叉树题目解析：题目的要求似乎不是太清晰，序列化的意思是指将一些特定的数据结构，变成有格式信息的字符串。例如对一个链表，可以将1->2->3->4->NULL序列化为"1,2,3,4"。对于序列化算法，必须支持反序列化，即在约定的格式下，可以将满足格式要求的字符串重新构造为原始的结构形式。实际上就是用序列来表示一棵二叉树，然后...
2018-05-09 10:26:41
341
1
原创 剑指Offer——二叉搜索树与双向链表
题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。题目分析二叉树中每个节点都有两个指向子节点的指针；在双向链表中，每个节点也有两个指针，分别指向前一个节点和后一个节点；在将二叉树转换成双向链表时，原先指向左子节点的指针调整为链表中指向前一个节点的指针，原先指向右子节点的指针调整为链表中指向后一个节点的指针。概念1、二叉搜索树：...
2018-05-07 21:26:02
105
原创 剑指Offer——字符串的排列
题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。NOTE：最后输出是按字典序打印出该字符串中字符的所有排列解题思路求整个字符串的全排列，可以分两步进行： 求可能出现在第一个位置上的字符，...
2018-05-05 22:07:45
256
原创 剑指Offer——复杂链表的复制
题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）概念复杂链表示例：方法一可以分为两步来完成：1、复制原始链表上的每一个结点，并用next链接起来；2、设置每个结点的random 指针：由于链表中节点的random指针指向的节点...
2018-05-05 17:04:05
174
原创 剑指Offer——二叉树中和为某一值的路径
题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。解题思路可以通过递归方法解决这个问题，我们每访问到一个节点的时候，对该节点进行判断：如果该节点是叶子节点（左右子树都为空），且值等于所需要的值，那么可以将该节点的值存入路径，并将路径进行存储；如果节点不满足条件，那么继续往下进行递归访问它的子节点。当访...
2018-05-04 22:20:36
125
原创 剑指Offer——二叉搜索树的后序遍历序列
题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。概念1、二叉搜索树：二叉搜索树(英语：Binary Search Tree)，也称二叉查找树、有序二叉树(英语：ordered binary tree)，排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：任意...
2018-05-04 21:28:35
194
原创 剑指Offer——按之字形顺序打印二叉树
题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。方法一方法和从上往下打印二叉树类似，遍历顺序是从上到下，每一行按照从左到右的顺序进行遍历，但是需要增加一个参数row来标记当前行数，如果是偶数行，则每次将值放入vector的末尾；如果是奇数行，则每次将值插入vector的第一个位置。代码/*st...
2018-05-04 18:13:03
739
1
原创 剑指Offer——从上往下打印二叉树
题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。解题思路本题需要借助队列来完成，每一次打印一个结点的时候，如果该结点有子节点，把该结点的子节点放到队列的尾。接下来到队列的头部取出最早进入队列的结点，重复前面打印操作，直到队列中所有的结点都被打印出为止。以如下二叉树为例:1 82 / \3 ...
2018-05-04 16:43:32
209
原创 剑指Offer——栈的压入、弹出序列
题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）解题思路需要借助一个辅助栈，i，j分别为pushV和popV当前值的下标，依次对需要压进栈的值...
2018-05-04 11:09:14
163
原创 剑指Offer——包含min函数的栈
题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。调用min、push及pop的时间复杂度都是O(1)。方法一考虑使用两个栈，一个数据栈（就是普通的栈），实现栈的push、pop等操作；另一个辅助栈用来存放每次栈操作时（包括入栈和出栈）栈中最小元素。辅助栈的操作：栈顶元素为当前栈中的最小元素要获取当前栈中最小元素，只需要返回栈顶元素即可；每次执行push操作，检查pus...
2018-05-03 22:43:28
139
原创 剑指Offer——对称的二叉树
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。例如下图中第一个树是对称的，而第二个不是。解题思路1、二叉树的镜像：二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 ...
2018-05-03 20:59:40
124
原创 剑指Offer——二叉树的镜像
题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5解题思路分析这两棵...
2018-05-03 18:22:09
115
原创 剑指Offer——树的子结构
题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）解题思路要查找树A中是否存在和树B结构一样的子树，我们可以分成两步： Step1：在树A中找到和B的根结点的值一样的结点R； Step2：判断树A中以R为根结点的子树是不是包含和树B一样的结构。当在树A中找到与B的根节点的值相同的节点R，则跳到step2判断树A中以R为根结点的子树是不是包含和树B...
2018-05-03 17:57:35
105
原创 剑指Offer——顺时针打印矩阵
题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.方法一按照右、下、左、上的顺序依次打印，将已经遍历过的...
2018-05-02 23:01:22
123
原创 剑指Offer——合并两个排序的链表
题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。方法一新建一个链表，遍历两个输入的链表，进行节点值的比较，新建链表的next指向值较小的节点。代码/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }...
2018-05-02 21:08:25
108
原创 剑指Offer——反转链表
题目描述输入一个链表，反转链表后，输出链表的所有元素。解题思路可以使用3个指针，分别指向当前遍历到的结点（指针cur）、它的前一个结点（指针pre）及后一个结点（指针next）。在遍历过程中，首先记录当前节点的后一个节点，然后将cur->next=pre，再令pre=cur，cur=next，如此反复，直到当前节点的后一个节点为NULL时，则代表当前节点时反转后的头结点了。代码/*stru...
2018-05-02 20:05:46
116
原创 剑指Offer——链表中环的入口结点
题目描述一个链表中包含环，请找出该链表的环的入口结点。方法一：对链表进行遍历，利用set等结构，将已经遍历过的节点存入set，每遍历一个节点，判断set中是否已经存在该节点，如果存在，那么说明链表存在环，且该节点就是入口节点，返回该节点；如果遍历到NULL，说明已经到了链表结尾，说明该链表不存在环，返回NULL。代码/*struct ListNode { int val; str...
2018-05-02 17:26:23
128
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人