Java日记2018-05-12

第一题 序列化反序列化二叉树
先序遍历，null节点用特殊符号标记。 比较简单，不再想了

public class Solution {

    public static void serialize(TreeNode root, PrintStream ps) {
        if (root == null)
            ps.print("# ");
        else {
            ps.print(root.val + " ");
            serialize(root.left, ps);
            serialize(root.right, ps);
        }
    }

    public static TreeNode deserialize(Scanner cin) {
        String token = cin.next();
        if (token.equals("#"))
            return null;
        int val = Integer.parseInt(token);
        TreeNode root = new TreeNode(val);
        root.left = deserialize(cin);
        root.right = deserialize(cin);

        return root;

    }

    public static void main(String[] args) throws FileNotFoundException {
        TreeNode root = new TreeNode(30);
        root.left = new TreeNode(20);
        root.left.left = new TreeNode(10);
        root.right = new TreeNode(40);
        root.right.left = new TreeNode(35);
        root.right.right = new TreeNode(50);
        PrintStream ps = new PrintStream(new File("serialize.txt"));
        serialize(root, ps);

        Scanner cin = new Scanner(new File("serialize.txt"));
        TreeNode back = deserialize(cin);
        
        System.out.println(back.val);

    }
}

第二题 字符串的排列

从字符串数组中每次选取一个元素，放到数组最前面。然后，对剩余的元素全排列，步骤跟上面一样。很明显这是个递归处理的过程，一直到最后即可。

package com.lyc.dataautest;

public class ArrangeString {
    public static void arrange(String str) {
        if(str.length()==0) return;
        StringBuffer strb = new StringBuffer(str);
        arrangecore(strb,0,str.length()-1);
    }
    public static void arrangecore(StringBuffer strb,int start,int end) {
        if(strb.length()==0) return;
        if(start==end) {
            System.out.println("strb is:"+strb);
        } else {
            for(int i=start;i<=end;i++) {
                //选取一个元素放到当前最开始的位置（因为有for循环来回的增加i的值）
                swap(strb,start,i);
                //剩余全排列，
                arrangecore(strb,start+1,end);
                //把元素放回原位置
                swap(strb,start,i);
            }
        }
        
    }
    public static void swap(StringBuffer strb,int start,int end) {
        char temp= strb.charAt(start);
        strb.setCharAt(start, strb.charAt(end));
        strb.setCharAt(end, temp);
        
    }
    
    public static void main(String[] args) {
        
        String str2 = "abc";
        arrange(str2);
    }

}

问题 3

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

package com.lyc.dataautest;

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;
        
    }
    
    public static void main(String[] args) {
        int[] arr={1,2,3,5,2,5,5,5,6,5,7,5,5,5,5};
        find(arr);
    }

}