当前位置: 首页 > news >正文

深入解析:【Leetcode】随笔

深入解析:【Leetcode】随笔

你好呀!我是 山顶风景独好
欢迎踏入我的博客世界,能与您在此邂逅,真是缘分使然!
愿您在此停留的每一刻,都沐浴在轻松愉悦的氛围中。
这里不仅有丰富的知识和趣味横生的内容等您来探索,更是一个自由交流的平台,期待您留下独特的思考与见解。
让我们一起踏上这段探索与成长的旅程,携手挖掘更多可能,共同进步!✨

题目一:最小好进制(LeetCode 483,困难)

题目分析

对于给定的整数 nn >= 3),返回 n 的一个 最小好进制。好进制是指:在该进制下,n 的表示形式为全 1 组成的字符串(例如,111 在 3 进制下表示 1*3² + 1*3 + 1 = 13,则 3 是 13 的一个好进制)。例如:输入 n = 13,输出 "3"(13 在 3 进制下为 111,且 3 是最小好进制);输入 n = 4681,输出 "8";输入 n = 1000000000000000000,输出 "999999999999999999"

解题思路(数学推导+二分查找)

核心是基于“好进制的数学性质”缩小查找范围,结合二分查找高效验证可能的进制,避免暴力枚举的低效:

  1. 好进制的数学本质
    • kn 的好进制,且 nk 进制下表示为 m 个 1(m >= 2),则满足公式:
      n = 1 + k + k² + ... + k^(m-1) = (k^m - 1) / (k - 1)
    • 推导可得:k < n^(1/(m-1))(因 k^(m-1) < n),且 m 的最大值为 log2(n) + 1(当 k=2 时,m 最大,如 n=13m=3)。
  2. 查找策略
    • 从大到小遍历 mm 越大,k 越小(如 m=log2(n)k 可能接近 2),优先找到的 k 即为最小好进制;
    • 二分查找验证 k:对每个 m,在 [2, n^(1/(m-1))] 范围内二分查找 k,验证 (k^m - 1)/(k - 1) == n 是否成立。
  3. 边界情况处理
    • 若遍历所有 m 未找到好进制,n 的最小好进制为 n-1(因 nn-1 进制下恒为 11,满足好进制定义)。

示例代码

def smallestGoodBase(n: str) -> str:
n = int(n)
# 计算m的最大可能值:m_max = floor(log2(n)) + 1
m_max = n.bit_length()  # bit_length()返回n的二进制位数,log2(n)≈bit_length()-1
# 从大到小遍历m(m>=2)
for m in range(m_max, 1, -1):
# 二分查找k:范围[2, n^(1/(m-1))]
left = 2
right = int(n ** (1.0 / (m - 1))) + 1  # +1避免浮点误差
while left <= right:
mid = (left + right) // 2
# 计算sum = 1 + mid + mid² + ... + mid^(m-1),避免溢出
sum_k = 1
overflow = False
for _ in range(m - 1):
sum_k = sum_k * mid + 1
if sum_k > n:
overflow = True
break
if overflow:
right = mid - 1
elif sum_k == n:
return str(mid)
else:
left = mid + 1
# 所有m均未找到,返回n-1(恒为好进制)
return str(n - 1)
# 测试示例
n1 = "13"
print("最小好进制1:", smallestGoodBase(n1))  # 输出:"3"
n2 = "4681"
print("最小好进制2:", smallestGoodBase(n2))  # 输出:"8"
n3 = "1000000000000000000"
print("最小好进制3:", smallestGoodBase(n3))  # 输出:"999999999999999999"

代码解析

  • 数学推导的核心价值:通过公式将“好进制”转化为可计算的数学关系,将 m 的范围从无限缩小到 [2, log2(n)+1],避免暴力枚举所有可能的进制;
  • 二分查找的高效性:对每个 m,二分查找 k 的时间复杂度为 O(log n),内部求和验证为 O(m),整体复杂度 O(log² n),即使处理 1e18 级别的 n 也能快速响应;
  • 溢出处理:求和过程中实时判断是否超过 n,避免Python整数溢出(虽Python支持大整数,但提前终止可提升效率)。

题目二:接雨水 II(LeetCode 407,困难)

题目分析

给定一个 m x n 的矩阵,其中每个单元格的值表示该位置的高度。计算在该矩阵中能接多少体积的雨水。例如:输入矩阵 heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],输出 4;输入 heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]],输出 10。

解题思路(最小堆+边界扩散)

