编程语言 | 萌叔

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

版权声明本站原创文章由萌叔发表转载请注明萌叔 | 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，现在一并迁移过来 ...

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 由于以上的做法修改的是模块的函数，因此对于多线程的场景，它不是线程安全的。 ...

两个栈实现的队列

版权声明本站原创文章由萌叔发表转载请注明萌叔 | 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限制流量请我喝瓶饮料

golang fasthttp优雅退出

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 引言使用Golang进行开发服务，我们会特别关心性能，fasthttp是标准库net/http性能的10倍。所以我们的web服务大量使用它。不过这个库并没有提供优雅退出方案, 查看了很多资料，我找到一个解决方案。 1.原理对于web服务而言，优雅退出其实分为2步 1）关闭监听的端口，不再接受新的请求 2）对于正在处理的请求等待它们处理完成，如果全部处理完成，或者默认的超时时间已达，则退出 2. 实现要达到这个目标需要实现 type Listener interface 下面展示一部分核心代码 grace_listener.go type GracefulListener struct { // inner listener ln net.Listener // maximum wait time for graceful shutdown maxWaitTime time.Duration // this channel is closed during graceful shutdown on zero open connections. done chan struct{} // the number of open connections connsCount uint64 // becomes non-zero when graceful shutdown starts shutdown uint64 } // Close closes the inner listener and waits until all the pending open connections // are closed before returning. func (ln *GracefulListener) Close() error { // 不再接受新的请求 err := ln.ln.Close() if err != nil { return nil } // 等待已经接到的请求处理完成 return ln.waitForZeroConns() } func (ln *GracefulListener) waitForZeroConns() error { atomic.AddUint64(&ln.shutdown, 1) fmt.Println("waitForZeroConns", atomic.LoadUint64(&ln.connsCount)) if atomic.LoadUint64(&ln.connsCount) == 0 { close(ln.done) return nil } select { case <-ln.done: return nil case <-time.After(ln.maxWaitTime): return fmt.Errorf("cannot complete graceful shutdown in %s", ln.maxWaitTime) } return nil } server.go 初始化&启动web服务 ...

程序hang住的问题的追踪

版权声明本站原创文章由萌叔发表转载请注明萌叔 | http://vearne.cc 引子: 我这里说的hang住，并不是指死锁，在真实的工作场景中，死锁的情况其实并不很多见。在我工作的几年中，有遇到好几次都是程序hang在某个IO请求上的。 1. 排查排查hang住的最有用的命令是strace和lsof命令比如我们有一个服务叫 atm-client 1.1 首先查出服务对应的进程 ps -ef| grep atm-client| grep -v grep 输出结果 root 5 1 0 2017 ? 01:05:39 atm-client 1.2 对于多线程的程序可以先列出进程的所有线程 ps -mp 5 -o THREAD,tid 输出结果 USER %CPU PRI SCNT WCHAN USER SYSTEM TID root 0.3 - - - - - - root 0.0 19 - poll_s - - 5 root 0.0 19 - sk_wai - - 11 root 0.0 19 - sk_wai - - 12 root 0.0 19 - sk_wai - - 13 root 0.0 19 - sk_wai - - 14 root 0.0 19 - sk_wai - - 15 root 0.0 19 - sk_wai - - 16 root 0.0 19 - sk_wai - - 17 root 0.0 19 - sk_wai - - 18 root 0.0 19 - sk_wai - - 19 root 0.0 19 - sk_wai - - 20 root 0.0 19 - sk_wai - - 21 1.3 strace 可以跟踪进程或者线程的系统调用跟踪线程 ...