LeetCode 1-50

1. Two Sum

leetcode link

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

题解思路1 暴力枚举

暴力解法，两层循环遍历数组，找到和为目标值的两个数。

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

复杂度分析

  • 时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

  • 空间复杂度：O(1) 只使用了常数个变量，没有使用额外的空间

解释:

外层循环需要遍历整个数组，执行 n 次, 内层循环对于第 i 个元素需要遍历 (n-i) 次, 总的执行次数是: (n−1)+(n−2)+...+2+1(n-1) + (n-2) + ... + 2 + 1 = n(n−1)2\frac{n(n-1)}{2} = n2−n2\frac{n^2 - n}{2} = 12n2\frac{1}{2}n^2 - 12n\frac{1}{2}n。 在大 O 表示法中，我们主要关注的是函数增长的最高阶项，并且忽略常数项和系数， 当 n 趋向于无穷大时：n² 的增长速度远超过 n， 常数项 1/2 的影响可以忽略，所以最终决定增长速度的是最高阶项 n²， 因此，时间复杂度为 O(N^2)，同样这里的空间复杂度表示为O(1)，而不是O(2)，因为不管是用了 1 个、2 个还是 3 个变量， 它们的空间占用都是固定的，不会随着输入数据的规模 n 的增长而增长。所以在大 O 表示法中，它们都简化表示为 O(1)。

题解思路2 哈希表

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    // 使用 map 来存储数组中的元素及其对应的下标
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        // 获取当前元素
        const cur = nums[i]
        // 计算目标值与当前元素的差值
        const cmp = target - cur
        // 如果 map 中存在该差值，则返回其下标和当前元素的下标
        if (map.has(cmp)) {
            return [map.get(cmp), i]
        } else {
            // 如果 map 中不存在该差值，则将当前元素及其下标存入 map
            map.set(cur, i)
        }
    }
    // 如果没有找到符合条件的两个数，则返回空数组
    return []
};

2. Add Two Numbers

leetcode link

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    let carry = 0
    // 初始化一个虚拟头节点
    let r = new ListNode()
    let c = r
    while (l1 || l2) {
        // 初始化 sum 为进位
        let sum = carry
        // 如果 l1 不为空，则将 l1 的值加到 sum 上
        if (l1) {
            sum += l1.val
        }
        // 如果 l2 不为空，则将 l2 的值加到 sum 上
        if (l2) {
            sum += l2.val
        }
        // 计算进位
        carry = Math.floor(sum / 10)
        // 计算当前位的值
        let val = sum % 10
        // 创建新节点
        c.next = new ListNode(val)
        c = c.next
        // 移动指针
        if (l1) {
            l1 = l1.next
        }
        if (l2) {
            l2 = l2.next
        }
    }
    // 如果最后还有进位，则创建新节点
    if (carry > 0) {
        c.next = new ListNode(carry)
    }
    // 返回虚拟头节点的下一个节点
    return r.next
};

3. Longest Substring Without Repeating Characters

leetcode link

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let l = 0
    let max = 0
    // 使用 map 来存储字符及其对应的下标
    const map = new Map()
    for (let r = 0; r < s.length; r++) {
        const c = s[r]
        if (map.has(c)) {
            // abba 在这里遇到第二a的时候，不能把第一个a的位置给l
            l = Math.max(map.get(c) + 1, l)
        }
        // 更新字符及其对应的下标
        map.set(c, r)
        // 计算当前无重复字符子串的长度
        let temp = r - l + 1
        // 更新最大长度
        if (max < temp) {
            max = temp
        }
    }
    return max
};

4. Median of Two Sorted Arrays

leetcode link

// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。


// 算法的时间复杂度应该为 O(log (m+n)) 。


// 示例 1：


// 输入：nums1 = [1,3], nums2 = [2]
// 输出：2.00000
// 解释：合并数组 = [1,2,3] ，中位数 2


// 示例 2：


// 输入：nums1 = [1,2], nums2 = [3,4]
// 输出：2.50000
// 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

题解思路1 暴力解法

有序合并两个数组，然后取中位数

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    // 初始化两个指针
    let i1 = 0, i2 = 0
    // 初始化一个数组来存储合并后的有序数组
    let arr = []
    while (i1 < nums1.length || i2 < nums2.length) {
        // 如果两个数组都还有元素
        if (i1 < nums1.length && i2 < nums2.length) {
            let v1 = nums1[i1]
            let v2 = nums2[i2]
            // 比较两个数组的当前元素
            if (v1 < v2) {
                // 如果 v1 小于 v2，则将 v1 添加到数组中，并移动 nums1 的指针
                i1++
                arr.push(v1)
            } else if (v1 > v2) {
                // 如果 v1 大于 v2，则将 v2 添加到数组中，并移动 nums2 的指针
                i2++
                arr.push(v2)
            } else {
                // 如果 v1 等于 v2，则将 v1 和 v2 都添加到数组中，并移动两个指针
                i1++
                arr.push(v1)
                i2++
                arr.push(v2)
            }
        } else if (i1 < nums1.length) {
            // 如果 nums1 还有元素，则将 nums1 的当前元素添加到数组中，并移动 nums1 的指针
            arr.push(nums1[i1])
            i1++
        } else if (i2 < nums2.length) {
            // 如果 nums2 还有元素，则将 nums2 的当前元素添加到数组中，并移动 nums2 的指针
            arr.push(nums2[i2])
            i2++
        }
    }
    // 计算合并后数组的长度
    const l = arr.length
    // 如果长度是偶数，则返回中间两个数的平均值
    if (l % 2 === 0) {
        return (arr[l / 2] + arr[l / 2 - 1]) / 2
    } else {
        // 如果长度是奇数，则返回中间一个数
        return arr[Math.floor(l / 2)]
    }
};

