package com.dazhongdianping.interview;
import java.util.HashMap;
import java.util.Map;
/**
* 求一个字符串中不重复字符的最长子串,如字符串"abcdefghiud",最长的不重复的子串为"abcdefghiu"
* @author yangjianzhou
*
*/
public class MaxSubstring {
public static void main(String[] args) {
longestNodupSubstring("abcdefghijhh");
}
/**cursor里面存放字符的在字符串中的位置
* lengAt[i]存放以字符string.charAt(i)结尾的最长子字符串的长度
* @param string
*/
public static void longestNodupSubstring(String string)
{
int len = string.length();
if(len>0){
Map<Character,Integer> cursor = new HashMap<Character,Integer>();
cursor.put(string.charAt(0), 0);
int [] lengthAt = new int[string.length()];
lengthAt[0] =1;
int max =0;
for(int i = 1 ;i<len;i++){
char c = string.charAt(i);
if(cursor.containsKey(c)){
lengthAt[i] = Math.min(lengthAt[i-1]+1, i-cursor.get(c));
}else {
lengthAt[i] = lengthAt[i-1]+1;
}
max = Math.max(max, lengthAt[i]);
cursor.put(c, i);
}
for(int i=0;i<len;i++){
if(max == lengthAt[i]){
System.out.println(string.substring(i-max+1, i+1));
}
}
}
}
}
运行结果:
abcdefghij
分享到:
相关推荐
[Java]算法练习-最长无重复字符子串练习题
java笔试题回文子串LPS-LCS-算法-分析 最长公共子串(LCS)问题是一直使用的经典计算问题。 该项目探索 LCS,它的一个特例,最长回文子串 (LPS) 问题,以及它的概括以及不同的问题域如何影响算法性能。 我对这些问题...
使用JavaScript,TypeScript,Go和Java的数据结构和算法问题 数据结构和算法问题,以及针对不同语言的解决方案说明和实现 :bar_chart: 按主题组织 二叉树 -硬 -中 -中 ...最长回文子串-中 最长有
原理 举例说明:A=GGATCGA,B=GAATTCAGTTA 第一步:初始化LD矩阵 公式一 若ai=bj,则LD(i,j)=LD(i-1,j-1) 若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 第二步:利用上述的公式一,计算第一行 ...
算法解析:深入解析了常见的字符串算法问题,如最长公共子串、字符串排序、子串查找等,并提供了解题思路和代码示例。 实战案例:通过具体的实战案例,演示了如何运用字符串处理技术解决实际问题,如文本处理、密码...
9.各最长回文子串查找算法 - 回文子串查找 - No5 10.中序遍历,莫里斯(morris)遍历法 - 二叉树遍历,二叉树线索化 - No94 11.传统快排,快排三数取中法 - 快排 - No215 12.小根堆 - 代码实现 - No215 13.两边递归组合...
算法 创建allUnique函数,如果子字符串中的字符都是唯一的,它会返回 True,否则会返回 False。遍历字符串 s 的所有可能的子字符串,更新子串长度的最大值。 时间复杂度:O(N^3) public class Solution { public ...
无重复字符最长子串.java) 4 [Java](/Java/004 两个有序数组的中位数.java) 5 [Java](/Java/005 最长回文子串.java) 6 [Java](/Java/006 ZigZag Conversion.java) 7 [Java](/Java/007 反向整数.java) 8 [Java](/Java...
KMP算法的核心在于构建一个名为“Next数组”的辅助数组,该数组用于存储模式串中每个位置前的子串的最长相同前后缀的长度。当主串中的字符与模式串的字符不匹配时,可以根据Next数组的值,快速将模式串滑动到正确的...
无重复字符的最长子串 - 0005 最长回文子串 - 0006 Z字形变换 - 0007 整数反转 - 0008 字符串转换整数 (atoi) - 0009 回文数 - 0011 盛最多水的容器 - 0013 罗马数字转整数 - 0014 最长公共前缀 - 0015 三数之和 - ...
无重复字符的最长子串 -滑动窗口2解法 找到字符串中所有字母异位词 - 滑动窗口 2020年7月5日: 最小覆盖子串【滑动窗口解法】: 2020年6月13日 德州扑克: 服务器广播: 九宫格输入问题: 判断一组数连续: 航班预定...
[重复字符的最长子串] Medium Two Pointers,Sliding Window 19 删除链表的倒数第N个节点 Medium Two Pointers 45 跳跃游戏 II Hard Greedy,DP 跳跃游戏 55 跳跃游戏 Meidum Greedy,DP 跳跃游戏 121 买卖股票的最佳...
本文实例讲述了PHP实现求解最长公共子串问题的方法。分享给大家供大家参考,具体如下: ...下面的算法是根据网上的java算法由酒逍遥 翻译过来的 已经经过修正 LCS经典算法php版本 <?php class LCS
删除无效括号 leetcode Java Zhang Yang's solutions ...无重复字符的最长子串 M 2018-6-10 北京 Y 删除排序数组中的重复项 E 2018-6-13 北京 Y 字符串转整数 M 2018-6-15 北京 Y 有效的括号 E 2018-
无重复字符的最长子串 (368 毫秒) 上) O(1) C# 使用数组会变慢 4 两个有序数组的中位数 (596 毫秒) O(对数(N+M)) O(1) 5 最长回文子串 (316 毫秒) 上) 上) 使用 Manacher 算法 问题 201-250 # 标题 解决...
q3_无重复字符的最长子串 q11_盛最多水的容器 q15_三数之和 q16_最接近的三数之和 q26_删除排序数组中的重复项 q42_接雨水 q121_买卖股票的最佳时机 q209_长度最小的子数组 快慢指针遍历 q141_环形链表 q202_快乐数 ...
前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法。 代码如下: <?php $a = 'abceee12345309878'; $b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew'; $c = ...
无重复字符的最长子串 双指针 √ --- √ × × 5 最长回文子串 动态规划 √ --- √ × × 7 整数反转 数学 √ --- √ × × 9 回文数 回文数 √ --- √ × × 13 罗马数字转整数 数学 √ --- √ × × 20 有效的括号...
2 8 字符串的最长回文子串:Manacher 算法 42 第 3 章 序列 44 3 1 网格中的最短路径 44 3 2 编辑距离(列文斯登距离45 3 3 最长公共子序列 47 3 4 升序最长子序列 49 3 5 两位玩家游戏中的必胜策略 52 第 4 章 数组...
高级java笔试题 个人博客 c++ c++primer - c++primer顺序容器与关联容器的一些用法 effective c++ - effective c++笔记归纳 ...数据结构与一些算法,来自算法导论,数据结构与算法分析-...LCS(最长公共子串),Rabin-Karp,