php算法题—无重复字符的最长子串
程序员文章站
2024-02-25 09:45:34
...
阅读量终于破万了, 不容易啊,不过看到访问量大的也就那么几个,都是比较常见的问题,其他的文章仍然是没人理采。 不说这了,说说今天做的一个算法提, 头大啊
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
具体算法
- 我自己写的一个,刚看到这个题感觉挺简单的,结果在做的过程中各种难。我的算法应该是 最差劲的算法了吧
执行用时:24 ms
内存消耗:17.7 MBclass 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); } }
- 这是别人写的,这因该是最优解了
执行用时:8 ms
内存消耗:15.1 MBclass 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; } }
这样一对比,感觉查的不是一个量级的,贴在这羞辱我自己吧
结论
别觉得自己厉害的不行不行的, 这样一对比,我才知道的我差距啊,不对是不可逾越的鸿沟。
加油吧,看来我是搬砖的料
如果您对这个文章有任何异议,那么请在文章评论处写上你的评论。
愿大家都能在编程这条路,越走越远。
努力加油,每一个困难,都会克服我。
下一篇: Python 学习之路-01