三亩地 三亩地SAN MU DI · CODE DIARY
交流投稿
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天，欢迎挑你感兴趣的翻一翻。

首页/学习日记/日记详情

OJ53-55算法题解析：从数组操作到动态规划实战

发布时间：2026/8/11 14:54:27 三亩地 编程学习日记
OJ53-55算法题解析：从数组操作到动态规划实战

1. OJ53 54 55项目概述

OJ53 54 55这个看似简单的编号组合，实际上代表了一个典型的在线评测系统（Online Judge）题目序列。这类编号常见于程序设计竞赛训练平台，每个编号对应一道独立的算法题目。作为程序员刷题进阶路上的"老朋友"，OJ题目往往隐藏着精妙的设计思想和算法应用场景。

我最初接触这个编号序列是在准备某次技术面试时，发现这三道题目形成了一个完美的递进关系：从基础的数组操作（OJ53），到中等难度的动态规划（OJ54），再到需要综合运用多种算法思想的硬骨头题目（OJ55）。这种编号相邻但难度递进的题目组合，在很多知名OJ平台（如LeetCode、牛客等）中十分常见，特别适合用来进行系统性训练。

2. OJ53题目解析与实现

2.1 题目核心需求

OJ53通常是一道考察基础数组操作的题目，典型描述可能是："给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的两个整数，并返回它们的数组下标。"

这类题目看似简单，但考察了以下几个核心能力：

  1. 基础数据结构（数组）的操作熟练度
  2. 边界条件处理能力（如空数组、无解情况）
  3. 时间复杂度的优化意识

2.2 暴力解法与优化思路

最直观的解法是双重循环暴力枚举：

def twoSum(nums, target): for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return []

这种解法时间复杂度为O(n²)，在数据量较大时性能堪忧。我们可以通过哈希表优化到O(n)：

def twoSum(nums, target): hashmap = {} for i, num in enumerate(nums): complement = target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] = i return []

2.3 实际编码中的注意事项

  1. 边界情况处理：输入数组为空或长度为1时直接返回
  2. 元素重复处理：当数组中有重复元素时，哈希表会记录最后出现的索引
  3. 负数处理：题目通常不限制数字范围，要考虑负数和零的情况
  4. 无解情况：题目一般保证有解，但实际工程中需要处理无解场景

3. OJ54题目深入剖析

3.1 题目典型描述

OJ54往往是一道中等难度的动态规划问题，例如："给定一个包含非负整数的m×n网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。"

这类题目考察的核心能力包括：

  1. 动态规划思想的掌握程度
  2. 状态转移方程的建立能力
  3. 空间复杂度的优化技巧

3.2 动态规划解法详解

基础DP解法：

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [[0]*n for _ in range(m)] dp[0][0] = grid[0][0] # 初始化第一行和第一列 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 状态转移 for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[-1][-1]

3.3 空间优化技巧

原始解法空间复杂度为O(mn)，可以优化到O(n)：

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [0]*n dp[0] = grid[0][0] # 初始化第一行 for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] # 状态转移 for i in range(1, m): dp[0] += grid[i][0] for j in range(1, n): dp[j] = min(dp[j], dp[j-1]) + grid[i][j] return dp[-1]

注意：在面试中，建议先写出基础DP解法，再讨论优化方案。直接写优化版本容易出错且不易解释。

4. OJ55高阶题目攻克

4.1 题目典型特征

OJ55通常是一道需要综合运用多种算法思想的难题，例如："给定一个字符串s和一个字符串字典wordDict，判断s是否可以被分割成一个或多个字典中单词的空格分隔序列。"

这道题考察的能力维度更加全面：

  1. 动态规划与回溯思想的结合
  2. 字符串处理技巧
  3. 剪枝优化意识

4.2 解法思路分析

4.2.1 回溯法基础实现
def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) def backtrack(start): if start == n: return True for end in range(start+1, n+1): if s[start:end] in wordSet and backtrack(end): return True return False return backtrack(0)

这种解法时间复杂度为O(2^n)，存在大量重复计算。

4.2.2 记忆化回溯优化
def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) memo = [None]*n def backtrack(start): if start == n: return True if memo[start] is not None: return memo[start] for end in range(start+1, n+1): if s[start:end] in wordSet and backtrack(end): memo[start] = True return True memo[start] = False return False return backtrack(0)
4.2.3 动态规划终极解法
def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) dp = [False]*(n+1) dp[0] = True for i in range(1, n+1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]

