devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leetcode 热门题目100道每日一题_leetcode题库

作者：小蓝xlanll | 2024-03-26 07:33:04

赞

踩

leetcode题库

 1.检索物品数量   

  1. /**
  2.  * @param {string[][]} items
  3.  * @param {string} ruleKey
  4.  * @param {string} ruleValue
  5.  * @return {number}
  6.  */
  7. var countMatches = function(items, ruleKey, ruleValue) {
  8.     let resSum=0
  9.     const ruleValueArr=["type","color","name"]
  10.     const index=ruleValueArr.indexOf(ruleKey)
  11.     if(index<0)
  12.     return 0
  13.     for(let item of items){
  14.         if(item[index]==ruleValue)
  15.         resSum++
  16.     }
  17.     return resSum
  18. };

2. 两数之和

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  */
  6. var twoSum = function(nums, target) {
  7.     for(let i=0,len=nums.length;i<len;i++){
  8.         let findingNum=target-nums[i]
  9.         if(nums.indexOf(findingNum)>=0&&nums.indexOf(findingNum)!==i){
  10.             return [i,nums.indexOf(findingNum)].sort((a,b)=>a-b)
  11.         }
  12.     }
  13.     return []
  14. };

3. 两数相加

当时第一反应想到的解法

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} l1
  10.  * @param {ListNode} l2
  11.  * @return {ListNode}
  12.  */
  13. var addTwoNumbers = function(l1, l2) {
  14.       function reverseList(head) {
  15.         let cur = head
  16.         let pre = null
  17.         let res = ""
  18.         while (cur != null) {
  19.             const next = cur.next
  20.             cur.next = pre
  21.             pre = cur
  22.             cur = next
  23.         }
  24.         while (pre != null) {
  25.             res = res + pre.val
  26.             pre = pre.next
  27.         }
  28.         return res
  29.     }
  30.     let res1 = reverseList(l1)
  31.     let res2 = reverseList(l2)
  32.     let res3 = (Number(res1) + Number(res2)).toString().split("").reverse()
  33.     let resL = new ListNode()
  34.     let cur = resL
  35.     for (let i = 0; i < res3.length; i++) {
  36.         cur.next = new ListNode(res3[i])
  37.         cur = cur.next
  38.     }
  39.     return resL.next
  40. };

就是翻转链表获取参数然后数字相加，但是发现了最后两题过不去，数字范围太大超过最大值导致返回NaN了。

 后来想到 应该可以直接链表相加。满10进1

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} l1
  10.  * @param {ListNode} l2
  11.  * @return {ListNode}
  12.  */
  13. var addTwoNumbers = function(l1, l2) {
  14.     //当前指针
  15.     let cur1 = l1
  16.     let cur2 = l2
  17.     let carry = 0
  18.     let res = new ListNode()
  19.     let resCur = res
  20.     while (cur1 && cur2) {
  21.         let tempRes = cur1.val + cur2.val + carry
  22.         resCur.next = new ListNode(tempRes % 10)
  23.         carry = Math.floor(tempRes / 10)
  24.         cur1 = cur1.next
  25.         cur2 = cur2.next
  26.         resCur = resCur.next
  27.     }
  28.     while (cur1) {
  29.         let tempRes = cur1.val + carry
  30.         resCur.next = new ListNode(tempRes % 10)
  31.         carry = Math.floor(tempRes / 10)
  32.         cur1 = cur1.next
  33.         resCur = resCur.next
  34.     }
  35.     while (cur2) {
  36.         let tempRes = cur2.val + carry
  37.         resCur.next = new ListNode(tempRes % 10)
  38.         carry = Math.floor(tempRes / 10)
  39.         cur2 = cur2.next
  40.         resCur = resCur.next
  41.     }
  42.     if (carry > 0) {
  43.         resCur.next = new ListNode(carry)
  44.     }
  45.     return res.next;
  46. };

4. 最长回文子串

 第一反应解法

时间复杂度太高了，她测试用例居然输入了那么长的字符串

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. var longestPalindrome = function(s) {
  6.    //双指针法
  7.     let p1 = 0
  8.     let res = ""
  9.     while (p1 < s.length) {
  10.         let p2 = p1
  11.         while (p2 < s.length) {
  12.             let target = s.slice(p1, p2 + 1)
  13.             if (target === target.split("").reverse().join("")) {
  14.                 res = res.length > target.length ? res : target
  15.             }
  16.             p2++
  17.         }
  18.         p1++
  19.     }
  20.     return res
  21. };

