用Js刷LeetCode拿offer-经典高频40题

原创

hellocoder2028

发布于 2022-12-08 09:10:02

5120

发布于 2022-12-08 09:10:02

文章被收录于专栏：高级前端面试题总结高级前端面试题总结

工作太忙没有时间刷算法题，面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题，整理的内容有点长，建议先收藏，慢慢消化，在来年顺利拿到满意的offer。

1、LeetCode 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = 2, 7, 11, 15, target = 9

因为 nums0 + nums1 = 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、LeetCodex的平方根

实现 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,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 家，此时金额为：resi = resi-2+numsi;

不偷，此时金额为：resi = resi-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、LeetCodeExcel表列名称

给定一个正整数，返回它在 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;
};

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

二叉树

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

登录后参与评论

0 条评论

热度