每日一道算法題,讓你的頭腦更活躍(沒有重複字符的最長子串)

2020-12-27 底層程式設計師的仰望

前言

時長不更新,小編的心裡也是非常的難過,怪自己沒有好的知識與大家分享。最近準備把算法慢慢的撿起來,所以準備日更一道算法題目,難度自然是由簡入難,所以同學們可以每天都來看看小編的更新。日更時間定在每晚20:00,希望大家多多關注啦。沒有重複字符的最長子串

給定一個字符串,查找不重複字符的最長子字符串的長度。

Example 1:

輸入: "abcabcbb"輸出: 3 說明: 正確的字串是 "abc", 長度是3。

Example 2:

輸入: "bbbbb"輸出: 1說明: 正確的字串是 "b", 長度是1.

Example 3:

輸入: "pwwkew"輸出: 3說明: 正確的字串是 "wke", 長度是3.

解題思路

看到題目,我們可以了解到,我們需要的是沒有重複字符的字符串,由此我想到了HashSet集合,我們可以利用它的特性來處理這道題目。有了HashSet集合來存儲數據,我們就可以非常簡單驗證重複,那後面就是通過簡單的暴力求解,來尋找最長的沒有重複的子串。有了以上兩點,我們把他們融合到一起,就可以實現尋找沒有重複字符的最長子串。詳見下方代碼及注釋:

最後說兩句

所有的題目都有很多種解法,我的一定不是最好的,甚至可以說是比較低端的解法,希望大牛們多多指教如果朋友們對算法、編程有很大興趣的話,可以私信我,大家一同探討;相互學習、共同進步。朋友們如果對這道題目有更好的解法,希望可以在評論中指出,讓大家一起討論學習。最後感謝大家的閱讀以及關注,謝謝大家!!!