第二反应采用的是中心扩散的方法 就是以一个字符为中心左右移动开始指针和结束指针，判断是否回文。

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. var longestPalindrome = function (s) {
  6.     //中心扩散 中心指针
  7.     //回文的几种基本情况
  8.     /**
  9.      * @type 仅自身回文  “a”
  10.      * @type 偶数回文 “abba”
  11.      * @type 中心对称奇数回文 “aba”
  12.      */
  13.     let res = ""
  14.     for (let len = s.length, i = 0; i < len; i++) {
  15.         getResString(i, i) //情况1 3 以某元素为中心左右扩展
  16.         getResString(i, i + 1)//情况2 以i和i+1元素为起始左右扩展
  17.     }
  18.     function getResString(left, right) {
  19.         while (left >= 0 && right < s.length) {
  20.             if (s.charAt(left) !== s.charAt(right)) {
  21.                 return
  22.             } else {
  23.                 let target = s.slice(left, right + 1)
  24.                 res = res.length > target.length ? res : target
  25.                 left--
  26.                 right++
  27.             }
  28.         }
  29.     }
  30.     return res
  31. };

5. 正则匹配

第一眼看完只能说是没什么思路。思考了一会：直接看答案

  1. /**
  2.  * @type .表示任意字符  *表示前面的单个字符任意数目重复
  3.  * @param {string} s 字符串
  4.  * @param {string} p  字符规律
  5.  * @return {boolean}
  6.  */
  7. var isMatch = function (s, p) {
  8.     //从左向右扫描的话 *的出现会影响结果 改为从右向左扫 把b*看成一个整体进行子集匹配
  9.     if (s == null || p == null) return false;
  10.  
  11.     const sLen = s.length, pLen = p.length;
  12.  
  13.     const dp = new Array(sLen + 1);
  14.     for (let i = 0; i < dp.length; i++) {
  15.         dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false
  16.     }
  17.     // base case
  18.     dp[0][0] = true;
  19.     for (let j = 1; j < pLen + 1; j++) {
  20.         if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
  21.     }
  22.     // 迭代
  23.     for (let i = 1; i < sLen + 1; i++) {
  24.         for (let j = 1; j < pLen + 1; j++) {
  25.  
  26.             if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
  27.                 dp[i][j] = dp[i - 1][j - 1];
  28.             } else if (p[j - 1] == "*") {
  29.                 if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
  30.                     dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
  31.                 } else {
  32.                     dp[i][j] = dp[i][j - 2];
  33.                 }
  34.             }
  35.         }
  36.     }
  37.     return dp[sLen][pLen]; // 长sLen的s串 是否匹配 长pLen的p串
  38. }

6. 注水容器

 暴力解法 计算出所有的组合比较大小 肯定超时就不试了，只能想其他的方法：

思路就是 左右指针 左指针如果移动到比上一位小的height 则跳过判断，右指针左移同理。

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var maxArea = function (height) {
  6.     //双指针法
  7.     let maxS = 0
  8.     let i = 0, tempStartMaxHeight = 0
  9.     while (i < height.length - 1) {
  10.         if (height[i] > tempStartMaxHeight) {
  11.             let j = height.length - 1, tempEndMaxHeight = 0
  12.             while (j > i) {
  13.                 if (height[j] > tempEndMaxHeight) {
  14.                     let tempS = Math.min(height[i], height[j]) * (j - i)
  15.                     maxS = tempS > maxS ? tempS : maxS
  16.                     tempEndMaxHeight = height[j]
  17.                 }
  18.                 j--
  19.             }
  20.             tempStartMaxHeight = height[i]
  21.         }
  22.         i++
  23.     }
  24.     return maxS
  25. };

7.三数之和

 猛一看全是思路，细想不暴力解决的话还是有点东西：

自己瞎写的通过了 但是算不上简洁

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var threeSum = function(nums) {
  6.     let res = []
  7.     let left = nums.filter(item => {
  8.         return item < 0
  9.     })
  10.     let right = nums.filter(item => {
  11.         return item >= 0
  12.     })
  13.     for (let i = 0; i < left.length; i++) {
  14.         for (let j = 0; j < right.length; j++) {
  15.             let target = 0 - left[i] - right[j]
  16.             if (left.indexOf(target, i + 1) !== -1 || right.indexOf(target, j + 1) !== -1) {
  17.                 let tempArrStr = [left[i], right[j], target].sort((a, b) => a - b).join("!")
  18.                 if (!res.includes(tempArrStr))
  19.                     res.push(tempArrStr)
  20.             }
  21.         }
  22.     }
  23.     res = res.map(item => {
  24.         return item.split("!")
  25.     })
  26.     let zeroNum = 0
  27.     for (let item of right) {
  28.         if (item === 0) {
  29.             zeroNum++
  30.         }
  31.     }
  32.     if (zeroNum >= 3) {
  33.         res.push([0, 0, 0])
  34.     }
  35.     return res
  36. };

