Python实现树的操作

二叉查找树 #coding: utf8 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def level_order(self, root): if root is None: return root queue = [root] while queue: node = queue.pop(0) print node.val, if node.left: queue.append(node.left) if node.right: queue.append(node.right) def pre_order(self, root): if root is None: return print self.val, if self.left: self.left.pre_order(root) if self.right: self.right.pre_order(root) def pre_order1(self, root): if root is None: return stack = [] node = root while node or stack: while node: print node.val, stack.append(node) node = node.left node = stack.pop() node = node.right def mid_order(self, root): if root is None: return...…

我的2015

整体 24年来「收获」最大的一年 学到了一些意想不到的东西 同时也「认识」到了一些本质性的错误 还完成了几件「大事」 养成的习惯 「可能」是好习惯 记日历: 自我push,完成 「TO-DO-LIST」 知道自己一年到头干了什么 写笔记: Evernote + Dropbox,多客户端同步,随时查看笔记 知识系统化,能随时温习 看文档: 遇到新的框架,第一时间看官方英文文档,不会第一时间去看「百度百科」了 勤阅读: 没具体统计一年看了多少书,但出门坐地铁会带本书在包里(= =! 虽然可能不会看) PAD 和 Kindle 简直就是地铁和睡前阅读神器 肯深入 有可能这是最大的进步,不会一味追求「广度」 自己动手实现一遍 「应该」是坏习惯 打球(运动)少了 总感觉自己腾不出时间 学校、实验室环境、温度各种场地导致等 依旧「优柔」 抉择 学会放弃 静心读书时间少 挑编程语言 不太积极主动的寻求和接受新的知识 有效代码量大概「1.2W」行 过渡 这一年有点特别,8月开始,「上课」的生活结束,开始全面进入实验室工作。 所以,这一年分为两部分: 1-8月,上课,学习,玩耍 8-12月,上班,上班,上班 上半年 上课的时间反倒没有太多的记忆,认真的修完了10个学分,写了几个大作业,考了个试。 上学期间经常去「CS」,大概40天一次,每次5-7天,其实有差不多一个月不在北京呢。 下半年 差不多每月一个项目 开始接触专业方向的工程类的项目 很多时候处于「无网」调试代码状态 完成: 老师布置的每一个任务 第一本英文书籍阅读《head first python》 认真研究了下「docker」 未完成: 说好的多看论文呢(diu lian a) 说好的「2W」 code呢 说好的每个月至少阅读一本有营养的书呢 说好的「github」很多绿呢 还有说好了很多呢…… 2016 先隐藏了…… …

this post is featured

深入了解ptrace

