工作太忙沒(méi)有時(shí)間刷算法題，面試的時(shí)候好心虛。這里雙手奉上40道LeetCode上經(jīng)典面試算法題，整理的內(nèi)容有點(diǎn)長(zhǎng)，建議先收藏，慢慢消化，在來(lái)年順利拿到滿(mǎn)意的offer。

1、[LeetCode] 兩數(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]

var twoSum = function(nums, target) {var len = nums.length;for(var i=0; i<len; i++){for(var j=i+1; j<len;j++){if(nums[i] + nums[j] == target){return [i, j];}}  }return [];
}; 

2、[LeetCode]路徑總和

給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，判斷該樹(shù)中是否存在根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

var hasPathSum = function(root, sum) {if (!root) return false;var cur = sum-root.val;if (!root.left&&!root.right&&cur==0) return true;if (!root.left) return hasPathSum(root.right, cur);if (!root.right) return hasPathSum(root.left, cur);return hasPathSum(root.left, cur)||hasPathSum(root.right, cur);};

3、[LeetCode]二叉樹(shù)的最小深度

給定一個(gè)二叉樹(shù)，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

var minDepth = function(root) {if (!root) return 0;if (!root.left&&!root.right) return 1;if (!root.left) return minDepth(root.right)+1;if (!root.right) return minDepth(root.left)+1;return Math.min(minDepth(root.left), minDepth(root.right))+1;};

4、[LeetCode] 二進(jìn)制求和

給定兩個(gè)二進(jìn)制字符串，返回他們的和（用二進(jìn)制表示）。

    var addBinary = function(a, b) {var res = [];var num = 0;var addOne = 0;//是否進(jìn)位//字符串對(duì)其while(a.length < b.length){a = 0 + a;}while(b.length < a.length){b = 0 + b;}for (var i=a.length-1; i>=0; i--){num = parseInt(a[i])+parseInt(b[i])+addOne;if(num>=2){res[i] = num-2;addOne = 1;}else{res[i] = num;addOne = 0;}}if(addOne>0){res.unshift(1);}return res.join('');};

5、[LeetCode]x的平方根

實(shí)現(xiàn) int sqrt(int x) 函數(shù)。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。
由于返回類(lèi)型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。

var mySqrt = function(x) {var i = 1;while(x>=i*i){i++;}return i-1;}; //方法2 ES6var mySqrt = function(x) {return Math.floor(x ** 0.5);//向下取整 x^0.5}; 

6、[LeetCode] 加一

給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字。

var plusOne = function(digits) {var len = digits.length;for (var i=len-1; i>=0; i--){if(digits[i]<9){digits[i]++;return digits;}digits[i] = 0;}digits.unshift(1);return digits;};

7、[LeetCode] 最后一個(gè)單詞的長(zhǎng)度

給定一個(gè)僅包含大小寫(xiě)字母和空格 ’ ’ 的字符串，返回其最后一個(gè)單詞的長(zhǎng)度。

var lengthOfLastWord = function(s) {s = s.trim();var arr = s.split(' ');return arr[arr.length-1].length;};

8、[LeetCode] 最大子序和

給定一個(gè)整數(shù)數(shù)組 nums，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）返回其最大和。參考視頻：傳送門(mén)

var maxSubArray = function(nums) {var max = nums[0];var sum = 0;for (let num of nums){if (sum < 0){sum = 0;}sum += num;max = Math.max(sum, max);}return max;};

9、[LeetCode]報(bào)數(shù)

報(bào)數(shù)序列是一個(gè)整數(shù)序列，按照其中的整數(shù)的順序進(jìn)行報(bào)數(shù)，得到下一個(gè)數(shù)。

var countAndSay = function(n) {var resultStr = '1';for (var i=1; i<n; i++){var repeatCount = 1;var str = '';for (var j=0; j<resultStr.length; j++) {if (resultStr[j]===resultStr[j+1]){repeatCount++;} else {str += repeatCount + resultStr[j];repeatCount = 1;}}resultStr = str;}return resultStr;}; 

10、[LeetCode]楊輝三角

給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角的前 numRows 行。
在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。
示例:
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

var generate = function(numRows) {var res = [];for (var i=0; i<numRows; i++){var arr = [1];for (var j=1; j<i; j++){arr[j] = res[i-1][j]+res[i-1][j-1];}arr[i] = 1;res.push(arr);}return res;};

11、[LeetCode]楊輝三角 II

給定一個(gè)非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。

var getRow = function(rowIndex) {var res = [1];if (rowIndex==0) return [1];if (rowIndex==1) {return [1,1];}var arr = getRow(rowIndex-1);for (var i=1; i<rowIndex; i++){res[i] = arr[i]+arr[i-1];}res.push(1);return res;};

12、[LeetCode]相交鏈表

編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。
例如

思路：
遍歷 A 表，指針 l1 等于尾部 c3 時(shí)，讓它指向 B 表的 b1
遍歷 B 表，指針 l2 等于尾部 c3 時(shí)，讓它指向 A 表的 a1
如果兩鏈表有交點(diǎn)，則會(huì)同時(shí)指向 c1，因?yàn)?#xff1a;
a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1 與
b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1 相等。

