跳到主要内容

字符串✅

字符串匹配​

设计一个支持以下两种操作的数据结构：

  • void addWord(word)
  • bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。. 可以表示任何一个字母。 说明: 你可以假设所有单词都是由小写字母 a-z 组成的。

addWord('bad')
addWord('dad')
addWord('mad')
search('pad') // false
search('bad') // true
search('.ad') // true
search('b..') // true
答案

字符串转换为整数​

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 `[−2^31,  2^31 − 1]`。如果数值超过这个范围，请返回  `INT_MAX (2^31 − 1)` 或 `INT_MIN (−2^31)`
示例 1:
输入: "42"
输出: 42

示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 ‘-’, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3: 输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。

解释: 第一个非空字符是 ‘w’, 它不是一个数字或有效的符号。输出: 0示例 4: 输入: "words and 987"

最长回文子串​

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

const s = 'babad'

function longestPalindrome (s) {

}
答案
function longestPalindrome (s) {
  const n = s.length
  if (n < 2) return s
  let maxLen = 1; let start = 0
  const dp = Array.from({ length: n }, () => Array(n).fill(false))
  for (let i = 0; i < n; i++) dp[i][i] = true
  for (let j = 1; j < n; j++) {
    for (let i = 0; i < j; i++) {
      if (s[i] === s[j]) {
        if (j - i < 3) {
          dp[i][j] = true
        } else {
          dp[i][j] = dp[i + 1][j - 1]
        }
      }
      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1
        start = i
      }
    }
  }
  return s.substring(start, start + maxLen)
}

module.exports = longestPalindrome

Open browser consoleTests

字符串的全排列​

给定一个没有重复数字的序列，返回其所有可能的全排列。

const s = 'abc'

function permute (s) {

}
答案
function permute (s) {
  const results = []
  const used = Array(s.length).fill(false)
  function backtrack (path) {
    if (path.length === s.length) {
      results.push(path.join(''))
      return
    }
    for (let i = 0; i < s.length; i++) {
      if (used[i]) continue
      used[i] = true
      path.push(s[i])
      backtrack(path)
      path.pop()
      used[i] = false
    }
  }
  backtrack([])
  return results
}

module.exports = permute

Open browser consoleTests

字符串的子序列​

给定一个字符串 s，返回所有可能的子序列。

const s = 'abc'

function subsequences (s) {

}
答案
function subsequences (s) {
  const results = []
  function backtrack (start, path) {
    results.push(path.join(''))
    for (let i = start; i < s.length; i++) {
      path.push(s[i])
      backtrack(i + 1, path)
      path.pop()
    }
  }
  backtrack(0, [])
  return results
}

module.exports = subsequences

Open browser consoleTests

字符串/数组处理​

function lengthOfLongestSubstring (s: string): number {
  const seen = new Map<string, number>()
  let start = 0
  let maxLength = 0

  for (let end = 0; end < s.length; end++) {
    const char = s[end]
    if (seen.has(char) && seen.get(char)! >= start) {
      start = seen.get(char)! + 1
    }
    seen.set(char, end)
    maxLength = Math.max(maxLength, end - start + 1)
  }

  return maxLength
}

大数字符串相加/相乘​

function addTwoString (num1, num2) {
  const res = []
  let carry = 0
  let i = num1.length - 1
  let j = num2.length - 1
  while (i >= 0 || j >= 0 || carry) {
    const sum = Number(num1[i] || 0) + Number(num2[j] || 0) + carry
    const mod = sum % 10
    res.unshift(mod)
    carry = Math.floor(sum / 10)
    i--
    j--
  }
  return res.join('')
}

function multiplyManyToMany (num1, num2) {
  let res = ''
  for (let i = num2.length - 1; i >= 0; i--) {
    let tempRes = ''
    for (let j = 0; j < num2.length - 1 - i; j++) {
      tempRes += '0'
    }
    tempRes = multiplyManyToOne(num1, num2[i]) + tempRes
    res = addTwoString(res, tempRes)
  }
  return res
}

