用 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
}
评论
互联网晚报 | 大麦网已退款凤凰传奇演唱会“柱子票”;钟薛高再成被执行人;iPhone 16或取消实体音量键和电源键
大麦网回应凤凰传奇演唱会买到“柱子票”:已退票退款据报道,凤凰传奇2024巡回演唱会常州站演出结束的第二天,有网友称自己在大麦网买到“柱子票”,因为观看效果不佳,要求退款被拒。23日,记者从涉事网友处了解到,大麦方面给出了退款建议,但被其拒绝,“我希望平台退款加赔偿,并重视屡次出现的‘柱子票’问题。
产品刘
0
AI论文写作工具和生成器(一)
随着人工智能和大模型的迅猛发展,AI对研究人员和学生提供了极大的写作便利。本文将介绍市面上常用的AI论文写作工具,帮助你提高论文写作效率并遵循学术道德。请仅将AI论文生成器视为辅助参考手段,切勿直接挪用全文。XPaper AlXPaper AI是由点击式创作工具晓语台推出的一款论文写作生成平台,只需
IQ前端
0
Langchain使用 | 模型、提示和解析器、存储
零、LangChain介绍为各种不同基础模型提供统一接口- 帮助管理提示的框架- 一套中心化接口,用于处理长期记忆(参见Memory)、外部数据(参见Indexes)、其他 LLM(参见Chains)以及 LLM 无法处理的任务的其他代理(例如,计算或搜索)。总的来说,有六大核心模块:Models:
Python之王
0
奇域AI,最懂新中式美学的AI绘画神器
「奇域AI」是一款非常适合驾驭新中式审美的AI绘画工具。作为国内首个主打新中式插画的AI绘画产品,它提供了上百种新中式美学风格模型,包括新中式插画、笔墨水彩、新铅油画等,为用户提供了丰富的选择。这款工具在「网页版」和「小程序」上都可以使用,只需输入你想要的画面,就能生成出符合新中式审美的作品。奇域A
IQ前端
0
我用这10招,能减少了80%的BUG
将Python客栈设为“星标⭐”第一时间收到最新资讯前言对于大部分程序员来说,主要的工作时间是在开发和修复BUG。有可能修改了一个BUG,会导致几个新BUG的产生,不断循环。那么,有没有办法能够减少BUG,保证代码质量,提升工作效率?答案是肯定的。如果能做到,我们多出来的时间,多摸点鱼,做点自己喜欢
Python客栈
0
你真的理解 devDependencies 和 dependencies 的区别吗?
点击上方 前端Q,关注公众号回复加群,加入前端Q技术交流群作者:井柏然原文:https://juejin.cn/post/7135795969370619918你是否真的理解 devDependencies 和 dependencies 的区别?如果不能确切的回答、理解还停留在模糊的阶段,
前端Q
0
SpringBoot+Minio实现上传凭证、分片上传、秒传和断点续传
关注我们,设为星标,每天7:40不见不散,架构路上与您共享回复架构师获取资源大家好,我是你们的朋友架构君,一个会写代码吟诗的架构师。Spring Boot整合Minio后,前端的文件上传有两种方式:1、文件上传到后端,由后端保存到Minio这种方式好处是完全由后端集中管理,可以很好的做到、身份验证、
Java架构师社区
0
分享一份抓取某东商品名称、价格和评论数的代码
点击上方“Python共享之家”,进行关注回复“资源”即可获赠Python学习资料今日鸡汤芳草已云暮,故人殊未来。大家好,我是皮皮。一、前言前几天在Python白银交流群【邮递员】问了一个Python网络爬虫的问题,提问截图如下:代码如下:import requestsfrom
IT共享之家
0