var getIntersectionNode = function(headA, headB) {if (!headA || !headB) return null;if (headA == headB) return headA;var l1 = headA;var l2 = headB;var count = 0;while(l1 != l2 && count < 3){if (!l1.next || !l2.next) count++;l1 = l1.next ? l1.next : headB;l2 = l2.next ? l2.next : headA;}return l1==l2 ? l1 : null;
};

13、[LeetCode]打家劫舍

你是一個(gè)專(zhuān)業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下，能夠偷竊到的最高金額。
思路：
偷取第 i 家時(shí)，有兩種選擇：
偷取第 i 家，此時(shí)金額為：res[i] = res[i-2]+nums[i];
不偷，此時(shí)金額為：res[i] = res[i-1];
所以最高金額為兩者取較大值。

var rob = function(nums) {var len = nums.length;if (len < 2) return nums[len-1]?nums[len-1]:0;var res = [nums[0], Math.max(nums[0], nums[1])];for (let i=2; i<len; i++){res[i] = Math.max(res[i-1], nums[i]+res[i-2]);}return res[len-1];
};

14、[LeetCode]最小棧

設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
push(x) – 將元素 x 推入棧中。
pop() – 刪除棧頂?shù)脑亍?br /> top() – 獲取棧頂元素。
getMin() – 檢索棧中的最小元素。

var MinStack = function() {this.stack = []};MinStack.prototype.push = function(x) {this.stack[this.stack.length] = x;  };MinStack.prototype.pop = function() {this.stack.length--;};MinStack.prototype.top = function() {return this.stack[this.stack.length-1];};MinStack.prototype.getMin = function() {var min = this.stack[0];var len = this.stack.length;for (var i=1; i<len; i++){if (this.stack[i]<min){min = this.stack[i];}}return min;};

15、[LeetCode]只出現(xiàn)一次的數(shù)字

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

var singleNumber = function(nums) {nums.sort(function(a, b){return a-b;});var len = nums.length;for (var i=0; i<len; i=i+2){if(nums[i]!=nums[i+1]){return nums[i];}}};

16、[LeetCode]驗(yàn)證回文串

給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫(xiě)。
說(shuō)明：本題中，我們將空字符串定義為有效的回文串。

var isPalindrome = function(s) {var str1 = s.toUpperCase().replace(/\W/g,'');var str2 = str1.split('').reverse().join('');return str1==str2;};

17、[LeetCode]買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。

var maxProfit = function(prices) {var max = 0;var len = prices.length;for (var i=0; i<len-1; i++){if (prices[i+1]>prices[i]){max += prices[i+1]-prices[i];}}return max;};

18、[LeetCode]移除元素

給定一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素，返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

var removeElement = function(nums, val) {var i = 0;var len = nums.length;for (var j = 0; j<len; j++){if(nums[j]!==val){nums[i] = nums[j]i++;}}return i;};//方法2var removeElement = function(nums, val) {var i = 0;var len = nums.length;while (i < len){if (nums[i] == val) {nums[i] = nums[len-1];len--;} else {i++;}}return len;};

19、[LeetCode]平衡二叉樹(shù)

