leetcode算法题—golang—无重复的字符的最长子串（题3）

题目：无重复的字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
     请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

方法一

<pre class="has"><code class="language-Go">//abcabcbb //判断子串是否合法 //内嵌一个循环判断是否有重复子串 //如果有个重复子串，则start和end的位置增加 //如果不重复则，继续增加子串的数量 func lengthOfLongestSubstring(s string) int { if s == ""{ return 0 } var strLen = len(s) var start,end=0,1 var s2 string for end <= strLen{ var s1 string = string(s[start:end]) //计算重复 var repeatCount int = 1 var s1Len int = len(s1) for i:=0;i < s1Len;i { var temp string = string(s1[i]) repeatCount = strings.Count(s1,temp) //说明有重复的了 if repeatCount >1{ start end =start len(s1) break } } if repeatCount ==1{ //增加 s2 = s1 //保存之前的值 end } } return len(s2) }</code></pre>

方法二

<pre class="has"><code class="language-Go">//n*n*n 找出该串的所有子串，不重复，且最大即可 func lengthOfLongestSubstring(s string)int{ var counts int = 0 for i:=0;i<len(s);i { //找出他所有的子串 for j:=i 1;j<=len(s);j { if allUnique(s,i,j){ temp := math.Max(float64(counts),float64(j-i)) counts = int(temp) } } } return counts } //找出子串不重复的 func allUnique(s string,start,end int)(bool){ //会截取start -> end-1位置的下标 s = s[start:end] for i:=0;i<len(s);i { //返回该子串在主串中的重复数量 repeatCount := strings.Count(s,string(s[i])) if repeatCount !=1 { return false } } return true }</code></pre>

方法三

<pre class="has"><code class="language-Go">//利用滑动窗口和容器 func lengthOfLongestSubstring(s string)int{ //借助一个容器，来判断，子串中是否有重复 妙 m := make(map[byte]byte) sLen := len(s) start,end := 0,0 var repeatCount int = 0 //start 和 end 双条件判断，只有end一个也可以，可能这样更严谨一些吧 for start <sLen && end <sLen{ temp := s[end] if _,ok := m[temp];!ok{ //不存在说明该key是唯一的 m[s[end]] = s[end] end //移动滑动窗口 repeatCount = int(math.Max(float64(repeatCount),float64(end-start))) }else{ //说明了有重复的，滑动窗口移动，则start 1, delete(m,s[start]) start } } return repeatCount }</code></pre>

方法四

<pre class="has"><code class="language-Go">//优化滑动窗口 // abcabcbb // abc // bca // cab // abc // cb // b func lengthOfLongestSubstring4(s string)int{ var n,ans = len(s),0 m := make(map[string]int) //存放字符出现的位置 for j,i :=0,0; j<n;j { if _,ok := m[string(s[j])];ok{ //发现重复的，则重新选择一个i，这个i停留在出现重复的前一位置 i = int(math.Max(float64(m[string(s[j])]),float64(i))) //这里的i则为下标 } //每次计算j-i 1的记录，j为字符串的下标，i为下标，重复，i则从重复位置前一位开始 ans = int(math.Max(float64(ans),float64(j-i 1))) m[string(s[j])] = j 1 } return ans }</code></pre>

推荐是  方法三、方法四

 

到此这篇关于“leetcode算法题—golang—无重复的字符的最长子串（题3）”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
leetcode算法题—golang—无重复的字符的最长子串（题3）
js时间函数综合例子(日期计算、字符串转日期等)
PHP中截取中文乱码解决办法
LeetCode面试算法-力扣 3. 无重复字符的最长子串
php5 字符串处理函数汇总
mysql导入导出数据时中文乱码的解决办法
网页标题随机显示名言js代码
专家教你如何有效的学习Drupal - Drupal问答
php session 同ip不同端口的多个网站session冲突的解决办法
mysql常用字符串函数的用法