寫在前面

最近經(jīng)常覺得自己越來越笨弦撩，一些很簡單的問題愣是想不出來力奋。今天去leetcode上做了幾道題驼修，面對上學(xué)時不止一次刷過的題目竟然有的連最笨的方法都想不出來。感覺還是要經(jīng)常用用腦子酥艳，不然真的會生銹。爬骤。充石。
算法對我目前的工作確實(shí)用不到，而且一些基礎(chǔ)常用的基本各個語言都有實(shí)現(xiàn)霞玄，專業(yè)算法更是各種現(xiàn)成的工具包赫冬。但真遇到問題時就算用別人的方法，自己起碼也要做到理解到位吧溃列。所以貴在堅(jiān)持積累劲厌，從基礎(chǔ)拾起??。

目的

解題不是目的听隐，重要的是通過做一道題目幫助自己get到哪些東西补鼻。我總結(jié)了以下幾點(diǎn)：

• 數(shù)據(jù)結(jié)構(gòu)。 定義合理的數(shù)據(jù)結(jié)構(gòu)很重要雅任。比如今天下面遇到的問題無非都是哈希表的使用风范、雙指針、數(shù)組的奇偶等沪么。對復(fù)雜的問題這點(diǎn)就更為明顯硼婿。
• 時間復(fù)雜度。 有時會發(fā)現(xiàn)一個笨方法也能通過禽车，但不能做完拉倒寇漫，想想問題理論上最優(yōu)的時間復(fù)雜度是多少，自己有沒更優(yōu)的方法殉摔。之后再去查閱其他人的解答州胳，理解消化。
• 知識點(diǎn)逸月。 畢業(yè)后還給老師的知識栓撞，有些很基礎(chǔ)的自以為早學(xué)透的東西，真正自己動手去寫發(fā)現(xiàn)還是有很多地方?jīng)]理解到位碗硬、沒掌握好的瓤湘。
• 代碼風(fēng)格。 有時候業(yè)務(wù)邏輯寫多了恩尾，明明有更簡潔還易讀的方式卻還是寫一堆冗長的代碼弛说，在閱讀別人代碼時多思考。

1.兩數(shù)之和

給定一個整數(shù)數(shù)組和一個目標(biāo)值特笋，找出數(shù)組中和為目標(biāo)值的兩個數(shù)剃浇。你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用猎物。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

這個我是想都沒想就兩層遍歷提交通過虎囚，也沒想過是不是有更好的方法。后來做到別的題目才想到蔫磨，這種簡單問題兩層遍歷O(n^2)是很高的時間復(fù)雜度了淘讥，寫的時候就該下意識的思考下，一般都有更優(yōu)的方法堤如。笨方法就不貼了蒲列，理論上一次遍歷就可以找到，借助哈希表O(1)的查找實(shí)現(xiàn)：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i=0,count=nums.length;i<count;i++) {
            if (map.get(target-nums[i]) != null) {
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

2.兩數(shù)相加

給定兩個非空鏈表來表示兩個非負(fù)整數(shù)搀罢。位數(shù)按照逆序方式存儲蝗岖，它們的每個節(jié)點(diǎn)只存儲單個數(shù)字。將兩數(shù)相加返回一個新的鏈表榔至。
你可以假設(shè)除了數(shù)字 0 之外抵赢，這兩個數(shù)字都不會以零開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

這道題確實(shí)在面試中被問過唧取，好在還能寫得出來铅鲤，主要是注意細(xì)節(jié)：兩數(shù)不等長、后面的進(jìn)位等枫弟，問題在于之前說過的代碼太過冗長邢享，我當(dāng)時這么寫的：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode p1=l1,p2=l2,pr=result;
        int sum=0,carry=0;

        while(p1!=null && p2!=null){
            sum = (p1.val+p2.val+carry)%10;
            carry = (p1.val+p2.val+carry)/10;

            pr.next = new ListNode(sum);
            pr = pr.next;
            p1 = p1.next;
            p2 = p2.next;
        }

        while (p1!=null){
            sum = (p1.val+carry)%10;
            carry = (p1.val+carry)/10;

            pr.next = new ListNode(sum);
            pr = pr.next;
            p1 = p1.next;
        }

        while (p2!=null){
            sum = (p2.val+carry)%10;
            carry = (p2.val+carry)/10;

            pr.next = new ListNode(sum);
            pr = pr.next;
            p2 = p2.next;
        }

        if (carry != 0)
            pr.next = new ListNode(carry);

        return result.next;
    }
}

