iT邦幫忙

10

[演算法][JavaScript]演算法挑戰系列(1)-Longest Substring Without Repeating Characters

Hello!大家好,最近在做Google Code Jam的過程中,不小心迷上了解題的過程XD,所以我又分心去多找了一些關於解演算法的題目網站,於是登愣「就被我找到啦!」如果各位對邏輯思考,然後喜歡燃燒大腦的都可以試著解一些題目,他是有難易度的,所以可以從簡單先下手,而且他也有一些關於資料庫SQL的題目,也滿有難度的(對我而言啦XD),所以我打算把這個過程開一個系列,讓我記錄下每次解題的過程,然後我PO上來的難度都會選在中以上,簡單的我就不在PO上來獻醜了,那今天就開始第一篇這個系列吧!

題目名稱:Longest Substring Without Repeating Characters
難易度:中
題目內容:輸入一個字串,然後找出這個字串中最長,而且又沒有重複的子字串,並回傳他的長度。
例如:
1.輸入abcabcbb,該字串中最長又沒有重複字母的子字串就是abc,然後回傳他的長度,答案是3。
2.輸入bbbbbb,該字串中最長又沒有重複字母的子字串就是b,然後回傳他的長度,答案是1。
3.輸入pwwkew,該字串中最長又沒有重複字母的子字串就是wke,然後回傳他的長度,答案是3。

那以下開始動工:

//這個function名稱是網站預設的
var lengthOfLongestSubstring = function(s) {
    //宣告一個陣列,用來裝不重複的字元。
    let arr = [];
    //宣告要回傳的變數,用來裝不重複的字元的字串長度
    let maxLen = 0;
    
    //首先跑迴圈,把每個字元都看過
    for(let i=0; i<s.length; i++){
    
        //先比較現在這個字母有沒有在陣列中
        if(arr.indexOf(s[i]) !== -1){
            /*如果有的話,因為重複了,所以把從該位置之前的字元都從陣列中拿掉
            陣列中保持著在該字串中連續,且不重複的字元*/
            arr = arr.slice(arr.indexOf(s[i])+1);
        };
        
        //經過判斷後把目前這個字元加進陣列中
        arr.push(s[i]);
        
        //如果目前陣列的長度,大於目前要回傳的最大長度,就把要回傳的最大長度更新
        if(maxLen < arr.length){
            maxLen = arr.length;
        }
    };
    
    //最後回傳
    return maxLen;
};

當然因為只是解題方式,所以我的絕對不會是唯一,而且最佳的解,如果大家看到我的程式碼有任何想法都歡迎告訴我,或是也可以交流看看有沒有更好,而且我沒有想到的方式,畢竟演算法好玩的地方在大家的想法不同,程式碼也會長的不一樣XD,好的那第一篇分享解題就到這裡,謝謝大家!


2 則留言

1
fysh711426
iT邦研究生 3 級 ‧ 2018-05-06 10:12:00

這題和 Code Jam 第一題一樣,也是貪婪法邏輯,
在跑迴圈時,每次都保持陣列內字串不重複,並記錄陣列的最大值,
迴圈跑完後 maxLen 就是最大子字串長度。

大大要開系列文了,期待 SQL 的題目,哈哈哈
/images/emoticon/emoticon42.gif

看更多先前的回應...收起先前的回應...
小魚 iT邦大師 1 級‧ 2018-05-06 10:51:47 檢舉

其實它同時也記了最大的子字串,
只不過沒有回傳而已。

哈哈,因為之前都沒有認真和演算法相處(應該可以說根本沒有XD),
所以我對一些解題的方法超級陌生,
像我第一次看見貪婪法就是在大大的文章中XD

ㄛ但是我不確定這一系列文能不能算技術文章,哈哈哈

fysh711426 iT邦研究生 3 級‧ 2018-05-06 20:40:41 檢舉

小魚大大
應該沒有紀錄最大子字串,只記錄了最大長度,
arr 有可能會變短。

fysh711426 iT邦研究生 3 級‧ 2018-05-06 20:51:20 檢舉

神Q超人大大
分享解題心得很不錯阿,哈哈哈

可能工作是寫 Web 的關係,
離開學校後就很少有機會接觸演算法了呢
/images/emoticon/emoticon02.gif

小魚 iT邦大師 1 級‧ 2018-05-06 21:12:34 檢舉

好像是這樣沒錯,
之前是我誤會了,
不過只要多一個變數就可以記錄了。

小魚對,哈哈,但是他只要遇到重複的字就會截掉前面的子字串了,所以跑到最後陣列裡也不一定是最長的子字串,不過就像大大說的,在一個變數就可以搞定XD
fysh711426哈哈哈,我也是寫web啊,只是因為是在寫系統,所以可能還是有一些邏輯要處理吧。

小魚 iT邦大師 1 級‧ 2018-05-06 21:18:19 檢舉

話說,
現在在業界除非你不用套件,
用C++或Java慢慢寫,
要不然演算法人家都幫你寫好了,
除非是要寫那種比較專業需要自己寫演算法的,
現在很少人在寫演算法了,
只有學校或做研究的有在寫而已。

而且為了省開發的時間,
基本上不大會去寫演算法了。

fysh711426 iT邦研究生 3 級‧ 2018-05-06 21:43:21 檢舉

對阿,大大說到重點,為了省開發的時間
很多時候為了要快點完成專案,效能架構什麼都是其次了,
只要最後程式能跑就好,覺得蠻可惜的。

ㄛ這是真的欸,現在太多太方便的套件,
導致大家再學的都是套件的使用方式,反而不是語言本身了,
有時候在讀JS朋友也會說讀那麼深幹嘛/images/emoticon/emoticon46.gif

1
f51486388
iT邦見習生 0 級 ‧ 2018-05-17 22:10:07

耶耶!學到了 我會一天比一天強 總有一天會超越你的 神Q超人大師!

哈哈哈,我還不是大師/images/emoticon/emoticon06.gif,不過我們可以一起變強XD

我要留言

立即登入留言