工作太忙没有工夫刷算法题，面试的时候好心虚。这里双手奉上 40 道 LeetCode 上经典面试算法题，整顿的内容有点长，倡议先珍藏，缓缓消化，在来年顺利拿到称心的 offer。
1、[LeetCode] 两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你能够假如每个输出只对应一种答案，且同样的元素不能被反复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 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]门路总和
给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。
阐明: 叶子节点是指没有子节点的节点。
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]二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短门路上的节点数量。
阐明: 叶子节点是指没有子节点的节点。
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] 二进制求和
给定两个二进制字符串，返回他们的和（用二进制示意）。
var addBinary = function(a, b) {var res = [];
var num = 0;
var addOne = 0;// 是否进位
// 字符串对其
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 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
因为返回类型是整数，后果只保留整数的局部，小数局部将被舍去。
var mySqrt = function(x) {
var i = 1;
while(x>=i*i){i++;}
return i-1;
};
// 办法 2 ES6
var mySqrt = function(x) {return Math.floor(x ** 0.5);// 向下取整 x^0.5
};
6、[LeetCode] 加一
给定一个由整数组成的非空数组所示意的非负整数，在该数的根底上加一。最高位数字寄存在数组的首位，数组中每个元素只存储一个数字。
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] 最初一个单词的长度
给定一个仅蕴含大小写字母和空格’’的字符串，返回其最初一个单词的长度。
var lengthOfLastWord = function(s) {s = s.trim();
var arr = s.split(' ');
return arr[arr.length-1].length;
};
8、[LeetCode] 最大子序和
给定一个整数数组 nums，找到一个具备最大和的间断子数组（子数组起码蕴含一个元素）返回其最大和。
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]报数
报数序列是一个整数序列，依照其中的整数的程序进行报数，失去下一个数。
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]杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输出: 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
给定一个非负索引 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]相交链表
编写一个程序，找到两个单链表相交的起始节点。
例如
思路：
遍历 A 表，指针 l1 等于尾部 c3 时，让它指向 B 表的 b1
遍历 B 表，指针 l2 等于尾部 c3 时，让它指向 A 表的 a1
如果两链表有交点，则会同时指向 c1，因为：
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]打家劫舍
你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。
给定一个代表每个屋宇寄存金额的非负整数数组，计算你在不触动警报安装的状况下，可能偷窃到的最高金额。
思路：
偷取第 i 家时，有两种抉择：
偷取第 i 家，此时金额为：res[i] = res[i-2]+nums[i];
不偷，此时金额为：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]最小栈
设计一个反对 push，pop，top 操作，并能在常数工夫内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
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]只呈现一次的数字
给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。
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]验证回文串
给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。
阐明：本题中，咱们将空字符串定义为无效的回文串。
var isPalindrome = function(s) {var str1 = s.toUpperCase().replace(/\W/g,'');
var str2 = str1.split('').reverse().join('');
return str1==str2;
};
17、[LeetCode]交易股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 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]移除元素
给定一个数组 nums 和一个值 val，你须要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要应用额定的数组空间，你必须在原地批改输出数组并在应用 O(1) 额定空间的条件下实现。
元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。
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;
};
// 办法 2
var 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]均衡二叉树
给定一个二叉树，判断它是否是高度均衡的二叉树。
本题中，一棵高度均衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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]删除排序数组中的反复项
给定一个排序数组，你须要在原地删除反复呈现的元素，使得每个元素只呈现一次，返回移除后数组的新长度。
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]合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
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]无效的括号
给定一个只包含‘(’，’)’，’{’，’}’，’[’，’]’的字符串，判断字符串是否无效。
无效字符串需满足：
左括号必须用雷同类型的右括号闭合。
左括号必须以正确的程序闭合。
留神空字符串可被认为是无效字符串。
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]最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串“”。
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]罗马数字转整数
罗马数字蕴含以下七种字符: I，V，X，L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II，即为两个并列的 1。12 写做 XII，即为 X + II。27 写做 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]回文数
判断一个整数是否是回文数。回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。
var isPalindrome = function(x) {var num = x.toString();
return x == num.split('').reverse().join('');
};
// 办法 2 找到两头地位，而后两边比照
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]反转整数
给定一个 32 位有符号整数，将整数中的数字进行反转。
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]实现 strStr() 函数
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串呈现的第一个地位 (从 0 开始)。如果不存在，则返回 -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;
};
// 超简做法
var strStr = function(haystack, needle) {return haystack.indexOf(needle);
};
28、[LeetCode]搜寻插入地位
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。
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]将有序数组转换为二叉搜寻树
将一个依照升序排列的有序数组，转换为一棵高度均衡二叉搜寻树。
本题中，一个高度均衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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]二叉树的档次遍历 II
给定一个二叉树，返回其节点值自底向上的档次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
var levelOrderBottom = function(root) {var queue = [];
var result = [];
if(root) queue.push(root);
while(queue.length){var arr = [];
var len = queue.length
for(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]二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。
阐明: 叶子节点是指没有子节点的节点。
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]爬楼梯
假如你正在爬楼梯。须要 n 阶你能力达到楼顶。
每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？
思路：
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 的递归写法
}
return a;
};
33、[LeetCode]合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
阐明:
初始化 nums1 和 nums2 的元素数量别离为 m 和 n。
你能够假如 nums1 有足够的空间（空间大小大于或等于 m + n）来保留 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]雷同的树
给定两个二叉树，编写一个函数来测验它们是否雷同。
如果两个树在结构上雷同，并且节点具备雷同的值，则认为它们是雷同的。
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]对称二叉树
给定一个二叉树，查看它是否是镜像对称的。
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]删除排序链表中的反复元素
删除排序链表中的反复元素
var deleteDuplicates = function(head) {
var l = head;
if(l==null) return null
while(l.next){if(l.val == l.next.val){l.next = l.next.next;}else{l = l.next;}
}
return head;
};
37、[LeetCode]Excel 表列名称
给定一个正整数，返回它在 Excel 表中绝对应的列名称。
例如，
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;
};