建站
咨詢
售后
建站咨詢
新聞中心
這篇文章主要講解了“Java/Python怎么找出無重復字符的最長子串”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java/Python怎么找出無重復字符的最長子串”吧！
在郁南等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站制作、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計制作專業(yè)公司,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)營銷推廣,外貿(mào)網(wǎng)站制作,郁南網(wǎng)站建設(shè)費用合理。
題目:
給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"輸出: 1解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"輸出: 3解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
解題思路:
暴力求解, 時間復雜度為 O(n^3), 因為要對所有字符遍歷, 對子串遍歷確認是否有重復字符, pass
滑動窗口, 維護一個索引 [i,j) 的滑動窗口, 對已存在的字符 i' 直接更新滑動窗口 [i',j), 你需要保留每一個字符值及其索引, 即由字符映射索引位置哈希映射: Key 為字符值, Value 為索引位置字符映射: ASCII 碼共 128 個字符, 維護一個長度為 128 的整型數(shù)組,數(shù)組索引值映射 128 個字符,存儲元素值為字符位置
哈希映射:
Java:
class Solution { public int lengthOfLongestSubstring(String s) { char[] chars = s.toCharArray();//轉(zhuǎn)為字符數(shù)組 if (chars.length == 0) return 0; HashMap map = new HashMap<>();//建立哈希映射 int size = s.length(), count = 0, i = 0; for (int j = 0; j < size; j++) {//遍歷字符 if (map.containsKey(chars[j]))//如果映射中存在該字符 i = Math.max(map.get(chars[j]), i);//更新滑動窗口的左邊界 i count = Math.max(count, j - i);//更新 count 為最大值 map.put(chars[j], j + 1);//更新映射中該字符映射的 Value 值為當前位置加一 } return count + 1;//返回最大累加總數(shù), 需要加 1 }} Python:
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 hash_map = dict() # 建立字典 size = len(s) i, count = 0, 0 for j, c in enumerate(s): # 枚舉字符 if c in hash_map: # 如果映射中存在該字符 i = max(i, hash_map[c]) # 更新滑動窗口的左邊界 i count = max(count, j-i) # 更新 count 為最大值 hash_map[c] = j+1 # 更新映射中該字符映射的 Value 值為當前位置加一 return count+1 # 返回最大累加總數(shù), 需要加 1
字符映射:
Java:
class Solution { public int lengthOfLongestSubstring(String s) { char[] chars = s.toCharArray(); if (chars.length == 0) return 0; int[] index = new int[128];//建立長度為 128 位的 ASCII 碼字符映射表 int size = s.length(), count = 0, i = 0; for (int j = 0; j < size; j++) {//遍歷字符 i = Math.max(index[chars[j]], i);//更新滑動窗口的左邊界 i count = Math.max(count, j - i);//更新 count 為最大值 index[chars[j]] = j + 1;//更新映射中該字符所在元素值為當前位置加一 } return count + 1;//返回最大累加總數(shù), 需要加 1 }}Python:
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 size = len(s) i, count = 0, 0 index = [0]*128 # 建立長度為 128 位的 ASCII 碼字符映射表 for j, c in enumerate(s): # 枚舉字符 i = max(i, index[ord(c)]) # 更新滑動窗口的左邊界 i count = max(count, j-i) # 更新 count 為最大值 index[ord(c)] = j+1 # 更新映射中該字符所在元素值為當前位置加一 return count+1 # 返回最大累加總數(shù), 需要加 1
因為 Python 沒有字符概念, 需要 ord() 函數(shù)轉(zhuǎn)為 ASCII 數(shù)字
感謝各位的閱讀，以上就是“Java/Python怎么找出無重復字符的最長子串”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Java/Python怎么找出無重復字符的最長子串這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！
網(wǎng)站欄目：Java/Python怎么找出無重復字符的最長子串
文章源于：http://fisionsoft.com.cn/article/geojph.html
