字符串常见的笔试面试题（无代码）-创新互联

字符串是我们每个程序员每天都要接触的数据类型，因此在面试的时候也有许多关于字符串的面试题，本文主要介绍面试常见的几种题型。

题型一 

     本题主要判断两棵树的拓扑结构是否相同，因此我们可以将此题转化成字符串的写法：将树序列化，然后用KMP算法判断t1树的序列化串是否含有t2树的序列化串即可，如果含有则说明t2是t1的子树，则满足拓扑结构。

题型二

本题大部分读者都很容易想到用两个哈希表来存储str1和str2的对应字符的出现次数，然后比较二者的哈希表，如果里面数据相同，则两个字符串互为变形词。

题型三

由分析可知，一个长度为n的字符串旋转词的所有可能性为下标0~下标n-1之前的字符串移到最后方，因此我们可以直接拼接一个字符串S=str1+str1，可见，上述所有可能性都会包含在S里面作为S的子串，因此只需要判断str2是否为S的子串即可。如果str2为S的子串，那么str1和str2互为旋转词。

题型四

本题我们可以利用字符串的反转+局部反转来解决问题。对于这样一个单词间逆序的问题，我们可以先将字符串整体反转，例如：“pig loves dog”--->“god sevol gip” 然后发现，离我们的目标“dog loves pig” 仅仅是每个单词之间的顺序还是逆序，所以我们再进行一个局部反转，对每个单词进行反转即可将“god sevol gip”--->“dog loves pig”。

题型五

本题我们还是可以利用字符串的反转+局部反转来解决问题。例如：“ABCDE”，i=2，将str调整为：“DEABC”，我们可以先将“ABCDE”  (0，i]的位置和  (i,n)的位置分别局部反转，变为：“CBAED”然后发现离我们的目标仅仅差一个整体反转，然后再进行一个整体反转即可。

（可见，许多关于字符串移动或者逆序的问题我们均可利用字符串的反转和局部反转来灵活解决问题，这里需要读者自行体会）

题型六

本题我们大部分读者会直接比较每个字符串的ASCII码值来进行排序，比如["ab","cd","ac"]排序后变为["ab","ac","cd"]，虽然这种解法对于大部分情况都满足，但是还是对于一些情况是不满足的，例如题目中的["b","ba"]排完序后变为["b","ba"]，但是我们可以知道，bab明显比bba小，因此此时不成立。本题正确的解法是将str1+str2与str2+str1作比较，如果str1+str2>str2+str1，则str2排在str1前面，反之排在后面，这样排完序再拼接起来的字符串才是所有可能性中字典顺序最小的。

题型七

本题大部分语言均可直接调用字符串的库（例如JAVA中调用replace，将空格直接都替换成%20）来完成。那么如果在纯代码情况下，我们可以构造一个新的字符数组S（长度n=str+空格数量*2），然后从左往右遍历字符串str，如果遇到非空格字符则直接填入S，遇到空格则填入%20。

题型八

本题我们可以定义一个变量n来帮我们记录此时左括号与右括号的差值，从左往右遍历字符串，遇到左括号n++，遇到右括号n--，如果过程中发现n<0则不是有效的字符串，如果最后n！=0，也不是有效的字符串，当且仅当过程中n>=0并且最后n=0才是一个有效的字符串。

题型九

本题是经典的求最长无重复字符子串的长度，我们可以利用哈希表来解决。定义一个当前子串长度变量now，从左往右遍历字符串，并且将遍历到的字符加入哈希表，如果发现哈希表中不包含本字符则当前子串长度now++，如果包含则需要回滚到上一个出现本字符的位置，然后now的长度变为当前位置减去上一个出现本字符的位置（这边读者需要自己思考一下为什么），但是，如果上一个出现字符的位置在我们子串起始位置之前，我们不需要回滚。

具体代码如下：

public class LengthOfLongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        if(s.isEmpty())return 0;
        int i=-1;
        int max=1;
        int now=1;
        Mapmap=new HashMap<>();
        //遍历数组
        for (int k = 0; k< s.length(); k++) {
            if(map.getOrDefault(s.charAt(k),-1)!=-1){  //判断哈希表中是否有本元素
                //有的话就将i值挪到上一个重复的地方  但是要注意，不可回退 因此要判断大小
                i=map.getOrDefault(s.charAt(k),-1)>i?map.getOrDefault(s.charAt(k),-1):i;
            }
            now=k-i;//用当前值减去上一个重复的
            map.put(s.charAt(k),k);
            max= Math.max(now, max); //取二者大值
        }
        return max;
    }
}

以上是常见的JAVA笔试面试题（图片来源于牛客网）。字符串在笔试面试中是必考的题目，希望读者们能深入理解每种解题的思想。一起加油进步！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