萌叔

求二叉树两个距离最远的叶子节点

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 题目求二叉树两个距离最远的叶子节点？分析首先我们分析一下距离最远的叶子节点都产生在什么位置情况1: 显然距离最远的两个节点是节点3和5，距离是4 情况2: 对于情况2，如果我们观察以节点0为根的树，我们发现距离最远的叶子节点是7和8,距离是6,最远节点出现在左子树，而节点2距离节点7和8的距离是5。同理我们可以画出最远距离出现在右子树的情况。由上面的情况，我们可以知道由分治法的思想，我们可以想到最远距离叶子节点只能出现在 A. 出现在左子树 B. 出现在右子树 C. 两个节点分别位于左右子树很容易想到满足此种遍历顺序的是后序遍历。每次遍历的时候需要做如下操作： 1.记录左子树中，到根节点最远的叶子节点编号N1，以及到根的距离L1，此子树中最远距离的两个叶子节点t1、t2，以及它们的距离D1 1.记录右子树中，到根节点最远的叶子节点编号N2，以及到根的距离L2，此子树中最远距离的两个叶子节点t3、t4，以及它们的距离D2 2.当访问到根节点时，需要计算一下前面提到情况C 有没有出现。此种情况计算起来非常简单，如果左右子树都存在，那么左子树中叶子节点到根的最远距离是 L1 +1 , 右子树中叶子节点到根的最远距离是 L2 +1, 那么情况C 下的距离是 L1 + L2 + 2 比较这三种情况哪种最大即可后记 2012年的文章，迁移过来请我喝瓶饮料

按金字塔形输出数字

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 按如下样式输出数字 0 1 2 3 4 5 6 7 8 9 代码如下 #include <stdio.h> void printPyramid(int n){ int spaceNum = n-1; int k=0; for(int i=0;i<n;i++){ for(int j=0;j<spaceNum;j++){ printf(" "); } for(int j=0;j<=i;j++){ printf("%d",k++); printf(" "); } spaceNum--; printf("\n"); } } int main(int argc,char* argv[]){ printPyramid(4); } 后记 2012年的文章，迁移过来请我喝瓶饮料

linux下tree命令的简易实现

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc #include <iostream> #include <sys/stat.h> #include <sys/types.h> #include <stdio.h> #include <stdlib.h> #include <dirent.h> #include <string.h> using namespace std; int is_regular_file(char * a){ if(*a=='.'){ return 0; }else{ return 1; } } char* append(const char * a,const char *b){ char* buffer = new char[256]; strcpy(buffer,a); strcat(buffer,"/"); strcat(buffer,b); return buffer; } void tree(char* argv,int level){ DIR* dirptr; struct stat buf; stat(argv,&buf); if(!S_ISDIR(buf.st_mode)){ return; } //open file if((dirptr = opendir(argv))!=NULL){ struct dirent* entry; while(entry=readdir(dirptr)){ if(!is_regular_file(entry->d_name)){ continue; } for(int i=0;i<level;i++){ printf("\t"); } printf("|"); printf("--"); printf("%s\n",entry->d_name); tree(append(argv,entry->d_name),level+1); } //close file closedir(dirptr); } } int main(int argc,char* argv[]){ tree(argv[1],0); } 后记这是我2012年的文章，原来发表在ITeye，现在一并迁移过来 ...