核心是将“二维接雨水”转化为“边界最小高度控制积水”的问题,用最小堆维护边界高度,从最低边界向内部扩散,计算每个单元格的积水量:

  1. 核心原理(木桶效应)
    • 二维矩阵的积水高度由“最低边界”决定,如同木桶的最短木板;
    • 初始边界为矩阵的最外层单元格(这些单元格无法积水),用最小堆存储边界单元格的 (高度, 行, 列)
  2. 扩散流程
    • 标记访问:用 visited 矩阵记录已处理的单元格,避免重复计算;
    • 弹出最小边界:每次从堆中弹出高度最小的边界单元格 (h, i, j)
    • 遍历相邻单元格:对上下左右四个方向的相邻单元格 (ni, nj),若未访问:
      • 积水量 = max(0, h - heightMap[ni][nj])(若相邻单元格高度低于边界,可积水);
      • 将相邻单元格的“有效高度”(max(h, heightMap[ni][nj]))加入堆(该单元格成为新的边界),并标记为已访问;
  3. 终止条件:堆为空时,所有可积水的单元格均已处理,累计积水量即为答案。

示例代码

import heapq
def trapRainWater(heightMap) -> int:
if not heightMap or len(heightMap) <= 2 or len(heightMap[0]) <= 2:
return 0  # 边界无法积水
m, n = len(heightMap), len(heightMap[0])
visited = [[False for _ in range(n)] for _ in range(m)]
heap = []
# 1. 初始化堆:加入矩阵最外层边界
# 第一行和最后一行
for j in range(n):
heapq.heappush(heap, (heightMap[0][j], 0, j))
heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
visited[0][j] = True
visited[m-1][j] = True
# 第一列和最后一列(排除已加入的行)
for i in range(1, m-1):
heapq.heappush(heap, (heightMap[i][0], i, 0))
heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
visited[i][0] = True
visited[i][n-1] = True
# 四向移动方向
directions = [(-1,0), (1,0), (0,-1), (0,1)]
water = 0
# 2. 从边界向内部扩散
while heap:
h, i, j = heapq.heappop(heap)
for dx, dy in directions:
ni, nj = i + dx, j + dy
# 检查相邻单元格是否在范围内且未访问
if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:
visited[ni][nj] = True
# 计算积水量:边界高度 - 单元格高度(若为正)
if h > heightMap[ni][nj]:
water += h - heightMap[ni][nj]
# 新边界高度为原边界高度(积水后水位升高)
heapq.heappush(heap, (h, ni, nj))
else:
# 新边界高度为单元格自身高度(无积水)
heapq.heappush(heap, (heightMap[ni][nj], ni, nj))
return water
# 测试示例
heightMap1 = [
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
print("接雨水量1:", trapRainWater(heightMap1))  # 输出:4
heightMap2 = [
[3,3,3,3,3],
[3,2,2,2,3],
[3,2,1,2,3],
[3,2,2,2,3],
[3,3,3,3,3]
]
print("接雨水量2:", trapRainWater(heightMap2))  # 输出:10

代码解析

  • 二维问题的降维思路:将复杂的二维积水问题转化为“边界最小高度优先处理”的一维逻辑,通过堆高效获取最小边界,符合“木桶效应”的物理规律;
  • 时间复杂度优化:每个单元格入堆和出堆各一次,堆操作时间复杂度 O(log(mn)),整体复杂度 O(mn log(mn)),能高效处理中等规模的矩阵;
  • 访问标记的必要性visited 矩阵确保每个单元格仅处理一次,避免重复入堆和计算,保证算法正确性和效率。

题目三:删除无效的括号(LeetCode 301,困难)

题目分析

给你一个由若干括号和字母组成的字符串 s,删除最小数量的无效括号,使得剩下的“括号字符串”有效。返回所有可能的有效字符串(结果不重复)。例如:输入 s = "()())()",输出 ["(())()","()()()"];输入 s = "(a)())()",输出 ["(a())()","(a)()()"];输入 s = ")(",输出 [""]

解题思路(BFS+剪枝+去重)

核心是通过广度优先搜索(BFS)逐层删除括号,找到“删除最少括号”的有效字符串,结合剪枝和去重避免冗余计算:

  1. BFS的核心逻辑
    • 层级含义:每一层代表“删除 k 个括号”后的字符串集合(k 从 0 开始递增),首次找到有效字符串的层级即为“最小删除数”;
    • 终止条件:当某一层出现有效字符串时,停止搜索(因BFS保证层级递增,该层的有效字符串即为删除最少括号的结果)。
  2. 剪枝与去重策略
    • 剪枝1:同一层级中,若两个字符串删除相同位置的同类型括号(如连续的 ')' 中删除任意一个),会产生重复字符串,仅保留首次出现的字符串(用集合 current_level 去重);
    • 剪枝2:删除括号时,仅删除“导致括号无效的括号”(如多余的 ')''('),避免无意义的删除;
  3. 有效性判断
    • 遍历字符串,用计数器 balance 记录括号平衡度('(' 加 1,')' 减 1),若 balance < 0 则无效;遍历结束后 balance == 0 则有效。

示例代码

def removeInvalidParentheses(s: str) -> list[str]:
def is_valid(string):
"""判断括号字符串是否有效"""
balance = 0
for c in string:
if c == '(':
balance += 1
elif c == ')':
balance -= 1
if balance < 0:
return False
return balance == 0
# BFS初始化:第一层为原字符串
current_level = {s}
while True:
# 检查当前层级是否有有效字符串
valid = [string for string in current_level if is_valid(string)]
if valid:
return valid
# 生成下一层级:删除一个括号的所有可能字符串(去重)
next_level = set()
for string in current_level:
for i in range(len(string)):
# 仅删除括号,字母不处理
if string[i] in ('(', ')'):
# 避免连续相同括号的重复删除(如"())"删除第1或2个')'结果相同)
if i > 0 and string[i] == string[i-1]:
continue
# 删除第i个字符,加入下一层
next_level.add(string[:i] + string[i+1:])
current_level = next_level
# 若下一层为空(无字符串可删),返回空列表(仅当s全为字母时)
if not current_level:
return [""]
# 测试示例
s1 = "()())()"
print("有效字符串1:", removeInvalidParentheses(s1))  # 输出:["(())()","()()()"]
s2 = "(a)())()"
print("有效字符串2:", removeInvalidParentheses(s2))  # 输出:["(a())()","(a)()()"]
s3 = ")("
print("有效字符串3:", removeInvalidParentheses(s3))  # 输出:[""]

代码解析

  • BFS的优势:天然保证“最小删除数”,因层级对应删除次数,首次找到的有效字符串即为最优解,无需后续搜索;
  • 去重的关键:用集合存储每一层的字符串,自动去重相同结果;同时跳过连续相同括号的重复删除(如 '())' 中删除第1或2个 ')'),减少无效计算;
  • 有效性判断的高效性:单次判断时间复杂度 O(n)n 为字符串长度),结合BFS的层级遍历,整体复杂度可控,能快速处理中等长度的字符串。

