剑指offer - 栈、队列、堆 - 《算法》

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 `appendTail` 和 `deleteHead` ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，`deleteHead` 操作返回 -1 ) 示例 1：输入： [“CQueue”,”appendTail”,”deleteHead”,”deleteHead”] [[],[3],[],[]] 输出：[null,null,3,-1]

题解思路1：双栈
维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作。根据栈先进后出的特点，我们每次往第一个栈里插入元素后，第一个栈的顶部元素是最后插入的元素。当我们需要删除元素时，需要将栈1的元素转移到栈2中，这样就能实现队列的先进先出。

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    public void appendTail(int value) {
        stack1.push(value);
    }
    public int deleteHead() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()){
            return -1;
        }else{
            return stack2.pop();
        }
    }
}

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

题解思路：使用一个额外的minStack，栈顶元素为当前栈中的最小的值，在对栈进行push入栈和push出栈操作时，同样需要对minStack进行入栈和出栈操作，从而使minStack栈顶元素一直为当前栈中的最小值。在进行push（）操作时，需要比较入栈元素和当前栈中的最小值，将值较小的push到minStack中。

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    /**
     * initialize your data structure here.
     */
    public MinStack() {
        dataStack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    public void push(int x) {
        dataStack.push(x);
        minStack.push(minStack.isEmpty() ? x : Math.min(minStack.peek(), x));        ***
    }
    public void pop() {
        dataStack.pop();
        minStack.pop();                                                        ***
    }
    public int top() {
        return dataStack.peek();
    }

关键点： 1、如何获取栈中的最小元素？如果在原来的栈上直接操作必然涉及大量的操作，所以可以考虑使用空间换时间，创建一个额外的栈，这个栈从上到下的顺序为原来栈当前拥有元素的最小值。 2、如何保证minStack中的栈顶元素始终为最小的元素？在dataStack弹出元素的使用，minStack也要弹出元素。 3、保证dataStack与minStack的数据量是一样的 minStack.push(minStack.isEmpty() ? x : Math.min(minStack.peek(), x));

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

题解思路：使用一个栈来模拟压入弹出的操作。每次入栈一个元素后，都要判断一下栈顶元素是不是当前出栈序列popped的第一个元素，如果是的话则执行出栈操作并将popped往后移动一位，继续进行判断。
自己的解法（错误）

 public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        //压栈判断
        while (i < pushed.length) {
            stack.push(pushed[i++]);
            if (popped[j] == stack.peek()) {
                stack.pop();
                j++;
            }
        }
        //出栈判断
        while (!stack.isEmpty()) {
            if (stack.pop() != popped[j++])
                return false;
        }
        return true;
    }

无法通过测试用例：[2,1,0] [1,2,0]

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while (i < n) {        //for(;i<n;)
            stack.push(pushed[i++]);
            while (j < n && !stack.isEmpty() && stack.peek() == popped[j]) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

关键就在于进栈后不一定只执行一次出栈操作，如果条件满足的话，需要执行多次的出栈操作。这也是我一开始错误的原因关键点： 1、如何判断最后是否满足条件？栈是否为空，如果为空说明全部出栈为true，否则为false； 2、如何保证执行多次出栈操作？ while死循环，注意stack为空的判断

剑指 Offer 40. 最小的k个数

输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。示例 1：输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]

题解思路1：排序

对原数组从小到大排序后取出前k个元素即可

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }
}

题解思路2：堆

用一个大根堆实时维护数组的前k小值。首先将前k个数插入大根堆中，随后从第k+1个数开始遍历，如果当前遍历到的数比大根堆堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数，最后将大根堆里的数存入数组返回即可。

top k算法的经典实现是大顶堆和小顶堆，在java中可以用PriorityQueue实现小顶堆
大顶堆实现

 public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) {
            return vec;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });//java中的优先队列，默认出队列的数据是小数，通过自定义比较器，出队列的数据的大数

        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            vec[i] = queue.poll();
        }
        return vec;
    }

在java中优先队列只保证每次取出的元素一定是最小的。

小顶堆实现

 public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];

        PriorityQueue<Integer> queue = new PriorityQueue<>();

        //直接将所有的元素加入到优先队列中
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
        }

        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }

        return res;
    }