轻量级服务器micro_httpd剖析

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 安装&配置安装请参考参考资料1和2 安装完成以后，可以使用man micro_httpd 来获得更详细的说明执行流程代码解析 micro_httpd /* micro_httpd - really small HTTP server ** ** Copyright � 1999,2005 by Jef Poskanzer <jef@mail.acme.com>. ** All rights reserved. ** ** Redistribution and use in source and binary forms, with or without ** modification, are permitted provided that the following conditions ** are met: ** 1. Redistributions of source code must retain the above copyright ** notice, this list of conditions and the following disclaimer. ** 2. Redistributions in binary form must reproduce the above copyright ** notice, this list of conditions and the following disclaimer in the ** documentation and/or other materials provided with the distribution. ** ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE ** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL ** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS ** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) ** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY ** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF ** SUCH DAMAGE. */ /* ####################################### 1.此程序对输入输出使用的是stdin和stdout 可以猜测它需要依赖其它程序对它的输入输出进行重定向 2.次程序没有创建socket服务因此需要其它程序为其创建socket服务 ###################################### */ #include <sys/types.h> #include <unistd.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <dirent.h> #include <ctype.h> #include <time.h> #include <sys/stat.h> #define SERVER_NAME "micro_httpd" #define SERVER_URL "http://www.acme.com/software/micro_httpd/" #define PROTOCOL "HTTP/1.0" #define RFC1123FMT "%a, %d %b %Y %H:%M:%S GMT" /* Forwards. */ //输出文件相关属性的详细信息 static void file_details( char* dir, char* name ); //返回出错页面 static void send_error( int status, char* title, char* extra_header, char* text ); //设置reponse static void send_headers( int status, char* title, char* extra_header, char* mime_type, off_t length, time_t mod ); //通过文件名推断文件mime_type static char* get_mime_type( char* name ); //URL 解码 static void strdecode( char* to, char* from ); //十六进制转换为十进制数 static int hexit( char c ); //用于文件名编码 static void strencode( char* to, size_t tosize, const char* from ); int main( int argc, char** argv ) { char line[10000], method[10000], path[10000], protocol[10000], idx[20000], location[20000], command[20000]; char* file; size_t len; int ich; struct stat sb; FILE* fp; struct dirent **dl; int i, n; if ( argc != 2 ) send_error( 500, "Internal Error", (char*) 0, "Config error - no dir specified." ); //更改工作目录 if ( chdir( argv[1] ) < 0 ) send_error( 500, "Internal Error", (char*) 0, "Config error - couldn't chdir()." ); if ( fgets( line, sizeof(line), stdin ) == (char*) 0 ) send_error( 400, "Bad Request", (char*) 0, "No request found." ); //解析请求形如 GET /abc/index.html HTTP/1.0 if ( sscanf( line, "%[^ ] %[^ ] %[^ ]", method, path, protocol ) != 3 ) send_error( 400, "Bad Request", (char*) 0, "Can't parse request." ); while ( fgets( line, sizeof(line), stdin ) != (char*) 0 ) { if ( strcmp( line, "\n" ) == 0 || strcmp( line, "\r\n" ) == 0 ) break; } if ( strcasecmp( method, "get" ) != 0 ) send_error( 501, "Not Implemented", (char*) 0, "That method is not implemented." ); if ( path[0] != '/' ) send_error( 400, "Bad Request", (char*) 0, "Bad filename." ); file = &(path[1]); strdecode( file, file ); if ( file[0] == '\0' ) file = "./"; len = strlen( file ); if ( file[0] == '/' || strcmp( file, ".." ) == 0 || strncmp( file, "../", 3 ) == 0 || strstr( file, "/../" ) != (char*) 0 || strcmp( &(file[len-3]), "/.." ) == 0 ) send_error( 400, "Bad Request", (char*) 0, "Illegal filename." ); if ( stat( file, &sb ) < 0 ) send_error( 404, "Not Found", (char*) 0, "File not found." ); //请求路径是文件夹吗 if ( S_ISDIR( sb.st_mode ) ) { if ( file[len-1] != '/' ) { (void) snprintf( location, sizeof(location), "Location: %s/", path ); send_error( 302, "Found", location, "Directories must end with a slash." ); } (void) snprintf( idx, sizeof(idx), "%sindex.html", file ); if ( stat( idx, &sb ) >= 0 ) { file = idx; goto do_file; } //显示请求文件夹下的文件列表 send_headers( 200, "Ok", (char*) 0, "text/html", -1, sb.st_mtime ); (void) printf( "<html><head><title>Index of %s</title></head>\n<body bgcolor=\"#99cc99\"><h4>Index of %s</h4>\n<pre>\n", file, file ); n = scandir( file, &dl, NULL, alphasort ); if ( n < 0 ) perror( "scandir" ); else for ( i = 0; i < n; ++i ) file_details( file, dl[i]->d_name ); (void) printf( "</pre>\n<hr>\n<address><a href=\"%s\">%s</a></address>\n</body></html>\n", SERVER_URL, SERVER_NAME ); } else { //返回请求的文件 do_file: fp = fopen( file, "r" ); if ( fp == (FILE*) 0 ) send_error( 403, "Forbidden", (char*) 0, "File is protected." ); send_headers( 200, "Ok", (char*) 0, get_mime_type( file ), sb.st_size, sb.st_mtime ); while ( ( ich = getc( fp ) ) != EOF ) putchar( ich ); } (void) fflush( stdout ); exit( 0 ); } //输出文件相关属性的详细信息 static void file_details( char* dir, char* name ) { static char encoded_name[1000]; static char path[2000]; struct stat sb; char timestr[16]; strencode( encoded_name, sizeof(encoded_name), name ); (void) snprintf( path, sizeof(path), "%s/%s", dir, name ); if ( lstat( path, &sb ) < 0 ) (void) printf( "<a href=\"%s\">%-32.32s</a> ???\n", encoded_name, name ); else { (void) strftime( timestr, sizeof(timestr), "%d%b%Y %H:%M", localtime( &sb.st_mtime ) ); (void) printf( "<a href=\"%s\">%-32.32s</a> %15s %14lld\n", encoded_name, name, timestr, (int64_t) sb.st_size ); } } //返回出错页面 static void send_error( int status, char* title, char* extra_header, char* text ) { send_headers( status, title, extra_header, "text/html", -1, -1 ); (void) printf( "<html><head><title>%d %s</title></head>\n<body bgcolor=\"#cc9999\"><h4>%d %s</h4>\n", status, title, status, title ); (void) printf( "%s\n", text ); (void) printf( "<hr>\n<address><a href=\"%s\">%s</a></address>\n</body></html>\n", SERVER_URL, SERVER_NAME ); (void) fflush( stdout ); exit( 1 ); } //设置reponse header //状态标题 mime_type 文件最后被修改的时间 static void send_headers( int status, char* title, char* extra_header, char* mime_type, off_t length, time_t mod ) { time_t now; char timebuf[100]; //\015\012 回车换行 (void) printf( "%s %d %s\015\012", PROTOCOL, status, title ); (void) printf( "Server: %s\015\012", SERVER_NAME ); now = time( (time_t*) 0 ); //将时间格式化后存在timebuf中 (void) strftime( timebuf, sizeof(timebuf), RFC1123FMT, gmtime( &now ) ); (void) printf( "Date: %s\015\012", timebuf ); if ( extra_header != (char*) 0 ) (void) printf( "%s\015\012", extra_header ); if ( mime_type != (char*) 0 ) (void) printf( "Content-Type: %s\015\012", mime_type ); if ( length >= 0 ) (void) printf( "Content-Length: %lld\015\012", (int64_t) length ); if ( mod != (time_t) -1 ) { (void) strftime( timebuf, sizeof(timebuf), RFC1123FMT, gmtime( &mod ) ); (void) printf( "Last-Modified: %s\015\012", timebuf ); } (void) printf( "Connection: close\015\012" ); (void) printf( "\015\012" ); } //通过文件名推断文件mime_type static char* get_mime_type( char* name ) { char* dot; dot = strrchr( name, '.' ); if ( dot == (char*) 0 ) return "text/plain; charset=iso-8859-1"; if ( strcmp( dot, ".html" ) == 0 || strcmp( dot, ".htm" ) == 0 ) return "text/html; charset=iso-8859-1"; if ( strcmp( dot, ".jpg" ) == 0 || strcmp( dot, ".jpeg" ) == 0 ) return "image/jpeg"; if ( strcmp( dot, ".gif" ) == 0 ) return "image/gif"; if ( strcmp( dot, ".png" ) == 0 ) return "image/png"; if ( strcmp( dot, ".css" ) == 0 ) return "text/css"; if ( strcmp( dot, ".au" ) == 0 ) return "audio/basic"; if ( strcmp( dot, ".wav" ) == 0 ) return "audio/wav"; if ( strcmp( dot, ".avi" ) == 0 ) return "video/x-msvideo"; if ( strcmp( dot, ".mov" ) == 0 || strcmp( dot, ".qt" ) == 0 ) return "video/quicktime"; if ( strcmp( dot, ".mpeg" ) == 0 || strcmp( dot, ".mpe" ) == 0 ) return "video/mpeg"; if ( strcmp( dot, ".vrml" ) == 0 || strcmp( dot, ".wrl" ) == 0 ) return "model/vrml"; if ( strcmp( dot, ".midi" ) == 0 || strcmp( dot, ".mid" ) == 0 ) return "audio/midi"; if ( strcmp( dot, ".mp3" ) == 0 ) return "audio/mpeg"; if ( strcmp( dot, ".ogg" ) == 0 ) return "application/ogg"; if ( strcmp( dot, ".pac" ) == 0 ) return "application/x-ns-proxy-autoconfig"; return "text/plain; charset=iso-8859-1"; } //用于URL 解码 static void strdecode( char* to, char* from ) { for ( ; *from != '\0'; ++to, ++from ) { if ( from[0] == '%' && isxdigit( from[1] ) && isxdigit( from[2] ) ) { *to = hexit( from[1] ) * 16 + hexit( from[2] ); from += 2; } else *to = *from; } *to = '\0'; } //十六进制转换为十进制数 static int hexit( char c ) { if ( c >= '0' && c <= '9' ) return c - '0'; if ( c >= 'a' && c <= 'f' ) return c - 'a' + 10; if ( c >= 'A' && c <= 'F' ) return c - 'A' + 10; return 0; /* shouldn't happen, we're guarded by isxdigit() */ } //用于文件名编码 static void strencode( char* to, size_t tosize, const char* from ) { int tolen; for ( tolen = 0; *from != '\0' && tolen + 4 < tosize; ++from ) { //ASCII 字符、数字或者 "/_.-~" 中的一个 if ( isalnum(*from) || strchr( "/_.-~", *from ) != (char*) 0 ) { *to = *from; ++to; ++tolen; } else //对特殊字符进行编码问题：什么样的特殊字符需要这样编码？ { (void) sprintf( to, "%%%02x", (int) *from & 0xff ); to += 3; tolen += 3; } } *to = '\0'; } 参考资料 micro_http 下载地址 micro_httpd的安装与配置后记这是我2012年的文章，原来发表在ITeye，现在一并迁移过来 ...

