- 博客(140)
- 资源 (2)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 多点两两相连问题
问题描述如下图，给定偶数个点，两两之间连线，规则为： 每个点仅能与另外一个点连接，如图：不准有1与3类似的连接 不能有剩余的点未与其他点连接。要求输入偶数个点，输出有多少中连接方式？问题分解当有两个点时：只有1-2连接的情况当有四个点时：会有1-2、3-4与1-4、2-3连接的情况，不能出现1-3这种交叉连接的情况当有六个点时： 首先固定点1，按照规则，能与1连
2018-01-09 11:52:18
5192
转载 简单实现thread pool
网上看得代码，两个小时时间改进一下源代码，增加log机制：#ifndef __thread_pool_h__#define __thread_pool_h__#include typedef struct work_s { void* (*routine)(void*); void* args; struct work_s* next;}w
2015-01-20 16:34:58
2515
转载 sublime 配置策略
大家好，今天给大家分享一款编辑器：sublime text2 我用过很多编辑器，EditPlus、EmEditor、Notepad++、Notepad2、UltraEdit、Editra、Vim，还有包括netbeans , zendstudio, dreamweaver 等。 最后我遇见了sublime text。 sublime是我见过的最好的编辑器，大型IDE能实现的功能，
2015-01-19 11:09:20
2265
原创 一个简易的打log的c代码
log.h #ifndef _log_h__#define _log_h__#define LEVEL_DEBUG 0#define LEVEL_TUNNINT 1#define LEVEL_INFO 2#define LEVEL_WARN 3#define LEVEL_ERROR 4#define TRACE_INFO(...) tr
2015-01-16 17:39:41
4383
原创 Bottom View of a Binary Tree
Given a Binary Tree, we need to print the bottom view from left to right. A node x is there in output if x is the bottommost node at its horizontal distance. Horizontal distance of left child of a nod
2014-12-17 15:15:23
2528
1
原创 输入一个无符号整数，用最少的步骤将该数变为1
输入一个无符号整数n，用最少的步骤将该数变为1，当n为偶数时可以采取的步骤是除2的形式，当n为奇数的时候可以采取加1或者减1的操作。#include #include using namespace std;int min(int a, int b) { if (a < b) return a; return b;}int get_pow(uint num) { if
2014-12-16 17:15:19
3854
2
转载 shell编程小示例
1.模拟linnux登录shell#/bin/bashecho -n "login:" read nameecho -n "password:"read passwdif [ $name = "cht" -a $passwd = "abc" ];thenecho "the host and password is right!"else echo "input is error!
2014-02-11 15:46:15
2733
原创 链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现
题目中最重要的就是学会一种方法，就是把链表中长度为k的一段从链表中摘除，翻转之后在将其衔接回链表。这是主要的思绪，以下按照此思路给出程序：#includeusing namespace std;typedef struct LNode { int m_nValue; struct LNode* m_pNext;}LNode;LNode* reverseList(LN
2013-11-10 21:47:32
6293
原创 顺时针打印nxn的矩阵
对于如下的矩阵进行顺时针的打印：1 2 34 5 67 8 9打印结果是：1,2,3,6,9,8,7,4,5这个打印很简单，就是按圈进行打印，看这个矩阵的维度是3，那么一共有一圈，和一个独立的点5，如果维度是4，那么就有两圈，没有独立的点，独立点进行单独处理，那么按圈进行打印，就要简单的多。自己拿出草稿纸画画就好，关键点是第几圈要有记录。#include
2013-11-10 20:48:56
3205
原创 given a single link list (l0, l1, l2, l3,,,ln), and transform it to (l0, ln, l1, ln-2, l2, ln-3)
一道微软的编程题，趁午休的时间做了一下，如果有不对之处，希望指出。#include#includeusing namespace std;typedef struct LNode { char m_nValue; struct LNode* p_mNext;}LNode;LNode* createList(char* pStr) { int strLen = strle
2013-11-08 13:57:36
2805
原创 一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后，而且各部分内部分别有序（创新工场）
一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后，而且各部分内部分别有序。思路：先进行字符串排序，用堆排序，按降序排列，排列依据字母对应的ascii值。排序之后按字符类别进行翻转。时间复杂度O（nlogn）#include#includeusing namespace std;void
2013-11-04 16:56:27
7377
1
原创 huffman 编码
huffman压缩是一种压缩算法，其中经典的部分就是根据字符出现的频率建立huffman树，然后根据huffman树的构建结果标示每个字符。huffman编码也称为前缀编码，就是每个字符的表示形式不是另一个字符表示的前缀。如果学过c语言版本的数据结构的话，那么会知道其上面的算法的时间复杂度是O(N^2)， 也算是比较复杂的，那么首先贴上这个版本算法的代码：#include#includeu
2013-07-25 14:09:15
2705
原创 不用递归和辅助空间对二叉树进行遍历
递归和非递归的进行二叉树的遍历从某种意义上来讲都是需要辅助空间的。那么进行非递归的和不需要辅助空间的遍历会有这种可能吗？答案是肯定的，应用线索二叉树，这样就能把左子树或者右子树为空的节点利用起来，二叉树线索之后就可能找到某个节点的前区或者后继。一个含有n个节点的二叉树，可定会有n+1个指针是空的。所有利用这n+1一个指针就能将二叉树线索化而不遗漏任何一个节点。下面给出利用这种线索化来遍历二叉树
2013-06-18 14:08:58
3276
原创 判断图中是否包含欧拉路径或者欧拉环
欧拉路径的定义：对于无向图来说，欧拉路径就是通过每条边有且只有一次，如果遍历的起始点和终止点都是一个顶点的话，那么就说这个图存在欧拉环。上图中有三个例子，分别是欧拉路径和欧拉环，以及非欧拉路径。那么怎么来判断一个图中是否含有欧拉路径或者欧拉环呢。首先回想一下图的定义，图中有v个顶点，那么着v个顶点中有0个或者两个或者两个以上的顶点度数为奇数。接下来，求欧拉路径就相当于用笔画一个图，笔可
2013-06-16 16:00:07
9063
原创 判断一个给定的字符串通过循环移位是否可以包含另一个字符串
比如说给定字符串“ABCD"通过循环移位是否可以包含“CDAB”。有两种方法，一种方法就是通过创建另外一个字符串，这个字符串是两个“ABCD”的连接，然后应用kmp在新创建的字符串中查找"CDAB"，这样的时间复杂度是O（n）， 空间复杂度也是O（n），还有另外一种方法是可在O（n）时间内完成，下面给出代码：#include#include#includeusing namespac
2013-06-13 16:42:47
4462
原创 zig tag traversal a binary tree
#include#includeusing namespace std;typedef struct tree_node_s { int value; struct tree_node_s* lchild; struct tree_node_s* rchild;}tree_node_t;tree_node_t* createNode(int value) { tree_nod
2013-06-08 10:49:44
2404
1
原创 Length of the longest substring without repeating characters(dp)
给出一个字符串，找出这个字符串中最长连续的而且没有重复字符的子串，并返回它的长度。例如，对于字符串“BDEFGABEF”最长连续且没有重复字符的子串可以是“DEFGAB”或者“DEFGAB”，长度是6。对于字符串“BBBB”，它满足要求的字串的长度是1，即“B”。首先分析一下，对于给定长度的字符串，它一共有多少个字串呢？ 子串数 = 长度为1的子串数+长度为2的子串数+ 。。。+长度为n的子串
2013-06-07 16:55:20
3163
原创 怎么判断一棵树的所有叶子节点都在同一层
给定一棵树，怎么判断它的所有叶子节点都在同一层，这种情况应该是完全二叉树的一种特例，如下图：如果去掉节点6的话，它是一棵完全二叉树，但是所有的叶子节点不在同一层，下面是层次遍历的一种方法：#include#includeusing namespace std;typedef struct tree_node_s { int value; struct t
2013-06-06 12:00:33
5863
1
原创 Connectivity in a directed graph
Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path between any two pair of vertices. For example, following is
2013-06-04 11:19:01
3671
原创 找出一个图中所有的强连通子图
如果一个有向图中的没对顶点都可以从通过路径可达，那么就称这个图是强连通的。一个 strongly connected component就是一个有向图中最大的强连通子图。下图中就有三个强连通子图：应用kosaraju算法，可以在O（v+e）的时间内找到强连通子图。下面是kosaraju算法的具体步骤：1，创建一个stack，对图进行深度优先遍历。对于每一个节点，当应用DFS遍历其所
2013-05-17 17:01:46
8406
原创 关于C/C++中的trigraph
先用简单的话讲一下什么是trigraph吧,这样不会一上来就是没人看得懂的话,trigraph是三字母词,又叫三连字。 言归正传,总得来说,thrgraph是C/C++ 为了照顾老一辈的"无产阶级革命家"而出现的,当时他们的条件极其艰苦，键盘上缺了很多键,无法输入以下九个字符: # \ ^ [ ] { } | ~由此推才出现了 trigraph .
2013-05-17 16:00:58
1982
原创 kruskal的最小生成树
给定一个无向图，它的生成树是能够连接图中所有定点的的子图。一个图可以有很多个生成树，但是一个无向，带全图的最小生成树是生成树的所有边的权值之和小于任何一个生成树的权值之和。 一棵最小生成树的边是多少呢，设定这个图一共有V条边，那么最小生成树应该有V-1条边。 应用kruskal来解决最小生成树的问题的步骤为：1，将图中的所有的边按照权值的大小进行非降序排序。2，保留
2013-05-16 15:22:44
1331
原创 并查集-用并查集判断图中是否有环（能够应用到kruskal的最小生成树）
先不介绍并查集的概念，先从它的应用说起吧，它有两个功能，第一就是判断给定的一个节点是否属于某一个集合，更确切的说是属于哪个集合。第二个功能就是合并两个集合。 给定一组数据，如：1， 2， 3， 4， 5， 6， 7， 8, 9，他们是一个大的集合，但是也可以将他们每一个数字看成一个独立的集合，然后我们通过合并来形成一个由他们所有组成的大集合。有的人很奇怪，他们已经是一个集合了，为什
2013-05-15 17:38:58
9707
1
原创 应用拓扑排序来解决DAG(directed acylic graph)的单源最短路径问题
熟悉图的人可以知道，对于单源最短路径的问题，我们可以用bellman-ford算法，或者dijkstra算法来解决，bellman-ford可以解决 有向无环图中边的权值为负数的情况，但是dijkstra不能解决复权值的问题。如果给定一个图G (v, e)， bellman-ford求最短路径的时间复杂度是O(ve)， 而dijkstra所用的时间是O(vlogv)。对于这两种方法就不介绍了。下面
2013-05-14 16:50:32
4343
原创 请打印给定文件的最后n行
首先想到的最笨的办法就是打开文件，然后遍历一遍，计算出文件中的行数，然后在从头开始遍历文件，在某个位置开始打印从文件中读出的行。这是一个比较笨的方法，还有一种很巧妙的方法就是应用circular buffer，初次见到这个名称的人可能感觉很神奇，但是如果知道循环队列这个概念的话，那么就不难理解了。如果我们准备打印一个文件的最后n行，我们可以建立一个n+1空间的循环队列，至于为什么是n+1的循环队列
2013-05-13 15:04:13
1908
原创 判断给定的图是否是有向无环图
判断给定的图是否是有向无环图，方法是应用拓扑排序，代码如下：#include#include#includeusing namespace std;class Graph { int vertexNum; list *adjacents;public: Graph(int _vertexNum) { vertexNum = _vertexNum; adjacent
2013-05-13 11:22:51
2003
翻译 An in-place algorithm for String Transformation
不好意思，我没有进行翻译，觉得原文讲的很好：Given a string, move all even positioned elements to end of string. While moving elements, keep the relative order of all even positioned and odd positioned elements same. For
2013-05-10 16:02:52
1154
原创 带有通配符的字符串和另一个字符串进行匹配
先吐个槽吧，公司也有这个算法，看了半天也不知道干什么呢，写的非常复杂，偶然的发现一个算法，小巧而精密，下面详细叙述：* 可以匹配0个或0个以上的字符？可以匹配一个字符这个算法应用的是递归的算法，开始担心如果字符串过长的话，会因递归引起栈的溢出，还好在网上查了一下，win32默认的递归栈大小是2M，这足以进行很长字符串的匹配。下面是核心的代码，思路都在代码的注释中，下面给出代
2013-05-09 15:07:33
3050
5
原创 计算一条英文句子中单词个数
给定一句英文，除了字母之外，还包含空格回车和水平制表符号('\t', '\n'), 根据这三个符号来计算一句英文中所含有单词的个数。下面给出的这个方法是我从一个国外网站上看到的，思路清晰而且很有逻辑性，于是决定记录下来：设定两个标志: IN, OUT和一个变量state，当遇到字母的时候state值为IN， 当遇到上面说的那三个字符的时候state为OUT。你可以测试任何情况，包括两个单词
2013-05-09 09:54:25
3323
原创 把二叉树转换成双向链表
记得这是一道微软的面试题，想了很长时间不知道怎么做，近期看别人的博客，找到了算法，自己实现了一下，下面是算法的叙述：1. If left subtree exists, process the left subtree…..1.a) Recursively convert the left subtree to DLL.…..1.b) Then find inorder predece
2013-05-08 11:26:33
1209
原创 Given an array of integers, sort the array according to frequency of elements
Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2,
2013-05-07 15:23:45
1335
原创 快捷键的难题
从一个编程网站上搞过来的题目，自己解了一下，发现就是类似于字符串旋转的问题：题目描述：Windows 7系统有很多的快捷键，Y同学最喜欢的快捷键就是Alt+Tab组合键，可以进行方便的进行多窗口之间的切换。为了方便，去掉一些复杂规则后，Y同学进行了如下定义。1.窗口队列：w1,w2,……wi……wn, (12.一次切换动作switch(x)：（1）按住Alt键不放（2）敲击
2013-05-05 10:42:42
1054
翻译 给图的顶点着色
给出一个无向图和一个数字m，此数字代表了允许使用颜色的种类，判断是否至多可以应用m种颜色，将图的每个顶点着色，并且相邻节点着的颜色不同。 输入： 1， 二维矩阵 graph[V][V],其中V代表图中顶点的个数，而矩阵本身是图的邻接矩阵表示形式。 2，对于graph[V][V]的理解是，graph[i][j], 如果i==j，那么graph[i][j]为1
2013-05-04 15:49:39
3147
原创 Given a sequence of numbers (or array).Find the maximum distance between all the same numbers.
题目要求如下：给定一列数组，找出在这个数组中相同数据出现位置的最大差值，例如：1, 2, 3, 4, 1, 1, 7, 4， max(1) = 5, max(2) = 0, max(4) = 4; 给出两种方法，一种是使用hash，这种方法比较有局限性，首先，如果数组中的某一个值比较大的话，应用hash就会比较浪费空间，定义这样的数据结构：typedef struct data_s
2013-05-02 14:33:32
1109
原创 linux客户端服务器回射程序-编程记录
#include#include#include#include#include#include#include#include#define MAXLINE 4096#define LISTEN_NUM 1024#define SERV_PORT 9877size_t my_write(int sock_fd, const void *vptr, int n) {
2013-04-27 22:27:30
853
原创 生产者消费者
#include#include#include#include#include#include#include#include#define BSIZE 10typedef struct buffer_s { char buf[BSIZE]; int occupied; int nextin; int nextout; pthread
2013-04-25 21:10:47
1102
原创 简单的thread_pool代码
#include#include#include#include#define DEFAULT_THREAD_NUM 4typedef struct job_s { void *(*process)(void*); void *arg; struct job_s *next;}job_t;typedef struct thread_pool_s {
2013-04-22 21:21:27
1140
原创 pthread_cond_wait详解
通常，和pthread _cond_wait 配对使用的有pthread_cond_signal , 同时还有用于pthread_cond_t初始化的pthread_cond_init，销毁的pthread_cond_destroy函数，还有用于加锁保护的pthread_mutex_lock和pthread_mutex_unlock，稍后会对为什么进行加锁做解释。 初始化条件变量int
2013-04-21 11:12:11
25476
4
原创 读effetive c++笔记之对象传递和对象返回
先写出关于对象传递和对象返回的总结：相对函数来说，如果是传递对象请使用pass-by-reference 而对象返回请使用pass-by-value. 为什么对象传递的时候要用pass-by-reference，而不用pass-by-value呢，举个例子，如下：#include#includeusing namespace std;class Person {p
2013-04-19 10:43:37
1275
原创 层次遍历二叉树-三种不同的方法
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：对此二叉树遍历的结果应该是：1，2 ， 34， 5， 67， 8第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：int print_at_level(Tree T, int level) {
2013-04-09 16:26:16
70281
6
an efficient implemention of double array trie
2013-01-06
shared ptr可以从boost库中单独提出来吗
2015-06-02
TA创建的收藏夹 TA关注的收藏夹
TA关注的人