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

CSDN每日一题学习训练——Python版(简化路径,不同的二叉搜索树)

版本说明

当前版本号[20231116]。

版本修改说明
20231116初版

目录

文章目录

  • 版本说明
  • 目录
  • 简化路径
    • 题目
    • 解题思路
    • 代码思路
    • 参考代码
  • 不同的二叉搜索树
    • 题目
    • 解题思路
    • 代码思路
    • 参考代码

简化路径

题目

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (…) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,‘//’)都被视为单个斜杠 ‘/’ 。 对于此问题,任何其他格式的点(例如,‘…’)均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:

始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名(如果存在)不能 以 ‘/’ 结尾。
此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 ‘.’ 或 ‘…’)。

返回简化后得到的 规范路径 。

示例 1:

输入:path = “/home/”
输出:“/home”
解释:注意,最后一个目录名后面没有斜杠。

示例 2:

输入:path = “/…/”
输出:“/”
解释:从根目录向上一级是不可行的,因为根目录是你可以到达的最高级。

示例 3:

输入:path = “/home//foo/”
输出:“/home/foo”
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:

输入:path = “/a/./b/…/…/c/”
输出:“/c”

提示:

1 <= path.length <= 3000
path 由英文字母,数字,‘.’,‘/’ 或 ‘_’ 组成。
path 是一个有效的 Unix 风格绝对路径。

解题思路

解题思路:

  1. 创建一个空列表 result,用于存储简化后的路径。
  2. 将输入的路径字符串 path 按照斜杠 ‘/’ 进行分割,得到一个列表 plist。
  3. 遍历 plist 中的每个元素 pos。
    • 如果 pos 不为空,则进行以下判断:
      • 如果 pos 等于 ‘…’,表示需要返回上一级目录。尝试从 result 中弹出最后一个元素(即返回上一级目录)。如果 result 为空,则将其重置为空列表。
      • 如果 pos 不等于 ‘.’,表示当前目录或文件名有效。将其添加到 result 列表中。
  4. 使用 join() 方法将 result 列表中的元素用斜杠 ‘/’ 连接起来,并在前面加上一个斜杠作为根目录。
  5. 返回简化后的规范路径。

代码思路

  1. 先定义了一个名为Solution的类,并在其中实现了一个名为simplifyPath的方法。该方法接受一个字符串类型的参数path,表示要简化的文件路径。

     def simplifyPath(self, path):
    
  2. 在方法内部,首先定义了一个空列表result,用于存储简化后的路径。然后,使用split('/')方法将输入的路径按照斜杠分割成一个列表plist,其中每个元素表示路径中的一个目录或文件名。

         result = []  # 初始化结果列表plist = path.split('/')  # 将路径按照斜杠分割成列表
    
  3. 接下来,使用一个循环遍历plist中的每个元素。如果当前元素不为空,则进行以下判断:

    • 如果当前元素为..,表示需要返回上一级目录。此时,尝试从result中弹出最后一个元素(即返回上一级目录)。如果result为空,则将其重置为空列表。

      for pos in plist:  # 遍历列表中的每个元素if pos:  # 如果元素不为空if pos == '..':  # 如果元素为'..',表示返回上一级目录try:result.pop()  # 弹出结果列表中最后一个元素except:result = []  # 如果结果列表为空,则将其重置为空列表
      
    • 如果当前元素不为.,表示当前目录或文件名有效。将其添加到result列表中。

         elif pos != '.':  # 如果元素不为'.',表示当前目录result.append(pos)  # 将当前目录添加到结果列表中
      
  4. 最后,使用join()方法将result列表中的元素用斜杠连接起来,并在前面加上一个斜杠作为根目录。最终返回简化后的路径。

      return '/' + '/'.join(result)  # 将结果列表中的元素用斜杠连接起来,并在前面加上一个斜杠作为根目录
    
  5. 在代码的最后,创建了一个Solution类的实例s,并调用其simplifyPath方法,传入一个示例路径/home/,并将结果打印输出。

s = Solution()  # 创建Solution类的实例
print(s.simplifyPath(path="/home/"))  # 调用simplifyPath方法,传入路径参数,并打印结果

参考代码

这段代码主要是使用栈来处理路径中的目录和文件名。

class Solution(object):def simplifyPath(self, path):""":type path: str:rtype: str"""result = []plist = path.split('/')for pos in plist:if pos:if pos == '..':try:result.pop()except:result = []elif pos != '.':result.append(pos)return '/'+'/'.join(result)
# %%
s = Solution()
print(s.simplifyPath(path = "/home/"))

不同的二叉搜索树

题目

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

image-20231116232715671

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

1 <= n <= 19

