- 博客(74)
- 资源 (1)
- 收藏
- 关注
RSS订阅转载 Linux文件属性以及链接
今天说的这个命令，不是经常用，但是只要配置环境，这个命令就离不开我们，尤其是同一环境不同版本同时存在的时候，今天我们就一起研究一下这个命令的具体使用方法和一些常见的使用场景。 ln是linux中又一个非常重要命令，它的功能是为某一个文件在另外一个位置建立一个同步的链接.当我们需要在不同的目录，用到相同的文件时，我们不需要在每一个需要的目录下都放一个必须相同的文件，我们只要在某个固定的目录，放上该...
2018-07-05 22:07:50
1111
原创 通配符和正则表达式
正则表达式：主要针对文件内容，文本过滤工具awk，sed中常用到 通配符:主要用于文件名，在管道命令中常用。find，ls,cp等命令 通配符是系统level的 而正则表达式需要相关工具的支持: egrep, awk, vi, perl，sed等 正则表达式（也称为“regex”或“regexp”）是一种用来描述文本模式的特殊语法。在 Linux 系统上，正则表达式通常被用来查找文本的模式，...
2018-06-22 18:32:31
453
原创 二维数组查找
在一个二维数组中每一行从左到右按照递增排序。每一列从上到下按照递增顺序排列。给定一个数字，在数组中查找这个数字，如果能找到则返回true，如果找不到则返回false1. bool Find(int target,vector<vector<int>> array) 2. { 3. int row=array.size();//计算行数 4. ...
2018-06-05 23:06:53
214
原创 空格替换
空格替换为 %20（1） 遍历字符串统计空格的个数n，以及字符串的长度len。 （2） 每增加一个空格字符串长度增加2，则替换后字符串长度为len1=len+2*n。 （3） 设置两个指针，一个指向原来字符串末尾len处，一个指向替换后总长度的末尾len1处。 （4） p1向前移动依次把经历的字符串放置p2所指位置，p2赋值后前移一位，直到p1遇到空格，此时p2处插入%20并前移三个。然...
2018-06-05 23:05:44
161
原创 按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。思路：采用树的广度优先搜索策略 借助两个栈：一个用来实现从左到右输出，一个用来实现从右到左输出，利用栈的先入后出顺序，不同的层时左右子树入栈的顺序不同，应该与其应出栈顺序相反/*struct TreeNode { int val;...
2018-05-29 23:05:33
146
原创 翻转单词顺序列
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？思路：先反转整个字符串，然后根据...
2018-05-29 22:09:04
160
原创 链表——剑指offer
从尾到头打印链表 思路：先把链表翻转，然后将翻转后的链表打印出来 这种方法:因为多分配链表节点指针，故可能会对内存的消耗要大一点 时间复杂度为O（n）vector<int> printListFromTailToHead(listnode *head){vector<int>a;listnode *p=NULL;listnode *p1=NULL;...
2018-05-23 20:23:28
186
原创 图的深度优先遍历和广度优先遍历
BFS思路广度优先遍历中从一个节点出发，例如1，先找到其邻接至的节点，如2,3,4然后依次把2,3,4放入队列，再从队列中依次取出每一个节点，找到其邻接至的节点插入到队列尾部最终当队列中元素为空时就找到了1可以到达的所有路径代码：virtual void bfs(int v,int reach[],int label)//所有图的表示方法都可以直接用的广度优先搜索方法...
2018-05-22 23:13:09
324
原创 对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路：对称的二叉树中左子树的左孩子等于右子树的右孩子，左子树的右孩子等于右子树的左孩子 而且当左右子树中有一个为空时就不会是对称/*struct TreeNode { int val; struct TreeNode *left; struct Tree...
2018-05-21 23:30:49
125
原创 Fibonacci数列
题目描述Fibonacci数列是这样定义的： F[0] = 0 F[1] = 1 for each i ≥ 2: F[i] = F[i-1] + F[i-2] 因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为...
2018-05-19 22:23:31
238
原创 把字符串转换成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0class Solution {public: int StrToInt(string str) { int flag = 1; //设置符号标志 long long ret = 0; //考虑到返回值可能较大，定义为long lon...
2018-05-12 23:12:54
151
原创 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。class Solution {public: void ScanString(char * &amp;number)//此处传入的...
2018-05-12 22:51:43
139
原创 左旋字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！分析：对于字符串左旋，实质为字符串旋转。对形如XY的字符串经过旋转后变为YX.此问题中，字符串左旋：n为旋...
2018-05-12 18:58:37
176
转载 Linux内存分配与释放：一
Linux的虚拟内存管理有几个关键概念：Linux 虚拟地址空间如何分布？malloc和free是如何分配和释放内存？如何查看堆内内存的碎片情况？既然堆内内存brk和sbrk不能直接释放，为什么不全部使用 mmap 来分配，munmap直接释放呢 ？Linux 的虚拟内存管理有几个关键概念： 1、每个进程都有独立的虚拟地址空间，进程访问的虚拟地址并不是真正的物理地址； 2、虚拟地址...
2018-05-10 18:00:17
9679
2
原创 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路：中序遍历整棵树。那么比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了/*struct TreeNode { in...
2018-05-10 00:23:45
112
原创 利用递归返回数组中的最大值
int theMax(int a[],int n){int t;if(n>1){t=f(a,n-1);return t>a[n-1]?t:a[n-1];}elsereturn a[0];}
2018-05-05 22:22:25
837
原创 删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : ...
2018-05-05 22:18:54
96
原创 和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!class Solution {public:...
2018-05-05 22:17:24
120
原创 和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。class Solution {public: vector<int> FindNumbersWithSum(vector<int> array,int sum) { //思路：首先查找数组中所有和为s的组合，然后计算...
2018-05-05 22:11:30
109
原创 构建乘积数组
题目描述 给定一个数组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]。不能使用除法。方法一：时间复杂度为O（n2）class Solution {public: vector<int> multiply(const vector<int>&...
2018-05-05 22:10:13
117
原创 网易： 被3整除
小Q得到一个神奇的数列: 1, 12, 123,…12345678910,1234567891011…。并且小Q对于能否被3整除这个性质很感兴趣。小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。 ## 输入描述: 输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。输出描述: 输出一个整数...
2018-05-04 23:01:28
496
原创 网易：安置路灯
小Q正在给一条长度为n的道路设计路灯安置方案。为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。 ## 输...
2018-05-04 23:00:25
156
原创 网易：迷路的牛牛
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他输入描述: 每个输入包含一个测试用例。 每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。 接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。输出描述: 输出牛牛最后面向的方向，N表示北，S表示南，E...
2018-05-04 22:58:04
179
原创 平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。平衡二叉树为：每一个节点的左右子树高度差都小于等于1.空树为平衡树 先序遍历每一个节点，并计算其左右子树的高度差class Solution {public: bool IsBalanced_Solution(TreeNode* pRoot) { //平衡二叉树的左右子树高度差小于1,所以首先求二叉树的高度 ...
2018-04-26 23:53:26
122
原创 二叉树的下一个结点
题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路：中序遍历顺序为：左->根->右判断是否有右子树，如果有那么下一个节点为其右子树的最左节点，如果没有右子树节点，那么该节点移动到其父节点（此处有指针直接指向父节点）。当该节点不是其父节点的右子树的时候，那么该节点就是所求。...
2018-04-26 23:27:30
93
原创 把数组排成最小数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。思路分析：对数组进行全排列，然后排序，此方法时间复杂度较高把数组转为字符串数组，定义字符串数组的一种排序规则，不是把小的数排在前边，而是两个字符串链接起来，nm，mn当nm<mn则n排在前边，否则n排在后边class ...
2018-04-16 23:22:44
128
原创 整数中1出现的次数
思路：对于整数中出现1的次数，可以考虑利用取余和除法运算来求得。采用暴力循环。对每一个数的每一位利除10取余来取得对于任何数字出现的次数都可以利用这种方法求得，只不过余数要等于对应的数字X；class Solution {public: int NumberOf1Between1AndN_Solution(int n) { int temp; int co...
2018-04-10 23:20:39
134
原创 数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。思路：一个数组中只出现一次，考虑位运算符：抑或；抑或的结果为，相同位为0，不同位为1.所以如果两个数相等时那么抑或结果为0，且0与任何一个数抑或的结果都为原数。故当数组中只有一个数出现一次时，可以从头到尾抑或数组的每一个元素，最后的结果一定是唯一的数。当数组中有两个数只出现一次时，按照上述办法抑或的结果为这...
2018-04-09 23:07:08
320
原创 堆排序
（1）堆排序为选择排序的一种，适合于大量数据的排序，不稳定的算法，时间复杂度为O（logn）；（2）大根堆为一个完全二叉树，根节点的关键字值大于子节点，整个树的根节点为最大值，用数组表示R[1....n]，R[1]为最大，将R[1]和R[n]互换，但此时从1到n-1依然是无序。需要对其进行重新调整处理；（3）建堆-》取首元素-》调整为大根堆//堆排序void HeapSort(int A[], ...
2018-04-04 17:13:18
94
原创 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
二叉搜索树的左子树节点小于根节点小于右子节点二叉搜索树的后序遍历序列中根节点一定在数组的最后一个位置可以把序列分为两部分，分别代表根节点左子树和右子树，然后对新形成的序列继续递归判断可得到结果class Solution {public: bool VerifySquenceOfBST(vector<int> sequence) { int len=sequ...
2018-04-03 23:15:29
1726
原创 树的子结构
/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: bool HasSubtree(TreeNode* p...
2018-04-02 23:45:49
82
原创 二叉树中和为某一值的路径
思路：建立一个二维数组，其中每一行代表一条路径；用一个一维数组统计每次的路径，统计结束后放到二维数组中；当满足结点值和相等并且节点为叶节点时满足条件，把此条路径加入；利用递归实现/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), l...
2018-04-01 16:47:56
90
原创 重建二叉树
问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。思路分析：利用循环和递归（1）在前序遍历序列中第一个元素一定为整个树的根节点（2）中序遍历中与此元素相等的元素之前的元素属于整个树的左子树，之后元素属于右...
2018-03-28 23:16:46
80
原创 字符串匹配
在文本中查找对应的模式成为字符串匹配：文本：T模式：P一：朴素的字符串匹配算法思路：（1）首先有两个游标i，j指向文本和模式的位置（2）当T[i]=P[j]时i++，j++，继续往下比较。（3）当T[i]！=P[j]时，i回溯到上次开始比较的下一位，j回溯到0（4）当找到一段连续的字符与模式字符串匹配最终模式字符串匹配成功，返回此次开始比较的文本位置。int native_stringmatch(...
2018-03-28 21:47:51
173
原创 链表环
第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x;n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2;此时p1指向环的入口...
2018-03-26 23:05:30
110
原创 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在
class Solution {public: int MoreThanHalfNum_Solution(vector<int> numbers) { int x; int y=numbers.size();//当数组为空时返回0 if(y==0)return 0;//当数组只有一个元素时返回其 if...
2018-03-24 22:18:47
166
原创 从上往下打印出二叉树的每个节点，同层节点从左至右打印
思路：首先从头结点开始，因为一层一层的读取，每读一个节点时，要记录其左右子节点，下一个读取的为其左子节点，然后再次读取其右子节点，所以要存入一个队列依次，然后每次从队列头去节点读取值 int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NU...
2018-03-23 22:49:59
595
原创 已知一个栈的入栈序列，判断给定的一个序列是否为其出栈序列
思路：（1）栈为后入先出序列（2）将入栈序列的元素一个一个入栈然后和出序列中每个元素比较。取序列第一个元素时，把第一个序列的各个元素依次入栈，然后入栈一个后和序列元素比较，如果相同那么将这个元素出栈，并且与序列的第二个元素再进行比较bool IspopOrder(vector<int> pushv,vector<int> popv){bool isPop=false...
2018-03-23 21:48:24
2377
原创 二叉树
二叉树的镜像利用栈实现void MirrorNonRecurively(BinaryTreeNode *pNode) { if(NULL == pNode) return; stack<BinaryTreeNode *> stackTreeNode; stackTreeNode.push(pNode); while(stac...
2018-03-20 21:30:33
143
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人