字符串专题（一）

冷不防 2021-12-08 20:17 229阅读 0赞

一直不太会字符串的处理，这周一定要攻克它。

str.toCharArray() : 将字符串转换为字符数组

**【1】判断两个字符串是否互为变形词**  
题目：两个字符串str1和str2，如果两个字符串出现的字符种类和每种字符出现的次数都一样，则互为变形词  
例如：  
str1 =“123”,str2 = “321” 返回true  
str1 = “123” str2 =“3221” 返回false  
**思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**代码实现**

package 字符串问题;
    
    public class 互为变形词 {
        public static void main(String[] args) {
            String str1 = "123";
            String str2 = "321";
            String str3 = "3221";
            System.out.println(isDeformation(str1,str2));
            System.out.println(isDeformation(str1,str3));
        }
        public static boolean isDeformation(String str1,String str2){
            if(str1 == null || str2 == null || str1.length() != str2.length()) return false;
            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();//将字符串转换成数组
            int[] map = new int[256];//建立map数组
            for (int i = 0;i<chars1.length;i++){
                map[chars1[i]]++;
            }
            for (int j =0;j<chars2.length;j++){
                if(map[chars2[j]]-- == 0){
                    return false;
                }
            }
            return true;
        }
    
    }

**结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
**【2】判断两个字符串是否互为旋转词**  
旋转词：把str前面任意部分挪到后面形成的字符串。  
例如str = “12345”的旋转词有“12345”“23451””34512“”45123“”51234“。  
给定ab判断：  
例如：  
a=“cdab” b = “abcd” 返回true  
a= “1ab2” b = “ab12” 返回false  
a = “2ab1” b =ab12" 返回true  
**思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]  
**代码实现**

package 字符串问题;
    
    public class 互为旋转词 {
        public static void main(String[] args) {
            String a = "cdab";
            String b = "abcd";
            System.out.println(isRotation(a,b));
            String c = "1ab2";
            String d = "ab12";
            System.out.println(isRotation(c,d));
        }
        public static boolean isRotation(String str1,String str2){
            if(str1 == null || str2 == null || str1.length() != str2.length()) return false;
            String str22 = str2+str2;
            return getIndexOf(str22,str1) != -1;//KMP算法
        }
        public static int getIndexOf(String s,String m){
            if(s == null || m == null || m.length()<1 || s.length() < m.length()){
                return -1;
            }
            char[] ss = s.toCharArray();
            char[] ms = m.toCharArray();
            int si = 0;
            int mi = 0;
            int[] next = getNextArray(ms);
            while (si < ss.length && mi < ms.length){
                if(ss[si] == ms[mi]){
                    si++;
                    mi++;
                }else if(next[mi] == -1){
                    si++;
                }else {
                    mi = next[mi];
                }
            }
            System.out.println(mi);
            return mi == ms.length ? si - mi : -1;
    
        }
        public static int[] getNextArray(char[] ms){
            if(ms.length == 1) return new int[] {-1};
            int[] next = new int[ms.length];
            next[0] = -1;
            next[1] = 0;
            int pos = 2;
            int cn = 0;
            while (pos < next.length){
                if(ms[pos - 1] == ms[cn]){
                    next[pos++] = ++cn;
                }else if(cn > 0){
                    cn = next[cn];
                }else {
                    next[pos++] = 0;
                }
            }
            return next;
        }
    }

**结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]  
**[KMP算法][KMP]**

**【3】将整数字符串转成整数值**  
旋转词：把str前面任意部分挪到后面形成的字符串。  
例如str = “12345”的旋转词有“12345”“23451””34512“”45123“”51234“。  
给定ab判断：  
例如：  
a=“cdab” b = “abcd” 返回true  
a= “1ab2” b = “ab12” 返回false  
a = “2ab1” b =ab12" 返回true  
**思路**  
给定一个字符串str，如果sr符合日常书写的整数形式，并且属于32位整数的范围，返回str所代表的整数值，否则返回0  
eg  
str = “123”,返回123  
str = “A13”返回0  
str = “2147483648”因为溢出所以返回0  
**首先检查str是否符合日常书写的整数形式**，具体判断：  
如果不以-开头，也不以数字字符开头，如str == “A12”返回false  
以-开头但str长度为1，即str = “-”返回false，如果为str ==”-0”或”-023”返回false  
以0开头，但是str的长度大于1，str == “023”返回false  
经过以上步骤，之后检查str\[1…N-1\]是否都是数字字符，如果有一个不是，则返回false。如果都是，返回true  
**判断过程代码实现**