解题思路

  1. 这个问题可以使用动态规划来解决。我们可以定义一个数组dp,其中dp[i]表示由i个节点组成的二叉搜索树的种数。根据题目要求,我们可以得到以下状态转移方程:

    dp[i] = Σ(dp[j-1] * dp[i-j]) (j=1,2,...,i)
    
  2. 这个方程的含义是,对于每个节点i,它有左子树和右子树,左子树的节点数为j-1,右子树的节点数为i-j。因此,我们需要遍历所有可能的j值,计算出对应的二叉搜索树的种数,并将它们累加起来。

代码思路

  1. 初始化一个长度为n+1的动态规划数组dp,初始值为0。

     # 初始化动态规划数组,长度为n+1,初始值为0dp = [0] * (n + 1)
    
  2. 当节点数为0时,只有一种可能,即空树,所以将dp[0]设为1。

  3. 当节点数为1时,只有一种可能,即只有一个节点的树,所以将dp[1]设为1。

      # 当节点数为0时,只有一种可能,即空树dp[0] = 1# 当节点数为1时,只有一种可能,即只有一个节点的树dp[1] = 1
    
  4. 从第2个节点开始遍历到第n个节点,对于每个节点level,遍历所有可能的根节点root。

    # 从第2个节点开始遍历到第n个节点for level in range(2, n + 1):# 对于每个节点,遍历所有可能的根节点for root in range(1, level + 1):
    
  5. 根据组合数公式,计算当前节点数下,以root为根节点的二叉搜索树的数量。具体计算公式为:dp[level] += dp[level - root] * dp[root - 1]。

      # 根据组合数公式,计算当前节点数下,以root为根节点的二叉搜索树的数量dp[level] += dp[level - root] * dp[root - 1]
    
  6. 返回给定节点数下的二叉搜索树数量,即dp[n]。

      # 返回给定节点数下的二叉搜索树数量return dp[n]
    
  7. 创建Solution对象s,并调用numTrees方法,传入节点数n=3,计算节点数为3的二叉搜索树数量,并打印结果。

# 创建Solution对象
s = Solution()
# 调用numTrees方法,计算节点数为3的二叉搜索树数量,并打印结果
print(s.numTrees(n = 3))

参考代码

这段代码是一个计算给定节点数的二叉搜索树数量的函数。它使用了动态规划的方法,通过遍历每个节点和所有可能的根节点,计算出以当前节点为根节点的二叉搜索树的数量。最后返回给定节点数下的二叉搜索树数量。

class Solution(object):def numTrees(self, n):""":type n: int:rtype: int"""dp = [0] * (n + 1)dp[0] = 1dp[1] = 1for level in range(2, n + 1):for root in range(1, level + 1):dp[level] += dp[level - root] * dp[root - 1]return dp[n]
# %%
s = Solution()
print(s.numTrees(n = 3))

相关文章:

CSDN每日一题学习训练——Python版(简化路径,不同的二叉搜索树)

版本说明 当前版本号[20231116]。 版本修改说明20231116初版 目录 文章目录 版本说明目录简化路径题目解题思路代码思路参考代码 不同的二叉搜索树题目解题思路代码思路参考代码 简化路径 题目 给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路…...

milvus集合管理

一、创建集合 集合由一个或多个分区组成。在创建新集合时&#xff0c;Milvus会创建一个默认分区_default 1.准备模式 需要创建的集合必须包含一个主键字段和一个向量字段。INT64和String是主键字段支持的数据类型。 首先&#xff0c;准备必要的参数&#xff0c;包括字段模式、…...

基于SSM的教学管理系统设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…...

【第2章 Node.js基础】2.7 Node.js 的流(一)可写流

&#x1f308;可写流 &#x1f680;什么是可写流 可写流是对数据被写入的目的地的一种抽象。 所有可写流都实现了 stream.Writable类定义的接口。 可写流的例子包括&#xff0c;也都是实现了可写流接口的双工流 客户端的 HTTP 请求、服务器的HTTP 响应、fs 的写入流、zlib…...

【kerberos】使用 curl 访问受 Kerberos HTTP SPNEGO 保护的 URL

前言&#xff1a; 大数据集群集成 Kerberos 后&#xff0c;很多 WEBUI 打开都会提示输入用户名和密码。由于我想获取 flink 任务的详情&#xff0c;且KNOX 并不支持Flink api&#xff0c;查看KNOX 直接的列表&#xff1a;https://docs.cloudera.com/cdp-private-cloud-base/7.…...

基于SSM的智慧养老平台设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…...

图像生成colab集合

