46、圆圈中最后剩下的数+++

约瑟夫环，数学

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

题意分析

用模拟来做自然是可以的。但复杂度是O(n*m)。看了一下别人的数学推导思路。

原问题是从0...n-1中循环去掉第m个数，求剩下的最后一个数是多少，我们假设原求解问题是f(n,m)。

去掉第一个数k=(m-1)%n之后，还剩下k+1...n-1,0...k-1这n-1个数，问题变成了从这n-1个数中循环删去第m个数，求最后剩下的一个数，记这个问题为f'(n-1,m)。那么f(n,m)与f'(n-1,m)最终得到的结果是相同的，即①f(n,m)=f'(n-1,m)。

而如果把k+1...n-1,0...k-1与0..n-1作置换，那么②f'(n-1,m)=(f(n-1,m)+k+1)%n，①②式联合，得到f(n,m)=(f(n-1,m)+k+1)%n。于是递归关系就找到了，这样计算的时间复杂度是O(n)。

最后注意递归的出口，见代码。

public class Solution {

    public int LastRemaining_Solution(int n, int m) {

        if (n == 0) return -1;

        if (n == 1) return 0;

        return (LastRemaining_Solution(n - 1, m) + m) % n;

    }

}

63、数据流中的中位数+++

妙用堆，PriorityQueue

题目描述

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

题意分析

gzshan的分析很清晰。

方法五：最大堆和最小堆。我们注意到当数据保存到容器中时，可以分为两部分，左边一部分的数据要比右边一部分的数据小。如下图所示，P1是左边最大的数，P2是右边最小的数，即使左右两部分数据不是有序的，我们也有一个结论就是：左边最大的数小于右边最小的数。

因此，我们可以有如下的思路：向堆中插入一个数据的时间是O(logn)，而中位数就是堆顶的数据，只需要O(1)的时间就可得到。

而在具体实现上，首先要保证数据平均分配到两个堆中，两个堆中的数据数目之差不超过1，为了实现平均分配，可以在数据的总数目是偶数时，将数据插入最小堆，否则插入最大堆。

此外，还要保证所有最大堆中的数据要小于最小堆中的数据。所以，新传入的数据要和最大堆中最大值或者最小堆中的最小值比较。当总数目是偶数时，我们会插入最小堆，但是在这之前，我们需要判断这个数据和最大堆中的最大值哪个更大，如果最大值中的最大值比较大，那么将这个数据插入最大堆，并把最大堆中的最大值弹出插入最小堆。由于最终插入到最小堆的是原最大堆中最大的，所以保证了最小堆中所有的数据都大于最大堆中的数据。

import java.util.Comparator;

import java.util.PriorityQueue;

public class Solution {

    PriorityQueue minQ = new PriorityQueue();// default

    PriorityQueue maxQ = new PriorityQueue(new Comparator() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o2 - o1;

        }

    });

    int cnt = 0;

    public void Insert(Integer num) {

        cnt++;

        if ((cnt & 1) == 1) {

            int candidate = num + 1;

            if (!minQ.isEmpty()) candidate = minQ.peek();

            if (num = candidate) minQ.offer(num);

            else {

                minQ.offer(candidate);

                maxQ.poll();

                maxQ.offer(num);

            }

        }

    }

    public Double GetMedian() {

        if ((cnt & 1) == 1) return (double) maxQ.peek();

        else return (minQ.peek() + maxQ.peek()) / 2.0;

    }

}

64、滑动窗口的最大值+++

模拟，滑动窗口，双端队列

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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.Deque;

import java.util.LinkedList;

public class Solution {

    public ArrayList maxInWindows(int[] num, int size) {

        ArrayList ans = new ArrayList();

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

            return ans;

        Deque dq = new LinkedList();// 存的是下标

        for (int i = 0; i = size) dq.pollFirst();

            while (!dq.isEmpty() && num[dq.peekLast()] 

public class Solution {

    public int cutRope(int target) {

        int[] dp = new int[60 + 5];

        dp[0] = dp[1] = 0;

        dp[2] = 1;

        dp[3] = 2;

        dp[4] = 4;

        if (target