博客

已知先序及中序遍历，重建二叉树

package cn.pbdata.util;

public class PreMidToAfter {

    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(){
            left = null;
            right = null;
        }
    }
    
    public TreeNode rebuild(int[] pre,int[] mid){
        return rebuild(pre,0,pre.length-1,mid,0,mid.length-1);
    }
    
    public TreeNode rebuild(int[] pre,int ps,int pe,int[] mid,int ms,int me){
        if(pre == null || pre.length == 0 || mid == null || mid.length==0){
            return null;
        }
        if(ps > pe){
            return null;
        }
        int val = pre[ps];
        TreeNode root = new TreeNode();
        root.val = val;
        
        int index;
        for(index = ms ; index <= me;index++){
            if(val == mid[index]){
                break;
            }
        }
        
        int leftPreStart = ps + 1;
        int leftPreEnd = ps + index - ms;
        int leftMidStart = ms;
        int leftMidEnd = index - 1;
        
        root.left = rebuild(pre,leftPreStart,leftPreEnd,mid,leftMidStart,leftMidEnd);
        
        int rightPreStart = ps + index -ms + 1;
        int rightPreEnd  = pe;
        int rightMidStart = index + 1;
        int rightMidEnd = me;
        root.right = rebuild(pre,rightPreStart,rightPreEnd,mid,rightMidStart,rightMidEnd);
        return root;
    }
    public void preView(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val);
        preView(root.left);
        preView(root.right);
    }
    public void midView(TreeNode root){
        if(root == null){
            return;
        }
        midView(root.left);
        System.out.print(root.val);
        midView(root.right);
    }
    public void lastView(TreeNode root){
        if(root == null){
            return;
        }
        lastView(root.left);
        lastView(root.right);
        System.out.print(root.val);
    }
    
    
    public static void main(String[] args){
        PreMidToAfter pt = new PreMidToAfter();
        int[] pre = { 1, 2, 4,7,3,5,6,8};
        int[] mid = {4,7,2,1,5,3,8,6};
        TreeNode node1 = pt.rebuild(pre, mid);
        pt.preView(node1); 
        System.out.println("");
        pt.midView(node1);
        System.out.println("");
        pt.lastView(node1);
        System.out.println("");
        
    }
}

2015年12月2日

算法运行时间-logN、NlogN

算法的运行时间通常与下列函数成比例：

1	大部分程序的大部分指令之执行一次，或者最多几次。如果一个程序的所有指令都具有这样的性质，我们说这个程序的执行时间是常数。
logN	如果一个程序的运行时间是对数级的，则随着N的增大程序会渐渐慢下来，如果一个程序将一个大的问题分解成一系列更小的问题，每一步都将问题的规模缩减成几分之一，一般就会出现这样的运行时间函数。在我们所关心的范围内，可以认为运行时间小于一个大的常数。对数的基数会影响这个常数，但改变不会太大：当N=1000时，如果基数是10，logN等于3；如果基数是2，logN约等于10.当N=1 00 000，logN只是前值的两倍。当N时原来的两倍，logN只增长了一个常数因子：仅当从N增长到N平方时，logN才会增长到原来的两倍。
N	如果程序的运行时间的线性的，很可能是这样的情况：对每个输入的元素都做了少量的处理。当N=1 000 000时，运行时间大概也就是这个数值；当N增长到原来的两倍时，运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入（或者产生N个输出），那么这种情况是最优的。
NlogN	如果某个算法将问题分解成更小的子问题，独立地解决各个子问题，最后将结果综合起来，运行时间一般就是NlogN。我们找不到一个更好的形容，就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时，NlogN大约是20 000 000。当N增长到原来的两倍，运行时间超过原来的两倍，但超过不是太多。
N平方	如果一个算法的运行时间是二次的（quadratic），那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入数据项的算法（在程序中很可能表现为一个嵌套循环）中，当N=1000时，运行时间是1 000 000；如果N增长到原来的两倍，则运行时间将增长到原来的四倍。
N三次方	类似的，如果一个算法需要处理输入数据想的三元组（很可能表现为三重嵌套循环），其运行时间一般就是三次的，只能用于一些规模较小的问题。当N=100时，运行时间就是1 000 000；如果N增长到原来的两倍，运行时间将会增长到原来的八倍。
2的N次方	如果一个算法的运行时间是指数级的（exponential），一般它很难在实践中使用，即使这样的算法通常是对问题的直接求解。当N=20时，运行时间是1 000 000；如果增长到原来的两倍时，运行时间将是原时间的平方！

