<p> 小伙伴们大家好，今天给大家带来几道算法题。</p> 讯享网
题意如图所示。先来讲比较简单的如何用队列实现栈。
准备两个队列，一个队列用于接受新元素，一个队列用于备用。比如我们定义两个队列a，b。a起初用来存储新元素，b用来备用。我们输入元素1，2，3，4。如果此时我们想得到栈顶，那么就把1，2，3依次放入b，a中此时剩余4，返回即可，并出队列。此时，b用来接受新的元素，当要返回栈顶时，只需将b队列元素除了最后一个均放到a，再出队列返回即可，此时a将用来接受新元素。重复操作。
讯享网
大家返回栈顶时要注意队列是否为空。
接下来讲如何使用栈实现队列。我们依然准备两个栈，一个栈用于接受新元素，一个栈用于备用。 当向栈中输入元素时，查看备用栈是否为空，为空则将输入栈的元素全部依次放入备用栈。这时栈顶就是队列首元素，可以直接返回。当输入元素后发现备用栈不为空，则不进行操作。当备用栈出元素后，变为空栈，则可以将入栈中的元素放入备用栈。
可以把数组值看成一个个格子，看有多少雨滴可以落在上面，这和它的左右有关。
首先，一个位置能不能接雨水可以是0也可以不是0。我们考虑第i个位置，那么rain【i】 的值可以由下式得到：rain【i】=max（0，min（max（arr【0~i-1】），max（arr【i+1~n-1】））-arr【i】）。i位置能接多少雨水取决于其左右最大值里的最小值，最后接完水肯定是一个长方形，高就是这个最小值，大家可以想一下。在此基础上减去i位置高度就是i位置可以接多少水。这个值可能为负数，因此我们需要和0作比较，取最大值。
求0~i-1位置最大值、求i+1~n-1位置最大值我们可以使用两个辅助数组。
讯享网
大家一定不要忘了减去i位置高度。
整个数组的最大值max肯定会取到，要不落在左边，要不落在右边。要求绝对值最大值肯定是要让另一部分最大值尽量小。
如果数组最大值落在左数组，那么绝对值的最大值就是max-arr【n-1】。大家肯定很疑惑，现在为大家解答。如果右数组仅有一个元素，那么肯定符合。如果右侧有多个元素，且n-1位置最大，那么也符合。如果右侧有多个元素，并且n-1位置并不是最大值，那么我们新得到的绝对值肯定比max-arr【n-1】小。所以当数组最大值落在数组左侧时，最大值为max-arr【n-1】。同样，当数组最大值落在数组右侧时，最大值为max-arr【0】。最后返回二者最大值即可。
这个题很简单。先把str加倍，比如str原来为12345，那么变成，我们可以发现只要是str的连接词那么都会出现在新的str中。这个问题就转化为字符串匹配问题了。我们就可以使用KMP算法了！！
不会KMP的小伙们看我之前的讲解：KMP算法-CSDN博客
讯享网
我们可以先统计出奇数的个数count1，是偶数但不是4的倍数数字的个数count2，4的倍数数字的个数count3。我们可以分情况讨论：
如果count2为0，那么只需要数字情况如下排列即可：奇4奇4奇4......，count1个奇数就需要count1-1个4的倍数。（奇数为0时都可以，奇数为1时仅需要1个）
现在我们讨论count2不为0的情况。我们分为有无奇数。
如果没有奇数，如果count2==1仅需要1个4的倍数，如果count2>1，那么有无4的倍数均可。
如果有奇数，那么无论多少个count2，都需要1个4的倍数配对。并且奇数安排如下：4奇4奇......
仅需要count1-1个4。因为第一个4是配对count2的，我们可以接着用。最终需要count1个4的倍数。
这里没有具体的题，只是想给大家分享一个思想：动态规划下的空间压缩。将二维数组压缩为一维数组。如果一个二维数组i，j位置和它的左侧元素和上方元素有关。那么第一行和第一列肯定是需要我们初始化的，我们肯定是知道的。那么填第二行时，第二行第二个元素（第一个元素已知）其可以根据左侧和上侧推导得来，我们可以将原先第一行第一个位置元素覆盖，第二行第三个元素左侧元素为现在第一行的第一个元素，其上方元素可以直接拿出，因此也可以推导出，并覆盖第一行第三个位置，同理第一行的其它元素。这样最终第一行就变成了二维数组的第二行元素。
如果是对角线型，跟其对角线有关，大家记得用临时变量存储要覆盖的位置元素。然后更新临时变量即可。
本次分享到此结束，大家多多支持！！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/187819.html