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

尝试几道算法题,提升python编程思维

一、跳跃游戏

题目描述
给定一个非负整数数组 nums,你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例

  • 输入:nums = [2,3,1,1,4] → 输出:True
  • 输入:nums = [3,2,1,0,4] → 输出:False

---------------------------------------------------------------------------------------------------------------------------------

代码实现

def can_jump(nums):max_reach = 0n = len(nums)for i in range(n):if i > max_reach:  # 当前位置无法到达,直接失败return Falsemax_reach = max(max_reach, i + nums[i])if max_reach >= n - 1:  # 已覆盖终点,提前成功return Truereturn max_reach >= n - 1  # 遍历结束后判断

详细解析

  1. 核心变量max_reach 记录当前能到达的最远索引,初始为 0(起点)。
  2. 遍历逻辑
    • 若当前索引 i 超过 max_reach,说明该位置不可达,直接返回 False(因为无法从前面的位置跳到这里)。
    • 计算从当前位置 i 能跳到的最远距离 i + nums[i],并更新 max_reach 为两者中的较大值(确保始终记录最远可达位置)。
    • 若 max_reach 已覆盖数组最后一个索引(n-1),说明可到达终点,提前返回 True 以优化效率。
  3. 边界处理:若遍历完所有位置后 max_reach 仍未覆盖终点,则返回 False(题目中大部分情况可提前判断,此处为兜底)。
  4. 贪心思想体现:无需记录具体路径,只需通过局部最优(每次更新最远可达距离)推导全局最优(是否能到终点),时间复杂度 O (n),空间复杂度 O (1)。

二、最长递增子序列(动态规划解法)

题目描述
给你一个整数数组 nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)元素而不改变其余元素的顺序,且子序列严格递增。

示例
输入:nums = [10,9,2,5,3,7,101,18] → 输出:4(最长子序列为 [2,3,7,101] 或 [2,5,7,18]

---------------------------------------------------------------------------------------------------------------------------------

代码实现

def length_of_lis(nums):if not nums:return 0n = len(nums)dp = [1] * n  # 每个元素至少自身是一个子序列for i in range(1, n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

详细解析

  1. 动态规划数组定义dp[i] 表示以 nums[i] 为结尾的最长严格递增子序列的长度。初始值均为 1(每个元素自身构成长度为 1 的子序列)。
  2. 状态转移逻辑
    • 对于每个 i(从 1 到 n-1),遍历所有 j < i
      • 若 nums[j] < nums[i],说明 nums[i] 可接在 nums[j] 后面形成更长的子序列,因此 dp[i] 可更新为 dp[j] + 1(与当前 dp[i] 取最大值,确保记录最长长度)。
  3. 结果计算:遍历完所有 i 后,dp 数组中的最大值即为整个数组的最长递增子序列长度。
  4. 示例验证:以 nums = [2,5,3,7] 为例:
    • i=0dp[0] = 1(初始值)。
    • i=1(nums[1]=5):j=0 时 nums[0]=2 < 5,故 dp[1] = dp[0]+1 = 2
    • i=2(nums[2]=3):j=0 时 nums[0]=2 < 3,故 dp[2] = dp[0]+1 = 2j=1 时 nums[1]=5 > 3,不更新)。
    • i=3(nums[3]=7):j=0 时 dp[0]+1=2j=1 时 dp[1]+1=3j=2 时 dp[2]+1=3,故 dp[3] = 3
      最终 max(dp) = 3(对应子序列 [2,5,7] 或 [2,3,7])。
  5. 复杂度:时间复杂度 O (n²)(两层循环),空间复杂度 O (n)(存储 dp 数组)。

三、最长递增子序列(贪心 + 二分查找解法)

题目描述
同第二题(题目一致,解法不同)。

---------------------------------------------------------------------------------------------------------------------------------

代码实现

import bisectdef length_of_lis(nums):tails = []for num in nums:# 找到tails中第一个 >= num的位置,替换它idx = bisect.bisect_left(tails, num)if idx == len(tails):tails.append(num)else:tails[idx] = numreturn len(tails)

详细解析

  1. 核心思路:维护一个 tails 数组,其中 tails[i] 表示长度为 i+1 的严格递增子序列的最小尾元素。例如:
    • tails[0] 是长度为 1 的子序列的最小尾元素(即数组中最小的元素)。
    • tails[1] 是长度为 2 的子序列的最小尾元素(即能接在 tails[0] 后面的最小元素)。
      这样做的目的是:尾元素越小,后续越容易添加更大的元素形成更长的子序列(贪心策略)。
  2. 二分查找的作用
    • 对于每个新元素 num,用 bisect_left 在 tails 中查找第一个大于等于 num 的位置 idxtails 始终是严格递增的,因此可二分)。
    • 若 idx 等于 tails 的长度,说明 num 比所有现有尾元素都大,可直接追加到 tails 末尾(此时子序列长度 + 1)。
    • 否则,将 tails[idx] 替换为 num(目的是用更小的尾元素更新该长度的子序列,为后续元素留更多可能)。
  3. 示例验证
    输入 nums = [10,9,2,5,3,7,101,18]
    • num=10 → tails 为空,idx=0 等于长度 0,追加 → tails = [10]
    • num=9 → 二分找到 tails 中第一个 ≥9 的位置是 0(tails[0]=10),替换 → tails = [9]
    • num=2 → 二分找到位置 0,替换 → tails = [2]
    • num=5 → 二分找到位置 1(超过 tails 长度 1),追加 → tails = [2,5]
    • num=3 → 二分找到 tails 中第一个 ≥3 的位置是 1(tails[1]=5),替换 → tails = [2,3]
    • num=7 → 二分找到位置 2(超过长度 2),追加 → tails = [2,3,7]
    • num=101 → 二分找到位置 3(超过长度 3),追加 → tails = [2,3,7,101]
    • num=18 → 二分找到位置 3(tails[3]=101 ≥18),替换 → tails = [2,3,7,18]
      最终 tails 长度为 4,即最长子序列长度为 4(与题目示例一致)。
  4. 关键说明tails 数组本身不是最长子序列,但其长度等于最长子序列的长度(因为每次更新都对应子序列长度的潜在增长)。
  5. 复杂度:时间复杂度 O (n log n)(每个元素二分查找 O (log k),k 是当前 tails 长度,总复杂度 O (n log n)),空间复杂度 O (n)(tails 最长为 n)。

