小傅哥 | https://
沉淀,、分享,、成長,，專注于原創(chuàng)專題案例,，以最易學(xué)習(xí)編程的方式分享知識,，讓自己和他人都能有所收獲。目前已完成的專題有,；Netty4.x實(shí)戰(zhàn)專題案例,、用Java實(shí)現(xiàn)JVM、基于JavaAgent的全鏈路監(jiān)控,、手寫RPC框架,、架構(gòu)設(shè)計專題案例、源碼分析,、算法學(xué)習(xí)等,。
你用劍🗡、我用刀🔪,，好的代碼都很燒,，望你不吝出招！

一,、前言

在刷了第一道 leetcode 的題以后我一直在思考,，怎么才能讓小白更清楚的了解到整個算法運(yùn)行的過程。如果只是單純的一點(diǎn)點(diǎn)看代碼，從中摸清楚整個流程確實(shí)還是有一些難度,。雖然就一道題來說,，代碼塊并不會很大，但僅憑借變量之間的交換以及斷點(diǎn)調(diào)試輸出結(jié)果,，還是很難在我們的大腦中形成一個完整的執(zhí)行流程,。

為此，最近經(jīng)過不斷的搜索在 Github 中找到了 MarkKoz 大神的算法可視化工程：algorithm-visualizer ,。這是 nodejs 代碼,，在按照文檔說明安裝以及寫測試用例驗(yàn)證后，確實(shí)可以滿足目前的可視化需求,。

好,！那么我就按照自己的需求，將代碼部署到本地以及創(chuàng)建了一套符合自己需求可以將各種算法題進(jìn)行可視化展示,。這套功能包括三部分,，如下(可以下載后運(yùn)行)；

效果展示：

• 最左側(cè)是代碼區(qū)域,，也就是我們提交到 algorithms中的算法代碼。不支持中文以及特殊符號
• 中間是展示運(yùn)行過程區(qū)域,，這部分主要來自于在算法代碼中添加的展示化代碼塊,，例如：array1DTracer.select(beginIdx, i - 1);
• 最右側(cè)是代碼區(qū)域，這里的代碼可以修改后構(gòu)建并運(yùn)行，但不會保存,。同時在運(yùn)行的時候可以調(diào)整運(yùn)行速度 Speed，極大的方便了我們觀察算法的執(zhí)行過程
• 上圖的展示內(nèi)容其實(shí)就是我們在 leetcode 中做的第一題《兩數(shù)之和》其中的一中使用自己定義的 bit 結(jié)構(gòu)數(shù)組的方式求解的演示

那么,！接下來我們開始刷 leetcode中第三題《無重復(fù)字符的最長子串》,，并最終動態(tài)展示給大家這段算法的執(zhí)行效果。如果你想在本地運(yùn)行,，可以關(guān)注公眾號：bugstack蟲洞棧

二,、題目：《無重復(fù)字符的最長子串》

給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度,。

示例 1:

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

示例 2:

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

示例 3:

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

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
       // TODO
    }
}

三、思路和實(shí)現(xiàn)

從題目和示例上可以分析到這個題主要是從字符串中順序?qū)ふ页鲆淮畠?nèi)部不重復(fù)又是整個字符串中最長的那個字串,。為了尋找到這樣的子串可能首先想到的是循環(huán)出所有子串的集合,，之后選取最長的。當(dāng)把整個思路在整理幾遍和簡化后,，那么是不就可以理解為,，這是兩個值指針在字符串中往前跑，當(dāng)結(jié)尾指針碰到的元素與開始指針指向的元素一致,，則將開始指針向前進(jìn)一位,，之后繼續(xù)執(zhí)行直到結(jié)束算出最長子串。整個思路可以用下圖展示,；

• 從上圖的算法可以看到,，只要先跑的那個指針也就是子串結(jié)尾的指針，碰到了開始指針中間,，一樣的元素,，就將指針位置指向相同元素的下一位。切記不是指針 +1
• 為了實(shí)現(xiàn)這樣的功能,，我們就需要存儲兩個指針,，同時需要有方法判斷元素所處的位置,。那么有如下幾個方法,；
  • 使用 indexOf,，整個方法可以判斷元素位置，同時可以指定從某個位置開始判斷后面的元素是否存在相同元素,。
  • 使用 toCharArray(),，轉(zhuǎn)換為數(shù)組,，并將元素按照按照編碼位置存放到新建的數(shù)組中,，用于判斷元素是否出現(xiàn)過。
  • 使用 bit,，建立一個數(shù)組結(jié)構(gòu),，通過與運(yùn)算獲取元素位置，并存放,。方便快速查找。
