牛客算法--第五章

牛客算法–第五章

题目一：猫狗队列
【题目】
宠物、狗和猫的类如下：

public class Pet {
   
private String type;
public Pet(String type) {
this.type = type;
}
public String getPetType() {
return this.type;
}
}
public class Dog extends Pet {
   
public Dog() {
super("dog");
}
}

public class Cat extends Pet {
   
public Cat() {
super("cat");
}
}

实现一种狗猫队列的结构，要求如下：
用户可以调用 add 方法将 cat 类或 dog 类的实例放入队列中；
用户可以调用 pollAll 方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
用户可以调用 pollDog 方法，将队列中 dog 类的实例按照进队列的先后顺序依次弹出；
用户可以调用 pollCat 方法，将队列中 cat 类的实例按照进队列的先后顺序依次弹出；
用户可以调用 isEmpty 方法，检查队列中是否还有 dog 或 cat 的实例；
用户可以调用 isDogEmpty 方法，检查队列中是否有 dog 类的实例；
用户可以调用 isCatEmpty 方法，检查队列中是否有 cat 类的实例。
【要求】
要求所有实现的方法，时间复杂度都为 O(1)

总结，是一个数据结构设计题，本题关键是如何分装实现时间戳，并且要注意解决能够多次重复进入同一对象的问题。基础解法map就是因为无法解决，所以不满足。视频中间出现过“装饰者模式”的字眼。

解法是再定义一个封装类，在cat和dog进入queue之前统一进行封装，加工成一个封装类对象，然后，在这个实例对象上实现时间戳。

题目二：用栈来求解汉诺塔问题
【题目】

汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有 N 层的时候，打印最优移动过程和最优移动总步数。
例如，当塔数为两层时，最上层的塔记为 1，最下层的塔记为 2，则打印：
Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.
注意：关于汉诺塔游戏的更多讨论，将在本书递归与动态规划的章节中继续。
【要求】
用以下两种方法解决。
方法一：递归的方法；
方法二：非递归的方法，用栈来模拟汉诺塔的三个塔

假设有1~N，总共N个盘子，那么移动最后一个的流程如下：

1.1~N-1  : L->R;
2.N      : L->M;
3.1~N-1  : R->L;
4.N      : M->R;
5.1~N-1  : L->R.

假设存在这么一个函数 : F(range,from,to)。
表示把从第1层到i层的range范围的盘子从from移动到to位置。

还有一个3步的过程：

    1.1~N-1    : L->R;
    2.N            : L->M;
    3.1~N-1    : R->M.

那么什么时候，是3步步骤，又是什么时候5步步骤呢？关键点其实就是from和to中是否有一个是middle，如果有，那么就是3步步骤。
另外还有一个很好理解的关键点，就是在3步步骤中会有一个another变量用来求解from和to之外的另一个盘子。

好的，那么如果不允许使用递归，要求用栈呢？

栈的操作动作可以有下面4种：

L->M
M->R
R->M
M->L

同时还有两个关键点要求：

1.小压大；
2.相邻动作不可逆。

那么为什么第2点成立呢？因为我们的操作的过程是要求最优的操作，假如我们L->M,又马上M->L，那么这个操作就是没有实际功能意义的，所以我们基于最优的操作，就是尽可能减少无用的操作。所以第2点也成立。

举个例子，假设上一步是 L->M,
那么，这一步不可能 L->M ，因为违反第一点，小压大。
这一步不可能 M->L，因为违反第二点，逆操作。
接下来只剩下两个互斥的选项
就是 R->M 和M->R
两个选项，而且也是凭借第一点小压大原则
可以从中挑选中满足条件的一个。

题目三：构造数组的 MaxTree
【题目】
定义二叉树节点如下：


public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}

一个数组的 MaxTree 定义如下。
数组必须没有重复元素。
MaxTree 是一棵二叉树，数组的每一个值对应一个二叉树节点。
包括 MaxTree 树在内且在其中的每一棵子树上，值最大的节点都是树的头。
给定一个没有重复元素的数组 arr，写出生成这个数组的 MaxTree 的函数，要求如果数组
长度为 N，则时间复杂度为 O(N)、额外空间复杂度为 O(N)。

总结，两种方法，第一种是可以用大根堆建树的方法来解决；第二种是可以用第4章的滑动窗口中用到的双端队列的数据结构有些关联来解题。

但是，也不太一样，因为只是要求max，所以这道题左神提供的算法原型是下面的：

提供了一个原始数组
其中规定数组两个边界都是INF，一个无穷大值。
从数组0号位开始遍历，分别查找其左边第一个比他大的数lmax和右边第一个比他大的数rmax，然后求min(lmax,rmax),把这个数的前驱设为min结点。这个数的结点变为min结点的子树。最后构造出的树结构的根结点的数值就是最大值。

首先，需要证明上面的算法原型。
1.以上的决策只会生成一棵树，不会生成多棵树。
为什么呢？
因为数组中提供的数据都是不相同的，不重复的，所以也就是根结点一定唯一，所以，树也唯一。

2.同时，以上的方法其实生成的是一颗二叉树。
怎么证明？
也就是证明一个结点最多只会有两个子结点。
也就是可以证明一个结点的单独一侧最多只会有一个子结点。
如何证明？

这里实际可以用反证法证明。

