摘要：題目全部用做的，基本上每天一題的節(jié)奏。題目這里記錄自己對一些題目的思路和想法數(shù)字回文，說不能用額外的空間一下子懵逼了，第一概念就是換成字符串比較，但是感覺這樣子做就沒有意義了。找出任意兩條線段與軸組成的木桶，可以盛水最大的值。

原文地址

無意間發(fā)現(xiàn) LeetCode 這個網(wǎng)站，一下子就陷進去了，大學(xué)時候看舍友參加 acm 一天到晚刷題，對算法總有點特殊的情懷。本以為我永遠是接觸不到這個了，沒想到 leetcode 卻讓我感覺到 Accepted 這個單詞的特殊魅力。

首先自己并不是為了找工作去刷題的，純粹享受做題的過程和ac的快感。題目全部用 JavaScript 做的，基本上每天一題的節(jié)奏。開始總是想著怎么把答案解出來就好，經(jīng)常 TLE ,感覺一路做下來自己慢慢會考慮復(fù)雜度，邏輯嚴(yán)謹(jǐn)性也在逐步加強，對特殊值的考慮越來越多，相比于算法能力的提升我更欣喜看到自己邏輯嚴(yán)謹(jǐn)性加強，感覺這對自己后面的道路幫助會很大。

這里記錄自己對一些題目的思路和想法

`

1         =>   true;
21         =>   false;
303        =>   true;

`

數(shù)字回文，說不能用額外的空間一下子懵逼了，第一概念就是換成字符串比較，但是感覺這樣子做就沒有意義了。看了別人思路發(fā)現(xiàn)給的數(shù)字每次取 10 的余數(shù)拼起來正好是數(shù)字倒過來寫。如果只取出一半，原數(shù)字也舍棄一半 正好就是回文的兩個內(nèi)容。有了思路就好做了判斷下特殊條件，比較最后兩個數(shù)字就可以了，如果是奇數(shù)位數(shù)字就減掉中間一位再比較。

    var max = Math.pow(2,31) - 1
    var isPalindrome = function(x) {
        if (x < 0 || x > max || (x != 0 && x % 10 == 0)) return false
        if (x < 10) return true
        var num = 0
        while(x > num) {
            num = num * 10 + x % 10
            x = Math.floor(x / 10)
        }
        return num == x || (x != 0 && Math.floor(num / 10) == x)
    };
    

`

給定一個數(shù)組，想象成一個二位坐標(biāo)系，數(shù)組中每一個元素 a[i] => n 就是坐標(biāo)系上的一條線段[ (i,0) => (i,x) ]。找出任意兩條線段與 x 軸組成的木桶，可以盛水最大的值。

`

看到題目想了一下就想著兩層循環(huán)去計算，果然就超時了，看了看別人的思路，開始就算出0到最后一個線段組成的木桶的面積，然后找出線段比較短的一條向中間靠攏，如果下一條線段比當(dāng)前線段還短就忽略，反之就繼續(xù)循環(huán)計算。想了想這樣做也是合理的如果下一條線段比當(dāng)前的還短那組成的面積肯定比較小。有了思路就好做了

    var maxArea = function(height) {
        let i = 0, l = height.length -1, res = 0
            
        while(i < l) {
            var h = Math.min(height[i],height[l])
            res = Math.max(res, (l-i) * h)
            if(height[i] < height[l]) {
                while(height[i] <= h && i < l){i++}
            } else {
                while(h >= height[l] && i < l){l--}
            }
        }
        return res
    }
    

`

實現(xiàn)正則，
"." Matches any single character.
"*" Matches zero or more of the preceding element.
isMatch("aa","a") → false 
isMatch("ab", ".*") → true     
isMatch("aab", "c*a*b") → true

`
剛開始看到這題目還是比較懵的，感覺要判斷的好多，后面從遞歸判斷做就有思路了，從正則表達式入手，先判斷第二位是不是 * ，如果不是就判斷第一位然后截取一位遞歸，如果是就先去除正則前兩位遞歸，不行再判斷第一個是不是相等然后循環(huán)遞歸

    var isMatch = function(s, p) {
        if(p[0] === undefined) return s[0] === undefined
        if (p[1] != "*") {
           if (s[0] === p[0] || (p[0] === "." && s[0] !== undefined)) 
               return isMatch(s.substr(1), p.substr(1))
           else 
               return false
        } else {
            if (isMatch(s, p.substr(2)))return true
            let index = 0
            while(index <= s.length && (s[index] === p[0] || p[0] === ".")){
                if(isMatch(s.substr(++index), p.substr(2))) return true
            }
            return false
        }
    }
    

看到一個面試題，JSON.stringify 是 javascript 的一個方法返回一個json格式的字符串，效果如下

    const obj = {a:1, b:2}
    JSON.stringify(obj) // => "{"a":1,"b":2}"
   

當(dāng)要轉(zhuǎn)化的對象有“環(huán)”存在時（子節(jié)點屬性賦值了父節(jié)點的引用），為了避免死循環(huán)，JSON.stringify 會拋出異常，例如：

    var a = [1]
    a.push(a)
    JSON.stringify(a) // => Uncaught TypeError: Converting circular structure to JSON

寫一個函數(shù)判斷參數(shù)是否包含 環(huán),自己想到的是用 map 對象把是對象的值做為鍵存儲值，然后判斷值是否存在來判斷是否回環(huán)， 要注意每一次要用一個新的 map 對象，避免同級別相互引用判斷錯誤的情況

    let isCircular = (o) => {
        var flag = false
        const func = (obj, map = new Map()) => {
            map.set(obj, true)
            Object.values(obj).forEach(d=> {
                if (flag) return
                if (typeof d == "object") {
                    if (map.get(d)) {
                        flag = true
                        return
                    } else {
                        let newmap = new Map(map)
                        func(d, newmap)
                    }
                }
            })
        }
        func(o)
        return flag
    }

給一個數(shù)字，寫一個函數(shù)根據(jù)數(shù)字生成所有形式良好的括號組合
2 => ["()()", "(())"]
3 => 
    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

想了一下有一個思路，就是根據(jù) () 里面的包含幾個子 () 來得出所有情況。 比如給出的數(shù)字是5, 那么循環(huán)到5，第n 就有 ( [func(n)的結(jié)果] ) * func(4-n)的結(jié)果 。

一直想著以一個優(yōu)雅的方式處理邊界的問題，但是想半天都沒結(jié)果，只能寫的丑陋點了。

    var generateParenthesis = function(n) {
        if(n == 0) return []
        if(n == 1) return ["()"]
        let arr = []
        for(let i = 0; i < n; i++) {
            if( i == 0) {
                arr = arr.concat(generateParenthesis([n-1]).map(d => "()" + d ))
            } else if (i == n-1){
                arr = arr.concat(generateParenthesis([n-1]).map(d => "(" + d + ")"))
            } else {
                generateParenthesis(i).forEach(d => {
                    let eachres = "(" + d +")"
                    generateParenthesis(n- i -1).forEach(c => {
                        arr.push(eachres + c)
                    })
                })
            }
        }
        return arr
    };