【第七章：高频算法】第27节：高频面试算法 - 基础（下）

大家好，很高兴我们可以继续交流学习算法相关的面试题。在上一小节中，我们主要对排序与查找算法，常见链表以及二叉树的面试题目进行了分析与交流。在本小节中，我们主要对队列，堆栈，字符串与数组等知识点进行交流。针对各个知识点最高频的面试题目来进行解析，希望遇到经典的基础算法题目时，大家可以把握机会，“手撕”成功。

（1）队列与堆栈：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列具有先进先出的特性，示意图如下所示：

堆栈是一种具有后进先出特性的数据结构，因为其只可以在栈顶进行数据的入栈和出栈操作。堆栈的数据结构示意图如下所示：

在上一小节介绍的二叉树的深度优先与宽度优先的遍历中，我们使用到了队列和堆栈来做为其辅助的数据结构，分别利用了其先进先出以及后进后出的特性。在算法题目的考察中，不光将队列和堆栈做为辅助数据结构考察，还会直接对其相关特性进行考察，典型的算法题目如下：

• 包含min函数的栈
• 用两个栈实现队列
• 用两个队列实现栈
• 自定义实现堆栈

限于文章篇幅，我们这里来介绍包含min函数的栈题目。

题目描述：

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

算法思路：

题目要求我们的各个方法均为O(1)复杂度，我们考虑增加辅助空间来实现，即增加一个专门用来存储min值的辅助栈。

实现步骤：

• 比如，data依次入栈：5, 4, 3, 8, 10, 11, 12, 1。则辅助栈依次入栈：5, 4, 3，no，no, no, no, 1。其中，no代表此次不入栈。也就是说每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则不入栈。
• 当出栈的时候，我们比较辅助栈与当前出栈的值是否相等。如果相等，则辅助栈栈顶元素也需要出栈。
• 当需要获取栈中最小元素的时候，我们直接获取到辅助栈的栈顶元素即可。

算法实现如下：

import java.util.Stack;   
public class Main {  

    Stack<Integer> stack = new Stack<>();  
    Stack<Integer> minStack = new Stack<>();  

/** 
 * 首先需要对stack执行入栈操作, 
 * 判断minStack中是否需要入栈操作 
 */  
    public void push(int node) {  
        stack.push(node);  
        if(minStack.isEmpty()||minStack.peek()>=node)  
            minStack.push(node);  
    }  

/** 
 * 判断minStack中是否需要出栈操作 
 */  
    public void pop() {   
        if(stack.peek()==minStack.peek()){  
            minStack.pop();  
        }  
        stack.pop();
    }  

    public int top() {  
        return stack.peek();  
    }  

/** 
 * 直接peek minStack 
 * @return 
 */  
    public int min() {  
        return minStack.peek();  
    }  
}

这里需要注意的是，在获取栈中的min值时，我们应该使用minStack.peek方法而不是minStack.pop方法。peek方法仅仅是获取数值，但是pop方法则会执行出栈操作。

（2）字符串相关算法：

字符串相关的算法题目绝对是面试考察的重点内容。字符串在我们的日常开发中无处不在，在面试中涉及到的相关题目一般均可以通过递归或者动态规划来解决。高频的算法题目包括：

• 最长不含重复元素的子串
• 最长公共子序列
• 最长公共子串
• 最长递增子序列
• 最长公共前缀
• 自定义函数实现字符串转整数的功能

在开始交流字符串面试题目之前，我们先来简单介绍下子串和子序列的区别吧。

• 子串：字符串中任意个连续的字符组成的子序列。
• 子序列：字符串中按照前后顺序取出的任意个字符组成，不要求连续。

算法题目：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设该字符串中只包含‘a’-'z'的字符。

例如，给出字符串abcabcbb，那么符合要求的字串为abc，其长度为3。

算法思路：

可以使用HashMap和双指针来实现该算法。HashMap中不断更新维护每个字符出现的位置。使用count变量进行计数，当统计的最长子字符串被重复字符破坏时，比较count和max的大小，判断是否需要更新max变量。不管是哪种情况，每次都需要更新map中的信息，并且需要更新count变量。

算法实现：

package pak3;

import java.util.HashMap;
import java.util.Map;

/**
 *  求最长不含重复字符的子字符串
 * @author ywq
 */
public class Main {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("arbacacfr"));
        System.out.println(lengthOfLongestSubstring("hkcpmprxxxqw"));
        System.out.println(lengthOfLongestSubstring("dvdf"));
        System.out.println(lengthOfLongestSubstring("tmmzuxt"));
        System.out.println(lengthOfLongestSubstring("jbpnbwwd"));

    }

    public static int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0)
            return 0;
        // 建立一个HashMap用来存放字符和位置信息
        Map<Character,Integer> map = new HashMap<Character, Integer>();
        int max = 0; // 用来记录最大值
        int count = 0