Java日记2018-06-06

37. 序列化二叉树
    所谓的序列化指的是把树的值，按照前序或者后序序列，变成一个字符串；反序列化就是字符串变成一个树结构；

//37. 序列化二叉树
    public static String Serialize(TreeNode root){
        if(root==null) return "#";
        return root.val+" "+Serialize(root.left) + " " + Serialize(root.right);
    }
    
    
    /**
     * 反序列化
     */
    private int index;
    public TreeNode Deserialize(String str) {
        if(str == null || str.trim().length() == 0)
            return null;
        String[] nums = str.split(",");
        index = 0;
        return Deserialize(nums);
    }

    public TreeNode Deserialize(String[] nums) {
        if(nums[index].equals("$")) {
            ++index;
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(nums[index++]));
        node.left = Deserialize(nums);
        node.right = Deserialize(nums);
        return node;
    }

38. 字符串的排列
    方法还记得，具体实现时候还是遇到了问题，细节还需要再学习一下

// 38. 字符串的排列
    public static void Permutation(StringBuffer stb) {
        if (stb == null)
            return;
        // for(int i=0;i<stb.length();i++) {
        PermuCore(stb, 0, stb.length() - 1);
        // }
    }

    public static void PermuCore(StringBuffer stb, int start, int end) {
        if (start > end)
            return;
        if (start == end) {
            System.out.println(stb);
        } else {
            for (int i = start; i <= end; i++) {
                //选取一个元素放到当前最开始的位置（因为有for循环来回的增加i的值）
                swap(stb, start, i);
                 //剩余全排列，
                PermuCore(stb, start + 1, end);
                 //把元素放回原位置
                swap(stb, start, i);
            }
        }

    }

    public static void swap(StringBuffer stb, int i, int j) {
        char temp = stb.charAt(i);
        stb.setCharAt(i, stb.charAt(j));
        stb.setCharAt(j, temp);

    }

39. 数组中出现次数超过一半的数字
    数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数的和还要多。因此我们可以遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1.如果次数为0，我们需要保存下一个数字，并把次数设为1.由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

public class moreThanHalfNum {
    public static int find(int[] arr) {
        if(arr.length<1) return -1;
        int res=arr[0];
        int count=1;
        for(int i=1;i<arr.length-1;i++) {
            if(count==0) {
                res=arr[i];
                count=1;
            }
            if(arr[i]==res) {
                count++;
            } else {
                count--;
            }
        }
        //判断这个res是不是占有一大半的数字
        int cnt = 0;
        for (int val : arr)
            if (val == res)
                cnt++;
        
        System.out.println("teh res is:"+res);
        //如果占有一大半返回res，否则返回0
        return cnt > arr.length / 2 ? res : 0;
        
    }

40. 最小的 K 个数
    可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字；
    Partition 来源于快速排序思想.
    观察快速排序是把全部数组排序，当前值需要前k个就行，所以加上对于index与k的判断，只要前k个

具体实现要观察注释里面写的坑

//40. 最小的 K 个数
    public static int littk(int[] arr,int k) {
        if(arr==null) return -1;
        int index=0;
        index = partion(arr,0,arr.length-1);
        int start = 0;
        int end = arr.length - 1;
        while(index!=k-1) {
            if(index>k-1){
                //end及下面的start要给值，不然会浪费大量时间
                end = index-1;
                index=partion(arr,start,end);
            }else{
                start = index+1;
                index=partion(arr,start,end);
            }
        }
        return index;
    }
    public static int partion(int[] arr,int start,int end){
        int res = arr[start];
        while(start<end){
            while(start<end&&arr[end]>=res) {
                end--;
            }
            arr[start] = arr[end];
            while(start<end&&arr[start]<res){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=res;
        return start;
        
    }
    
    //快速排序
    public static void sort_fast(int[] arr,int left,int right) {
        if(left>right) return;
        
        int i= partion2(arr,left,right);
        sort_fast(arr,left,i-1);
        sort_fast(arr,i+1,right);
        
    }