欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

php算法题—无重复字符的最长子串

程序员文章站 2024-02-25 09:45:34
...

阅读量终于破万了, 不容易啊,不过看到访问量大的也就那么几个,都是比较常见的问题,其他的文章仍然是没人理采。 不说这了,说说今天做的一个算法提, 头大啊

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

具体算法

  1. 我自己写的一个,刚看到这个题感觉挺简单的,结果在做的过程中各种难。我的算法应该是 最差劲的算法了吧
    执行用时:24 ms
    内存消耗:17.7 MB
    class Solution {
    
        /**
         * @param String $s
         * @return Integer
         */
        function lengthOfLongestSubstring($s) {
            $len = strlen($s);
            $arr = [];
            $arr_len = [];
            for($i = 0; $i < $len; $i ++){
                $a = substr($s,$i, 1);
                if(end($arr) != $a){
                    if(in_array($a, $arr)){
                        $index = array_search($a, $arr);
                        $arr_len[] = $index+1;
                        $arr_len[] = count($arr);
                        $end = end($arr);
                        $arr = array_slice ($arr, $index+1);
                        $arr[] = $a;
                    }else{
                    $arr[] = $a; 
                    }
                }else{
                    $arr_len[] = count($arr);
                    $arr[] = $a;
                    $arr = array(end($arr));
                }
            }
            $arr_len[] = count($arr);
            return max($arr_len);
        }
    }
    
  2. 这是别人写的,这因该是最优解了
    执行用时:8 ms
    内存消耗:15.1 MB
    	class Solution {
        /**
         * @param String $s
         * @return Integer
         */
        function lengthOfLongestSubstring($s) {
            $len = strlen($s);
            $i = 0;
            $rIndex = 0;//开始搜索的位置
            $result = 0;//子串的长度
            while($i < $len){
                $pos = strpos($s,$s[$i],$rIndex);
                //出现重复
                if($pos < $i){
                    //如果匹配的位置小于当前字符的下标,出现重复,搜索位置以重复字符位置开始
                    $rIndex = $pos+1;
                }
                $result = max($result,($i - $rIndex + 1));
                $i++;
            }
            return $result;
        }
    }
    

这样一对比,感觉查的不是一个量级的,贴在这羞辱我自己吧

结论

别觉得自己厉害的不行不行的, 这样一对比,我才知道的我差距啊,不对是不可逾越的鸿沟。
加油吧,看来我是搬砖的料

如果您对这个文章有任何异议,那么请在文章评论处写上你的评论。
愿大家都能在编程这条路,越走越远。

努力加油,每一个困难,都会克服我。

相关标签: php php 算法