字符串类型面试题目总结

Dear 丶 2021-09-10 03:16 374阅读 0赞

## 字符串系列题目一览： ##

1.t1是否有与t2树拓扑结构相同的子树  
2.判断两个字符串是否互为变形词？  
3.判断两个字符串是否为旋转词？  
4.字符串str，请在单词间做逆序调整。  
5.给字符串str和一个整数i,i代表str中的位置，将str\[0...i\]移到右侧，str\[i+1...N-1\]移到左侧  
6.将字符串数组strs拼接一个字符串，字典顺序最小  
7.将str中空格字符替换成"%20",假设有足够空间  
8.判断字符串是不是有效的括号字符串 str="(()" 返回false  
9.判断字符串最长无重复子串的长度 str="abcd" 返回3

#### 1.t1是否有与t2树拓扑结构相同的子树 ####

#### 2.判断两个字符串是否互为变形词？ ####

两个字符串出现的字符种类和每个字符种类出现的次数一样，成为互为变形词。  
可以声明256的数组，但是在Java中一个char字符类型占用两个字节，16位65535，所以可以声明65536大小的数组。  
也可以使用哈希表解决这个问题。key为字符，value存储出现的次数。str1增加，str2减少。遍历结束正确的结果刚好为0，说明字符种类与出现次数相同。

public static boolean distortion_test(String s1,String s2){
             if(s1==null||s2==null||s1.length()!=s2.length()){  
                    return false;  
                }
            char[] c1=s1.toCharArray();
            char[] c2=s2.toCharArray();
            int[] k=new int[256];
            for(int i=0;i<c1.length;i++){
                k[c1[i]]++;
            }
            for(int i=0;i<c2.length;i++){
                if(k[c2[i]]==0)
                    return false;
                k[c2[i]]--;
            }
            return true;
        }
        
        public static boolean distortion_test2(String s1,String s2){
             if(s1==null||s2==null||s1.length()!=s2.length()){  
                    return false;  
                }  
            char[] c1=s1.toCharArray();
            char[] c2=s2.toCharArray();
            Map<Character, Integer> map=new HashMap<Character,Integer>();
            for(int i=0;i<c1.length;i++){
                if(map.get(c1[i])==null)
                    map.put(c1[i], 1);
                else        
                    map.put(c1[i],map.get(c1[i])+1);
            }
            for(int i=0;i<c2.length;i++){
                if(map.get(c2[i])==null||map.get(c2[i])==0)
                    return false;
                else
                    map.put(c2[i], map.get(c2[i])-1);
            }
            return true;
        }

#### 3.判断两个字符串是否为旋转词？ ####

把str前面任意部分挪到后面形成的字符串叫做str旋转词  
a="abcd" b="cdab" 返回true

#### 4.字符串str，请在单词间做逆序调整。 ####

"pig loves dog"逆序成"dog loves pig"  
构造一个字符串全体逆序方法。  
先对将整体逆序 --->"god sevol gip"，再循环到空格处，对单词进行逆序--->"dog loves pig"，得到结果。

public static void inverse(char[] ch,int begin,int end){
            while(begin<end){
                char temp=ch[begin];
                ch[begin]=ch[end];
                ch[end]=temp;
                begin++;
                end--;
            }
        }
        
        public static String swapWord(String s){
            char[] a=s.toCharArray();
            inverse(a,0,a.length-1);
            int blank=-1;
            for(int i=0;i<a.length;i++){
                if(a[i]==' '){
                    int nextBlank=i;
                    inverse(a,blank+1,nextBlank-1);
                    blank=nextBlank;
                }
            }
            inverse(a,blank+1,a.length-1);
            return (new String(a));
        }

#### 5.给字符串str和一个整数i,i代表str中的位置，将str\[0...i\]移到右侧，str\[i+1...N-1\]移到左侧 ####

str="abcde",i=2 调整后 str="deabc"  
同上题，先构造逆序方法。对str逆序--->"edcba"，然后再根据i的位置对两侧分别逆序，--->"deabc"

public static void inverse(char[] ch,int begin,int end){
            while(begin<end){
                char temp=ch[begin];
                ch[begin]=ch[end];
                ch[end]=temp;
                begin++;
                end--;
            }
        }
        
        public static String shift(String s,int i){
            char[] ch=s.toCharArray();
            inverse(ch,0,ch.length-1);
            inverse(ch,0,ch.length-i-2);
            inverse(ch,ch.length-i-1,ch.length-1);
            return new String(ch);
        }
        
        public static void main(String args[]){
            String s="abcde";
            System.out.println(shift(s,3));
        }