时间复杂度：O(m+n)，空间复杂度：O(m+n)

题解思路2 直接确定中位数位置在哪

因为数组是有序的，所以没有必要合并数组，直接确定中位数位置在哪，然后取值即可。

5. Longest Palindromic Substring

leetcode link

// 给你一个字符串 s，找到 s 中最长的 回文子串。


// 示例 1：


// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案。


// 示例 2：


// 输入：s = "cbbd"
// 输出："bb"


// 提示：


// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成

题解思路1 中心扩散

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    if (s.length === 1 || s == null) return s;
    let maxStr = "";
    for (let i = 0; i < s.length; i++) {
        let l = i - 1
        let r = i + 1
        // 向左扩散
        while (l >= 0 && s[l] === s[i]) {
            l--
        }
        // 向右扩散
        while (r < s.length && s[r] === s[i]) {
            r++
        }
        // 向两边扩散
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            l--
            r++
        }
        // 获取当前回文子串 l+1 是因为向两边扩散的时候，l 和 r 都多减了一次和多加了一次
        // r 不需要减 1 是因为 substring 不包含 r 位置的字符
        let tmp = s.substring(l + 1, r)
        // 更新最大回文子串
        if (tmp.length > maxStr.length) {
            maxStr = tmp
        }
    }
    return maxStr;
};

题解思路2 动态规划

当dp[l][r] = true 时，表示 s[l] 到 s[r] 是回文子串，那么 dp[l+1][r-1] 也是回文子串。 当已知dp[l][r] = true 时，当s[l] === s[r] 时，dp[l-1][r+1] = true

  • …a… 当 l=x,r=x 时，s[l] === s[r] r-l = 0 是回文子串
  • …aa… 当 l=x,r=x+1 时，s[l] === s[r] r-l = 1 是回文子串
  • …aba… 当 l=x-1,r=x+1 时，s[l] === s[r] r-l = 2 是回文子串
  • …abba… 当 l=x-1,r=x+2 时，s[l] === s[r] r-l = 3 是回文子串 此时 dp[l+1][r-1] = true
  • …abca… 当 l=x-1,r=x+2 时，s[l] !== s[r] r-l = 3 不是回文子串 此时 dp[l+1][r-1] = false
var longestPalindrome = function (s) {
  if (s.length === 1 || s === null) return s;
  let n = s.length;
  let maxL = 0;
  let maxR = 0;
  let maxLength = 1;
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));


  for (let r = 1; r < s.length; r++) {
    for (let l = 0; l < r; l++) {
      if (s[l] === s[r] && (r - l <= 2 || dp[l + 1][r - 1])) {
        dp[l][r] = true;
        const currLength = r - l + 1;
        if (currLength > maxLength) {
          maxLength = currLength;
          maxL = l;
          maxR = r;
        }
      }
    }
  }
  return s.substring(maxL, maxR + 1);
};

6. Zigzag Conversion

leetcode link

可以想象就是在不同高度放置字符，然后按行输出。

var convert = function (s, numRows) {
    let h = 0
    let increase = true
    let arr = []
    for (let i = 0; i < s.length; i++) {
        if (arr[h]) {
            arr[h].push(s[i])
        } else {
            arr[h] = [s[i]]
        }
        if (increase) {
            h++
            if (h === numRows - 1) {
                increase = false
            }
        } else {
            h--
            if (h === 0) {
                increase = true
            }
        }
    }
    return arr.map(a => a.join("")).join("")
};

7. Reverse Integer

leetcode link

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
    if (x === 0) return 0
    const isN = x < 0
    const MAX_V = Math.pow(2, 31) - 1
    const MIN_V = - Math.pow(2, 31)
    x = isN ? -x : x


    let r = 0


    while (x > 0) {
        const l = x % 10
        r = r * 10 + l
        if (r > MAX_V) return 0
        if (r < MIN_V) return 0
        x = Math.floor(x / 10)
    }


    return isN ? -r : r
};

8. String to Integer (atoi)

leetcode link

9. Palindrome Number

leetcode link

10. Regular Expression Matching

leetcode link

#leetcode

Read Next

JavaScript Special Notes

A collection of notes on JavaScript special features.

NVM and Node Preset

a tool that can help you manage your nodejs version