曲小鑫-CSDN博客

原创排序算法总结

本文将给出六大经典排序的实现。简单排序算法：冒泡，插入，选择改进排序算法：快排，归并，堆排以下排序用到的交换函数：void swap(int &A, int &B) { int temp = A; A = B; B = temp;}1. 冒泡排序2个相邻的元素相互比较，不满足顺序则交换；每遍历一次数组，使一个元素处于最终位置。时间复杂度O(n2)O(n^2) 空间复杂度O(1)

2015-07-28 15:51:53 1005

原创二叉树各种操作的总结

求二叉树中的节点个数求二叉树中叶子节点的个数求二叉树的深度求二叉树第K层的节点个数递归遍历前序中序后序非递归遍历前序中序后序层序1 前序遍历2 中序遍历3 后序遍历4 层序遍历将二叉查找树变为有序的双向链表判断两棵二叉树是否结构相同判断二叉树是不是平衡二叉树判断二叉树是否是搜索二叉树求二叉树中两个节点的最低公共祖先节点求二叉树中节点的最大距离由前序遍历序列和中序遍历序列重建二叉树

2015-07-26 11:43:48 5674 1

原创 key-value 多线程服务器的Linux C++实现

项目需求总体思路网络通信字符解析数据存储与查询1 存储管理2 数据查询多线程待改进GitHub源码项目需求设计一个基于Socket或基于HTTP的服务器，服务内容是提供一种简单的key/value映射关系的管理与查询下面的所有操作都是通过结构体Node来传递的： struct Node { char key[KEY_SIZE];

2015-07-17 15:09:58 2502

原创基于文件页的 LRU Cache：磁盘缓存实现

基于文件页的 LRU Cache：磁盘缓存实现1. 功能需求本文链接：http://blog.csdn.net/quzhongxin/article/details/46700787在服务器实现过程中，服务端需要接受客户端的get和put两种操作， put(key, value): 在接收一定数量的数据后需要将数据保存到磁盘上，并且需要检查是否存在相同的key； get(key): 向服务端查询

2015-06-30 21:35:24 2094

原创 C/C++ 知识点总结

静态编译与动态编译malloc和new的区别关于STL中的map和hash_mapSTL 中的 set 和 mapstatic作用extern 的作用struct 和 class 区别堆和堆栈内存重载Overload Override 和 Overwrite排序算法的时空复杂度稳定性分析如何选择排序算法CC内存泄露和检测7JAVA的垃圾回收机制C派生类对象的初始化如

2015-09-30 21:49:54 11215 3

原创操作系统和网络面试总结

以下关于TCP/IP的总结均来自：TCP三次握手/四次挥手详解1. TCP/IP 分层应用层：ftp, e-mail,http,dns 传输层：tcp, udp 网络层：IP, ARP 链路层：驱动程序和网卡，交换机OSI分层：第7层应用层(Application Layer) 提供为应用软件而设的界面，以设置与另一应用软件之间的通信。例如: HTTP，HTTPS，FTP，TELNET，

2015-09-30 21:47:21 6861

原创扑克牌大小，错误统计，给出最高分

扑克牌大小最高分是多少简单错误记录2016华为笔试题：1. 扑克牌大小扑克牌游戏大家应该都比较熟悉了，一副牌由54张组成，含3~A，2各4张，小王1张，大王1张。牌面从小到大用如下字符和字符串表示（其中，小写joker表示小王，大写JOKER表示大王）:) 3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER 输入两手牌，两手牌之间用“-”连接，每手牌的每张牌以空

2015-09-03 21:51:52 1543

原创二分查找的递归和非递归实现，二分查找的扩展

凡是有序数组中的查找问题，都应该联系二分查找解决1. 递归实现// 递归二分查找int BinarySearch(int nums[], int left, int right, int key) { if (left > right) { return -1; } int mid = left + ((right - left) >> 1); if

2015-08-31 22:24:52 1674

原创 memcpy, strcpy, strlen, strcmp, itoa, atoi 的函数实现

不使用库函数，实现 memcpy, strcpy, strlen, strcmp, itoa, atoi. 本文地址： 1. memcpy内存拷贝函数。函数原型void *memcpy(void*dest, const void *src, size_t n); // n 为字节数注意问题： 1. 判断输入地址有效性 2. 将src，dst 指针强制转换成字符型指针，逐字节复制 3.