給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
本題中，一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。

var isBalanced = function(root) {if (!root) return true;if (Math.abs(depth(root.left)-depth(root.right))>1) return false; return isBalanced(root.left) && isBalanced(root.right);  function depth(node){if (!node) return 0;var left = depth(node.left);var right = depth(node.right);return Math.max(left, right)+1;}};

20、[LeetCode]刪除排序數(shù)組中的重復(fù)項(xiàng)

給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。

var removeDuplicates = function(nums) {var i = 0;var len = nums.length;for (var j=1; j<len; j++){if (nums[i] !== nums[j]){i++;nums[i] = nums[j]}}return i+1;};

21、[LeetCode]合并兩個(gè)有序鏈表

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

var mergeTwoLists = function (l1, l2) {var lHead = new ListNode(0);var lCur = lHead;while (l1 !== null && l2 !== null) {if(l1.val < l2.val) {lCur.next = l1;lCur = lCur.next;l1 = l1.next;} else {lCur.next = l2;lCur = lCur.next;l2 = l2.next; }}if (l1 === null) {lCur.next = l2;} if (l2 === null) {lCur.next = l1;}return lHead.next;};

22、[LeetCode]有效的括號(hào)

給定一個(gè)只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判斷字符串是否有效。
有效字符串需滿(mǎn)足：
左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。

var isValid = function(s) {var stack = [];var len = s.length;for (var i=0; i<len; i++){var char = s[i];var stackLen = stack.length;if(stackLen==0) {stack.push(char); }else{if(isMatch(stack[stackLen-1],char)){stack.pop();}else{stack.push(char);}}     }return stack.length==0;function isMatch(char1, char2){if (char1=='(' && char2==')'||char1=='{' && char2=='}'||char1=='[' && char2==']'){return true;}return false;}};

23、[LeetCode]最長(zhǎng)公共前綴

編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。如果不存在公共前綴，返回空字符串 “”。

var longestCommonPrefix = function(strs) {if (!strs.length) return '';var str1 = strs[0];var res = '';var str1Len = str1.length;var strsLen = strs.length;for (var i=0; i<str1Len; i++) {for (var j=1; j<strsLen; j++) {if (str1[i] !== strs[j][i]) {return res;}}res += str1[i];}return res;}; 

24、[LeetCode]羅馬數(shù)字轉(zhuǎn)整數(shù)

羅馬數(shù)字包含以下七種字符: I， V， X， L，C，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫(xiě)做 II ，即為兩個(gè)并列的 1。12 寫(xiě)做 XII ，即為 X + II 。 27 寫(xiě)做 XXVII, 即為 XX + V + II 。

var romanToInt = function(s) {var romanObj = {'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000};var num = 0;var len = s.length;for (var i=0; i<len-1; i++) {var curNum = romanObj[s.charAt(i)];var rightNum = romanObj[s.charAt(i+1)];num += curNum>=rightNum?curNum:-curNum;}num += romanObj[s.charAt(i)]return num;};

25、[LeetCode]回文數(shù)

判斷一個(gè)整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。

var isPalindrome = function(x) {var num = x.toString();return x == num.split('').reverse().join('');};  //方法2 找到中間位置，然后兩邊對(duì)比    var isPalindrome = function(x) {var str = x.toString();var len = str.length;var halfLen = (len-1)/2;for (var i=0; i<halfLen; i++){if(str.charAt(i)!==str.charAt(len-1-i)){return false;}}return true;}; 

26、[LeetCode]反轉(zhuǎn)整數(shù)

給定一個(gè) 32 位有符號(hào)整數(shù)，將整數(shù)中的數(shù)字進(jìn)行反轉(zhuǎn)。

var reverse = function(x) {var num = x.toString().split('').reverse();var res = parseInt(num.join(''));if(res>2**31) return 0;return x>0?res:-res;};

27、[LeetCode]實(shí)現(xiàn) strStr() 函數(shù)

給定一個(gè) haystack 字符串和一個(gè) needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開(kāi)始)。如果不存在，則返回 -1。

var strStr = function(haystack, needle) {if (needle=='') return 0;var len2 = needle.length;var len = haystack.length - len2;for (var i = 0; i<=len; i++) {if (haystack.substring(i, i+len2) == needle) {return i;}}return -1;};//超簡(jiǎn)做法var strStr = function(haystack, needle) {return haystack.indexOf(needle);};

28、[LeetCode]搜索插入位置

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

var searchInsert = function(nums, target) {var len = nums.length;for(var i=0; i<len; i++){if(target<=nums[i]){return i;}}return len;}; 

29、[LeetCode]將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)

