20180826_ARTS_W3

Algorithm

315. Count of Smaller Numbers After Self
解题思路：暴力破解法时间复杂度o(n^2), 显然不符合条件；仔细分析发现跟二分有点关系，然后基本就能想到二叉搜索树了，时间复杂度为o(nlogn)

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return list;
        
        BST bst = new BST();
        
        Integer[] tmp = new Integer[nums.length];
        
        for(int i=nums.length-1;i>=0;i--){
            tmp[i] = bst.insert(nums[i]);
        }
        
        list.addAll(Arrays.asList(tmp));
        
        return list;
    }
    
    private static class BST{
        private Node root;
        private int insert(int val){
            int scnt = 0;
            if(root == null){
                root = new Node(val);
                return scnt;
            }
            else{
                Node cur = root;
                while(true){
                    if(cur.val < val){
                        scnt += cur.selfcnt + cur.lcnt;
                        if(cur.right != null){
                            cur = cur.right;
                        }
                        else{
                            cur.right = new Node(val);
                            return scnt;
                        }
                    }
                    else if(cur.val > val){
                        cur.lcnt++;
                        if(cur.left != null){
                            cur = cur.left;
                        }
                        else{
                            cur.left = new Node(val);
                            return scnt;
                        }
                    }
                    else{
                        scnt += cur.lcnt;
                        cur.selfcnt++;     //自己的不能加进去
                        return scnt;
                    }
                }
            }
        } 
    }
    
    private static class Node{
        private Node left;
        private Node right;
        private int val;
        //左边的叶子树 比当前根小的个数
        private int lcnt;
        //当前根存在的个数(因为可能存在重复元素)
        private int  selfcnt;
        private Node(int val){
            this.val = val;
            selfcnt = 1;
        }
    }
}

Review

最近刚好想深入了解下kafka的原理而不只限于使用，看到耗叔推荐的论文：Kafka - A Distributed Messaging System for Log Processing, 将kafka的主要特性描述了一遍，很受用。
写了一下读书笔记：https://www.jianshu.com/p/60c37b35215c

Tips

java如何dump查看线程运行情况
windows系统：cmd输入：jvisualvm 查看java进程号==>jstack pid (其中pid就是进程号)，也可以将其内容打印到文件 jstack -l pid > dump11.txt
linux: ps -ef|grep java查询进程号==>jstack pid

Share

很惭愧，之前漏了两周的ARTS，但是我会接受事实，不会因为之前的偷懒而一直偷懒下去，改变的最好时刻就是现在，所以也不想太多，静下来每周定期总结。
自己现在写的ARTS水平不高，我的目标就是坚持，坚持下来再说别的，其实RTS把一周的工作过程总结一下就行了，A算法花1个小时左右写一下就ok了，关键还是坚持，坚持写下去，完成耗叔所说的"深度学习"。
工作时间好好工作，工作之余该学技术好好学，该运动运动，还是要将工作和生活分清楚，既不能让工作影响到生活，也别让生活影响到工作，当然这里说的影响是负面的，正面的当然是没问题的。