• 另外在比對是否撞上相同元素的時候,，可以輸出當(dāng)前開始指針與結(jié)束指針中間的長度，并與之前的記錄的值比對,，如果超過則更新,，直到最后輸出。

1. 實(shí)現(xiàn)方式,，indexOf

public int lengthOfLongestSubstring_1(String s) {
    if (null == s || "".equals(s)) return 0;
    if (" ".equals(s) || s.length() == 1) return 1;  

    int beginIdx = 0, endIdx = 0, maxSize = 0;
    for (int i = 1; i  s.length(); i++) {
        endIdx = i;
        int existIdx = s.indexOf(s.charAt(i), beginIdx);
        if (existIdx  endIdx) {
            beginIdx = existIdx + 1;
        }
        int eval = endIdx - beginIdx + 1;
        if (maxSize  eval) {
            maxSize = eval;
        }
    }
    return maxSize;
}

• 不滿足條件的字符串直接按照規(guī)則返回,。
• 每次循環(huán)計算是否碰撞到相同的元素，并處理開始指針的位置,。
• 最后輸出最長子串的長度,。

2. 實(shí)現(xiàn)方式，toCharArry

public int lengthOfLongestSubstring_2(String s) {
    if (null == s || "".equals(s)) return 0;
    if (" ".equals(s) || s.length() == 1) return 1;    

    char[] array = s.toCharArray();
    int[] exist = new int[127];
    exist[array[0]] = 1;     

    int beginIdx = 1, endIdx = 1, maxSize = 0;
    for (int i = 1; i  array.length; i++) {
        endIdx = i;
        if (exist[array[i]] >= beginIdx) {
            maxSize = Math.max(i - beginIdx + 1, maxSize);
            beginIdx = exist[array[i]] + 1;
        }
        exist[array[i]] = i + 1;
    }
    maxSize = Math.max(exist[array[endIdx]] - beginIdx + 1, maxSize);
    return maxSize;
}

• 同樣不滿足的字符串直接返回,。
• 字符串轉(zhuǎn)換為數(shù)組,，同時定義一個新的數(shù)組用于存放地址。int[] exist = new int[127],，元素作為地址,，位置作為值,。
• 只有在碰撞時候才計算兩個指針間的長度,，其他時間不計算。
• 最后輸出最長子串的長度,。

3. 實(shí)現(xiàn)方式,，bit結(jié)構(gòu)

public int lengthOfLongestSubstring_3(String s) {
    if (null == s || "".equals(s)) return 0;
    if (" ".equals(s) || s.length() == 1) return 1;    

    int volume = 128;
    int bitMode = volume - 1;
    int[] t = new int[volume];
    int beginIdx = s.charAt(0) & bitMode, endIdx = 0, maxSize = 0;
    t[beginIdx] = 1;
    for (int i = 1; i  s.length(); i++) {
        endIdx = s.charAt(i) & bitMode;
        int val = t[endIdx];
        if (val != 0 && val >= t[beginIdx]) {
            beginIdx = s.charAt(val) & bitMode;
            t[beginIdx] = val + 1;
        }
        t[endIdx] = i + 1;
        int v = t[endIdx] - t[beginIdx] + 1;
        if (v > maxSize) {
            maxSize = v;
        }
    }
    return maxSize;
}

• 如果你把上面的代碼看明白了，那么這塊的邏輯變化只是在于將元素通過與運(yùn)算存放到bit結(jié)構(gòu)中，這和我們在計算《兩數(shù)之和》的算法方式一樣,。

四,、算法可視化運(yùn)行

• 通過可視化運(yùn)行可以很方便的看到算法的執(zhí)行過程，這要比我們只是用腦子一遍遍過程流程清晰的多,。尤其是對新人來說,，簡直太方便了。
• 這個可視化運(yùn)行的工具,，可以自己下載安裝,，他是nodejs的環(huán)境。如果在使用過程中遇到什么問題,，可以關(guān)注公眾號(bugstack蟲洞棧)內(nèi)聯(lián)系我,。

五、總結(jié)

• 想做好算法目前看到最主要的是捋清楚它的執(zhí)行思路,，之后選擇不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行填充數(shù)據(jù),。最后按照這個流程一點(diǎn)點(diǎn)調(diào)試算法，以滿足所有情況,。
• 在可視化工具的輔助下,，可以更加輕松的看到算法內(nèi)部的執(zhí)行過程。并且將算法轉(zhuǎn)換為可視化,，也不是很復(fù)雜,，只要按照標(biāo)準(zhǔn)編寫即可。
• 如果你也是一個愛做算法題的小白或者大牛,，也歡迎你加入我們的算法可視化中,，讓我們一起開始算法之旅：https://github.com/niubility-algorithm