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

一、前言

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

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

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

效果展示：

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

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

二、題目：《無(wú)重復(fù)字符的最長(zhǎng)子串》

給定一個(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è)子序列，不是子串。

java

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

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

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

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

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)計(jì)算是否碰撞到相同的元素，并處理開始指針的位置。
• 最后輸出最長(zhǎng)子串的長(zhǎng)度。

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í)定義一個(gè)新的數(shù)組用于存放地址。int[] exist = new int[127]，元素作為地址，位置作為值。
• 只有在碰撞時(shí)候才計(jì)算兩個(gè)指針間的長(zhǎng)度，其他時(shí)間不計(jì)算。
• 最后輸出最長(zhǎng)子串的長(zhǎng)度。

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;
}

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

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

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

五、總結(jié)

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