寫在前面

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

目的

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

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

1.兩數(shù)之和

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

這個(gè)我是想都沒想就兩層遍歷提交通過，也沒想過是不是有更好的方法。后來(lái)做到別的題目才想到，這種簡(jiǎn)單問題兩層遍歷O(n^2)是很高的時(shí)間復(fù)雜度了，寫的時(shí)候就該下意識(shí)的思考下，一般都有更優(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ù)相加

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

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

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í)看著不舒服。對(duì)比找了網(wǎng)上的解答來(lái)看，其實(shí)這個(gè)結(jié)果鏈表往前加的來(lái)源就三個(gè)：兩個(gè)加數(shù)和進(jìn)位，只要存在其中一個(gè)循環(huán)就繼續(xù)，這樣寫起來(lái)就簡(jiǎn)潔多了：

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.無(wú)重復(fù)字符的最長(zhǎng)子串

給定一個(gè)字符串，找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
示例：給定 "abcabcbb" ，沒有重復(fù)字符的最長(zhǎng)子串是 "abc" ，那么長(zhǎng)度就是3。
給定 "bbbbb" ，最長(zhǎng)的子串就是 "b" ，長(zhǎng)度是1。
給定 "pwwkew" ，最長(zhǎng)子串是 "wke" ，長(zhǎng)度是3。請(qǐng)注意答案必須是一個(gè)子串，"pwke" 是 子序列 而不是子串。

這個(gè)做的時(shí)候沒想出來(lái)，但總的寫一下在去查答案。。最笨的窮舉總是可以試試的，兩層遍歷以每個(gè)字符為起點(diǎn)，還得通過string的contains方法做判斷，竟然還超過了4%的java提交記錄。。。只能說這個(gè)網(wǎng)站對(duì)運(yùn)行時(shí)間測(cè)的不準(zhǔn)吧，算上contains方法這個(gè)時(shí)間復(fù)雜度高得嚇人了，肯定是超時(shí)的。
寫的過程竟還錯(cuò)了好多細(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é)校校招那會(huì)肯定做過不止一次，和第一題一樣，利用哈希表存下標(biāo)，只是一時(shí)沒想起來(lái)（這么安慰下自己吧）
思路就是兩個(gè)指針，一個(gè)用來(lái)遍歷，一個(gè)記錄當(dāng)前字符前一次出現(xiàn)的下標(biāo)pre，這個(gè)下標(biāo)信息可以用一個(gè)HashMap記錄，只要當(dāng)前字符在pre之后出現(xiàn)過，就將pre移動(dòng)到出現(xiàn)的位置之后(因?yàn)檫@之間的子串都包含當(dāng)前字符的重復(fù)，而子串不會(huì)是最長(zhǎng)的)：

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)方案，這兩個(gè)類似，都是用map存儲(chǔ)下標(biāo)，因?yàn)椴檎移饋?lái)復(fù)雜度為O(1)；
• 2是代碼冗余，遇到問題不要上來(lái)就寫循環(huán)，先理清楚思路，想想出入口；
• 不要想當(dāng)然，確保正確性，細(xì)節(jié)問題、臨界點(diǎn)等要先想好；
• 遇到看都看不懂的，說明有模糊的知識(shí)點(diǎn)需要好好梳理了