题目1——判断一个链表是否为回文结构

给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。

示例
输入：{1,2,2,1}
输出：true
输入：{2,1}
输出：false

解题思路

可以利用快慢指针，将左半部分字符串入栈，然后慢指针从中间部分开始遍历链表，每遍历一个元素，与栈顶元素作比较，若不等，则不是回文结构；否则继续遍历，链表遍历结束后则为回文字符串。
时间复杂度O(n)，空间复杂度为O(n)。

也可以使用快慢指针，当慢指针达到中间位置时，将慢指针后面的部分进行翻转，再与前半部分进行比较。
时间复杂度O(n)，空间复杂度O(1)。

代码实现

import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; * } */
public class Solution {
    
    public boolean isPail (ListNode head) {
    
        if(head == null || head.next == null)
            return true;
        
        Stack<Integer> st = new Stack<Integer>();
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
    
            st.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null)
            slow = slow.next;
        while(slow != null){
    
            if(slow.val != st.pop())
                return false;
            slow = slow.next;
        }
        return true;
    }
}

import java.util.*;
/* * public class ListNode { * int val; * ListNode next = null; * } */
public class Solution {
    
    public boolean isPail (ListNode head) {
    
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
    
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null)
            slow = slow.next;
        slow = reverse(slow);
        fast = head;
        while(slow != null){
    
            if(slow.val != fast.val)
                return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
    
        ListNode pre = null;
        while(head != null){
    
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

题目2——数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
要求：空间复杂度O(n)，时间复杂度O(nlogn)。

示例
输入：[5,2,3,4,1,6,7,0,8]
输出："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：数据流里面不断吐出的是5,2,3…，则得到的平均数分别为5,(5+2)/2,3,(3+4)/2,…

解题思路

可以利用集合，并保证每次插入一个新的元素都能使得集合中的元素有序，插入排序的做法就是遍历集合，然后找到元素的插入位置。最后根据集合大小返回中间元素。
空间复杂度O(n)，时间复杂度O(n)。

中位数在左半部分元素中是最大的，在右半部分元素中是最小的，所以我们可以通过维护左右两部分，就能得到最大值和最小值。可以想到利用堆排序，每次插入元素时间复杂度是O(logn)，并且可直接取出堆顶元素。具体做法如下：

• 维护两个堆，左边是大顶堆用于获取左半部分最大值，右边是小顶堆用于获取右半部分最小值；
• 当一共有奇数个元素时，使小顶堆的个数比大顶堆多一，取小顶堆的堆顶元素；当有偶数个元素时，两个堆的个数相同，取两个堆顶元素的平均值；
• 每次输入元素时先进入小顶堆排序，然后将小顶堆的最大值弹入到大顶堆中，完成整个排序；
• 大顶堆的数据可能会可能会多于小顶堆的数据，需要从大顶堆中弹出顶部元素到小顶堆中进行平衡。

代码实现

//插入排序
import java.util.*;
public class Solution {
    
    private ArrayList<Integer> arr = new ArrayList<Integer>();
    public void Insert(Integer num) {
    
        if(arr.isEmpty())
            arr.add(num);
        else{
    
            int i=0;
            for(;i<arr.size();i++){
    
                if(num<=arr.get(i))
                    break;
            }
            arr.add(i,num);
        }
    }
    public Double GetMedian() {
    
        int n = arr.size();
        if(n%2 == 1)
            return (double)(arr.get(n/2));
        else
            return (arr.get(n/2-1)+arr.get(n/2))/2.0;
    }
}

import java.util.*;
public class Solution {
    
    //大顶堆
    private PriorityQueue<Integer> max = new PriorityQueue<>();
    //小顶堆
    private PriorityQueue<Integer> min = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
// private PriorityQueue<Integer> min = new PriorityQueue<>(new Comparaotr<Integer>(){
    
// @Override
// public int compare(Integer i1,Integer i2){
    
// return i2-i1;
// }
// });
    public void Insert(Integer num) {
    
        //先进入到小顶堆
        min.offer(num);
        //然后进入到大顶堆完成整体排序
        max.offer(min.poll());
        //平衡两个堆的数量
        if(min.size()<max.size())
            min.offer(max.poll());
    }

    public Double GetMedian() {
    
        //奇数个元素
        if(min.size()>max.size())
            return (double)min.peek();
        else
            return (double)(min.peek()+max.peek())/2;
    }
}

PriorityQueue常用方法

PriorityQueue类是基于优先级的队列的通用实现，其中的元素排序由自然排序原则确定
或根据创建期间提供的Comparator进行定制。

PriorityQueue实现了Queue接口，不允许放入空元素，它通过完全二叉树实现的小顶堆，即
任意一个非叶子结点的权值，都不大于其左右子节点的权值，其底层可通过数组来实现。

• boolean add(E e)：将指定的元素插入到此优先级队列中。
• boolean offer(E e)：将指定的元素插入到此优先级队列中 。
• E poll()：返回并删除此队列的头，如果队列为空则返回null。
• E peek()：返回此队列的头但是并不删除，如果队列为空则返回null。
• boolean element()：返回此队列的头但是并不删除，如果为空抛出异常。
• boolean remove(Object o)：如果存在，则从该队列中删除指定元素的单个实例。
• boolean remove()：删除此队列的头，操作失败则抛出异常。