public class CodingInterview_042 {
    public int FindGreatestSumOfSubArray(int[] array) {
       int[] dp=new int[array.length+1];
       dp[0]=0;
       int maxSum=Integer.MIN_VALUE;
       for(int i=0;i<array.length;i++){
           dp[i+1]=Math.max(array[i],array[i]+dp[i]);
           if(dp[i]>=maxSum){
               maxSum=dp[i];
           }
       }
       return maxSum;
    }

    public static void main(String[] args) {
        int[] arr={1,-2,3,10,-4,7,2,-5};
        CodingInterview_042 c=new CodingInterview_042();
        System.out.println(c.FindGreatestSumOfSubArray(arr));
    }
}

public class CodingInterview_041_1 {
    HashMap<Character, Integer> map=new HashMap();
    ArrayList<Character> list=new ArrayList<Character>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch)){
            map.put(ch,map.get(ch)+1);
        }else{
            map.put(ch,1);
        }

        list.add(ch);
    }

    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {   char c='#';
        for(char key : list){
            if(map.get(key)==1){
                c=key;
                break;
            }
        }

        return c;
    }
}

public class CodingInterview_041 {
    //小顶堆
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    //大顶堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    //记录偶数个还是奇数个
    int count = 0;
    //每次插入小顶堆的是当前大顶堆中最大的数
    //每次插入大顶堆的是当前小顶堆中最小的数
    //这样保证小顶堆中的数永远大于等于大顶堆中的数
    //中位数就可以方便地从两者的根结点中获取了
    public void Insert(Integer num) {
        //个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
        if(count % 2 == 0){
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        }else{
            //个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }

    public Double GetMedian() {
        //当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
        if(count % 2 == 0){
            return new Double(minHeap.peek() + maxHeap.peek())/2;
        }else{
            //当前为奇数个，则直接从小顶堆中取元素即可
            return new Double(minHeap.peek());
        }
    }
}

public class CodingInterview_039 {
    /*
    第一种思路是比较正常的思路，用map记录所有数字出现的次数。然后直接进行比较就可以。
     */
    public int MoreThanHalfNumWithMap_Solution(int [] array) {
        int num = 0;

        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int len =  array.length ;
        if(len == 0) return 0;
        for(int i = 0; i < len ;i++){
            if(map.containsKey(array[i])){
                int count = map.get(array[i]);
                ++count;
                map.put(array[i],count);
            }else{
                map.put(array[i],1);
            }
        }
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(entry.getValue() > (len/2)){
                num = entry.getKey();
            }

        }
        return num;
    }

    /*
    某个数字出现的次数大于数组长度的一半，意思就是它出现的次数比其他所有数字出现的次数和还要多。因此我们可以在遍历数组的时候记录两个值：1. 数组中的数字;2. 次数。
    遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。最后再判断它是否符合条件。
    */
    public int MoreThanHalfNum_Solution(int [] array) {
        int res = array[0], count = 1;
        for(int i=1; i<array.length; i++){
            if(array[i] == res)
                count++;
            else{
                count--;
            }
            if(count == 0){
                res = array[i];
                count = 1;
            }
        }
        count = 0;
        for(int i=0; i<array.length; i++){
            if(array[i] == res)
                count++;
        }
        return count > array.length/2 ? res : 0;
    }

}

public class CodingInterview_038 {


    public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            //Collections.sort可以直接按字典序打印出字符串的排列，所以我们要做的实际上只是把字符串的全排列放到list里面去就行了
            Collections.sort(list);
        }
        return list;
    }

    //i表示用第i位与后面的字符交换
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            //用当前字符（下标为i的字符）放在第i位对应的字符串排列总数
            charSet.add(chars[i]);
            PermutationHelper(chars,i+1,list);
            //将第i个字符依次与后面的字符交换放在第i位对应第字符串第排列总数。
            for(int j=i+1;j<chars.length;++j){
                if(!charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }


    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

public class CodingInterview_037 {
    public static void main(String[] args) {
        //这一题我们需要先明确serialze之后表示树的字符串长成什么样子，比如一个最简单的树以1为root，2，3分别为其左右节点的树经过前序遍历的字符串打印出来应该是：1,2,#,#,3,#,#,的
        TreeNode t=new TreeNode(1);
        t.left=new TreeNode(2);
        t.right=new TreeNode(3);
        CodingInterview_037 c=new CodingInterview_037();
        String s=c.Serialize(t);
        System.out.println(s);
    }


    int index=-1;
    public String Serialize(TreeNode root) {
        //通过前序遍历构建二叉树字符串
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    public TreeNode Deserialize(String str) {
        String[] numberArray=str.split(",");
        TreeNode node=DeserialzieArray(numberArray);
        return node;
    }
    //下面这种解法是错误范例，结合例子很容易就看出来右子树的下标不对，这种情况下我们应该用全局变量来处理，让递归函数自己递增下标。
    /*
    private TreeNode DeserialzieArray(String[] numberArray,int index){
        if(numberArray[index].equals("#")){
            return null;
        }else{
            TreeNode node=new TreeNode(Integer.parseInt(numberArray[index]));
            node.left=DeserialzieArray(numberArray,index+1);
            node.right=DeserialzieArray(numberArray,index+2);
            return node;
        }
    }
    */
    //像这种感觉需要返回多个值的递归问题，我们都可以采用全局变量来处理。本题中用全局变量index来追踪index的位置
    private TreeNode DeserialzieArray(String[] numberArray){
        index++;
        if(numberArray[index].equals("#")){
            return null;
        }else{
            TreeNode node=new TreeNode(Integer.parseInt(numberArray[index]));
            node.left=DeserialzieArray(numberArray);
            node.right=DeserialzieArray(numberArray);
            return node;
        }
    }



}

public class CodingInterview_036 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }

    public TreeNode Convert(TreeNode root) {
        if(root==null)
            return null;
        if(root.left==null&&root.right==null)
            return root;
        // 1.将左子树构造成双链表，并返回链表头节点
        TreeNode left = Convert(root.left);
        TreeNode p = left;
        // 2.定位至左子树双链表最后一个节点
        while(p!=null&&p.right!=null){
            p = p.right;
        }
        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
        if(left!=null){
            p.right = root;
            root.left = p;
        }
        // 4.将右子树构造成双链表，并返回链表头节点
        TreeNode right = Convert(root.right);
        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
        if(right!=null){
            right.left = root;
            root.right = right;
        }
        return left!=null?left:root;
    }
}