8. 电话号码数字组合

 看着一般

回溯法：JS算法之回溯法_js回溯算法_前端小魔女的博客-CSDN博客

  1. /**
  2.  * @param {string} digits
  3.  * @return {string[]}
  4.  */
  5. var letterCombinations = function (digits) {
  6.     let res = []
  7.     if(digits.length===0) return []
  8.     const digitsObj = {
  9.         "1": [],
  10.         "2": ["a", "b", "c"],
  11.         "3": ["d", "e", "f"],
  12.         "4": ["g", "h", "i"],
  13.         "5": ["j", "k", "l"],
  14.         "6": ["m", "n", "o"],
  15.         "7": ["p", "q", "r", "s"],
  16.         "8": ["t", "u", "v"],
  17.         "9": ["w", "x", "y", "z"]
  18.     }
  19.     /**
  20.      * 
  21.      * @param {number} index 当前处理的digits索引 
  22.      * @param {string} path 当前生成的组合 
  23.      */
  24.     function dfs(index, path) {
  25.         if (index === digits.length) res.push(path)
  26.         else if (index < digits.length) {
  27.             for (let item of digitsObj[digits.charAt(index)]) {
  28.                 path = path + item
  29.                 dfs(index + 1, path)
  30.                 path = path.slice(0, path.length - 1)
  31.             }
  32.         }
  33.     }
  34.     dfs(0, [])
  35.     return res
  36. };

9. 删除链表的倒数第n个节点

指针法怼它就完事了

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @param {number} n
  11.  * @return {ListNode}
  12.  */
  13. var removeNthFromEnd = function(head, n) {
  14.     let res = new ListNode()
  15.     res.next = head
  16.     let o = res
  17.     let p = head
  18.     let q = head
  19.     for (let i = 0; i < n-1; i++) {
  20.         q = q.next
  21.     }
  22.     while (q.next) {
  23.         o = o.next
  24.         p = p.next
  25.         q = q.next
  26.     }
  27.     o.next = p.next
  28.     return res.next
  29. };

10. 有效括号数

 经典题目 入栈出栈思维就好

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isValid = function (s) {
  6.     let left = ["(", "[", "{"]
  7.     let tempItems = []
  8.     for (let i = 0; i < s.length; i++) {
  9.         if (left.includes(s.charAt(i))) {
  10.             tempItems.push(s.charAt(i))
  11.         } else if (s.charAt(i) === ")" && tempItems[tempItems.length - 1] === "(") {
  12.             tempItems.pop()
  13.         } else if (s.charAt(i) === "]" && tempItems[tempItems.length - 1] === "[") {
  14.             tempItems.pop()
  15.         } else if (s.charAt(i) === "}" && tempItems[tempItems.length - 1] === "{") {
  16.             tempItems.pop()
  17.         } else {
  18.             return false
  19.         }
  20.     }
  21.     if (tempItems.length === 0) return true
  22.     return false
  23. };

 11. 合并有序链表

经典中的经典了

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} list1
  10.  * @param {ListNode} list2
  11.  * @return {ListNode}
  12.  */
  13. var mergeTwoLists = function(list1, list2) {
  14.     let res=new ListNode()
  15.     let o=res
  16.     while(list1&&list2){
  17.         if(list1.val<list2.val){
  18.             res.next=list1
  19.             list1=list1.next
  20.         }else{
  21.             res.next=list2
  22.             list2=list2.next
  23.         }
  24.         res=res.next
  25.     }
  26.     while(list1){
  27.         res.next=list1
  28.         list1=list1.next
  29.         res=res.next
  30.     }
  31.     while(list2){
  32.         res.next=list2
  33.         list2=list2.next
  34.         res=res.next
  35.     }
  36.     return o.next
  37. };

12. 括号生成

还是回溯法 只不过可以剪枝

  1.     let res = []
  2.     let path = ""
  3.     function getLength(str, target) {
  4.         return str.split(target).length - 1
  5.     }
  6.     function dfs(index) {
  7.         if (index === 2 * n) {
  8.             res.push(path)
  9.         } else {
  10.             for (let item of ["(", ")"]) {
  11.                 if (item === "(" && getLength(path, "(") < n) {
  12.                     path = path + "("
  13.                     dfs(index + 1)
  14.                     path = path.slice(0, path.length - 1)
  15.                 } else if (item === ")" && getLength(path, "(") > getLength(path, ")")) {
  16.                     path = path + ")"
  17.                     dfs(index + 1)
  18.                     path = path.slice(0, path.length - 1)
  19.                 }
  20.             }
  21.         }
  22.     }
  23.     dfs(0)
  24.     return res

