用 PHP和Golang 来刷leetCode 之 无重复字符 最长子串
码农编程进阶笔记
共 778字,需浏览 2分钟
· 2020-08-15
精选文章
免费获取Git GO Java视频教程
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
}
评论
中华人民共和国和法兰西共和国关于人工智能和全球治理的联合声明
中国邀请法国参加2024世界人工智能大会暨人工智能全球治理高级别会议。冲击万店,汉堡界能跑出下一个蜜雪冰城吗?应法兰西共和国总统埃马纽埃尔·马克龙邀请,中华人民共和国主席习近平于2024年5月5日至7日对法国进行国事访问。在两国建交60周年之际,两国元首重申共同致力于深化2023年4月5日至7日法兰
亿欧网
0
微软大模型Phi3安装和介绍,普通电脑不联网也能提问!
你好,我是郭震1 前沿 最近,微软发布Phi-3模型,最小尺寸的phi-3-mini(3.8B参数量)在更大、更干净的数据集(包含3.3T个tokens)上进行训练,在各大公开的学术基准和内部测试中,实现了与Mixtral 8x7B和GPT-3.5等大尺寸模型的性能。模型小,phi-3-mini的尺
Python与算法社区
0
100种分析思维模型之:逻辑思维
你好,我是林骥。假设给你无限的资源,请问你能造出火箭吗?面对这种从来没有遇到过的难题,很多人可能会有点迟疑。但如果你拥有逻辑思维,也许就会自信地做出回答:肯定能。下面介绍 100 种分析思维模型的第 100 种:逻辑思维,它能帮助我们找到化解难题的方法,获得可重复、可叠加的成功。1. 为什么学习逻辑
林骥
1
重点城市和商场“五一”销售数据出炉
出品/联商网&搜铺网整理/西泠雪今年“五一”假期,消费市场呈现多元化趋势,旅游、餐饮市场持续升温,家电市场购销两旺,零售市场活力迸发,经济向好稳定发展。《联商网》根据公开数据,统计了餐饮、旅游、电影等行业数据,及部分省份和城市发布的相关实体商业消费通报。从公布的数据来看,“五一”假期,全国各
联商网资讯
1
小美播报|广电总局公布治理电视“套娃” 收费和操作复杂工作投诉渠道
小美播报广电总局公布治理电视“套娃” 收费和操作复杂工作投诉渠道在广大人民群众和有关部门的大力支持下,国家广播电视总局积极解决“看电视难、看电视烦”等问题,已取得阶段性进展。为更好倾听人民群众意见建议,进一步巩固提升治理电视“套娃”收费和操作复杂工作成果,国家广播电视总局公布“双治理”工作用户投诉渠
流媒体网
0
南京专家来盱眙县中医院坐诊信息(5月6日-5月11日)
盱眙县中医院长期聘请省城医院多位知名专家每周定期来院坐诊、查房、手术。为方便群众就医,现将本周(5月6日—5月11日)来院坐诊专家有关信息公布如下:专家介绍夏建国主任医师,江苏省人民医院胃肠病区原主任,普外科专家。专业擅长:消化系肿瘤诊断及胃癌、肠癌、腹膜后肿瘤的根治手术,经腹腔镜结直肠癌根治术治疗
盱眙老妹
0
抖音最火的嘴替文案,来自史铁生~
来源:新闻与写作“20岁读不懂他的文字,30岁之后想读千遍。”根据前几日发布的《2024抖音读书生态数据报告》显示,史铁生成为了抖音最受欢迎的作家,相关视频累积18.6万个,00后、90后、80后组成了偏好观看的TOP3。在小红书上一段史铁生讲余华带他踢球的段子点赞2w多,说一句史铁生是当今互联网的
运营大叔
1