將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹(shù)。
本題中，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。

var sortedArrayToBST = function(nums) {var len = nums.length;if(!len) return null;if(len===1) return new TreeNode(nums[0]);var mid = parseInt(len/2);var root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(nums.slice(0, mid));root.right = sortedArrayToBST(nums.slice(mid+1));return root;};

30、[LeetCode]二叉樹(shù)的層次遍歷 II

給定一個(gè)二叉樹(shù)，返回其節(jié)點(diǎn)值自底向上的層次遍歷。 （即按從葉子節(jié)點(diǎn)所在層到根節(jié)點(diǎn)所在的層，逐層從左向右遍歷）

    var levelOrderBottom = function(root) {var queue = [];var result = [];if(root) queue.push(root);while(queue.length){var arr = [];var len = queue.lengthfor(var i=0; i<len; i++){var curNode = queue.shift();arr.push(curNode.val);if(curNode.left) queue.push(curNode.left);if(curNode.right) queue.push(curNode.right);}result.unshift(arr);}return result;};

31、[LeetCode]二叉樹(shù)的最大深度

給定一個(gè)二叉樹(shù)，找出其最大深度。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

var maxDepth = function(root) {if(!root) return 0;var left_depth = maxDepth(root.left);var right_depth = maxDepth(root.right);return Math.max(left_depth, right_depth)+1;};

32、[LeetCode]爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
思路：
f(1) : 1
f(2) : 11 , 2
f(3) : 12, 111, 21
f(4) : 121, 1111, 211, 112, 22
f(n) = f(n-1) + f(n-2)

var climbStairs = function(n) {let a = b = 1;for (let i = 0; i < n; i++) {[a, b] = [b, a + b];//ES6的遞歸寫(xiě)法}return a;};

33、[LeetCode]合并兩個(gè)有序數(shù)組

給定兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個(gè)有序數(shù)組。
說(shuō)明:
初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來(lái)保存 nums2 中的元素。
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]

var merge = function(nums1, m, nums2, n) {for (let i=0; i<n; i++){nums1[m+i] = nums2[i]}nums1.sort(function(a, b){return a-b;})};

34、[LeetCode]相同的樹(shù)

給定兩個(gè)二叉樹(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)檢驗(yàn)它們是否相同。
如果兩個(gè)樹(shù)在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

var isSameTree = function(p, q) {if (p===null && q===null) return true;if (p===null || q===null) return false;if (p.val != q.val) return false;return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);};

35、[LeetCode]對(duì)稱(chēng)二叉樹(shù)

給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱(chēng)的。

var isSymmetric = function(root) {if (!root) return true;var leftAndRight = function(left, right){if (!left && !right) return true;if (!left || !right) return false;if (left.val != right.val) return false;return leftAndRight(left.left, right.right) && leftAndRight(left.right, right.left);}return leftAndRight(root.left, root.right);};

36、[LeetCode]刪除排序鏈表中的重復(fù)元素

刪除排序鏈表中的重復(fù)元素

var deleteDuplicates = function(head) {var l = head;if(l==null) return nullwhile(l.next){if(l.val == l.next.val){l.next = l.next.next;}else{l = l.next;}}return head;};

37、[LeetCode]Excel表列名稱(chēng)

給定一個(gè)正整數(shù)，返回它在 Excel 表中相對(duì)應(yīng)的列名稱(chēng)。
例如，
1 -> A
2 -> B
3 -> C
…
26 -> Z
27 -> AA
28 -> AB
…

var convertToTitle = function(n) {var res='';while(n>0){var a = parseInt((n-1)%26);n = parseInt((n-1)/26);res = String.fromCharCode(a+65) + res;}return res;
};