查找字符串中连续不重复最长字符串和长度(Java)
1.思路
2.结果
字符串:abacbefkb
开始遍历:
链表的变化情况:
a:长度:1 链表:[a]
b:长度:2 链表:[a,b]
a:长度:2 链表:[b,a]
c:长度:3 链表:[b,a,c]
b:长度:3 链表:[a,c,b]
e:长度:4 链表:[a,c,b,e]
f:长度:5 链表:[a,c,b,e,f]
k:长度:6 链表:[a,c,b,e,f,k]
b:长度:4 链表:[e,f,k,b]
遍历结束
连续不重复的字符串:acbefk 长度:6
这是想到的是使用滑动窗口机制
1.将字符串转化成char数组.并且定义一个滑动窗口(window).
2.遍历char数组.每次拿到元素element=char[i]
3.开始操作window,先判断widow中是否有此element.
3.1.如果没有将element添加到窗口的尾部.
3.2.如果window有此element.
3.2.1.取出window的数据currentStr,如果currentStr的长度大于maxStr的长度,则将currentStr赋给maxStr.否则不更新maxStr.
3.2.2.从window移除element前数据(包含自己).
3.2.3.将element添加到window的尾部.
4.最后maxStr就是最大的连续不重复字符串.
滑动窗口:
这里我是自定义了一个单向链表.
3.数据结构
节点:Node
public E value;//链表的值
public Node next;//下一节点
public Node() {
}
public Node(E value) {
this.value = value;
}
public Node(E value, Node next) {
this.value = value;
this.next = next;
}
}
自定义的单向链表:SimpleList.(模拟的是窗口)
addLast(E e):尾插入
getFirstValue(E e):获取e在链表中的第一次出现的位置
removeAfterAllIndex(int index):移除指定为位置前的结点(包含自己)
toString():打印窗口的字符串
println():打印当前链表:为了方便查看窗口的情况
public class SimpleList<E> {
Node<E> head;//头结点
Node<E> last;//尾结点
public SimpleList() {
}
/**
* 添加数据:默认尾插入
*
* @param e
*/
public void addLast(E e) {
if (e == null) {
return;
}
lastAdd(new Node(e, null));
}
/**
* 获取链表中第一个结点值为e的结点
*
* @param e
* @return
*/
public int getFirstValue(E e) {
Node h = head;
for (int i = 0; h != null; i++, h = h.next) {
if (h.value == e || h.value.equals(e)) {
return i;
}
}
return -1;
}
/**
* 删除当前index位置之前的所有结点(包含当前结点)
*
* @param index
*/
public void removeAfterAllIndex(int index) {
//1.先找到当前结点
Node h = head;
Node nodeRemove = null;
for (int i = 0; i <= index; i++, h = h.next) {
if (i == index) {
nodeRemove = h;
break;
}
}
//2.进行删除结点
if (h != null) {
//头结点指向当前结点的next结点
head = nodeRemove.next;
//当前结点next置为null
nodeRemove.next = null;
}
}
/**
* 打印链表
*/
public void println() {
int count = 0;
StringBuilder sb = new StringBuilder();
sb.append("[");
Node h = head;
while (h != null) {
if (count > 0) {
sb.append(",").append(h.value);
} else {
sb.append(h.value);
}
count++;
h = h.next;
}
sb.append("]");
System.out.println("长度:" + count + "\t" + " 链表:" + sb.toString());
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node h = head;
while (h != null) {
sb.append(h.value);
h = h.next;
}
return sb.toString();
}
/**
* 尾插入
*
* @param node 新插入的结点
*/
private void lastAdd(Node node) {
//1.将last结点的next指向node
if (last != null) {
last.next = node;
//2.将last结点指向node结点(last结点后移)
last = node;
} else {
// 3.保证开始头结点和尾结点不能为空
head = last = node;
}
}
}
4.例子
public class TestWindow {
public static void main(String[] args) {
System.out.println("-----\n");
searchMaxStrAndLength();
System.out.println("\n-----");
}
public static void searchMaxStrAndLength() {
//1.遍历的字符串
String str = "abacbefkb";
String maxStr = "";
String temp;
System.out.println("字符串:" + str);
char[] chars = str.toCharArray();
//2.创建一个滑动窗口
SimpleList<Character> window = new SimpleList<>();
char c;
//3.开始遍历字符串
System.out.println("开始遍历:\n链表的变化情况:");
for (int i = 0, size = chars.length; i < size; i++) {
c = chars[i];
System.out.print(c + ":");
//3.
// 3.1先判断窗口中是否有此c,
int firstValue = window.getFirstValue(c);
// 3.2如果有的话,则删除窗口中此值之前的结点
if (firstValue != -1) {
//取出当前窗口的值与maxStr比较.
temp = window.toString();
if (maxStr.length() < temp.length()) {
maxStr = temp;
}
//移除当前位置前的所有结点
window.removeAfterAllIndex(firstValue);
}
// 3.3添加链表的尾部
window.addLast(c);
window.println();
}
//4.输出结果
System.out.println("遍历结束");
String resultStr = window.toString();
System.out.println("连续不重复的字符串:" + maxStr + " 长度:" + maxStr.length());
}
}
5.总结
1.这里使用的是链表模拟窗口
1.1.考虑到可能要频繁的删除数据,所以选择了链表.
1.2.但是可能查找元素的时候,要多次遍历链表.
1.3.优化:可以在查找结点时,可以直接进行返回当前结点,然后通过判断返回的结点是否为null,来判断是否进行移除结点.
2.也可以使用数组进行模拟滑动窗口.数组的移动可以使用System.arraycopy();
3.当然也可以使用系统提供的数据结构:ArrayList,LinkedList.作为滑动窗口.
源码下载