2015-08-31 16:50:38 1255

原创 C/C++ 实现可变参数的函数

头文件： C #include <stdarg.h> C++ #include <cstdarg>C函数要在程序中用到以下这些宏:void va_start( va_list arg_ptr, prev_param ); type va_arg( va_list arg_ptr, type ); void va_end( va_list arg_ptr );va_list: 变长参数列表的

2015-08-31 09:11:18 890 1

原创多方法实现 swap 2 个 int 变量的值

最常用方法是用临时变量保存备份值void swap(int &x, int &y){ int temp = x; x = y; y = temp;}不使用临时变量，方法是：按位异或及四则运算实现#include <iostream>#include <limits>using namespace std;void swap(int &x, int &y){

2015-08-30 20:08:52 1053

原创单向链表排序：快速排序和归并排序

归并排序改变链接快速排序改变链接快速排序改变节点值所有源码和测试函数对单向链表的排序有2种形式，只改变节点的值和只改变链接// 节点struct ListNode { int val; ListNode* next; ListNode(int v, ListNode* n = NULL) { val = v; next = n;

2015-08-29 15:22:36 5533

原创寻找和为定值的多个数

问题： 1. 找出一个序列中和为sum的两个数 2. 找出一个序列中和为sum的多个数（不限个数） 3. 找出一个序列中和为sum的4个数解析：1. 找出一个序列中和为sum的两个数将序列排序用左右2个指针指向序列的头部和尾部如果当前2个指针指向数的当前和等于sum，则这两个数是一个结果；如果当前和小于sum，说明当前和应该大一点，则将左指针右移 1 位；如果当前和大于sum，说明当前和

2015-08-25 09:47:08 1732

转载理解 Linux 的硬链接与软链接

概括：硬链接：具有相同索引节点号和数据块，仅文件名不同的文件；软链接：具有自己的索引节点号和数据块，只是数据块中放的是另一个文件的文件名。原文链接：http://www.ibm.com/developerworks/cn/linux/l-cn-hardandsymb-links/理解 Linux 的硬链接与软链接从 inode 了解 Linu

2015-08-24 14:48:01 823

原创 C++多线程学习：生产者消费者问题

多线程相关知识点：C++11 线程库：http://zh.cppreference.com/w/cpp/thread互斥量和锁 std::unique_lock::lock 和 std::unique_lock::unlock 上锁操作，调用它所管理的 Mutex 对象的 lock 函数。如果在调用 Mutex 对象的 lock 函数时该 Mutex 对象已被另一线程锁住，则当前线程会被阻

2015-08-19 20:56:01 16262 1

原创 C/C++ 中的特殊关键字：volatile, register, restrict, attribute

1.volatile：告诉编译器i是随时可能发生变化的，每次使用它的时候必须从i的地址(内存)中读取，而不会使用寄存器中的缓存值；volatile int i=10; 2.register：使用修饰符register声明的变量属于寄存器存储类型。该类型与自动存储类型相似，具有自动存储时期、代码块作用域和内连接。声明为register仅仅是一个请求，因此该变量仍然可能是普通的自动变量。无论哪种情况

2015-08-19 14:53:20 1883

原创按之字形顺序打印二叉树

题目描述：按之字形顺序打印二叉树请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。解析：要分层打印，不能用常规方法，访问一个节点后，将该节点的左右子节点压入队列。奇数层从左到右打印，偶数层从右向左打印。使用两个栈存储每一层的节点。在访问奇数层时，将奇数层的子节点，按先左后右的顺序将子节点压入偶

2015-08-18 16:59:24 1041

原创字符串匹配：KMP

参考：从头到尾彻底理解KMP 在字符串 str 中匹配模式串 pattern 1. 计算模式串的 next 数组； 2. 在字符串中匹配模式串；当一个字符匹配时，str[i++], pattern[k++] 继续匹配下一个字符；当当前字符不匹配时，根据 next 数组移动模式字符串，k = next[k] next 数组：描述模式串中最长相同的前缀和后缀的长度。#include <iostr

2015-08-17 16:45:09 861

原创树的子结构

面试题 16 - 树的子结构输入二叉树 A 和 B，判断 B 是不是 A 的子结构。解析：空树不是树的子结构。递归求解：如果母树 A 的当前节点等于 B 的根节点，则递归地对 A，B的左右子树分别判断是否满足子结构性质如果母树 A 的当前节点不等于 B 的根节点，则递归分别判断 A 的左右子节点，是否和 B 的根节点相等终止条件是：B 为 NULL，A 非NULL，B 是 A 的