题解思路3：快排思想
快排的划分函数每次执行完后都能将数组划分成两个部分，小于等于分界值的元素会被放在数组的左边，大于的会被放在分界值的右边，然后返回分界值的下标。与快排不同的是，快排会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分一边。查找前k个元素时，不需要对整个数组进行排序，因此使用快排的效率是最高的。

 public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0)
            return new int[0];
        //最后一个参数表示要找的是下标为k-1的数（即找到k个数）
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        //每快排切分一次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        return j > k ? quickSearch(nums, 0, j - 1, k) : quickSearch(nums, j + 1, hi, k);
    }

    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v) ;
            while (--j >= lo && nums[j] > v) ;
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }

剑指 Offer 41. 数据流中的中位数

| 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000] | | —- |

题解思路1：双顶堆
创建一个大顶堆和一个小顶堆

class MedianFinder {
    private PriorityQueue<Integer> left;
    private PriorityQueue<Integer> right;
    private int size;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        left = new PriorityQueue<Integer>((o1, o2) -> (o2 - o1));
        right = new PriorityQueue<Integer>();
        size = 0;

    }

    public void addNum(int num) {
        if (size % 2 == 0) {
            left.offer(num);                ***        
            right.offer(left.poll());        ***
        } else {
            right.offer(num);
            left.offer(right.poll());
        }
        size++;
    }

    public double findMedian() {
        if (size % 2 == 0) {
            return (left.peek()+ right.peek()) / 2.0;
        } else {
            return (double) right.peek();
        }
    }
}

关键点： 1、如何保证左边的队列全是小于的，右边的队列全是大于的？添加的时候先在大顶堆中，再从大顶堆中弹出一个元素，这样就能保证获取的元素是要比中心值大的。 2、如何保证输出的元素是double？除一个浮点数或者强制类型转换

剑指 Offer 41.2 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。如果当前字符流没有存在出现一次的字符，返回#字符。

题解思路：
1、使用统计数组来统计每个字符出现的次数，本题涉及到的字符为都为 ASCII 码，因此使用一个大小为 128 的整型数组就能完成次数统计任务。
2、使用队列来存储到达的字符，并在每次有新的字符从字符流到达时移除队列头部那些出现次数不再是一次的元素。因为队列是先进先出顺序，因此队列头部的元素为第一次只出现一次的字符。

private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();

public void Insert(char ch) {
    cnts[ch]++;
    queue.add(ch);
    while (!queue.isEmpty() && cnts[queue.peek()] > 1)
        queue.poll();
}

public char FirstAppearingOnce() {
    return queue.isEmpty() ? '#' : queue.peek();
}

本题与剑指Offer 50 类似

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(Map.Entry<Character, Boolean> d : dic.entrySet()){
            if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

Map方法的灵活使用，通过Character，Boolean的方式来判断该键元素是不是出现过一次以上。

剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大。
题解思路1：大顶堆

 public int[] maxSlidingWindow(int[] nums, int k) {
        if (k > nums.length || k < 1)
            return new int[0];

        int[] res = new int[nums.length - k + 1];
        int x = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> (o2 - o1));

        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }

        res[x++] = queue.peek();

        for (int i = 0, j = i + k; j < nums.length; i++, j++) {
            queue.remove(nums[i]);
            queue.offer(nums[j]);
            res[x++] = queue.peek();
        }

        return res;
    }

关键点： 1、queue.remove( ):删除指定元素

题解思路2：双端队列

 public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) {
            return nums;
        }

        int[] arr = new int[len - k + 1];
        int arr_index = 0;
        //维护一个单调递增的双端队列
        Deque<Integer> deque = new LinkedList<>();
        //先将第一个窗口的值按照规则入队
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.offerLast(nums[i]);
        }
        //将第一个窗口的最优解存到数组中
        arr[arr_index++] = deque.peekFirst();
        //移动窗口
        for (int j = k; j < len; j++) {
            if (nums[j - k] == deque.peekFirst()) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
                deque.removeLast();
            }
            deque.offerLast(nums[j]);
            arr[arr_index++] = deque.peekFirst();
        }
        return arr;
    }