程序员代码面试指南：IT名企算法与数据结构题目最优解 - (EPUB全文下载)

文件大小：2.69 mb。
文件格式：epub 格式。
书籍内容：

程序员代码面试指南：IT名企算法与数据结构题目最优解
第1章 栈和队列
第2章 链表问题
第3章 二叉树问题
第4章 递归和动态规划
第5章 字符串问题
第6章 大数据和空间限制
第7章 位运算
第8章 数组和矩阵问题
第9章 其他题目
第1章 栈和队列
设计一个有getMin功能的栈
【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O（1）。
2.设计的栈类型可以使用现成的栈结构。
【难度】
士 ★☆☆☆
【解答】
在设计时，我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式有两种。
第一种设计方案
（1）压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：
● 如果为空，则newNum也压入stackMin。
● 如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
如果newNum更小或两者相等，则newNum也压入stackMin；
如果stackMin中栈顶元素小，则stackMin不压入任何内容。
举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-1所示。
图1-1
（2）弹出数据规则
先在 stackData 中弹出栈顶元素，记为 value。然后比较当前 stackMin 的栈顶元素和 value哪一个更小。
通过上文提到的压入规则可知，stackMin 中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。
当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value。
很明显可以看出，压入与弹出规则是对应的。
（3）查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值。所以，stackMin的栈顶元素始终是当前stackData中的最小值。
方案一的代码实现如MyStack1类所示：
第二种设计方案
（1）压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
如果为空，则newNum也压入stackMin；如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小。
如果newNum更小或两者相等，则newNum也压入stackMin；如果 stackMin 中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。
举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-2所示。
图1-2
（2）弹出数据规则
在stackData中弹出数据，弹出的数据记为value；弹出stackMin中的栈顶，返回value。
很明显可以看出，压入与弹出规则是对应的。
（3）查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以stackMin的栈顶元素始终是当前stackData中的最小值。
方案二的代码实现如MyStack2类所示：
【点评】
方案一和方案二其实都是用 stackMin 栈保存着 stackData 每一步的最小值。共同点是所有操作的时间复杂度都为O（1）、空间复杂度都为O（n）。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。
由两个栈组成的队列
【题目】
编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。
【难度】
尉 ★★☆☆
【解答】
栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。
具体实现时是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。
因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1～5依次压入stackPush，那么从stackPush的栈顶到栈底为5～1，此时依次再将5～1倒入stackPop，那么从stackPop的栈顶到栈底就变成了1～5。再从stackPop弹出时，顺序就像队列一样，如图1-3所示。
图1-3
听起来虽然简单，实际上必须做到以下两点。
1.如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。
2.如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。违反了以上两点都会发生错误。
违反1的情况举例：1～5依次压入stackPush，stackPush的栈顶到栈底为5～1，从stackPush压入stackPop时，只将5和4压入了stackPop，stackPush还剩下1、2、3没有压入。此时如果用户想进行弹出操作，那么4将最先弹出，与预想的队列顺序就不一致。
违反2的情况举例：1～5依次压入stackPush，stackPush将所有的数据压入stackPop，此时从stackPop的栈顶到栈底就变成了1～5。此时又有6～10依次压入stackPush，stackPop不为空，stackPus ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。