public static Boolean isValid(char[] chas){
            if(chas[0] != '-' &&(chas[0]<'0' ||chas[0] > '9'))return false;
            if(chas[0] == '-' &&(chas.length == 1 ||chas[1] =='0')) return false;
            if (chas[0] == '0' && chas.length > 1) return  false;
            for(int i = 1;i<chas.length;i++){
                if(chas[i]<'0' ||chas[i]>'9') return false;
            }
            return true;
        }

**如果符合日常书写，则进行转换过程**  
1.生成四个变量  
布尔变量posi ：表示结果为正数（true）还是负数（false）  
整型常量minq：32位整数最小值除以10得到的商  
整型常量minr：32位整数最小值除以10得到的余数  
整形变量res：转换的结果，初始为0  
2.**判断正负**  
32位最小值为-2147483648 最大值为2147483647.（最小值的绝对值比最大值大1）  
转换过程中的绝对值一律以负数的形式出现，然后根据posi决定最后返回什么  
eg：  
str = “-123” 转换完成结果为-123，posi = false所以最后返回-123  
str = “123” 转换完成结果为-123，posi = true 所以最后返回123  
3\*\*.遍历\*\*  
如果str以’-‘开头，那么从str【1】开始遍历否则从str【0】开始  
eg：  
str = ”123“  
遍历到’1‘时，res = res*10+（-1） == -1  
遍历到’2‘时，res = res*10+（-2） == -12  
遍历到’2‘时，res = res\*10+（-3） == -123  
在遍历过程中如何判断res已经溢出？  
假设当前字符为a，’0‘-a就是当前字符所表示的负数形式，为cur  
如果在res加上cur之前，发现res已经小于minq，那么res加上cur之后一定会溢出，任何一种溢出情况，直接返回0  
4.遍历后得到的res根据posi符号决定返回值。

**代码实现**

package 字符串问题;
    
    public class 字符串转为整数值 {
        public static void main(String[] args) {
            String str1 = "123";
            String str2 = "-123";
            System.out.println(convert(str1));
            System.out.println(convert(str2));
        }
        public static Boolean isValid(char[] chas){
            if(chas[0] != '-' &&(chas[0]<'0' ||chas[0] > '9'))return false;
            if(chas[0] == '-' &&(chas.length == 1 ||chas[1] =='0')) return false;
            if (chas[0] == '0' && chas.length > 1) return  false;
            for(int i = 1;i<chas.length;i++){
                if(chas[i]<'0' ||chas[i]>'9') return false;
            }
            return true;
        }
        public static int convert(String str){
            if(str == null ||str.equals("")) return 0;//不能转
            char[] chas = str.toCharArray();
            if(!isValid(chas))return 0;
            boolean posi = chas[0] == '-' ? false : true;
            int minq = Integer.MIN_VALUE /10;
            int minr = Integer.MIN_VALUE %10;
            int res = 0;
            int cur = 0;
            for (int i = posi ?0:1;i<chas.length;i++){
                cur = '0'-chas[i];
                if((res <minq) || (res == minq && cur<minr)) return 0;
                res = res*10 +cur;
            }
            if(posi && res == Integer.MIN_VALUE) return 0;
            return posi ? -res :res;
        }
    
    }

**结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]  
参考：  
《程序员代码面试指南：IT名企算法与数据结构题目最优解》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20211209/d7c6155839534d0ebe0aab5458d5f610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20211209/740d3d27ab58453d9279b0cbf376a144.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20211209/5b993012a4ae4960a6073cf7eefaa250.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]: /images/20211209/45389811f9db4ac2b5196b18fa6800bd.png
[KMP]: https://blog.csdn.net/weixin_39795049/article/details/96102418
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 4]: /images/20211209/16a64798961b4c3a81ee48e958d98527.png