2015-08-15 20:30:33 632

试题来源：http://www.nowcoder.com/test/151724/begin正在挑战一个CrackMe的你，把需要填写的前面几位密码都正确猜出了，可是这最后一位密码，好像藏得有点深。CrackMe的作者还挑衅般的在里面藏了个.tar.gz文件，解压缩出来，里面写道你要的最后一个字符就在下面这个字符串里。这个字符是下面整个字符串中第一个只出现一次的字符。（比如，串是abaccdeff

2015-08-13 16:46:35 2108 1

原创挑选镇长问题

试题来源：http://www.nowcoder.com/question/next?pid=151724&qid=25196&tid=718946360员工桂最近申请了一个长假，一个人背着包出去自助游了。　　路上，他经过了一个小镇，发现小镇的人们都围在一棵树下争吵。桂上前询问情况，得知小镇的人们正缺一个镇长，他们希望能选一个知名又公正的镇长，即，大家希望能选出一个人，所有人都认识他，但同时他不

2015-08-13 16:24:36 2477 1

原创如何求结构体成员的偏移地址 || 结构体的 sizeof 总结

C 语言中允许将值为 0 的变量强制转换成任一类型的指针，转换结果是一个NULL指针；(type*)0 // 一个 type 类型的NULL指针用这个指针访问结构体内的成员是非法的，但是&(((type*)0)->field)是为了计算 field 的地址，编译器不会产生访问 field 的代码，只会根据 type 的布局和起始地址在编译期计算这个地址（常量）。而又因为初始地址为 0，故该地址的值

2015-08-12 16:22:45 2899

转载你所不知道的传输层

原文链接：http://java-mzd.iteye.com/blog/1007577你所不知道的传输层题记：23页的文档上，满满当当的写满了笔记，纸质的东西，始终害怕丢失，还是选择把它总结到博客上来。PS.老规矩，列出可能遇到的20个问题，如果您是都能回答的高手，请您绕道，我是小菜，只做自己的学习笔记。 1. 传输层的主要功

2015-08-10 09:43:04 534

原创生成所有的出栈序列（回溯法）

给定一个入栈序列，找出所有可能的出栈序列。如入栈序列为 [1, 2, 3] 则可能的出栈序列为 : [ 3 2 1 ] [ 2 3 1 ] [ 2 1 3 ] [ 1 3 2 ] [ 1 2 3 ]采用回溯法和递归统计所有可能的出栈序列。当所有的入栈序列已经全部入栈后，则只能出栈当栈为空时，只能进栈当仍有入栈元素且栈不为空时，可以入栈，也可以出栈入栈 -> 递归处理下一个入栈元

2015-08-09 20:45:00 5283 4

原创 32 - 从 1 到 n 整数中 1 出现的次数

问题：给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。例如： N= 2，写下1，2。这样只出现了1个“1”。 N= 12，我们会写下1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。这样，1的个数是5。直观思路是，逐个计算出1 ~ N 这 N 个数含有 1 的个数。如 1 ~ 12345 ：判断最后 1 位是否为

2015-08-08 22:20:29 775

转载负数的带符号和不带符号的右移运算

原文链接：http://smufvgwy.iteye.com/blog/987608负数的移位操作和正数不一样，负数是按补码移位。当涉及到负数的移位时，一定要细心。左移是逻辑/算术左移(两者完全相同),右移是算术右移,会保持符号位不变负数的带符号和不带符号的右移运算博客分类： Java基础ITeyeJ# 多年没用过很基础的东西，对这些移位

2015-08-05 16:37:48 3110

原创费波那也数列的非递归实现

n =0, f(0) = 0;n = 1, f(1) = 1n > 1, f(n) = f(n-1) + f(n-2)使用 2 个临时变量，存储 n-1 和 n-2 的费波那也数； f(2) = f(0) + f(1) ，因此用f(2) 覆盖 f(0) ，因为 f(1) 仍然需要保留；即 f(0) = f(0) + f(1) f(3) = f(1) + f(2) , 因此用f(3) 覆盖

2015-08-05 15:44:47 1406

