网站建设个人工作室,沈阳seo网站推广优化,河北省任免,沧州建设网站公司工作太忙没有时间刷算法题#xff0c;面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题#xff0c;整理的内容有点长#xff0c;建议先收藏#xff0c;慢慢消化#xff0c;在来年顺利拿到满意的offer。
1、[LeetCode] 两数之和
给定一个整数数组和一个目标值…工作太忙没有时间刷算法题面试的时候好心虚。这里双手奉上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 i0; ilen; i){for(var ji1; jlen;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.rightcur0) 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 ia.length-1; i0; i--){num parseInt(a[i])parseInt(b[i])addOne;if(num2){res[i] num-2;addOne 1;}else{res[i] num;addOne 0;}}if(addOne0){res.unshift(1);}return res.join();};5、[LeetCode]x的平方根
实现 int sqrt(int x) 函数。 计算并返回 x 的平方根其中 x 是非负整数。 由于返回类型是整数结果只保留整数的部分小数部分将被舍去。
var mySqrt function(x) {var i 1;while(xi*i){i;}return i-1;}; //方法2 ES6var mySqrt function(x) {return Math.floor(x ** 0.5);//向下取整 x^0.5}; 6、[LeetCode] 加一
给定一个由整数组成的非空数组所表示的非负整数在该数的基础上加一。最高位数字存放在数组的首位 数组中每个元素只存储一个数字。
var plusOne function(digits) {var len digits.length;for (var ilen-1; i0; 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 i1; in; i){var repeatCount 1;var str ;for (var j0; jresultStr.length; j) {if (resultStr[j]resultStr[j1]){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 i0; inumRows; i){var arr [1];for (var j1; ji; 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 (rowIndex0) return [1];if (rowIndex1) {return [1,1];}var arr getRow(rowIndex-1);for (var i1; irowIndex; 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 l1l2 ? 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 i2; ilen; i){res[i] Math.max(res[i-1], nums[i]res[i-2]);}return res[len-1];
};14、[LeetCode]最小栈
设计一个支持 pushpoptop 操作并能在常数时间内检索到最小元素的栈。 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 i1; ilen; 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 i0; ilen; ii2){if(nums[i]!nums[i1]){return nums[i];}}};16、[LeetCode]验证回文串
给定一个字符串验证它是否是回文串只考虑字母和数字字符可以忽略字母的大小写。 说明本题中我们将空字符串定义为有效的回文串。
var isPalindrome function(s) {var str1 s.toUpperCase().replace(/\W/g,);var str2 str1.split().reverse().join();return str1str2;};17、[LeetCode]买卖股票的最佳时机 II
给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
var maxProfit function(prices) {var max 0;var len prices.length;for (var i0; ilen-1; i){if (prices[i1]prices[i]){max prices[i1]-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; jlen; 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]平衡二叉树
给定一个二叉树判断它是否是高度平衡的二叉树。 本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 j1; jlen; j){if (nums[i] ! nums[j]){i;nums[i] nums[j]}}return i1;};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 i0; ilen; i){var char s[i];var stackLen stack.length;if(stackLen0) {stack.push(char); }else{if(isMatch(stack[stackLen-1],char)){stack.pop();}else{stack.push(char);}} }return stack.length0;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 i0; istr1Len; i) {for (var j1; jstrsLen; j) {if (str1[i] ! strs[j][i]) {return res;}}res str1[i];}return res;}; 24、[LeetCode]罗马数字转整数
罗马数字包含以下七种字符: I V X LCD 和 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 i0; ilen-1; i) {var curNum romanObj[s.charAt(i)];var rightNum romanObj[s.charAt(i1)];num curNumrightNum?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 i0; ihalfLen; 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(res2**31) return 0;return x0?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; ilen; i) {if (haystack.substring(i, ilen2) 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 i0; ilen; i){if(targetnums[i]){return i;}}return len;}; 29、[LeetCode]将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组转换为一棵高度平衡二叉搜索树。 本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
var sortedArrayToBST function(nums) {var len nums.length;if(!len) return null;if(len1) 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(mid1));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.lengthfor(var i0; ilen; 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 i0; in; i){nums1[mi] nums2[i]}nums1.sort(function(a, b){return a-b;})};34、[LeetCode]相同的树
给定两个二叉树编写一个函数来检验它们是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。
var isSameTree function(p, q) {if (pnull qnull) return true;if (pnull || qnull) 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(lnull) return nullwhile(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(n0){var a parseInt((n-1)%26);n parseInt((n-1)/26);res String.fromCharCode(a65) res;}return res;
};