#### 6.将字符串数组strs拼接一个字符串，字典顺序最小 ####

strs=\["abc","de"\] 拼成"abcde"  
strs=\["b","ba"\]拼成"bab"  
比较的内容为o1+o2>o2+o1，是两个字符串连接后的大小，而不是单独字符串的比较。

public static String findSmallest(String[] strs, int n) {
                // write code here
                Arrays.sort(strs, new Comparator<String>() {
         
                    @Override
                    public int compare(String o1, String o2) {
                        //此方法如果这个字符串是等参数字符串那么返回值0，==  
                        //如果这个字符串是按字典顺序小于字符串参数那么返回小于0的值，<  
                        //如果此字符串是按字典顺序大于字符串参数那么一个大于0的值 >  
                        String s1=o1+o2;
                        String s2=o2+o1;
                        return s1.compareTo(s2);
                    }
                });
                 
                StringBuilder sb=new StringBuilder();
                for(int i=0;i<n;i++){
                    sb.append(strs[i]);              
                }
                return sb.toString();     
          }
        
          public static void main(String args[]){
              String s[]=new String[]{"ba","b"};
              System.out.println(findSmallest(s, s.length));
          }

#### 7.将str中空格字符替换成"%20",假设有足够空间 ####

s=s.replace(" ", "%20");

#### 8.判断字符串是不是有效的括号字符串 str="(()" 返回false ####

设置num，代表‘（’与‘）’出现此时差值，（就++，）就--，最后应该=0

#### 9.判断字符串最长无重复子串的长度 str="abcd" 返回3 ####

求出每个字符结尾的情况下，最长无重复字符子串的长度，并找出最大值返回  
哈希表map --> 统计了每种字符之前出现的位置  
整型数组preArr-->代表以s\[i\]结尾的情况下，最长无重复子串的长度

![5057999-461e91f32c60201b.png][]

![5057999-238ea25e0516a162.png][]

当循环中，遇见字符重复出现，求该字符的最大不重复子串时。需要比较：上一次该字符出现位置+1与 该字符左边字符的最长无重复子串。如上图位置A与位置B。选择A与B中靠右的点，该点到c的距离便是c的最长无重复子串。（A与B之间必然会重复，所以选择靠右的点）

public static int longestSubstring(String A, int n) {
            //charPosition统计A中每种字符之前出现的位置
            Map<Character, Integer> charPosition = new HashMap<Character, Integer>();
            //preArr代表以s[i-1]结尾的情况下，最长无重复子串的长度
            int[] preArr = new int[A.length()];
            char[] str2charArr = A.toCharArray();
            //从头到尾遍历str2charArr，统计出以每个字符为当前位置的向前最长无重复子串的长度
            for(int i=0; i<A.length(); i++){
                Integer lastPosOfChar = charPosition.get(str2charArr[i]);
                if(lastPosOfChar == null){//说明当前字符第一次出现
                    //更新最长无重复子串的长度
                    preArr[i] = i == 0 ? 1 : preArr[i-1] + 1;
                    //记录当前字符出现的位置
                    charPosition.put(str2charArr[i], i);
                }
                else{//当前字符不是第一次出现(既然不是第一次出现，那也不是在第一个位置),也就是之前出现过该字符
                    //获取前一个字符最长无重复子串的长度
                    int aPos = lastPosOfChar + 1; //上一次出现该字符的位置+1
                    int unRepeatLen = preArr[i-1];//以该字符左侧一位字符为标准的最长无重复子串的长度
                    int bPos = i - unRepeatLen;
                    if(aPos >= bPos){
                        //当前位置的最长无重复子串长度
                        preArr[i] = i - aPos + 1;
                    }
                    else{
                        //当前位置的最长无重复子串长度
                        preArr[i] = unRepeatLen + 1;
                    }
                    //更新当前字符出现的位置
                    charPosition.put(str2charArr[i], i);
                }
            }
            //遍历preArr,最大值即为所求
            int max = preArr[0];
            for(int i: preArr) if(i > max) max = i;
            return max;
        }

[5057999-461e91f32c60201b.png]: /images/20210811/81beb67ce0a3499fa4380b0dfc969783.png
[5057999-238ea25e0516a162.png]: /images/20210811/f2e7ddc5cd234916816f7a8c0355df3b.png