本文共 2547 字,大约阅读时间需要 8 分钟。
二叉搜索树的第k个结点
给定一颗二叉搜索树,请找出其中的第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 { int index = 0; //计数器 TreeNode KthNode(TreeNode root, int k) { if(root != null){ //中序遍历寻找第k个 TreeNode node = KthNode(root.left,k); if(node != null) return node; index ++; if(index == k) return root; node = KthNode(root.right,k); if(node != null) return node; } return null; }}
数据流中的中位数
得到一个数据流中的中位数。如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。import java.util.LinkedList;public class Solution { LinkedListlist = new LinkedList (); public void Insert(Integer num) { if (list.size()==0||num < list.getFirst()) { list.addFirst(num); } else { boolean insertFlag = false; for (Integer e : list) { if (num < e) { int index = list.indexOf(e); list.add(index, num); insertFlag = true; break; } } if (!insertFlag) { list.addLast(num); } } } public Double GetMedian() { if (list.size() == 0) { return null; } if (list.size() % 2 == 0) { int i = list.size() / 2; Double a = Double.valueOf(list.get(i - 1) + list.get(i)); return a / 2; } return Double.valueOf(list.get((list.size() + 1) / 2 - 1)); }}
滑动窗口的最大值
给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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.ArrayList;import java.util.Collections;import java.util.Arrays;public class Solution { public ArrayListmaxInWindows(int [] num, int size) { if(num==null||size<0){ return null; } ArrayList list=new ArrayList (); if(size==0){ return list; } ArrayList temp=null; int length=num.length; if(length (); for(int j=i;j
源代码:
转载地址:http://vhrin.baihongyu.com/