atoi()和itoa()的实现

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 引子自己实现一下atoi()和itoa() 这2个函数实现 my_itoa.cpp #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; char * my_itoa( int value, char * str, int base ){ char array[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; bool is_minus = false; if(value<0){ is_minus = true; value = - value; } //buffer char buffer[256]; int i=0,j=0; int temp; while(value){ temp =value%base; buffer[i++]=array[temp]; value = value/base; } //cout<<buffer<<endl; if(is_minus){ str[j++] = '-'; } while(--i>=0){ str[j++]=buffer[i]; } str[j]='\0'; return str; } int main () { int i; char buffer [33]; printf ("Enter a number: "); scanf ("%d",&i); itoa (i,buffer,10); printf ("decimal: %s\n",buffer); my_itoa (i,buffer,10); printf ("decimal: %s\n",buffer); itoa (i,buffer,16); printf ("hexadecimal: %s\n",buffer); my_itoa (i,buffer,16); printf ("hexadecimal: %s\n",buffer); itoa (i,buffer,2); printf ("binary: %s\n",buffer); my_itoa (i,buffer,2); printf ("binary: %s\n",buffer); return 0; } my_atoi.cpp ...

shell脚本统计C／C++代码行

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc #current directory CURR_DIR='.' if [ ! -z $1 ];then CURR_DIR=$1 fi # create 3 tempory file to record detail infomation find $CURR_DIR -name "*.cpp" | xargs wc -l > cpp_line_detail.txt find $CURR_DIR -name "*.c" | xargs wc -l > c_line_detail.txt find $CURR_DIR -name "*.h" | xargs wc -l > h_line_detail.txt #count CPP_COUNT=$(tail -1 cpp_line_detail.txt | sed -e 's/^ *//' | sed -e 's/ .*$//') C_COUNT=$(tail -1 c_line_detail.txt | sed -e 's/^ *//' | sed -e 's/ .*$//') H_COUNT=$(tail -1 h_line_detail.txt | sed -e 's/^ *//' | sed -e 's/ .*$//') echo "The code in *.cpp files is "$CPP_COUNT" lines" echo "The code in *.c files is "$C_COUNT" lines" echo "The code in *.h files is "$H_COUNT" lines" echo "------------------------------------" #the final result echo "The total number of lines is "$(($CPP_COUNT + $C_COUNT + $H_COUNT)) 后记这是我2012年的文章 ...

