二叉查找树 (BST)

定义

任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。

特点

插入删除查找的平均复杂度都是O(log n),当节点有序的时候退化成链表O(n)复杂度(树的全部结点都只有左/右子树)

public class BinaryTree implements ITree {
    Node root;

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(4, 2);
        binaryTree.insert(3, 23423);
        binaryTree.insert(2, 234);
        binaryTree.display(binaryTree.root);
    }

    public void display(Node node) {
        if (node != null) {
            System.out.println(node.id + " " + node.data);
        }
        if (node.left != null) {
            display(node.left);
        }
        if (node.right != null) {
            display(node.right);
        }
    }

    public void insert(int id, Object data) {
        Node node = new Node();
        node.id = id;
        node.data = data;
        insert(node);
    }

    public void insert(Node node) {
        if (root == null) {
            root = node;
            return ;
        }

        Node currentNode = root;
        while (true) {
            if (node.id < currentNode.id) {
                currentNode = currentNode.left;
                if (currentNode == null) {
                    currentNode = node;
                }
            } else if (node.id > currentNode.id) {
                currentNode = currentNode.right;
                if (currentNode == null) {
                    currentNode = node;
                }
            } else {
                currentNode = node;
                break;
            }
        }

    }

    public Node max(){
        Node currentNode;
        if(root!=null){
            currentNode = root;
        }else{
            return null;
        }
        while(true){
            if(currentNode.right!=null){
                currentNode = currentNode.right;
            }else{
                return currentNode;
            }
        }
    }

    public Node min(){
        Node currentNode;
        if(root!=null){
            currentNode = root;
        }else{
            return null;
        }
        while(true){
            if(currentNode.left!=null){
                currentNode = currentNode.left;
            }else{
                return currentNode;
            }
        }
    }

    public Node find(int key) {
        Node currentNode = root;
        while (currentNode.id != key) {
            if (currentNode.id > key) {
                currentNode = currentNode.left;
            } else if (currentNode.id < key) {
                currentNode = currentNode.right;
            }
            if (currentNode == null) {
                return null;
            }

        }
        return currentNode;
    }

}

watch 实时监控命令

某司面试,问使用 Linux 命令,实时监控日志输出显示在终端。
watch 是 Linux 常见的命令行工具,watch 可以帮你监测一个命令的运行结果,省去一遍遍运行。

命令

watch [args][commond]

切换终端: Ctrl+x
退出:Ctrl+g

参数

-n --interval 指定间隔的时间,默认为两秒
-d --differences 高亮显示变化的区域,-d=cumulative选项会把有变动过的地方都高亮显示出来
-t -no-title 不显示在顶部的时间间隔和命令

示例

  1. 实时显示 Tomcat 访问记录
watch -n 1 tail -n 10 xxx_access.log

QQ图片20160818163431.jpg

  1. 监控实时访问80端口的IP
watch -n 0.5 'netstat -an | grep:80 | wc -l' 

ASCii Unicode Java 转换

如果一个仅包含基本7位ASCIII字符的Unicode文件,如果每个字符都使用2字节的原Unicode编码传输,其第一字节的8位始终为0。这就造成了比较大的浪费。对于这种情况,可以使用UTF-8编码,这是一种变长编码,它将基本7位ASCII字符仍用7位编码表示,占用一个字节(首位补0)。而遇到与其他Unicode字符混合的情况,将按一定算法转换,每个字符使用1-3个字节编码,并利用首位为0或1进行识别,这样大大节省了空间。

转换

ascii => char

char char1 = 32

char => ascii

int asciiNum = (int)char1

字符串转ASCii

    public static String string2Ascii(String value) {
        StringBuffer sb = new StringBuffer();
        char[] chars = value.toCharArray();
        for (int i = 0; i < chars.length; i++) {
                sb.append((int) chars[i]).append(",");
        }
        return sb.substring(0,sb.length()-1).toString();
    }

ASCii转字符串

   public static String ascii2String(String value) {
        StringBuffer sb = new StringBuffer();
        String[] chars = value.split(",");
        for (int i = 0; i < chars.length; i++) {
            sb.append((char) Integer.parseInt(chars[i]));
        }
        return sb.toString();
    }

字符转Unicode

Integer.toHexString('蛤') //十六进制
Integer.toOctalString('蛤') //十进制

Unicode构造字符

(char)Integer.parseInt("103344", 16)

注意

\r 回车,ASCii码13
\n 换行,ASCii码10
空格,ASCii码32
阿拉伯数字的码数(48~57)比大写字母(65~90)小,大写字母的码数比小写字母(97~122)小

不要再写错二分查找

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
但是边界问题需要严谨确定,否则陷入死循环或者找不到应有对象。

  public int find(int[] array, int value) {
        int found = -1;
        int start = 0;
        int end = array.length - 1;    //  下标范围是数目减去一
        int mid;
        int o=1;
        while (start <= end) {    // 必须是闭合区间,否则当两者差一的时候会陷入死循环
            mid = (start + end) / 2;
            if (array[mid] == value) {
                return mid;
            } else if (array[mid] < value) {
                start = mid + 1;
            } else if (array[mid] > value) {
                end = mid - 1;
            }
            o++;
        }
        return found;
    }

Ubuntu Oracle Java8

Oracle JDK与OpenJDK里的JVM都是HotSpot VM,从源码层面说,两者大部分是同一个东西,但是在桌面上上最重要的是GUI部分代码有较大不同,OpenJDK环境下的图像渲染效果与Oracle JDK 有较大差异。
添加软件源

sudo add-apt-repository ppa:webupd8team/java

更新依赖

sudo apt-get update

安装

sudo apt-get install oracle-java8-installer

查看安装后的 Java 版本

java -version
java version "1.8.0_101"
Java(TM) SE Runtime Environment (build 1.8.0_101-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.101-b13, mixed mode)