這篇文章主要講解了“Java/Python怎么找出無(wú)重復(fù)字符的最長(zhǎng)子串”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“Java/Python怎么找出無(wú)重復(fù)字符的最長(zhǎng)子串”吧！

網(wǎng)站設(shè)計(jì)制作過(guò)程拒絕使用模板建站；使用PHP+MYSQL原生開(kāi)發(fā)可交付網(wǎng)站源代碼;符合網(wǎng)站優(yōu)化排名的后臺(tái)管理系統(tǒng)；成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作收費(fèi)合理；免費(fèi)進(jìn)行網(wǎng)站備案等企業(yè)網(wǎng)站建設(shè)一條龍服務(wù).我們是一家持續(xù)穩(wěn)定運(yùn)營(yíng)了10余年的創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司。

題目:

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: "abcabcbb"輸出: 3 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入: "bbbbb"輸出: 1解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: "pwwkew"輸出: 3解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。     請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

解題思路:

• 暴力求解, 時(shí)間復(fù)雜度為 O(n^3), 因?yàn)橐獙?duì)所有字符遍歷, 對(duì)子串遍歷確認(rèn)是否有重復(fù)字符, pass

• 滑動(dòng)窗口, 維護(hù)一個(gè)索引 [i,j) 的滑動(dòng)窗口, 對(duì)已存在的字符 i' 直接更新滑動(dòng)窗口 [i',j), 你需要保留每一個(gè)字符值及其索引, 即由字符映射索引位置哈希映射: Key 為字符值, Value 為索引位置字符映射: ASCII 碼共 128 個(gè)字符, 維護(hù)一個(gè)長(zhǎng)度為 128 的整型數(shù)組,數(shù)組索引值映射 128 個(gè)字符,存儲(chǔ)元素值為字符位置

哈希映射:

Java:

class Solution {    public int lengthOfLongestSubstring(String s) {        char[] chars = s.toCharArray();//轉(zhuǎn)為字符數(shù)組        if (chars.length == 0) return 0;        HashMap<Character, Integer> 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);//更新滑動(dòng)窗口的左邊界 i            count = Math.max(count, j - i);//更新 count 為大值            map.put(chars[j], j + 1);//更新映射中該字符映射的 Value 值為當(dāng)前位置加一        }        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]) # 更新滑動(dòng)窗口的左邊界 i            count = max(count, j-i) # 更新 count 為大值            hash_map[c] = j+1 # 更新映射中該字符映射的 Value 值為當(dāng)前位置加一        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];//建立長(zhǎng)度為 128 位的 ASCII 碼字符映射表        int size = s.length(), count = 0, i = 0;        for (int j = 0; j < size; j++) {//遍歷字符            i = Math.max(index[chars[j]], i);//更新滑動(dòng)窗口的左邊界 i            count = Math.max(count, j - i);//更新 count 為大值            index[chars[j]] = j + 1;//更新映射中該字符所在元素值為當(dāng)前位置加一        }        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 # 建立長(zhǎng)度為 128 位的 ASCII 碼字符映射表        for j, c in enumerate(s): # 枚舉字符            i = max(i, index[ord(c)]) # 更新滑動(dòng)窗口的左邊界 i            count = max(count, j-i) # 更新 count 為大值            index[ord(c)] = j+1 # 更新映射中該字符所在元素值為當(dāng)前位置加一        return count+1 # 返回大累加總數(shù), 需要加 1

因?yàn)?Python 沒(méi)有字符概念, 需要 ord() 函數(shù)轉(zhuǎn)為 ASCII 數(shù)字

感謝各位的閱讀，以上就是“Java/Python怎么找出無(wú)重復(fù)字符的最長(zhǎng)子串”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)Java/Python怎么找出無(wú)重復(fù)字符的最長(zhǎng)子串這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

標(biāo)題名稱：Java/Python怎么找出無(wú)重復(fù)字符的最長(zhǎng)子串-創(chuàng)新互聯(lián)
標(biāo)題URL：http://jinyejixie.com/article40/djsgho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開(kāi)發(fā)、Google、響應(yīng)式網(wǎng)站、網(wǎng)站制作、外貿(mào)建站、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)