log log N 可以看作是一个常数：即使N很多，两次去对数之后也会变得很小

转自：http://clarkluo2004.blog.163.com/blog/static/32973801200845115213422/

2015年11月25日

upubtu下，将docker1.4升级到1.9

# docker -v
# apt-get update
# apt-get -u -y upgrade lxc-docker

2015年11月25日
Redis AOF rewrite的触发机制

如果Redis只是将客户端修改数据库的指令重现存储在AOF文件中，那么AOF文件的大小会不断的增加，因为AOF文件只是简单的重现存储了客户端的指令，而并没有进行合并。对于该问题最简单的处理方式，即当AOF文件满足一定条件时就对AOF进行rewrite，rewrite是根据当前内存数据库中的数据进行遍历写到一个临时的AOF文件，待写完后替换掉原来的AOF文件即可。

Redis触发AOF rewrite机制有三种：

1、Redis Server接收到客户端发送的BGREWRITEAOF指令请求，如果当前AOF/RDB数据持久化没有在执行，那么执行，反之，等当前AOF/RDB数据持久化结束后执行AOF rewrite

redis> BGREWRITEAOF
Background append only file rewriting started

2、在Redis配置文件redis.conf中，用户设置了auto-aof-rewrite-percentage和auto-aof-rewrite-min-size参数，并且当前AOF文件大小server.aof_current_size大于auto-aof-rewrite-min-size(server.aof_rewrite_min_size)，同时AOF文件大小的增长率大于auto-aof-rewrite-percentage(server.aof_rewrite_perc)时，会自动触发AOF rewrite

3、用户设置“config set appendonly yes”开启AOF的时，调用startAppendOnly函数会触发rewrite

2015年10月14日
Android SDK在线更新镜像服务器及使用方法

中国科学院开源协会镜像站地址:

IPV4/IPV6: http://mirrors.opencas.cn 端口：80

IPV4/IPV6: http://mirrors.opencas.org 端口：80

IPV4/IPV6: http://mirrors.opencas.ac.cn 端口：80

上海GDG镜像服务器地址:

http://sdk.gdgshanghai.com 端口：8000

北京化工大学镜像服务器地址:

IPv4: http://ubuntu.buct.edu.cn/ 端口：80

IPv4: http://ubuntu.buct.cn/ 端口：80

IPv6: http://ubuntu.buct6.edu.cn/ 端口：80

大连东软信息学院镜像服务器地址:

http://mirrors.neusoft.edu.cn 端口：80

腾讯Bugly 镜像:

http://android-mirror.bugly.qq.com 端口：8080

腾讯镜像使用方法:http://android-mirror.bugly.qq.com:8080/include/usage.html

使用方法：

