小編給大家分享一下編程語(yǔ)言中如何實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
創(chuàng)新互聯(lián)堅(jiān)持“要么做到,要么別承諾”的工作理念,服務(wù)領(lǐng)域包括:網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù),滿(mǎn)足客戶(hù)于互聯(lián)網(wǎng)時(shí)代的固鎮(zhèn)網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求,幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(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ù)字
以上是“編程語(yǔ)言中如何實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道!
文章標(biāo)題:編程語(yǔ)言中如何實(shí)現(xiàn)無(wú)重復(fù)字符的最長(zhǎng)子串
網(wǎng)站鏈接:http://muchs.cn/article10/pdgigo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供云服務(wù)器、網(wǎng)站策劃、建站公司、網(wǎng)站排名、網(wǎng)站制作、域名注冊(cè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶(hù)投稿、用戶(hù)轉(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)