思路還算清楚，但這代碼著實(shí)看著不舒服淡诗。對比找了網(wǎng)上的解答來看骇塘，其實(shí)這個結(jié)果鏈表往前加的來源就三個：兩個加數(shù)和進(jìn)位，只要存在其中一個循環(huán)就繼續(xù)韩容，這樣寫起來就簡潔多了：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode p1=l1,p2=l2,pr=result;
        int carry=0;
        while(p1 != null || p2 != null || carry != 0){
            int sum = ((p1 == null) ? 0 : p1.val) + ((p2 == null) ? 0 : p2.val) + carry;
            carry = sum/10;
            pr.next = new ListNode(sum%10);
            pr = pr.next;
            if(p1 != null) p1 = p1.next;
            if(p2 != null) p2 = p2.next;
        }
        return result.next;
    }
}

3.無重復(fù)字符的最長子串

給定一個字符串绪爸，找出不含有重復(fù)字符的最長子串的長度。
示例：給定 "abcabcbb" 宙攻，沒有重復(fù)字符的最長子串是 "abc" 奠货，那么長度就是3。
給定 "bbbbb" 座掘，最長的子串就是 "b" 递惋，長度是1。
給定 "pwwkew" 溢陪，最長子串是 "wke" 萍虽，長度是3。請注意答案必須是一個子串形真，"pwke" 是 子序列 而不是子串杉编。

這個做的時候沒想出來超全，但總的寫一下在去查答案。邓馒。最笨的窮舉總是可以試試的嘶朱，兩層遍歷以每個字符為起點(diǎn)，還得通過string的contains方法做判斷光酣，竟然還超過了4%的java提交記錄疏遏。。救军。只能說這個網(wǎng)站對運(yùn)行時間測的不準(zhǔn)吧财异，算上contains方法這個時間復(fù)雜度高得嚇人了，肯定是超時的唱遭。
寫的過程竟還錯了好多細(xì)節(jié)戳寸，瞬間感覺自己菜的一匹：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        if(length == 0 || length == 1) return length;
        int result = 1;
        for(int i=0; i<= length-result ;i++){
            // 這里一開始寫的 for(int j=i+result ...) ，以當(dāng)前result為基準(zhǔn)查找拷泽，有
            // 點(diǎn)想當(dāng)然了庆揩，中間也可能有重復(fù)的。
            for(int j=i+1;j<length;j++)  
            {
                if(!s.substring(i,j).contains(s.substring(j,j+1)))
                {
                    if (result < j-i+1) result = j-i+1;
                }
                else
                {
                    break;
                }

            }
        }
        return result;
    }
}

這么垃圾的方法還一再運(yùn)行不過跌穗，確實(shí)有點(diǎn)受打擊订晌。但仔細(xì)想想，這道題在學(xué)校校招那會肯定做過不止一次蚌吸，和第一題一樣锈拨，利用哈希表存下標(biāo)，只是一時沒想起來（這么安慰下自己吧）
思路就是兩個指針羹唠，一個用來遍歷奕枢，一個記錄當(dāng)前字符前一次出現(xiàn)的下標(biāo)pre，這個下標(biāo)信息可以用一個HashMap記錄佩微，只要當(dāng)前字符在pre之后出現(xiàn)過缝彬，就將pre移動到出現(xiàn)的位置之后(因?yàn)檫@之間的子串都包含當(dāng)前字符的重復(fù)，而子串不會是最長的)：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int result = 0;
        HashMap<Character,Integer> preIdx = new HashMap<>();
        for (int i=0, pre=0, length=s.length();i<length;i++) {
            Integer p = preIdx.get(s.charAt(i));
            if (p != null && p >= pre){
                pre = p + 1;
            }
            result = Math.max(result,i-pre+1);
            preIdx.put(s.charAt(i),i);
        }
        return result;
    }
}

總結(jié)一下：

• 1和3都沒有一次找到最優(yōu)方案哺眯，這兩個類似谷浅，都是用map存儲下標(biāo)，因?yàn)椴檎移饋韽?fù)雜度為O(1)奶卓；
• 2是代碼冗余一疯，遇到問題不要上來就寫循環(huán)，先理清楚思路夺姑，想想出入口墩邀；
• 不要想當(dāng)然，確保正確性盏浙，細(xì)節(jié)問題眉睹、臨界點(diǎn)等要先想好荔茬；
• 遇到看都看不懂的，說明有模糊的知識點(diǎn)需要好好梳理了