function multiplyManyToOne (num1, x) {
  const res = []
  let carry = 0
  for (let i = num1.length - 1; i >= 0; i--) {
    const product = Number(num1[i]) * Number(x) + carry
    const mod = product % 10
    res.unshift(mod)
    carry = Math.floor(product / 10)
  }
  if (carry) {
    res.unshift(carry)
  }
  return res.join('')
}

字符串/数组处理​

  1. 3. 无重复字符的最长子串
    • 难度：中等
    • 考点：滑动窗口、哈希表
    • 应用场景：前端字符串处理、性能优化

暴力

function lengthOfLongestSubstring (s: string): number {
  let maxLength = 0

  let currentStr = ''
  for (const char of s) {
    const index = currentStr.indexOf(char)
    if (index >= 0) {
      currentStr = currentStr.slice(index + 1)
    }
    currentStr = `${currentStr}${char}`
    if (currentStr.length > maxLength) {
      maxLength = currentStr.length
    }
  }
  return maxLength
}

滑动窗口

function lengthOfLongestSubstring (s: string): number {
  const seen = new Map<string, number>()
  let start = 0
  let maxLength = 0

  for (let end = 0; end < s.length; end++) {
    const char = s[end]
    // If we've seen this char and it's after our current start,
    // move start to after the last occurrence
    if (seen.has(char) && seen.get(char)! >= start) {
      start = seen.get(char)! + 1
    }
    seen.set(char, end)
    maxLength = Math.max(maxLength, end - start + 1)
  }

  return maxLength
}

记忆技巧：

  • 双指针 start / end
  • 当遇到重复的，更新 start 到上一次出现的下一位
  • 判断重复，记住是动态的窗口，额外判断 lastSeen >= start

5. 最长回文子串​

  • 难度：中等
  • 考点：动态规划、中心扩展
  • 应用场景：文本处理、算法优化

暴力

// 暴力 x 2
function isPalindromic (s: string) {
  return s === s.split('').reverse().join('')
}
// 递归
function isPalindrome (s: string, start: number, end: number): boolean {
  if (start >= end) return true
  if (s[start] !== s[end]) return false
  return isPalindrome(s, start + 1, end - 1)
}

function longestPalindrome (s: string): string {
  let longest = ''
  for (let start = 0; start < s.length; start++) {
    let str = s[start]
    for (let end = start + 1; end < s.length; end++) {
      str = `${str}${s[end]}`
      if (isPalindromic(str) && str.length > longest.length) {
        longest = str
      }
    }
  }
  return longest
}

中心扩展

function longestPalindrome (s: string): string {
  if (s.length < 2) return s

  let start = 0; let maxLength = 1

  function expandAroundCenter (left: number, right: number): void {
    // 从中心向两边扩展，直到不是回文
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const currentLength = right - left + 1
      if (currentLength > maxLength) {
        start = left
        maxLength = currentLength
      }
      left--
      right++
    }
  }

  // 遍历每个可能的中心点
  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i) // 奇数长度的回文
    expandAroundCenter(i, i + 1) // 偶数长度的回文
  }

  return s.substring(start, start + maxLength)
}

动态规划

function longestPalindrome (s: string): string {
  const n = s.length
  if (n < 2) return s

  // dp[i][j] 表示 s[i..j] 是否为回文串
  const dp: boolean[][] = Array(n)
    .fill(0)
    .map(() => Array(n).fill(false))

  // 单个字符都是回文串
  for (let i = 0; i < n; i++) {
    dp[i][i] = true
  }

  let start = 0
  let maxLength = 1

  // 枚举子串长度
  for (let len = 2; len <= n; len++) {
    // 枚举起始位置
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1 // 终止位置

      if (len === 2) {
        dp[i][j] = s[i] === s[j]
      } else {
        dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j]
      }

      if (dp[i][j] && len > maxLength) {
        start = i
        maxLength = len
      }
    }
  }

  return s.substring(start, start + maxLength)
}
22%