假设有一个数a，证明它的右边最多只有一个子结点。假设它的右边存在两个子结点b,c。
因为b,c都是a的子结点，所以a>b ,a>c.
那么b和c呢？
首先b肯定不等于c.
假设b>c的话，因为又存在a>b，所以根据原意，c应该是b的子结点而不是a的子结点，所以不成立；
如果b<c的话，因为又存在a>c，所以根据原意，b应该是c的子结点而不是a的子结点，所以不成立。

那么这道题如何设计编程呢？

用到的数据结构是栈。

1 2 3 4 5
比如数据像上面这样，
如果stack.empty()或者栈顶元素top>data，那么就是说，将data直接入栈，stack.push。
反之，如果遇到data>top的情况，那么就将当前的栈顶top弹出，并且同时可以获得，它的左边距离它最近的比他大的数就是他弹出之后的stack.top栈顶元素，而他的右边距离它最近的比他大的数，就是那个引起它弹出栈顶的data元素。

题目四：
最大值减去最小值小于或等于 num 的子数组数量
【题目】
给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组 arr[i..j]中的最大值，min(arr[i..j])表示子数组 arr[i..j]中的最
小值。
【要求】
如果数组长度为 N，请实现时间复杂度为 O(N)的解法。

总结，这道题再次复习上一章出现的双端队列的结构。

这里需要总结一下用法。

一开始的左右边界L和R都在左边。

假设数据

3 5 6 4

如果想要窗口内的最小值，就把双端队列设计成递增的；如果时时刻刻想要窗口内的最大值，就把双端队列设计成递减的。

以本道题为例，

双端队列的变化如下

 3   5   6   4
L,R 
此时的双端队列里面的内容是{}，是空的。
 3   5   6   4
L  R
此时双端队列里面的内容是{3}
 3   5   6   4
L      R
此时双端队列里面的内容是{3,5}
 3   5   6   4
L          R
此时双端队列里面的内容是{3,5,6}

下面的一步要注意了，因为R右边界要包含4了，但是这里4比双端队列尾部的6小，所以将6弹出：

 3   5   6   4
L              R
此时双端队列里面的内容是{3,5}

又因为5同样比4小，所以把5继续弹出，这道碰到3,3未过期，并且他比4小，所以把4压入双端队列的尾部。此时的情况如图：

 3   5   6   4
L              R
此时双端队列里面的内容是{3,4}

这里需要特别注意的一点，这里是为了演示，所以双端队列里面存放的是数据，实际编程的时候，双端队列里面存放的应该是数据的下标。

然后双端队列的L向右移动，检测L指向的值是否和双端队列头部的数据相等，如果相等的话，也就是说明已经过期了，此时把双端队列头部的元素弹出，也就是把3弹出，所以此时的双端队列的情况又变成下面的情况：
 3   5   6   4
   L          R
此时双端队列里面的内容是{4}

然后L继续向右滑动。。。过程基本上就是这样，在这个过程中，可以得到双端队列中的队头元素就是L~R范围之内数据的最小值是多少，当然编程中，我们得到的是最小值的下标。

回归本题的话，因为要求的是最大值-最小值。所以实际上我们需要两个双端队列。

接下来还有一个关键点。

同样有一个非常直观的现象需要我们的肯定。假设L不动，R在向右移动，那么因为R的移动总是在原来的内容基础上增加元素，所以我们实际上的得到的MAX最大值只会不变或者变得更大；
同理，实际上得到的MIN最小值只会不变或者变得更小。

上面说白了，到底揭秘了什么黑暗森林法则呢？
这里总结，就是L固定的情况下，R向右移动的过程中，只会出现最大值变得相等或更大，最小值变得相等或更小的情况。
也就是说，最大值-最小值只会变得相等或者更加大的情况，本题是<=num的情况，如果出现>num的情况，那么就没有必要继续R向右移了，因为之后的一定已经不满足了；
此时就是该L向右移动的时候了，那么R如何处理呢？其实有两种方法：第一种同时重置R，也就是R=L，但是这种方法时间负责度就不是O（N）了；第二种方法就是R还在原来的位置不动。因为是在原来的基础上减少内部的一个数，所以L~R范围内的MAX只可能相等或者更小，MIN只可能相等或更大，

一句话，就是一定符合题目的要求，直接计算子数组个数即可。

因为上面的题目中L只会从0~N遍历一遍，R也只会从0~N遍历一遍，所以时间负责度是2*N，所以还是O（N）。

继续之前的步骤。

题目五：
环形单链表的约瑟夫问题
【题目】
据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人
与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是
决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自
杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一
个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链
表描述该结构并呈现整个自杀过程。
输入：一个环形单向链表的头节点 head 和报数的值 m。
返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。
【要求】
如果链表节点数为 N，请实现时间复杂度为 O(N)的解法。

从模拟法实现程序来看，这个算法的时间复杂度是O(M*N)，其中N为人数。每回报M这个数的人退出队列。这意味着如果M和N都很大时，用此算法计算约瑟夫环问题的效率是十分低下的。恰当地运用一些数论只是可以有效地提高该问题的求解效率。

核心算法，约瑟夫环形链表公式：


class Solution {  
public:  
    int LastRemaining_Solution(int n, int m)  
    {  
        if(n < 1 || m<1){  
            return -1;  
        }  
        int last = 0;  
        for(int i = 2; i<=n;i++){  
            last = (last + m)%i;  
        }  
        return last;  
    }  
};

其中，last就是最后留在队列中的人。

模拟法：如果链表中只有一个结点的时候，这个唯一的结点就是答案。