用 PHP和Golang 来刷leetCode 之 无重复字符 最长子串

共 778字,需浏览 2分钟

 ·

2020-08-15 13:26

精选文章

免费获取Git GO Java视频教程
Go语言生成二维码是如此简单

涨见识| 字节PHP/Golang社招面经

一文让你知道为什么学了PHP的都要转学Go语言



方法一

class Solution {    /**     * @param String $s     * @return Integer     */    function lengthOfLongestSubstring($s) {        if (strlen($s)==0) return 0;        $map = [];        $max = 0;        $left = 0;        for($i = 0; $i < strlen($s); $i++){            if(array_key_exists($s[$i],$map)){                $left = max($left, $map[$s[$i]] + 1);            }            $map[$s[$i]] = $i;            $max = max($max,$i-$left+1);        }        return $max;    }}


方法二:

思路:逐个检查所有的子字符串,看它是否包含有重复的字符。

$str = "";function lengthOfLongestSubstring($s) {    $strlen = strlen($s);    if($strlen<=1){        return $strlen;    }    $subStrlen = [];
for($i=0;$i<$strlen;$i++){ $subStrArr = []; $subStrArr[] = $s[$i]; for($j=$i+1;$j<$strlen;$j++){ $subStrArr[] = $s[$j]; if(count(array_unique($subStrArr))!=count($subStrArr)){ array_pop($subStrArr); break; }
} $subStrlen = count($subStrArr)>count($subStrlen)?$subStrArr:$subStrlen; } return count($subStrlen);}$a = lengthOfLongestSubstring($str);print_r($a)


方法三

如果从索引 i 到 j - 1 之间的子字符串s[i,j)已经被检查为没有重复字符。我们只需要检查 s[j] 对应的字符是否已经存在于子字符串 s[i,j) 中。

function lengthOfLongestSubstring($s) {        $len = strlen($s);        if ($len < 2){            return $len;        }        $win = [];        $res_len = 0;        $i = 0;        $j = 0;        while ($i<$len && $j<$len){            if(!in_array($s[$i],$win)){                $win[]= $s[$i++];                $res_len = max($res_len,$i-$j);
}else{ $j++; array_shift($win); } } return $res_len; }


嗯 简单试了一下 差不多是上面方法的20倍 并且随着字符串的长度增长会更大  因为他是O(n)  


方法四:优化版滑动窗口

  function lengthOfLongestSubstring($s){        $len = strlen($s);        $j = 0;        $i = 0;        $maxStrLen = 0;        $set = [];        while ($j<$len){            if(array_key_exists($s[$j],$set)){                $i = max($i,$set[$s[$j]]);
} $maxStrLen = max($maxStrLen,$j-$i+1); $set[$s[$j]]=$j+1; $j++; } return $maxStrLen; }

使用Golang方法

package main
import "fmt"//最长不含有重复字符的子串func lenthOfNonRepeatingSubstr(s string) int { lastOccurred := make(map[byte]int) start := 0 maxLength := 0 for i, ch := range []byte(s) { if lastI, ok := lastOccurred[ch]; ok && lastI >= start { start = lastI + 1 } if i-start+1 > maxLength { maxLength = i - start + 1 } lastOccurred[ch] = i } return maxLength}
func main() { fmt.Println(lenthOfNonRepeatingSubstr("abcabcbb")) //3 fmt.Println(lenthOfNonRepeatingSubstr("bbbbb")) //1 fmt.Println(lenthOfNonRepeatingSubstr("pwwkew")) //3}

浏览 35
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报