Thana 的算法笔记

刷题、思考、沉淀

发表于 分类于

题目描述

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

解题思路

方法一：中心扩展法

以每个字符（或两个字符的间隙）为中心向两边扩展，检查是否构成回文。

  • 时间复杂度： O(n^2)
  • 空间复杂度： O(1)

方法二：动态规划

定义 dp[i][j] 表示 s[i..j] 是否为回文。状态转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]。

  • 时间复杂度： O(n^2)
  • 空间复杂度： O(n^2)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        start, max_len = 0, 1

        def expand(l, r):
            nonlocal start, max_len
            while l >= 0 and r < n and s[l] == s[r]:
                if r - l + 1 > max_len:
                    start = l
                    max_len = r - l + 1
                l -= 1
                r += 1

        for i in range(n):
            expand(i, i)      # 奇数长度
            expand(i, i + 1)  # 偶数长度

        return s[start:start + max_len]

总结

回文问题的经典解法有两种：中心扩展和动态规划。中心扩展法空间更优，推荐优先使用。

发表于 分类于

题目描述

给定一个二叉树，找出其最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。

解题思路

递归计算左右子树的最大深度，取较大值加 1。

  • 时间复杂度： O(n)
  • 空间复杂度： O(h)，h 为树的高度

代码实现

1
2
3
4
5
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

总结

二叉树问题的天然解法是递归。理解递归的终止条件和递推关系是关键。

发表于 分类于

题目描述

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

解题思路

使用哈希表存储已遍历的元素及其下标。遍历数组时，对于每个元素，检查 target - nums[i] 是否在哈希表中。

  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

代码实现

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hash_map:
                return [hash_map[complement], i]
            hash_map[num] = i
        return []

总结

哈希表是解决”查找配对”类问题的经典工具，以空间换时间。

0%