JAVA面试题笔试题-查找一个字符串不重复最长的串（个人方法）

• 面试题或者笔试题常问的算法

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import org.apache.commons.lang.StringUtils;

/*
 * 【Author】 爱吃早餐的程序员
 * 【Time】2020年11月23日 下午2:28:17
 * 【Function】查找一个字符串不重复最长的串
 */
public class Test5 {
   
	public static void main(String[] args) {
   
		String string = "suhdfuisehwerqiowo";
		String findNotDupLong = findNotDupLong(string);
		System.err.println("不重复最长的串："+findNotDupLong);
	}

	private static String findNotDupLong(String string) {
   
		
		if (StringUtils.isBlank(string)) {
   
			return "没有找到";
		}
		
		ArrayList<String> arrayList = new ArrayList<String>();// 用于存入符合条件的串
		String[] split = string.split("");
		for (int i = 0; i < split.length; i++) {
   
			String begin = split[i];
			for (int j = i; j < split.length; j++) {
   
				if (begin.equals(split[j])) {
   
					if (StringUtils.isNotBlank(string.substring(i, j))) {
   
						arrayList.add(string.substring(i, j));
					}
				}
			}
		}
		Collections.sort(arrayList, new Comparator<String>() {
   
			@Override
			public int compare(String o1, String o2) {
   
				if (o1.length()>o2.length()) {
   
					return -1;
				}else {
   
					return 1;
				}
			}
		});
		
		return arrayList.size()>0?arrayList.get(0):"没有找到";
			
	}
}

• 大家有什么好的方法没
• 后来测试有错 已更新方法

private static String findNotDupLong(String string) {
   
		
		if (StringUtils.isBlank(string)) {
   
			return "没有找到";
		}
		ArrayList<String> arrayList = new ArrayList<String>();// 用于存入符合条件的串
		String[] split = string.split("");
		for (int i = 0; i < split.length; i++) {
   
			for (int j = i; j < string.length(); j++) {
   
				if (string.substring(i,j).contains(string.charAt(j)+"")) {
   
					System.err.println(string.substring(i,j)+"==="+string.charAt(j)+"");
					arrayList.add(string.substring(i,j));
					i++;
					j=i;
				}
			}
		}
		Collections.sort(arrayList, new Comparator<String>() {
   
			@Override
			public int compare(String o1, String o2) {
   
				if (o1.length()>o2.length()) {
   
					return -1;
				}else if (o1.length()< o2.length()) {
   
					return 1;
				}else {
   
					return 0;
				}
			}
		});
		return arrayList.size()>0?arrayList.get(0):"没有找到";
	}

第二种方法 比较复杂 难以理解 大家可以研究一下哈。

private static String findNotDupLong3(String dupString) {
   
		
		long currentTimeMillis = System.currentTimeMillis();
        char[] chars = dupString.toCharArray();
        int[] data = new int[1024];
        for (int i = 0; i < data.length; i++) {
   
            data[i] = -1;
        }
        Stack<Character> stack = new Stack<Character>();
        Stack<Character> temp = new Stack<Character>();
        
        int maxLength = 0;
        int index = 0;
        
        for (char aChar : chars) {
   
        	
            if (data[aChar] == -1) {
   
                data[aChar] = index++; // 同时操作  如果 data 数组里面没有数据的话 分别将 数据放在 data 和 stack 中
                stack.push(aChar);
            } else {
   
            	
                if (stack.size() > maxLength) {
    // 如果 data 数组里面有数据 则需要暂时把stack的数据放在临时stack中
                    maxLength = stack.size(); // 当前最大的长度是 maxLength
                    temp = (Stack<Character>)stack.clone();
                }
                stack.push(aChar); // 将新的重复的元素放在 stack 中
                int popSize = stack.size() - index + data[aChar]; // 求出一个 size 
                do {
   
                	data[stack.get(0)] = -1; // data中存在的 stack的第一个元素置为-1
                    stack.remove(0); // 删除stack 中的第一个元素
                }while (--popSize !=0);
                   data[aChar] = index++; // 当popSize ！= 0 的时候  data中的这个元素所在的位置为 index ++ 
            }
        }
        
        if (stack.size() > maxLength) {
   
            temp = stack;
        }
        String result = "";
        int size = temp.size();
        for (int i = 0; i < size; i++) {
   
            result += temp.get(i);
        }
        System.out.println("方法3耗时："+(System.currentTimeMillis()-currentTimeMillis) +"毫秒");
        return result;
    }