相關焦點

  • LeetCode 熱題 HOT 100(02,無重複字符的最長子串)
    LeetCode 熱題 HOT 100(02,無重複字符的最長子串)不夠優秀,發量尚多,千錘百鍊,方可成佛。算法的重要性不言而喻,無論你是研究者,還是最近比較火熱的IT 打工人,都理應需要一定的算法能力,這也是面試的必備環節,算法功底的展示往往能讓面試官眼前一亮,這也是在大多數競爭者中脫穎而出的重要影響因素。
  • LeetCode刷題筆記 - 3. 無重複字符的最長子串
    學好算法很重要,然後要學好算法,大量的練習是必不可少的,LeetCode是我經常去的一個刷題網站,上面的題目非常詳細
  • 算法連載之求解不含有重複字符的最長子串長度
    問題給定一個字符串,找出其中不含有重複字符的最長子串長度。分析程序,匹配在給定字符串中是否有重複字符isRepeating函數的時間複雜度是O(n)。因此,完成算法的時間複雜度是O(n);空間複雜度是O(min(n, m)),其中n是字符串的長度,m是相異字符的數量。
  • 無重複字符的最長子串 | Leetcode題解
    題目描述給定一個字符串,請你找出其中不含有重複字符的 最長子串 的長度。示例 1:輸入: "abcabcbb"輸出: 3解釋: 因為無重複字符的最長子串是 "abc",所以其長度為 3。示例 2:輸入: "bbbbb"輸出: 1解釋: 因為無重複字符的最長子串是 "b",所以其長度為 1。
  • 圖解LeetCode第 3 號問題:無重複字符的最長子串
    題目描述 給定一個字符串,找出不含有重複字符的最長子串的長度。示例 1:  輸入: "abcabcbb"   輸出: 3   解釋: 無重複字符的最長子串是 "abc",其長度為 3。示例 2:  輸入: "bbbbb"  輸出: 1.     解釋: 無重複字符的最長子串是 "b",其長度為 1。
  • 經典leetcode算法題分享(字符串)
    不要給另外的數組分配額外的空間,你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。你可以假設數組中的所有字符都是 ASCII 碼錶中的可列印字符。解題思路:一看到這道題,直呼是送分題,這反轉字符串不就是JavaAPI就有了嗎,於是乎直接大膽的,兩行代碼搞定,好傢夥!一下子重拾回作為程式設計師的信心!
  • LeetCode刷題實戰3:最長不重複子串
    算法的重要性,我就不多說了吧,想去大廠,就必須要經過基礎知識和業務邏輯面試+算法面試。所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !https://leetcode.com/problems/longest-substring-without-repeating-characters/翻譯題目只有一句話:給定一個字符串,要求返回不包含重複字符的最長子串的長度。
  • 最長回文子串——馬拉車算法詳解
    馬拉車算法馬拉車算法(Manacher『s Algorithm)是用來解決每天一道算法:最長回文子串問題的。此算法充分利用了回文字符串的性質,將算法複雜度降到了線性,非常值得一學。我將網上所有講解馬拉車算法的文章基本看了一遍,總結出了最通俗易懂的介紹,同時用 python 進行了實現。題目給定一個字符串s,找到s中最長的回文子字符串。
  • 一文帶你AC十道題【滑動窗口】
    窗口大小可能會根據網絡流量的變化而有所不同,但是在更簡單的實現中它們是固定的。窗口大小必須大於零才能進行任何操作。我們算法中的滑動窗口也是類似,只不過包括的情況更加廣泛。實際上上面的滑動窗口在某一個時刻就是固定窗口大小的滑動窗口,隨著網絡流量等因素改變窗口大小也會隨著改變。接下來我們講下算法中的滑動窗口。
  • 上升下降字符串 | LeetCode
    「好久沒刷 LeetCode 了,剛打開頁面,啪,每日一題就顯示出來了,很快啊。
  • 另一道滑動窗口算法題【最長無重複子串】
    一 前言        昨天寫了一個算法題,引出一個求解方法——滑動窗口。很多人只是掃了一眼,沒細看文中代碼,就很不以為意。
  • [每日一題]140. Word Break II
    圖四圖四的case有一個特點,就是有很多重複的字符。所以,我們可以在圖三的代碼的基礎上做優化:緩存結果。在圖一和圖二的分析中,我們可以知道,遍歷所有的可能解的過程中 ,有許多重複的分支。所以,我們可以得到如下的思路:假設 字符串當前的位置是 n ,f(n) 表示所有的可能解, w(x) 表示 從位置 x 到 n 的子串:f(n) = w(n) * f(n-1) + w(n-1) * f(n-2) + ... + w(0)以 catsanddog 為例子,如下圖所示
  • Java數據結構與算法——字符串匹配相關算法
    Java裡用的是indexOf函數,其底層就是字符串匹配算法.其中字符串匹配算法主要包括:1. BF(暴力匹配)算法1.1概念和原理Brute Force叫作暴力匹配算法,也叫樸素匹配算法。其主要實現原理就是 在主串中,檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串,看有沒有跟模式串匹配的。
  • 「數據結構」變換『a』,『b』的最長子串
    題目描述:有一個僅包含』a』和』b』兩種字符的字符串s,長度為n,每次操作可以把一個字符做一次轉換(把一個』a』設置為』b』,或者把一個』b』置成』a』);但是操作的次數有上限m,問在有限的操作數範圍內,能夠得到最大連續的相同字符的子串的長度是多少。
  • 一道Python面試題:如何反轉字符串
    (點擊上方公眾號,可快速關注一起學Python)來源:公眾號-哎媽呀Bug  連結:https://mp.weixin.qq.com/s/wC5x8fRAwVvZYs3YGVr5iw按單詞反轉字符串是一道很常見的面試題。
  • 漫畫:什麼是字符串匹配算法?
    為了統一概念,在後文中,我們把字符串A稱為主串,把字符串B稱為模式串。由此得到結果,模式串 bce 是主串 abbcefgh 的子串,在主串第一次出現的位置下標是 2:以上就是小灰想出的解決方案,這個算法有一個名字,叫做BF算法,是Brute Force(暴力算法)的縮寫。
  • 字符串匹配算法之 AC 自動機
    我們經常用的字符串方法indexOf,都是判定兩個字符串的包含關係,底層使用類似KMP,BM, Sunday這樣的算法。如果我們要判斷一個長字符串是否包含多個短字符串呢?Aho 和 Margaret J.Corasick 於1975年發明的,幾乎與KMP算法同時問世,至今日仍然在模式匹配領域被廣泛應用。AC自動機的核心算法仍然是尋找模式串內部規律,達到在每次失配時的高效跳轉。這一點與單模式匹配KMP算法是一致的。不同的是,AC算法尋找的是模式串之間的相同前綴關係。
  • 十道Google面試題,你能搞定幾道?
    機器學習專家和超級碼農Koth說了,會給出每一道題的coding。]Google 面試題7 翻轉遊戲(Flip Game II)你和你的朋友正在玩一個翻轉遊戲:給定一個只包含'+'和'-'的字符串,你和你的朋友輪流進行以下操作:翻轉兩個連續的'+',使得」++」變成」—」。
  • 字節大佬Leetcode刷題筆記,看完吊打問你算法的面試官
    第四部分是每日一題,每日一題是在交流群(包括微信和 qq)裡進行的一種活動,大家一起 解一道題,這樣討論問題更加集中,會得到更多的反饋。而且 這些題目可以被記錄下來,日後會進行篩選添加到倉庫的題解模塊。
  • [每日一題]131. Palindrome Partitioning
    雙指針是通過兩個指針,分別指向字符串的首尾,如果當前的兩個字符相等則繼續,直到兩個指針相遇(或者位置相差 1)。和 除去首尾兩個字符的子串是否為回文。,一般動態語言的字符串都有反轉字符串的API,所以代碼最簡單。