✨ 本次分享的3道题覆盖“数学推导+二分(最小好进制)”“最小堆+边界扩散(接雨水II)”“BFS+剪枝(删除无效的括号)”,均为LeetCode困难题中“思维模型独特”且“工程实现有技巧”的经典案例,避免了之前重复的题目类型。若对某题的拓展场景(如好进制的最大进制、三维接雨水)或其他冷门困难题有需求,随时告诉我!
更多算法解析欢迎到CSDN主页交流:山顶风景独好

http://www.hskmm.com/?act=detail&tid=24258

相关文章:

  • 实用指南:Linux驱动之V4L2
  • 儿童与青少年数据安全及体育发展新方向会议
  • 威联通NAS Emby-Server 的SQLite数据库损坏和程序损坏修复
  • Embarcadero Dev-C++ 6.3 中文乱码问题 - 教程
  • 2025.10.4——2绿
  • 十月四日就听《10월 4일》
  • windows上的实用小软件
  • 比赛题2
  • ZR 2025 十一集训 Day 4
  • 价值处理单元(VPU)专题研究:从价值危机到透明决策的计算革命——声明Ai研究
  • 13-Neo4j Desktop
  • 中兴ZXHN F450光猫关闭TR069实录
  • 完整教程:六款智能证照工具盘点,打造个性化“数字身份档案”
  • 随机化学习笔记
  • PWN手的从成长之路-08-not_the_same_3dsctf_2016-溢出+函数调用劫持
  • 12-windows11的WSL详解
  • 完整教程:如何将文件从电脑传输到安卓设备
  • [vmware+openeuler22.03]创建软RAID
  • C++右值引用
  • 价值处理单元(VPU)专题研究:构建可信AI的基石
  • NOIP模拟赛记录
  • 软件工程第一次作业--关于未来规划和自我发展
  • 2025太阳能厂家推荐天津龙腾,太阳能热水系统,发电系统,光伏热系统,热水工程系统,预加热系统,中央热水系统,彩图发电系统,分户储水系统,分户计量系统推荐
  • 集训模拟赛日志
  • 1688 商品采集 API 调用全流程分享:从准备到实操 - 实践
  • 2025最新推荐化妆品代工公司排行榜:含 OEM / ODM / 一站式服务企业,助力品牌方精准选合作方
  • 悟空博弈单元(WBUC)专题研究:面向可能性计算的结构化创新架构
  • 访问控制、用户认证、https - 实践
  • GO_基础
  • sg.完整布局演示