绑定本地出口IP

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 起因最近公司有一批数据要备份到对象存储中。机房为3线机房，为了充分利用机房的出口带宽，我只能轮流绑定源IP（本机有3个IP，分别是联通、移动、电信）源码如下: # -*- coding: utf-8 -*- import socket import requests class BindAddress(object): def __init__(self, ip): self.ipbind = ip self.real_socket = socket.socket def __enter__(self): def bound_socket(*a, **k): sock = self.real_socket(*a, **k) sock.bind((self.ipbind, 0)) return sock socket.socket = bound_socket def __exit__(self, type, value, trace): socket.socket = self.real_socket ip= 'xxx.xxx.xxx.xxx' with BindAddress(ip): r = requests.get('http://ip.vearne.cc:8080/') print r.content 我在峰云大神的基础上做了进一步封装，使得bind操作变得更简单另外代码中用到了我在快速获取本机出口IP 一文中搭建的服务，以判断bind是否生效。额外的说明1 其实我们在爬虫的时候，也有用这种方法，在增加客户端IP，以减少被封杀的概率。只需要在一块网卡上绑定多个公网IP即可。额外的说明2 由于以上的做法修改的是模块的函数，因此对于多线程的场景，它不是线程安全的。 ...

快速获取本机出口IP

两个栈实现的队列

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc #include <iostream> #include <stack> using namespace std; template<typename T> class MyQueue{ public: MyQueue(){} ~MyQueue(){} void push(T& a); T& front(); void pop(); int size(){ return st1.size()+st2.size(); } bool empty(){ return size()==0; } private: stack<T> st1; stack<T> st2; }; template<typename T> void MyQueue<T>::push(T& a){ st1.push(a); } template<typename T> T& MyQueue<T>::front(){ if(st2.empty()){ while(!st1.empty()){ st2.push(st1.top()); st1.pop(); } } return st2.top(); } template<typename T> void MyQueue<T>::pop(){ front(); st2.pop(); } int main(){ MyQueue<int> q; int a=1; int b=2; int c=3; q.push(a); q.push(b); //cout<<q.size()<<endl; cout<<q.front()<<endl; q.push(c); while(!q.empty()){ cout<<q.front()<<endl; q.pop(); } //cout<<q.front()<<endl; } 后记这是我2012年的文章，从别的博客迁移进来 ...

