首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

leetcode, 3#,这题我的算法虽然 AC,但是总觉得有 bug?

  •  
  •   nutting · 2018-02-27 17:31:38 +08:00 · 750 次点击
    这是一个创建于 650 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

    Given a string, find the length of the longest substring without repeating characters.

        public int lengthOfLongestSubstring(String s) {
            int longest=Integer.MIN_VALUE;
            for(int i=0;i<s.length();i++){
                int k=i;
                while(++k<=s.length()){
                    String sub=s.substring(i,k);
                    longest=sub.length()>longest?sub.length():longest;
                    // 子串到结尾或者子串后面的那个字符包含在子串里,结束循环
                    if(k==s.length()||sub.contains(s.substring(k,k+1) )){
                        break;
                    }
                }
            }
            return longest==Integer.MIN_VALUE?s.length():longest;
        }
    
    1 回复  |  直到 2018-03-24 12:20:11 +08:00
        1
    snowonion   2018-03-24 12:20:11 +08:00
    尝试证明正确性:
    当执行到 `String sub=s.substring(i,k);` 时,`s.substring(i,k)` 总是无重复字符的,那么只要 `s.substring(i,k)` 不含有 `s.charAt(k)`,`s.substring(i,k+1)` 就是无重复字符的。

    楼主可以再试试证贪心算法做这题的正确性。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1349 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 23:44 · PVG 07:44 · LAX 15:44 · JFK 18:44
    ♥ Do have faith in what you're doing.