算法：一个长字符串中含多个连续和不连续的空格，求不含空格的最长字符串长度

我就是我 2023-10-04 13:49 21阅读 0赞

一个长字符串中含多个连续和不连续的空格，求不含空格的最长字符串长度。

如：uyuy 11 ikkhkhkhk kkj，结果：9

最暴力方案1（没分，只能用于验证其他方案结果正确性）：

public static int test1(String str) {
    		String[] arr = StringUtils.split(str);//默认以空格拆分
    		int len = 0 ;
    		
    		for (int i = 0; i < arr.length; i++) {
    			if(arr[i].length()>len) {
    				len = arr[i].length();
    			}
    		}
    		return len;
    	}

方案2：使用indexOf

public static int test2(String str) {
    		int i = 0;
            while (true) {
                int k = str.indexOf(" ");
                if (k < 0) {
                    break;
                }
                if (i < str.substring(0, k).length()) {
                    i = str.substring(0, k).length();
                }
                str = str.substring(k + 1);
            }
            return i;
    	}

方案3：使用char数组（我所知道的最优方案）

public static int test3(String str) {
    		char[] cs = str.toCharArray();
    		int startIndex = 0;
    		int count = 0;
    		for (int i = 0; i < cs.length; ) {
    			if(cs[i] != 32 ) {
    				i++;
    				continue;
    			}
    			count = Math.max(count, i-startIndex);
    			i++;
    			startIndex = i;
    		}
    		return count;
    	}

方案4：

public static int test4(String str) {
    		int count = 0;
    		int len = str.length();
    		int leftPoint = 0;
    		int rightPoint = 0;
    		while(leftPoint<len && rightPoint<len) {
    			if(leftPoint == rightPoint) {
    				rightPoint++;
    				continue;
    			}
    			String subStr = str.substring(leftPoint, rightPoint);
    			if(!subStr.contains(" ")) {
    				count = Math.max(count, rightPoint++-leftPoint);
    			}else {
    				leftPoint++;
    			}
    		}
    		return count;
    	}

各自运行1000次进行测试：

public static void main(String[] args) {
    		long startTime = System.currentTimeMillis(); //获取开始时间
    		String str = "a1 123# abc a bc defkdfkhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfdfdhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdffdfddefdefkdfkhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfdfdfdfddefdefkdfkhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfdfdfdfddefkdfkhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf dfdfdfdfdfdfdfddefkdfkhfkgfghkfghfkjgkffg ghi j k lmn op qfdfds fdfdf dsfsdfdsfdf";
    //		String str = "a 12 2";
    		System.out.println("字符总长度:"+str.length());
    		//String[] arr = str.split(" ");
    		int count1 = 0;
    		for (int i = 0; i < 1000; i++) {
    			count1 = test1(str);
    		}
    		System.out.println("1最大长度："+count1);
    		long endTime = System.currentTimeMillis(); //获取结束时间
            System.out.println("1程序运行时间：" + (endTime - startTime) + "ms");
            
            ///
            long startTime2 = System.currentTimeMillis(); //获取开始时间
            int count2 = 0;
    		for (int i = 0; i < 1000; i++) {
    			count2 = test2(str);
    		}
            System.out.println("2最大长度："+count2);
            long endTime2 = System.currentTimeMillis(); //获取结束时间
            System.out.println("2程序运行时间：" + (endTime2 - startTime2) + "ms");
            
            /
            long startTime3 = System.currentTimeMillis(); //获取开始时间
            int count3 = 0;
    		for (int i = 0; i < 1000; i++) {
    			count3 = test3(str);
    		}
            System.out.println("3最大长度："+count3);
            long endTime3 = System.currentTimeMillis(); //获取结束时间
            System.out.println("3程序运行时间：" + (endTime3 - startTime3) + "ms");
            
            /
            long startTime4 = System.currentTimeMillis(); //获取开始时间
            int count4 = 0;
    		for (int i = 0; i < 1000; i++) {
    			count4 = test4(str);
    		}
            System.out.println("4最大长度："+count4);
            long endTime4 = System.currentTimeMillis(); //获取结束时间
            System.out.println("4程序运行时间：" + (endTime4 - startTime4) + "ms");
    	}

输出结果：

字符总长度:621
    1最大长度：44
    1程序运行时间：563ms
    2最大长度：44
    2程序运行时间：49ms
    3最大长度：44
    3程序运行时间：27ms
    4最大长度：44
    4程序运行时间：182ms

可见方案3还是不错的，不过除了方案1其他的都有bug，就是如果最后一个长字符串是最大长度，那么他们就出错了，解决办法就是在每个方法第一行增加：

str+=" ";