* 面试题或者笔试题常问的算法 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; }

技术
©2019-2020 Toolsou All rights reserved,
Java开发2020年最新常见面试题整理【Spring源码分析】42-@Conditional详解element-ui踩坑记录神仙面试宝典你有了吗?半月看完25大专题,居然斩获阿里P8offer使用css样式设计一个简单的html登陆界面XCTF攻防世界web新手练习_ 9_command_executionJS中的解构赋值的详解与具体用途Python Web 框架elementui 穿梭框 el-transfer 展示列表内容文字过长ConcurrentHashMap实现原理及源码解析