1.启动 Android SDK Manager
2.打开主界面，依次选择『Tools』、『Options…』
3.弹出『Android SDK Manager – Settings』窗口；
4.在『Android SDK Manager – Settings』窗口中，在『HTTP Proxy Server』和『HTTP Proxy Port』输入框内填入上面镜像服务器地址(不包含http://)和端口，
5.选中『Force https://… sources to be fetched using http://…』复选框
6.设置完成后单击『Close』按钮关闭『Android SDK Manager – Settings』窗口返回到主界面；
7.依次选择『Packages』、『Reload』
OK!

2015年10月9日
国内可用的时间同步服务器

试了很多，目前能用的基本也就是ntp.api.bz。其他网络上公布的各高校的时间服务器基本不可用

服务器与时间服务器同步的步骤如下（ubuntu14.0.4）：
1.安装ntpdate工具
# sudo apt-get install ntpdate
2.设置系统时间与网络时间同步
# ntpdate ntp.api.bz

2015年9月13日

ubuntu14.0.4通过apt-get安装软件时错误问题解决

ubuntu14.0.4通过apt-get安装软件包时，报以下错误：

E: 有未能满足的依赖关系。请尝试不指明软件包的名字来运行“apt-get -f install”(也可以指定一个解决办法)。

经过查找，原来ubuntu系统在新安装好后需要进行一些包的升级和清理工作，不然的话，后续安装各种软件都不顺畅，会出现各种各样的问题。

需要进行的包升级和清理工作其实很简单，只需要执行以下两条命令即可：

    apt-get -f install #用来升级一些相互依赖的包  
    apt-get autoremove #用来删除一些过时的包

但是在执行：

apt-get -f install

报以下错误：

Could not calculate the upgrade

A unresolvable problem occurred while calculating the upgrade.

Please report this bug against the 'update-manager' package and include the following error message:
'E:错误，pkgProblemResolver::Resolve 发生故障，这可能是有软件包被要求保持现状的缘故。

这个问题可能是源的问题导致的，可以通过换源解决
我把源更换成了sohu的，如下：

#vi /etc/apt/source.list
#在文件最后添加内容如下：
deb http://mirrors.sohu.com/ubuntu/ trusty main restricted universe multiverse
deb http://mirrors.sohu.com/ubuntu/ trusty-security main restricted universe multiverse
deb http://mirrors.sohu.com/ubuntu/ trusty-updates main restricted universe multiverse
deb http://mirrors.sohu.com/ubuntu/ trusty-proposed main restricted universe multiverse
deb http://mirrors.sohu.com/ubuntu/ trusty-backports main restricted universe multiverse
deb-src http://mirrors.sohu.com/ubuntu/ trusty main restricted universe multiverse
deb-src http://mirrors.sohu.com/ubuntu/ trusty-security main restricted universe multiverse
deb-src http://mirrors.sohu.com/ubuntu/ trusty-updates main restricted universe multiverse
deb-src http://mirrors.sohu.com/ubuntu/ trusty-proposed main restricted universe multiverse
deb-src http://mirrors.sohu.com/ubuntu/ trusty-backports main restricted universe multiverse

2015年9月13日

Docker 和 Lxc的异同
Docker is not a replacement for lxc. “lxc” refers to capabilities of the linux kernel (specifically namespaces and control groups) which allow sandboxing processes from one another, and controlling their resource allocations.

On top of this low-level foundation of kernel features, Docker offers a high-level tool with several powerful functionalities:
- Portable deployment across machines. Docker defines a format for bundling an application and all its dependencies into a single object which can be transferred to any docker-enabled machine, and executed there with the guarantee that the execution environment exposed to the application will be the same. Lxc implements process sandboxing, which is an important pre-requisite for portable deployment, but that alone is not enough for portable deployment. If you sent me a copy of your application installed in a custom lxc configuration, it would almost certainly not run on my machine the way it does on yours, because it is tied to your machine’s specific configuration: networking, storage, logging, distro, etc. Docker defines an abstraction for these machine-specific settings, so that the exact same docker container can run – unchanged – on many different machines, with many different configurations.
- Application-centric. Docker is optimized for the deployment of applications, as opposed to machines. This is reflected in its API, user interface, design philosophy and documentation. By contrast, the lxc helper scripts focus on containers as lightweight machines – basically servers that boot faster and need less ram. We think there’s more to containers than just that.
- Automatic build. Docker includes a tool for developers to automatically assemble a container from their source code, with full control over application dependencies, build tools, packaging etc. They are free to use make, maven, chef, puppet, salt, debian packages, rpms, source tarballs, or any combination of the above, regardless of the configuration of the machines.
- Versioning. Docker includes git-like capabilities for tracking successive versions of a container, inspecting the diff between versions, committing new versions, rolling back etc. The history also includes how a container was assembled and by whom, so you get full traceability from the production server all the way back to the upstream developer. Docker also implements incremental uploads and downloads, similar to “git pull”, so new versions of a container can be transferred by only sending diffs.
- Component re-use. Any container can be used as an “base image” to create more specialized components. This can be done manually or as part of an automated build. For example you can prepare the ideal python environment, and use it as a base for 10 different applications. Your ideal postgresql setup can be re-used for all your future projects. And so on.
- Sharing. Docker has access to a public registry (https://registry.hub.docker.com/) where thousands of people have uploaded useful containers: anything from redis, couchdb, postgres to irc bouncers to rails app servers to hadoop to base images for various distros. The registry also includes an official “standard library” of useful containers maintained by the docker team. The registry itself is open-source, so anyone can deploy their own registry to store and transfer private containers, for internal server deployments for example.
- Tool ecosystem. Docker defines an API for automating and customizing the creation and deployment of containers. There are a huge number of tools integrating with docker to extend its capabilities. PaaS-like deployment (Dokku, Deis, Flynn), multi-node orchestration (maestro, salt, mesos, openstack nova), management dashboards (docker-ui, openstack horizon, shipyard), configuration management (chef, puppet), continuous integration (jenkins, strider, travis), etc. Docker is rapidly establishing itself as the standard for container-based tooling.
摘自：http://stackoverflow.com/questions/17989306/what-does-docker-add-to-lxc-tools-the-userspace-lxc-tools
2015年8月12日
在Windows中监控liunx中的tomcat

目标：
在win7上通过jconsole监控远程服务器（192.168.100.128 端口19999）上的tomcat
linux上java的安装路径为：/usr/java/jdk1.6.0_20

1.登陆liunx，打开Tomcat目录下的bin/catalina.sh，在该文件中添加以下内容

CATALINA_OPTS=”$CATALINA_OPTS -Djava.rmi.server.hostname=192.168.100.128″
CATALINA_OPTS=”$CATALINA_OPTS -Dcom.sun.management.jmxremote -Dcom.sun.management.jmxremote.port=19999 -Dcom.sun.management.jmxremote.ssl=false -Dcom.sun.management.jmxremote.authenticate=false”

注意：
（1）必须设置-Djava.rmi.server.hostname，否则无法通过远程jmx方式连接
（2）此处是”CATALINA_OPTS”,而不是”JAVA_OPTS”
网上很多都写的是“JAVA_OPTS”，这样写是有问题的。
因为，添加到JAVA_OPTS中的配置会在启动和关闭的时候都尝试运行，在关闭tomcat的时候就会报端口已在使用的错误（ java.rmi.server.ExportException: Port already in use: 19999）。
因此，把监控的配置加入到CATALINA_OPTS，这样的配置只会在tomcat启动的时候运行。
2.配置jmxremote.password文件
$cd /usr/java/jdk1.6.0_20/jre/lib/management
$cp jmxremote.password.template jmxremote.password
$chomd 600 /usr/java/jdk1.6.0_20/jre/lib/management/jmxremote.password
如果不配置此项，在启动tomcat时，会报
3. 进入Tomcat安装目录下的bin目录，执行./startup.sh，启动Tomcat
4. linux上查看端口是否开启
netstat -an | grep 19999
如果看到19999端口已经启用，说明Tomcat的JMX配置成功

5.在win7中，打开jconsole，
（1）选择“远程进程”，
（2）输入“192.168.100.128:19999”
（3）点击“连接”
即可启动jconsole的管理界面.

2015年8月7日
解决eclipse hadoop1.2.1 插件 new hadoop location无反应

用eclipse4.3编译的hadoop1.2.1插件，在点击“new hadoop location”时，会出现没有反应，不出现对话框的情况。
原因就是eclipse的版本不匹配。

需要用eclipse4.2编译hadoop插件后，然后安装到eclipse4.3或者eclipse4.2中，就可以正常了

2015年3月31日