四、岛屿数量(DFS 解法)

题目描述
给你一个由 '1'(陆地)和 '0'(水)组成的二维网格,请你计算网格中岛屿的数量。岛屿由相邻的陆地连接形成,相邻指水平或垂直方向(斜向不算)

示例
输入:

grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]

输出:3

-------------------------------------------------------------------------------------

答案

def num_islands(grid):if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0def dfs(i, j):# 越界或不是陆地,直接返回if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':returngrid[i][j] = '0'  # 标记为已访问(淹没)# 递归遍历四个方向(上下左右)dfs(i+1, j)  # 下dfs(i-1, j)  # 上dfs(i, j+1)  # 右dfs(i, j-1)  # 左for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1  # 发现新岛屿dfs(i, j)  # 淹没整个岛屿,避免重复计数return count

详细解析

  1. 核心问题:统计 “连通分量” 的数量(相邻陆地构成的独立区域)。
  2. DFS 函数作用:从坐标 (i,j) 出发,递归 “淹没” 所有相连的陆地(将 '1' 改为 '0'),确保每个岛屿只被计数一次。
  3. DFS 终止条件
    • 坐标越界(i 或 j 超出网格范围)。
    • 当前位置不是陆地(grid[i][j] != '1',可能是水或已被淹没的陆地)。
  4. 主循环逻辑
    • 遍历网格中的每个单元格 (i,j)
    • 若遇到 grid[i][j] == '1',说明发现一个新岛屿,计数器 count 加 1。
    • 立即调用 dfs(i,j) 淹没该岛屿(将所有相连的 '1' 改为 '0'),防止后续遍历再次计数。
  5. 示例验证
    以上述示例为例:
    • 首次遇到 (0,0) 为 '1'count=1,启动 DFS 淹没左上角所有相连的 '1'(第一、二行前两列变为 '0')。
    • 继续遍历,遇到 (2,2) 为 '1'count=2,启动 DFS 淹没中间岛屿。
    • 最后遇到 (3,3) 为 '1'count=3,启动 DFS 淹没右下角岛屿((3,3) 和 (3,4) 相连)。
      最终 count=3,与示例一致。
  6. 复杂度:时间复杂度 O (rows×cols)(每个单元格最多被访问一次),空间复杂度 O (rows×cols)(最坏情况全是陆地,递归栈深度为网格大小)。

 

http://www.lryc.cn/news/601105.html

相关文章:

  • C语言中:形参与实参的那些事
  • 1. Qt多线程开发
  • PYTHON从入门到实践-15数据可视化
  • 方案C,version2
  • 主要分布在腹侧海马体(vHPC)CA1区域(vCA1)的混合调谐细胞(mixed-tuning cells)对NLP中的深层语义分析的积极影响和启示
  • 深度解析 noisereduce:开源音频降噪库实践
  • C 与 C++ 的区别:发展、特性及优缺点详解
  • 对比JS“上下文”与“作用域”
  • 秋招Day19 - 分布式 - 分布式设计
  • RoPE:相对位置编码的旋转革命——原理、演进与大模型应用全景
  • LChot100--128. 最长连续序列
  • 前缀和-238-除自身以外数组的乘积-力扣(LeetCode)
  • 基于深度学习的图像分类:使用Inception-v3实现高效分类
  • FastAPI入门:demo、路径参数、查询参数
  • GPU运维常见问题处理
  • Vibe Coding | 技术让我们回归了创造的本质
  • 基于深度学习的图像分类:使用Capsule Networks实现高效分类
  • 【HTML】<script>元素中的 defer 和 async 属性详解
  • 前端开发 Vue 结合Sentry 实现性能监控
  • 掌握JavaScript函数封装与作用域
  • LeetCode 895:最大频率栈
  • 【micro:bit】从入门到放弃(六):示例蜂鸣器音乐、摇色子、光照强度、串口调试、麦克风
  • C++/CLI与标准C++的语法差异(一)
  • 大话数据结构之 < 栈>(C语言)
  • Pspice仿真电路:(三十四)如何使用Pspcie进行仿真
  • 每日一题【删除有序数组中的重复项 II】
  • k8s之控制器详解
  • 基于springboot的图书借阅系统
  • mysql-数据表-DDL语句
  • Python爬虫实战:诗词名句网《三国演义》全集