cyxHehui-CSDN博客

原创 TCP 连接状态

主要列出两个TCP状态迁移图，以供需要的时候参考：

2016-01-10 19:30:15 554

转载 C++的内存管理

这篇文章是我在学习高质量C++/C编程指南中的第7章"内存管理"后的一篇笔记,之前我也写过相关的文章指针以及内存分配,但我感觉那篇还不是很好,这篇我很把它更完善一些一.内存的常见分配方式 1. 从静态区分配,一般是全局变量和static类型变量 2.从栈区分配内存,一般是局部的变量,会随着所在函数的结束而自动释放 3.从堆中分配,一般是使用手动分配,使用malloc(

2014-02-24 13:36:35 752

原创进程与线程

1、基本概念：进程：程序在一个数据集上的一次运行过程。是操作系统资源分配的基本单位。进程又被细化为线程。也就是一个进程下有多个能独立运行的更小单位。进程还拥有一个私有的虚拟地址空间，该空间仅能被它所包含的线程访问。线程：是进程中的一个实体。是被操作系统独立调度和执行的基本单位。一个进程包含一个或多个线程。进程是执行实体，是资源分配的基本单位；而线程是处理机调度的

2014-02-24 11:24:03 801

转载一致性哈希算法

tencent2012笔试题附加题问题描述：例如手机朋友网有n个服务器，为了方便用户的访问会在服务器上缓存数据，因此用户每次访问的时候最好能保持同一台服务器。已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器，这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了，那么n就变为了n-1，那么ServerIPIndex[QQNUM%

2014-02-22 22:18:54 714

转载程序员编程艺术--7、全排列，跳台阶，奇偶调序

1、字符串的排列。题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab 和cba。分析：此题最初整理于去年的微软面试100题中第53题，第二次整理于微软、Google等公司非常好的面试题及解答[第61-70题] 第67题。无独有偶，这个问题今年又出现于今年的

2014-02-22 22:15:47 957

原创程序员编程艺术--->6、关于链表的追赶问题

本章主要涉及链表的相关检测问题，诸如：链表的倒数第k个结点检测链表是否带环两链表是否相交而此类问题，如果用直观的想法去做的话，无疑时间复杂度不太可观，因此可以继续寻求更加的解决方案。下面就这些问题展开来谈。1、求链表的倒数第k个结点解析：（1）两次遍历链表，第一次求出链表的长度，第二次找出n-k个结点，便是倒数第k个结点。（2）既然要尔链表的倒数第k

2014-02-22 21:22:21 663

原创程序员编程艺术---5、寻找满足和为定值的两个或多个数

1、寻找和为定值的两个数题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的数字。解析：（1）可以用穷举法，从数组中任取两个数，看其和是否是该数字。但是O(N)=O(n^2)(2)可以同时从数组首元素a[i] 和尾元素a[j] 之和遍历，如果>sum,j--; 如果#include "stdafx.h"#include using namespace s

2014-02-22 17:08:05 1775

转载程序员编程艺术---4、常用字符串函数的编写

第一节、字符串查找1.1题目描述：给定一个字符串A，要求在A中查找一个子串B。如A="ABCDF"，要你在A中查找子串B=“CD”。分析：比较简单，相当于实现strstr库函数，主体代码如下：char strStr(char *string ,char *subString){ int length1 = strlen(string); int length2

2014-02-22 10:27:46 825

原创程序员编程艺术--2、字符串包含问题

题目描述：假设这有一个各种字母组成的字符串A，和另外一个字符串B，字符串里B的字母数相对少一些。什么方法能最快的查出所有小字符串B里的字母在大字符串A里都有？比如，如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPO答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：

2014-02-21 21:16:40 654

原创程序员编程艺术----1、左旋转字符串

题目描述：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转两位得到字符串cdefab.请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O（1）。方法1：直接移位法。void ShiftString(char *str, int length, int m){ char tmp; for(i

2014-02-21 20:22:37 599

原创 2014年华为机试试题

一、题目描述（60分）：通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“abacacde”过滤结果为“abcde”。要求实现函数：void stringFilter(const char *pInputStr, long lInputLen, char *pOutputStr);【

2014-02-21 17:05:05 772

原创 NYOJ 163 Phone List

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=163如：给出三组phone numbers,Emergency 911Alice 97 625 999Bob 91 12 54 26判断较短的phone number是否是这组numbers中的一条或多条的前缀。也是判断一组字符串中，是否存在某一字符串是其它字符串的前缀。这里较

2014-02-21 11:27:00 636

原创字典树详解----串查找、排序、公共前缀之杀手锏

1、字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变形。典型应用是用于统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计。它的优点是利用最大公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。2、性质根节点不包含字符，除根节点以外的每

2014-02-21 11:15:57 6703

原创 NYOJ 138 找球号

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=138题目描述：描述在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，还有一个空箱子，现在有两种动作：一种是"ADD"，表示向空箱子里放m(0<m<=100)个球，另一种是"QUERY”，表示说出

2014-02-20 11:27:24 922 1

原创 Hash结构详解

1、什么是Hash Hash，即”散列“，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换也是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，因此不可能从散列值来唯一确定输入值。简单地说就是将一种任意长度的消息压缩成某一固定长度的消息摘要的函数。 HASH主要用于信息安全领域中加密算法，它把一

2014-02-20 11:00:06 15168 4

转载二叉树相关算法总结

一、二叉树的遍历-前序、中序、后序以及层次遍历（递归与非递归）参考另外一篇笔记《二叉树的遍历-递归与非递归 -海子 - 博客园》。二、重建二叉树，依据前序遍历结果和中序遍历结果《剑指Offer》面试题6. 前、中；后，中-----》均可以重建二叉树，但是前、后则不行，给出“前、后”序列只能判断父子关系，而不能区分左子树和右子树。思想：递归代码：// 《剑

2014-02-13 19:31:13 1694

转载 C++-----虚析构函数

我们知道，用C++开发的时候，用来做基类的类的析构函数一般都是虚函数。可是，为什么要这样做呢？下面用一个小例子来说明：有下面的两个类：class ClxBase{public: ClxBase() {}; virtual ~ClxBase() {}; virtual void DoSomething() { cout

2013-12-27 09:10:25 536

原创 C++---之inline

C++背景在C&C++中一、inline关键字用来定义一个类的内联函数，引入它的主要原因是用它替代C中表达式形式的宏定义。表达式形式的宏定义一例：#define ExpressionName(Var1,Var2) ((Var1)+(Var2))*((Var1)-(Var2))为什么要取代这种形式呢，且听我道来：1．首先谈一下在C中使用这种形式宏定义的原因，C语言是

2013-12-19 22:18:28 580

原创查找字符串中第一个只出现一次的字符

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。析：可以用一种简单的hashTable结构来解决这一问题，以字符所对应的ASCII码值作为key,以该字符出现的次数作为value。遍历完字符串的，hashTable中便存储了所有字符出现的次数。然后，再依次查找字符串中字符出现的次数，返回次数等于1的即可。// 13_第一个只出现一次的字符.cpp

2013-12-03 19:19:45 895

原创查找单链表的第k个结点

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：struct ListNode{ int m_nKey; ListNode* m_pNext;};解析：方案一：可以对单链表来个逆置，然后再取逆置后的单链表的第k个元素。但是这样，在逆置的过程中涉及到大量的插入和删除的工作，实为不佳的

2013-12-03 16:14:43 1382

原创翻转字符串中单词的顺序

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。#include "stdafx.h"#include using namespace std;void Reverse(char *pBe

2013-12-03 15:17:38 1738

原创查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。例如：输入1，2，3，4，5，6，7，8，则最小的4个数是1，2，3，4。分析：采取一般的排序算法，如快速排序，堆排序，归并排序，等，先将这n个整数进行排序，然后再取最小的k个。那么时间复杂度为nlgn。我们可以从数组中取k个元素，建一个k个元素的最大堆，继续从数组里面取出元素，如果该元素大于堆中最大元素，那么舍弃，继续；如果小

2013-12-03 14:36:03 1017

转载海量数据处理------Bloom filter

1. Bloom-Filter算法简介 Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。 Bloom Filter（BF）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filt

2013-12-02 20:38:44 1091

转载海量数据处理----Bit map算法详解

1. Bit Map算法简介来自于《编程珠玑》。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。2、 Bit Map的基本思想我们先来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序

2013-12-02 20:26:02 834

原创 B树的原理分析及实现

B树是为磁盘或其他直接存取的辅助设备而设计的一种平衡搜索树。许多数据库系统使用B树或B树的变种来存储信息。为何会采用这种树结构进行设计呢，《算法导论》18章讲得很到位，值得细细品味。下面直接开始了解B树的实现细节吧！一、B树的定义它与二叉搜索树和红黑树一样，把卫星数据和关键字都存放在同一个结点中。 1、每个结点的属性：（1）x.n: 每个结

2013-11-26 22:11:04 9747 4

原创红黑树的解析与实现

红黑树上一篇中讲到，一棵高度为h的二叉搜索树，它所进行的操作都可以在O(h)时间内完成。因此搜索树的高度较低时，可以较快的完成。但是，如果树的高度较高时，这些集合操作可能并不比链表上快。如何实现一种搜索树的结构，使得其任何一种基本操作都可以在O(lgn)的时间内完成呢？红黑树，就是这种“平衡”搜索树中的一种。可以保证最坏的情况下，基于动态集合操作的时间复杂度为O(lgn)。

2013-11-26 19:22:32 701 1

原创 C++中几个重要的概念（一）

我们先来读一小段代码吧，从而引出几个概念：template class PFArray{public: PFArray(); PFArray(int capacityValue ); PFArray(const PFArray& copyArray); void addElement(int element); bool isfull() const {return (use

2013-11-26 11:08:58 1906

原创二叉查找树的原理与实现

二叉查找树，又名二叉搜索树，主要性质：左孩子二叉查找树上的基本操作包括：search, minimum, maximum, predecessor, successor, insert, delete. 而这些操作基本所花费的时与这棵树的高度成正比。对于一棵完全树来说，这些操作的最坏运行时间为：O(lgn)，而对于n个结点连成一条线的树来说，则为O（n)。那如何才能保证所有的基本操作复杂度控

2013-11-26 09:59:31 1028

原创二叉树的C++实现

关于二叉树的实现直接贴代码吧：// BinaryTree_Class.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include "stdafx.h"#include #include#include using namespace std;templatestruct _BinNode{ T data; struct _B

2013-11-25 19:36:57 722

转载 posix_memalign详解

转载：http://hi.baidu.com/freelonely/blog/item/340341077c4d287302088189.html预对齐内存的分配在大多数情况下，编译器和C库透明地帮你处理对齐问题。POSIX 标明了通过malloc( ), calloc( ), 和 realloc( ) 返回的地址对于任何的C类型来说都是对齐的。在Linux中，这些函数返回的地址在

2013-11-22 22:04:55 6819 2

转载线程的终止方式：pthread_cleanup_push, pthread_cleanup_pop()

以下内容根据【1】进行整理。关于取消点，将在后面进一步讨论。1、一般来说，Posix的线程终止有两种情况：正常终止和非正常终止。线程主动调用pthread_exit()或者从线程函数中return都将使线程正常退出，这是可预见的退出方式；非正常终止是线程在其他线程的干预下，或者由于自身运行出错（比如访问非法地址）而退出，这种退出方式是不可预见的。2、线程终止时的清理不论是可预见

2013-11-19 08:40:56 860

转载 Linux多线程，线程的分离与集合

（2）线程的分离与结合在任何一个时间点上，线程是可结合的（joinable），或者是分离的（detached）。一个可结合的线程能够被其他线程收回其资源和杀死；在被其他线程回收之前，它的存储器资源（如栈）是不释放的。相反，一个分离的线程是不能被其他线程回收或杀死的，它的存储器资源在它终止时由系统自动释放。线程的分离状态决定一个线程以什么样的方式来终止自己。在上面的例子中，我们采用了

2013-11-19 08:34:01 887

转载 Linux多线程，基本概念

一、Linux多线程，基本概念说明：以下内容，根据参考中【1~6】内容整理而得。一、基本概念1、线程是计算机中独立运行的最小单位。进程是分配资源的单位。2、为什么使用多线程？（1）启动一个新的进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段、堆栈段和数据段，这是一种"昂贵"的多任务工作方式。而运行于一个进程中的多个线程，它们彼此之间使用相同的地址空间，共享大部分

2013-11-19 08:26:18 733

转载 pthread_cancel引起的死锁

说明：本文由【2,3】整理而得。这篇文章主要从一个 Linux下一个pthread_cancel函数引起的多线程死锁小例子出发来说明 Linux系统对 POSIX线程取消点的实现方式，以及如何避免因此产生的线程死锁。目录：1.一个pthread_cancel引起的线程死锁小例子2.取消点(Cancellation Point)3.

2013-11-19 08:07:53 1079

原创 linux线程同步之读写锁

读写锁与互斥量类似，不过读写锁的并行性更高。读写锁可以有三种状态：（1）读模式加锁；（2）写模式加锁；（3）不加锁。在写加锁状态时，在解锁之前，所有试图对这个锁加锁的线程都会被阻塞。在读加锁状态时，所有试图以读模式对它进行加锁的线程都可以得到访问权限。但是如果线程希望以写模式加锁，它必须阻塞，直至所有的线程释放读锁。读写锁很适合于对数据结构读的次数远大于写的情况。相关函数：

2013-11-13 19:54:46 4539 1

翻译 linux 线程同步之条件变量

与互斥锁不同，条件变量是用来等待而不是用来上锁的。条件变量用来自动阻塞一个线程，直到某特殊情况发生为止。通常条件变量和互斥锁同时使用。条件变量使我们可以睡眠等待某种条件出现。条件变量是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使"条件成立"（给出条件成立信号）。条件的检测是在互斥锁的保护下进行的。如果一个条件为

2013-11-13 19:01:04 620

原创 Skiing

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=10http://描述：下面是一个例子 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的

2013-11-04 20:44:14 609

原创最长公共子序列与字符串的相似度问题

字符串相似度与最长公共子序列字符串的相似性：如果将一个串转换成为另一个串所需的操作数最少，那么可以说这两个串是相似的。另外一种权衡的方法是，寻换第三个串s3，如果s3都出现在s1和s2中，且出现的顺序相同，但不要求在s1和s2中连续，那么s3的长度越大，就说明相似度越高。后一种对相似度概念命名为最长公共子序列。 1、最长公共子序列的特征

2013-11-04 14:37:36 3105

原创括号匹配

括号匹配问题题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=15http://给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。如：[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的分析：之所以采用动态规划方法去解这道

2013-11-04 09:19:23 732

原创最长递增子序列

最长递增子序列题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=17求一个字符串的最长递增子序列如：dabdbf最长递增子序列就是abdf，长度为4 这是一道基本的动态规划求解的题目，与此类似的还有：最长公共子序列分析：用一维数组dp[i]来存储以a[i]为末元素的最长递增子序列的长度，那么dp[i]至少为1（即包含

2013-11-04 07:56:31 796