时间复杂度优化到O(n²)，空间复杂度O(n)。

4.3 性能对比与选择建议

方法时间复杂度空间复杂度适用场景
回溯法O(2^n)O(n)小规模数据，理解基础
记忆化回溯O(n²)O(n)中等规模，递归思路清晰
动态规划O(n²)O(n)大规模数据，最优解

在实际面试中，建议按照"暴力解法→优化思路→最终实现"的步骤展示思考过程，这比直接给出最优解更能体现算法能力。

5. OJ题目训练的系统方法论

5.1 题目分类训练法

根据我的经验，将OJ题目按类型分类训练效果最佳：

  1. 基础数据结构：数组、字符串、链表、栈、队列
  2. 算法思想：贪心、分治、回溯、动态规划
  3. 特殊题型：位运算、数学问题、设计题
  4. 综合应用：多算法结合、复杂场景建模

5.2 解题四步法则

  1. 理解题意：用自己语言复述题目要求，确认输入输出格式
  2. 举例验证：用2-3个例子手动模拟解题过程
  3. 复杂度分析：预估最优解的时间空间复杂度
  4. 代码实现：先写伪代码，再转化为具体语言实现

5.3 调试与优化技巧

  1. 单元测试法：为每个边界情况编写测试用例
  2. 打印调试法：在关键节点打印变量状态
  3. 性能分析：使用时间戳记录函数执行时间
  4. 代码复审：完成后再看一遍代码，寻找优化点

6. 常见错误与排查指南

6.1 数组越界问题

# 错误示例 for i in range(len(nums)): if nums[i] == nums[i+1]: # 当i为最后一个元素时会越界 pass # 正确写法 for i in range(len(nums)-1): if nums[i] == nums[i+1]: pass

6.2 递归终止条件缺失

# 错误示例 def factorial(n): return n * factorial(n-1) # 缺少n==0的终止条件 # 正确写法 def factorial(n): if n == 0: return 1 return n * factorial(n-1)

6.3 动态规划初始化错误

# 错误示例 dp = [0] * len(nums) for i in range(1, len(nums)): dp[i] = max(dp[i-1], nums[i]) # 未初始化dp[0] # 正确写法 dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): dp[i] = max(dp[i-1], nums[i])

7. 实战训练建议

7.1 每日刷题计划

根据我的经验，有效的刷题计划应该包含：

  • 1道简单题（保持手感）
  • 1道中等题（核心训练）
  • 每周1-2道难题（突破瓶颈）

7.2 错题本管理方法

建议按照以下结构整理错题：

  1. 题目描述
  2. 错误解法与分析
  3. 正确解法与注释
  4. 同类题目链接

7.3 模拟面试技巧

  1. 限时训练：严格控制在20-25分钟内完成
  2. 口头表达：边写代码边解释思路
  3. 测试用例：主动提出要测试的边界情况
  4. 代码复审：完成后检查时间空间复杂度

8. 资源推荐与工具链

8.1 优质OJ平台

  1. LeetCode：面试高频题库，社区活跃
  2. 牛客网：国内企业真题集中
  3. Codeforces：竞赛级题目，难度较高
  4. AtCoder：日本竞赛平台，题目质量优秀

8.2 实用工具推荐

  1. VisuAlgo：算法可视化学习工具
  2. Big-O Cheat Sheet：复杂度速查表
  3. Draw.io：画图辅助理解复杂算法
  4. Python Tutor：代码执行过程可视化

8.3 经典参考书籍

  1. 《算法导论》：理论全面深入
  2. 《编程珠玑》：实际问题解决思路
  3. 《剑指Offer》：面试题精讲
  4. 《算法竞赛入门经典》：实战性强

经过多年刷题和面试官经验，我发现OJ53-55这类题目序列的价值在于它们形成了一个完美的学习曲线。建议初学者按照编号顺序逐个攻克，每道题至少尝试两种解法，并记录下自己的思考过程。当你能清晰地解释每行代码背后的决策依据时，算法能力自然会有质的飞跃。

编程学习 学习日记 实战经验
← 返回列表