当前位置: 代码迷 >> Java相关 >> 一道string经典题的有关问题
  详细解决方案

一道string经典题的有关问题

热度:98   发布时间:2016-04-22 20:17:01.0
一道string经典题的问题
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题目就是leetcode第三题。 我是刚开始刷题的,java也是接触不久,是一个小菜鸟。参考网上的答案自己写出了一个。发现通过不了。 我的代码如下:
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean flag[] = new boolean[256];
        char [] ary= s.toCharArray();
        int start = 0;
        int result = 0;
        
        for (int i=0; i<ary.length;i++){
            char current = ary[i];
            if(flag[current]) {
                result = Math.max(result, i-start);
                for (int k=start; k<i;k++){
                    if (ary[k]== current){
                        start=k+1;
                        break;
                    }
                    flag[current]=false;    //flag[ary[k]]=false;    
                }
            }else {
                flag[current]=true;
            }
        }
        result = Math.max(ary.length - start, result);
        return result;
    }
}

******************************
出错的地方加粗了,我认为在这个情况下,current和 ary[k]表示的都是同一个char,但注释的代码就能AC,我用current就会报错。得出的答案比正确答案多1。请各位大大帮忙解惑一下,究竟是哪里出错?在此先谢过了。新注册的号,分数不多,请理解。
------解决思路----------------------
如果arr[k]==current就直接跳出循环了,现在能走到下面说明这两个是不等的。这个算法我没看懂,我觉得应该是个dp问题,用arr[i][j]表示第i~j个char是否满足要求
------解决思路----------------------
首先,我还是没看懂你写的方法,,,对不起了,由于今天来图书馆没带鼠标,就胡乱给你写了一个算法(性能上很渣渣的那种,不过估计能用吧。。),看图:
package com.test;
/**
 * find the length of the longest substring without repeating characters 
 * @author Administrator
 */
public class T5 {

public static int findNotReaptingNumber(String str){
char[] orginalChar = str.toCharArray() ;
char[] newChar = new char[orginalChar.length];
int maxLength = 0 ;

int index = 0 ;
for (int i = 0; i < orginalChar.length; i++) {
if (!hasContains(newChar, orginalChar[i])) {
newChar[index++] = orginalChar[i];
}else{
maxLength = index > maxLength ? index : maxLength ;
index = 0 ;
newChar = new char[orginalChar.length];
}
}
return maxLength ;
}

/**
 * 判断字符是否在字符数组中
 * @param org
 * @param mychar
 * @return
 */
static boolean hasContains(char[] org , char mychar){
for (int i = 0; i < org.length; i++) {
if(org[i] == mychar)
return true ;
}
return false ;
}

public static void main(String[] args) {

System.out.println(findNotReaptingNumber("aaaaaaaab"));
}
}


希望你能用得上,估计我这一天也只能看看视频什么滴了啊。。。。
  相关解决方案