不过colab会做检测&#xff0c;一般文生图算法是基本很难跑起来的。 https://github.com/camenduruhttps://github.com/camenduru这哥们有很多colab。 1.stable-diffusion-webui https://colab.research.google.com/drive/1Iy-xW9t1-OQWhb0hNxueGij8phCyluOh#scrollTow3KNZ-…...

SpringBoot整合Quartz示例

数据表 加不加无所谓,如果需要重启服务器后重新执行所有JOB就把sql加上 如果不加表 将application.properties中的quartz数据库配置去掉 自己执行自己的逻辑来就好,大不了每次启动之后重新加载自己的逻辑 链接&#xff1a;https://pan.baidu.com/s/1KqOPYMfI4eHcEMxt5Bmt…...

物联网AI MicroPython学习之语法 I2C总线

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; I2C 介绍 模块功能: I2C Master设备驱动 接口说明 I2C - 构建硬件I2C对象 函数原型&#xff1a;I2C(id, scl, sda, freq)参数说明&#xff1a; 参数类型必选参数&#xff1f;说明idintYI2C外设&#xff…...

RocketMQ的适用场景有哪些?

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…...

ubuntu启动转圈,无法进入登录界面

安装卸载搜狗拼音输入法相关东西后出现启动转圈问题 当前使用的是lightdm,按网上说去切换成gdm3 &#xff08;1&#xff09;要在刚进入系统没显示圈圈和ubuntu时长按shift进入gurb。 &#xff08;2&#xff09;选择Ubuntu高级选项&#xff0c;enter &#xff08;3&#xff09…...

MATLAB 机械臂逆运动学进行轨迹控制建模

系列文章目录 文章目录 系列文章目录前言一、模型概览1.1 Target Pose Generation 目标姿势生成1.2 Inverse Kinematics 逆运动学1.3 Manipulator Dynamics 机械手动力学1.4 Pose Measurement 姿势测量 二、机械手定义三、生成航点四、模型设置五、模拟机械手运动六、将结果可视…...

【计算机组成原理】定点加法、减法运算

系列文章目录 绘制出纯整数(1字节)和纯小数的数轴 将十进制数20.59375&#xff0c;转换成754标准的32位浮点数的二进制存储格式 用双符号位补码求 x 0.1010011, y -0.1001010, 分别求出 x y, x - y&#xff0c;并判溢出...

scp 跨服务器传输命令,把一个服务器上的文件复制传到当前服务器目录下

要将一个服务器上的文件复制到当前服务器的目录下&#xff0c;可以使用 scp 命令进行跨服务器传输。以下是具体的命令格式&#xff1a; 复制 scp usernamesource_server:/path/to/source_file destination_directory username: 远程服务器的用户名。 source_server: 远程服务…...

【python基础】用户输入和while循环详解

文章目录 一. 函数input()的工作原理1. 编写清晰的程序2. 使用int()来获取数值输入3. 求模运算符 二. while循环简介1. 使用while循环2. 让用户选择何时退出3. 使用标志4. 使用break退出循环5. 在循环中使用continue 三. 使用while循环处理列表和字典1. 在列表之间移动元素2. 删…...

k8s-部署Redis-cluster(TLS)

helm pull bitnami/redis-cluster v8.3.8拉取源码生成证书 git clone https://github.com/redis/redis.git #文档 https://redis.io/docs/management/security/encryption/#getting-started生成你的TLS证书用官网的工具生成 1 Run ./utils/gen-test-certs.sh 生成根CA和服务…...

计算机毕业设计选题推荐-幼儿园管理微信小程序/安卓APP-项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...

ElasticStack日志分析平台-ES 集群、Kibana与Kafka

一、Elasticsearch 1、介绍&#xff1a; Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;Logstash 和 Beats 收集的数据可以存储在 Elasticsearch 中进行搜索和分析。 Elasticsearch为所有类型的数据提供近乎实时的搜索和分析&#xff1a;一旦数据被索引&#…...

微机原理_10

一、单项选择题(本大题共15小题,每小题3分,共45分。在每小题给出的四个备选项中,选出一个正确的答案。&#xff09; 1,将二进制数110110.01转换为十六进制为(&#xff09; A. 66.1H B. 36.4H C. 66.4 D. 36.2 2,一台计算机的字长是4个字节,含义是(&#xff09; A.能处理的最大…...

(SpringBoot)第八章:SpringMVC程序开发

文章目录 一:Spring MVC概述(1)什么是Spring MVC(2)什么是MVC(3)Spring MVC和SpringBoot(4)如何学习Spring MVC二:Spring MVC创建和连接(1)Spring MVC项目创建(2)@RequestMapping注解三:Spring MVC处理参数(1)传递简单参数(2)传递对象(3)@RequestParam:重…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...