Amazon S3 上传限速

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 引言最近公司有一批数据要上传到白山云的对象存储中，白山云的对象存储兼容AWS S3的API 因此我使用的是boto3, 然而网络管理员要求对上行带宽有限制解决方法 1. 使用Trickle 见参考资料1 2. 使用iptables 见参考资料2 3. 使用SDK 使用Trickle，要求上传程序只对使用Glibc库应用有效, 而使用iptables，配置还是比较麻烦的，而且iptables只能按照对端的IP进行限制，而我们访问对象存储，实际使用的是域名，如果域名解析的IP发生变化，我们无法及时感知。仔细阅读代码和文档之后，我发现boto3原生已经支持限速了 max_bandwidth: The maximum bandwidth that will be consumed in uploading and downloading file content. The value is in terms of bytes per second. # -*- coding: utf-8 -*- import boto3 from boto3.s3.transfer import TransferConfig # from s3transfer.manager import TransferConfig access_key = "xxx" secret_key = "xxx" cli = boto3.client( 's3', aws_access_key_id=access_key, aws_secret_access_key=secret_key, endpoint_url='http://ss.bscstorage.com' ) config = TransferConfig( multipart_threshold=30 * 1024 * 1024, multipart_chunksize=8 * 1024 * 1024, max_concurrency=10, ) # 50MB/s # 单位是byte config.max_bandwidth = 50 * 1024 * 1024 resp = cli.upload_file( '/tmp/VSCode-darwin-stable.zip', 'test', 'test-key-xx2', ExtraArgs={ 'ContentType': 'text/plain', # 请替换为合适的文件类型 'ACL': 'private', }, Config=config ) 参考资料 Linux 下使用Trickle限制下载/上传带宽 linux下使用iptables和tc限制流量请我喝瓶饮料