算法学习之剑指offer（十一）

一

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

import java.util.*;

/*

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer> > list = new ArrayList<ArrayList<Integer> >();

        int layer=1;

        Stack<TreeNode> stack1 = new Stack<>();

        stack1.push(pRoot);

        Stack<TreeNode> stack2 = new Stack<>();

        while(!stack1.empty()||!stack2.empty()){

            if(layer%2==1){

                ArrayList<Integer> tmp = new ArrayList<Integer>();

                while(!stack1.empty()){

                    TreeNode node = stack1.pop();

                    if(node!=null){

                        tmp.add(node.val);

                        stack2.push(node.left);

                        stack2.push(node.right);

                    }

                }

                if(!tmp.isEmpty())

                    list.add(tmp);

                layer++;

            }else{

                ArrayList<Integer> tmp = new ArrayList<Integer>();

                while(!stack2.empty()){

                    TreeNode node = stack2.pop();

                    if(node!=null){

                        tmp.add(node.val);

                        stack1.push(node.right);

                        stack1.push(node.left);

                    }

                }

                if(!tmp.isEmpty())

                    list.add(tmp);

                layer++;

            }

        }

        return list;

    }

}

二

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

import java.util.*;

/*

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {

        ArrayList<ArrayList<Integer> > list = new ArrayList<ArrayList<Integer> >();

        ArrayList<TreeNode> tmpList = new ArrayList<TreeNode>();

        if(pRoot==null)

            return list;

        tmpList.add(pRoot);

        while(!tmpList.isEmpty()){

            ArrayList<TreeNode> tmpList2 = new ArrayList<TreeNode>();

            ArrayList<Integer> tmpInt = new ArrayList<Integer>();

            for(int i=0;i<tmpList.size();i++){

                tmpInt.add(tmpList.get(i).val);

                if(tmpList.get(i).left!=null)

                    tmpList2.add(tmpList.get(i).left);

                if(tmpList.get(i).right!=null)

                tmpList2.add(tmpList.get(i).right);

            }

            list.add(tmpInt);

            tmpList = new ArrayList<TreeNode>(tmpList2);

        }

        return list;

    }

}

三

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

/*

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    String Serialize(TreeNode root) {

        StringBuffer sb = new StringBuffer();

        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();

  }

    private int index=-1;

    TreeNode Deserialize(String str) {

        index++;

       int len = str.length();

        if(index >= len){

            return null;

        }

        String[] strr = str.split(",");

        TreeNode node = null;

        if(!strr[index].equals("#")){

            node = new TreeNode(Integer.valueOf(strr[index]));

            node.left = Deserialize(str);

            node.right = Deserialize(str);

        }

        return node;

  }

}

四

题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

/*

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    private int index=0;

    TreeNode resultNode;

    TreeNode KthNode(TreeNode pRoot, int k)

    {

        if(pRoot == null || k <= 0){

            return null;

        }

        KthNode2(pRoot,k);

        return resultNode;

    }

     void KthNode2(TreeNode pRoot, int k){

         if(pRoot == null){

             return;

         }

         KthNode(pRoot.left,k);

         index++;

         if(index == k){

             resultNode = pRoot;

         }

         KthNode(pRoot.right,k);

     }

}

五

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

import java.util.*;

public class Solution {

    private int count=0;

    //PriorityQueue默认按自然排序，优先取最小的

    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1;

        }

    });

    //第偶数个插入minHeap,第奇数个插入maxHeap。maxHeap里的数据都小于minHeap里的

    public void Insert(Integer num) {

        //因为要保证minHeap里的都比maxHeap大，所以先放入maxHeap，再挑maxHeap里最大的放入minHeap

        if (count %2 == 0) {

            maxHeap.offer(num);

            int filteredMaxNum = maxHeap.poll();

            minHeap.offer(filteredMaxNum);

        } else {

            minHeap.offer(num);

            int filteredMinNum = minHeap.poll();

            maxHeap.offer(filteredMinNum);

        }

        count++;

    }

    public Double GetMedian() {

        if (count %2 == 0) {//偶数取中位数得除2

            return new Double((minHeap.peek() + maxHeap.peek())) / 2;

        } else {//奇数个，说明最后一个插到minHeap里了

            return new Double(minHeap.peek());

        }

    }

}

六

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

import java.util.*;

public class Solution {

    public ArrayList<Integer> maxInWindows(int [] num, int size)

    {

        ArrayList<Integer> list = new ArrayList<Integer>();

        if(num==null||num.length==0||size<=0)

            return list;

        int i=0,length=num.length;

        while((i+size)<=length){

            list.add(maxInNums(num,i,i+size-1));

            i++;

        }

        return list;

    }

    public int maxInNums(int [] num, int start,int end)

    {

        int maxnum=num[start];

        for(int i=start+1;i<=end;i++){

            if(maxnum<num[i])

                maxnum=num[i];

        }

        return maxnum;

    }

}

巴特西

算法学习之剑指offer（十一）

题目描述

题目描述

题目描述

题目描述

题目描述

题目描述

最新文章

热门文章