leetcode 一些演算法題目記錄

leetcode 一些演算法題目記錄

前言

原文地址

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

個人

首先自己並不是為了找工作去刷題的,純粹享受做題的過程和ac的快感。題目全部用 JavaScript

`

數字迴文,說不能用額外的空間一下子懵逼了,第一概念就是換成字串比較,但是感覺這樣子做就沒有意義了。看了別人思路發現給的數字每次取 10 的餘數拼起來正好是數字倒過來寫。如果只取出一半,原數字也捨棄一半 正好就是迴文的兩個內容。有了思路就好做了判斷下特殊條件,比較最後兩個數字就可以了,如果是奇數位數字就減掉中間一位再比較。


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

Container With Most Water

`

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

`

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


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
}

Regular Expression Matching

`

實現正則,
'.' 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

`
剛開始看到這題目還是比較懵的,感覺要判斷的好多,後面從遞迴判斷做就有思路了,從正規表示式入手,先判斷第二位是不是 * ,如果不是就判斷第一位然後擷取一位遞迴,如果是就先去除正則前兩位遞迴,不行再判斷第一個是不是相等然後迴圈遞迴


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

Is Circular

看到一個面試題,JSON.stringify 是 javascript

當要轉化的物件有“環”存在時(子節點屬性賦值了父節點的引用),為了避免死迴圈,JSON.stringify 會丟擲異常,例如:

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

寫一個函式判斷引數是否包含

Submission Details

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

想了一下有一個思路,就是根據 ()