原创 8 - 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。看到排序相关的查找问题，想到二分查找。举例分析： {1, 2, 3, 4, 5} {5, 1, 2, 3, 4}; {4, 5, 1, 2, 3}; {3, 4

2015-08-05 14:49:22 620

转载快速排序分析

In general, the code you have is neat, and easy to follow. The QuickSort algorithm is relatively traditional, and the pieces I expect to see are about where I expect them to be.Let's go through th

2015-08-04 16:09:24 528

原创 67 - 机器人的移动范围

题目：地上有个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。　　例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+7=18.但它不能进入方格(35,38)，因为3+5+3+8=19.请问该机器人能够达到多少格子？和上一题66 - 矩阵中的路径类似，只是约束条件发生了改变。

2015-08-03 15:19:29 1134

原创 66 - 矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中间向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的 3*4 的矩阵中包含一条字符串“bcced”的路径。但矩阵中不包含字符串“abcb”的路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二格子之后，路径不能再次进

2015-08-03 11:30:33 921

原创 65 - 滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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,5,

2015-08-03 09:28:00 2955

原创 64 - 数据流中的中位数 || STL 堆

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。思路解析数据是从数据流读出，因此数组的个数是再逐渐的增加。如何选用一个容器，能够存储数据，并能够给出中位数。无序数组：插入O(1) partation操作找出中位数 O(n)有序数组：插入O(n) 找出

2015-08-02 17:12:14 1762

原创 59 - 对称的二叉树

判断一棵的。 1 / \ 2 2 / \ / \3 4 4 3递归地对比左子树的左节点和右子树的右节点 && 对比左子树的右节点和右子树的左节点bool isSysmmeticalCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) { if (pRoot1 == NULL && pRoot2 == NULL)

2015-08-02 11:04:56 524

原创 58 - 二叉树的中序遍历的下一个节点

题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历顺序的下一个节点？树中的节点除了由两个分别指向左右节点的指针外，还有一个指向父节点的指针。中序遍历：先访问当前节点的左子树，再访问当前节点本身，最后访问当前节点的右子树。因此：如果给定节点有右子树，则下一个节点是它的右子节点；如果给定节点没有右子树，需要向上找到一个祖父节点（它是自己父节点的左节点），该祖父节点的父节点就是下一个节

2015-08-02 10:48:01 1427

原创 57 - 删除链表中重复的节点

题目：在一个排序的链表中，删除重复的节点。如：1 -> 2 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5；删除之后：1 -> 2 -> 3 -> 4 -> 5解析：定义 prev，cur； prev = pHead; 向后找到一个不等于 prev 的 cur 节点。 prev->next = cur; 链接 prev 和 cur prev , cur 向后移动，

2015-08-01 22:10:22 938

原创 56 - 链表中环的入口节点

题目：一个链表中包含环，如何找出环的入口节点？例如 1->2->3->4->5->6->(3) ; 的链表中，环的入口及诶到哪是节点 3。解析：首先找到链表中的环：定义2个指针，一个快指针一次走2步，一个慢指针一次走1步，如果2个指针能够相遇，证明有环。统计链表中环的长度：从相遇指针开始，固定 1 个指针，另一个指针从相遇指针走，当2个指针再次相遇时，即走了 1 圈，得到环的长度 l

2015-08-01 21:22:55 584

原创 55 - 字符流中第一个不重复的字符

当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时，第一个只出现 1 次的字符是”l”。首先要记录一个字符出现的次数，为了实现O(1)查找，使用简易hash表存储。用occurences[256] 记录字符出现的次数。设置： occurences[i] = 0, 该字符未出现； occurences[i] = 1, 该字符出现一

2015-08-01 16:57:30 969

原创 54 - 判断字符串是否是数值

面试题 54 - 表示数值的字符串请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。如： “-23.14e+12”, “600.”，”-.123” 都是数值; “+”，”12e” 不是数值。一个

2015-08-01 15:46:18 1175 1

原创 53 - 正则表达式匹配

题目：请实现一个函数用来匹配包含‘.’和‘*’的正则表达式。模式中的字符’.’表示任意一个字符，而‘*’表示它前面的字符可以出现任意次（含0次）。本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串“aaa”与模式“a.a”和“ab*ac*a”匹配，但与“aa.a”及“ab*a”均不匹配。解析：字符串 str = “aaa”; 模式字符串 pattern = “.b*ac*a” 每次分别

2015-08-01 11:48:32 769