13. 合并k个升序链表

 虽然是困难题，但是我的解决办法就是循环执行11题，两两排序。就比较简单了。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode[]} lists
  10.  * @return {ListNode}
  11.  */
  12. var mergeKLists = function (lists) {
  13.     if (lists.length === 0) return null
  14.     let res = lists[0]
  15.     function sortTwoList(l1, l2) {
  16.         let o = new ListNode()
  17.         let res = o
  18.         while (l1 && l2) {
  19.             if (l1.val < l2.val) {
  20.                 o.next = l1
  21.                 l1 = l1.next
  22.             } else {
  23.                 o.next = l2
  24.                 l2 = l2.next
  25.             }
  26.             o = o.next
  27.         }
  28.         while (l1) {
  29.             o.next = l1
  30.             o = o.next
  31.             l1 = l1.next
  32.         }
  33.         while (l2) {
  34.             o.next = l2
  35.             o = o.next
  36.             l2 = l2.next
  37.         }
  38.         return res.next
  39.     }
  40.     for (let i = 1; i < lists.length; i++) {
  41.         res = sortTwoList(res, lists[i])
  42.     }
  43.     return res
  44. };

14. 下一个排列

做的时候没啥思路太困了 看了官方的方法

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var nextPermutation = function(nums) {
  6.     //逆序找变小值返回索引
  7.     let indexMin = -1
  8.     let changeIndex = -1
  9.     for (let i = nums.length - 2; i >= 0; i--) {
  10.         if (nums[i] < nums[i + 1]) {
  11.             indexMin = i
  12.             break
  13.         }
  14.     }
  15.     if (indexMin === -1) return nums.sort((a, b) => a - b)
  16.     //查找第一个比min大的数
  17.     for (let i = nums.length; i >= indexMin; i--) {
  18.         if (nums[i] > nums[indexMin]) {
  19.             changeIndex = i
  20.             break
  21.         }
  22.     }
  23.     //交换两个数的位置
  24.     let tempData = nums[indexMin]
  25.     nums[indexMin] = nums[changeIndex]
  26.     nums[changeIndex] = tempData
  27.     //将后面的排序
  28.     let tempArray = []
  29.     for (let i = nums.length - 1; i > indexMin; i--) {
  30.         tempArray.push(nums.pop())
  31.     }
  32.     nums.push(...tempArray)
  33. };

15. 最长有效括号

开始懒得想直接暴力求解 果然超时

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var longestValidParentheses = function(s) {
  6.     let maxLength = 0
  7.     function judge(str) {
  8.         let list = []
  9.         for (let i = 0; i < str.length; i++) {
  10.             let target = str.charAt(i)
  11.             if (target === "(") {
  12.                 list.push("(")
  13.             } else if (target === ")" && list[list.length - 1] === "(") {
  14.                 list.pop()
  15.             } else {
  16.                 return false
  17.             }
  18.         }
  19.         if (list.length === 0) return true
  20.         return false
  21.     }
  22.     for (let pre = 0; pre < s.length; pre++) {
  23.         for (let next = 1; next < s.length; next++) {
  24.             if(s.length-pre<maxLength) return maxLength
  25.             let target = s.slice(pre, next+1)
  26.             if (judge(target)) {
  27.                 maxLength = maxLength > target.length ? maxLength : target.length
  28.             }
  29.         }
  30.     }
  31.     return maxLength
  32. };

 后来直接去看答案 还是答案想的周到，这里采用双指针法

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var longestValidParentheses = function (s) {
  6.     let left = 0
  7.     let right = 0
  8.     let maxLength = 0
  9.  
  10.  
  11.     for (let i = 0; i < s.length; i++) {
  12.         const target = s.charAt(i)
  13.         if (target === "(") {
  14.             left++
  15.         } else if (target === ")") {
  16.             right++
  17.         }
  18.         if (right > left) {
  19.             right = 0
  20.             left = 0
  21.         }else if (left === right) {
  22.             const length = 2 * right
  23.             maxLength = maxLength > length ? maxLength : length
  24.         }
  25.     }
  26.     right=left=0
  27.     for (let i = s.length - 1; i >= 0; i--) {
  28.         const target = s.charAt(i)
  29.         if (target === "(") {
  30.             left++
  31.         } else if (target === ")") {
  32.             right++
  33.         }
  34.         if (right < left) {
  35.             right = 0
  36.             left = 0
  37.         }else if (left === right) {
  38.             const length = 2 * left
  39.             maxLength = maxLength > length ? maxLength : length
  40.         }
  41.     }
  42.  
  43.     return maxLength
  44. };

关于贪心算法的补充

贪心算法详解

后面有几道过于简单的就省略掉了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/315508
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号