主要介绍基于LINUX 64的ptrace fork() 在Linux中,每一个进程都有一个唯一的编号,被称作pid(Process ID)。在Linux中,进程不能凭空产生(init进程是个例外),只能从一个已有进程衍生出来。原来的进程被称做父进程,衍生出来的进程叫子进程。一个系统中所有进程以父子关系相连接,形成一棵树,这棵“树”的树根就是init进程,它是在系统启动时被直接启动的,因此它没有父进程。并且系统中所有其他进程都直接或间接地是它的子进程。 在Linux系统中,实现“把一个进程变成两个”这一功能的有三个系统调用,即fork()、vfork()和clone(),这里主要介绍fork() fork()将当前进程所有数据复制一份,产生一个和父进程一模一样的子进程。并在两个进程中返回不同的返回值. int pid=fork(); if (pid==0){ //子进程的工作 }else{ //父进程的工作 } 一般来说,子进程的工作就是调用exec族函数,启动另一个程序(把自己替换掉)。如果子进程还在执行而父进程已结束,那么它就成为“孤儿”进程,成为init进程的子进程。 fork() + exec() exec int execl (const char *path, const char *arg, ...); int execlp (const char *file, const char *arg, ...); int execle (const char *path, const char *arg, ..., char * const envp[]); int execv (const char *path, char *const argv[]); int execve (const char *path, char *const argv[], char *const envp[]); int execvp (const char *file, char *const argv[]); int execvpe(const char *file, char *const argv[], char *const envp[]); 他们的作用就是把某个进程(通常是fork出来的子进程)从里到外,完完整整,包括代码、堆栈,全部换成另一个程序,然后从头开始运行。 它们的调用效果是一样的,区别在于调用方式。 带l(代表list)的函数使用了一种比较接近人类方法来表示程序参数表,即以(char *)NULL作为结尾的变参列表 带e(environment),则该函数接受一个字符串数组表示的环境变量表;反之,则会默认传递所有当前环境变量 带p,那么你就不必在第一个参数中列出完整路径,系统会自动检查当前目录和PATH环境变量 不管你使用那种方法表示程序参数表,第0个参都应当和可执行文件路径保持一致,虽然不一致依然可以正确运行,但有可能出现奇奇怪怪的问题。 组合介绍 一般来说,exec结合fork这么使用: pid_t pid =...…

Homework1

请上网了解”三分查找”的含义,并且举一个例子应用算法并做描述 答:在二分查找的基础上,在右区间(或左区间)再进行一次二分,这样的查找算法称为三分查找,也就是三分法。三分查找通常用来迅速确定最值。 如上图所示,最顶端为需要查找的点,做如下操作,即可得到答案: 先取 [L,R] 的中点 mid,再取 [mid,R]的中点 mmid,通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。当最后 L=R-1 时,再比较下这两个点的值,我们就找到了答案。 伪代码如下: int fun(int l,int r) { while(l < r-1) { int mid = (l+r)/2; int mmid = (mid+r)/2; if( f(mid) > f(mmid) ) r = mmid; else l = mid; } return f(l) > f(r) ? l : r; } 其中f(x)代表要查找当前x的值 请上网了解欧氏距离与曼哈顿距离的概念,并在下面做出陈述 答:欧氏距离:指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。 曼哈顿距离:曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。 曼哈顿距离示意图在早期的计算机图形学中,屏幕是由像素构成,是整数,点的坐标也一般是整数,原因是浮点运算很昂贵,很慢而且有误差,如果直接使用AB的距离,则必须要进行浮点运算,如果使用AC和CB,则只要计算加减法即可,这就大大提高了运算速度,而且不管累计运算多少次,都不会有误差。 欧氏距离(欧几里德距离):在二维和三维空间中的欧式距离的就是两点之间的距离,二维的公式是三维的公式是推广到n维空间,欧式距离的公式是 这里i=1,2...n,表示第一个点的第i维坐标, 表示第二个点的第i维坐标。 字母 H 的 ASCII 码是72 数字 9 的 ASCII码是57 十进制数字734的二进制表示是1011011110 二进制数字 1000 + 1010101010 的结果的十进制表示是690 请写出纯红色的十六进制RGB色值编码#FF0000 请简述身份证最后一个校验位的编码方式: 答:校验位是根据前面十七位数字码,按照ISO 7064:1983.MOD 11-2校验码计算出来的检验码。 计算公式:∑(a[i]×W[i])(mod 11) i表示号码字符从右至左包括校验码在内的位置序号, a[i]表示第i位置上的号码字符值, W[i]计算公式为:2^(i-1) mod (11), 表示第i位上的加权因子。 最后,得出∑(a[i]×W[i])(mod 11)的值, 0 1 2 3 4 5 6...…

mac下eclipse调试vagrant hadoop

情况简介 mac下不想装图形界面虚拟机,所以用vagrant+virtual box虚拟了ubuntu环境,在ubuntu下配置好hadoop环境,然后利用eclipse远程调试 简直就是蛋疼…… 准备 vagrant环境 virtual box hadoop环境,我的是hadoop 2.5.2 + hbase 0.98.11 一切部署都在这里弄好了,配一次,以后可以直接用了,不要因为换机器而烦恼了……: https://github.com/yijia2413/vagrant-cascading-hadoop-cluster 配置步骤 step1: 假设hadoop + hbase都配置好了,在远程(或者vagrant里面) step2: 下载安装eclipse,官网解决即可,for os x step3: 下载hadoop2x-eclipse-plugin,放入ecipse插件下 在release目录下,没想到2.6.0的插件居然也做好了,2.6.0可以兼容2.5.2,可以放心使用,执行以下操作 cp hadoop-eclipse-kepler-plugin-2.2.0.jar /your_path/eclipse/plugins /your_path/eclipse/ -clean step4: 下载hadoop源码包,在本地,无需配置,解压即可,eclipse要用到里面的lib文件,在preference里面,添加hadoop的location即可。比如:~/hadoop-2.5.2/ step5: eclipse->window->Open Perspective->others->mapreduce,下方mapreduce location,右键添加location 接下来要配置location的一些参数,我的配置如下: location name: Namenode map/reduce(v2) Master: host:192.168.7.10 port:9001 dfs master: host:192.168.7.10 port:9000 username:vagrant IP为远程IP,此处为vagrant的master节点对应的ip(伪分布式) step6: 新建mapreduce项目,新建一个class,就可以开始写程序了 可以用官方的程序做一个验证 step7: 配置参数: 下面是我的运行参数配置,ip地址也可以改为master.local,当然修改了hosts hdfs://192.168.7.10:9000/tmp/pg20417.txt hdfs://192.168.7.10:9000/tmp/pg20417.out step8: 运行,检测,搞定 step9: 添加log,在eclipse的控制台,在src里面加入log4j.properties即可 完成 此时,可以在eclipse里面尽情的远程调试hadoop程序了 …

setuid和setgid

setuid Linux中每个进程都会有一个uid,uid=0则为root用户进程,uid>0则为普通用户进程。不同uid进程之间(不包括root进程)是相互隔离的,各自都有自己独立的权限,互不干扰。 如果打算执行不可信的程序,那么你可以在启动该程序时为其分配一个random uid。一个可能的执行流程如下: fork() -> setuid() -> {set some limits} -> execve() setuid:意思是任何执行这个文件的进程,它的有效UID(即用户ID)将会被改为文件所有者。 int setuid(uid_t uid); setuid()用来重新设置执行目前进程的用户识别码. 不过, 要让此函数有作用, 其有效的用户识别码必须为0(root). 在Linux 下, 当root 使用setuid()来变换成其他用户识别码时, root 权限会被抛弃, 完全转换成该用户身份, 也就是说, 该进程往后将不再具有可setuid()的权利, 如果只是向暂时抛弃root 权限, 稍后想重新取回权限, 则必须使用seteuid(). 详解 内核会给每个进程关联两个和进程ID无关的用户ID,一个是真实用户ID,还有一个是有效用户ID或者称为setuid(set user ID)。真实用户ID用于标识由谁为正在运行的进程负责。有效用户ID用于为新创建的文件分配所有权、检查文件访问许可,还用于通过kill系统调用向其 它进程发送信号时的许可检查。内核允许一个进程以调用exec一个setuid程序或者显式执行setuid系统调用的方式改变它的有效用户ID。 所谓setuid程序是指一个设置了许可模式字段中的setuid bit的可执行文件。当一个进程exec一个setuid程序的时候,内核会把进程表以及u区中的有效用户ID设置成该文件所有者的ID。为了区分这两个 字段,我们把进程表中的那个字段称作保存用户ID。 setuid系统调用的语法是 setuid(uid) ,其中,uid是新的用户ID,该系统调用的结果取决于有效用户ID的当前值。如果调用进程的有效用户ID是超级用户,内核会把进程表以及u区中的真实和 有效用户ID都设置成uid。如果调用进程的有效用户ID不是超级用户,仅当uid等于真实用户ID或保存用户ID时,内核才会把u区中的有效用户ID设 置成uid。否则,该系统调用将返回错误。 …