前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >用 PHP和Golang 来刷leetCode 之 无重复字符 最长子串

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

作者头像
码农编程进阶笔记
发布2021-07-20 16:28:24
发布2021-07-20 16:28:24
48000
代码可运行
举报
运行总次数:0
代码可运行

精选文章

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

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

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

方法一

代码语言:javascript
代码运行次数:0
运行
复制
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;
    }
}

方法二:

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

代码语言:javascript
代码运行次数:0
运行
复制
$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) 中。

代码语言:javascript
代码运行次数:0
运行
复制
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)

方法四:优化版滑动窗口

代码语言:javascript
代码运行次数:0
运行
复制
  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方法

代码语言:javascript
代码运行次数:0
运行
复制
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
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-08-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码农编程进阶笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 精选文章
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档