华为OD机试真题 - 最长子字符串的长度
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String inputString = scanner.nextLine();
System.out.println(findLongestSubstringWithoutRepetition(inputString));
}
/**
* 计算输入字符串中不包含重复字符的最长子串的长度。
* 使用位运算和链表数组来跟踪每个状态(字符组合)下的最早出现位置。
*
* @param input 输入字符串
* @return 不包含重复字符的最长子串的长度
*/
public static int findLongestSubstringWithoutRepetition(String input) {
int status = 0; // 使用位运算表示当前字符组合的状态
LinkedList<Integer>[] positionMap = new LinkedList[8]; // 映射每个状态到最早出现位置的链表
for (int i = 0; i < 8; i++) {
positionMap[i] = new LinkedList<>();
}
positionMap[0].add(-1); // 初始化空状态的位置为-1
int maxLength = 0; // 记录最长子串的长度
for (int i = 0; i < input.length() * 2; i++) {
char c = input.charAt(i % input.length()); // 循环输入字符串以处理重叠子串
switch (c) {
case 'l':
status ^= 4; // 对应0b100
break;
case 'o':
status ^= 2; // 对应0b010
break;
case 'x':
status ^= 1; // 对应0b001
break;
}
if (i < input.length()) {
positionMap[status].add(i); // 记录当前字符在当前状态下的位置
}
// 清理不再可能构成最长子串的状态位置
while (!positionMap[status].isEmpty()) {
int earliestPosition = positionMap[status].getFirst();
if (i - earliestPosition > input.length()) {
positionMap[status].removeFirst();
} else {
maxLength = Math.max(maxLength, i - earliestPosition);
break;
}
}
}
return maxLength;
}
Scanner scanner = new Scanner(System.in);
String inputString = scanner.nextLine();
System.out.println(findLongestSubstringWithoutRepetition(inputString));
}
/**
* 计算输入字符串中不包含重复字符的最长子串的长度。
* 使用位运算和链表数组来跟踪每个状态(字符组合)下的最早出现位置。
*
* @param input 输入字符串
* @return 不包含重复字符的最长子串的长度
*/
public static int findLongestSubstringWithoutRepetition(String input) {
int status = 0; // 使用位运算表示当前字符组合的状态
LinkedList<Integer>[] positionMap = new LinkedList[8]; // 映射每个状态到最早出现位置的链表
for (int i = 0; i < 8; i++) {
positionMap[i] = new LinkedList<>();
}
positionMap[0].add(-1); // 初始化空状态的位置为-1
int maxLength = 0; // 记录最长子串的长度
for (int i = 0; i < input.length() * 2; i++) {
char c = input.charAt(i % input.length()); // 循环输入字符串以处理重叠子串
switch (c) {
case 'l':
status ^= 4; // 对应0b100
break;
case 'o':
status ^= 2; // 对应0b010
break;
case 'x':
status ^= 1; // 对应0b001
break;
}
if (i < input.length()) {
positionMap[status].add(i); // 记录当前字符在当前状态下的位置
}
// 清理不再可能构成最长子串的状态位置
while (!positionMap[status].isEmpty()) {
int earliestPosition = positionMap[status].getFirst();
if (i - earliestPosition > input.length()) {
positionMap[status].removeFirst();
} else {
maxLength = Math.max(maxLength, i - earliestPosition);
break;
}
}
}
return maxLength;
}
全部评论
相关推荐
点赞 评论 收藏
分享
09-13 17:09
西安交通大学 供应链其他 点赞 评论 收藏
分享