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

【九日集训】第九天:简单递归

递归就是自己调用自己,例如斐波那契数列就是可以用简单递归来实现。

第一题 172. 阶乘后的零

https://leetcode.cn/problems/factorial-trailing-zeroes/description/
这一题纯粹考数学推理能力,我这种菜鸡看了好久都没有懂。
大概是这样的思路:
n!中尾随0的数量第一时间想到的是10的因子,但到n = 5就不适用了,毕竟这里还是120包含1个0呢;
仔细观察可以发现有0的尾数阶乘结果中都包含2和5,恰好2*5 = 10我们只需要找成对的2和5就可以了。
但是举一个例子:
11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
其中含有2的因子比5的次数多,且每出现一次5就会出现一次2,所以我们这里只需要找有多少个5即可。
但仔细观察可以发现,每隔5个数字出现一个5,每隔25个数字出现两个5,每隔125个数字出现3个5,以此类推
所以只需要按顺序加下去就得到最终的结果

int trailingZeroes(int n) {if(n < 5) return 0;return n / 5 + trailingZeroes(n / 5);
}

第二题 1342. 将数字变成 0 的操作次数

https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/description/
如果是0则返回0;
如果给定的数是偶数则除以2递归到下一层,同时将操作数 + 1;
否则减2同时操作数 + 1;

int numberOfSteps(int num) {if(num == 0) return 0;if(num % 2 == 0) {return numberOfSteps(num / 2) + 1;}return numberOfSteps(num - 1) + 1;
}

第三题 222. 完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/description/
算二叉树的节点个数,递归节点的左子树和右子树每次递归都将结果 + 1;
如果递归到节点为空则返回0;

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int countNodes(struct TreeNode* root) {if(root == NULL) {return 0;}return countNodes(root->left) + countNodes(root->right) + 1;
}

第四题 LCP 44. 开幕式焰火

https://leetcode.cn/problems/sZ59z6/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int Hash[1024];void transfer(struct TreeNode* root) {if(root) {Hash[root->val] = 1;transfer(root->left);transfer(root->right);}
}int numColor(struct TreeNode* root){int sum = 0;memset(Hash, 0, sizeof(Hash));transfer(root);for(int i = 1; i <= 1000; ++i) {if(Hash[i]) ++sum;}return sum;
}

第五题 397. 整数替换

https://leetcode.cn/problems/integer-replacement/description/

int min(int a, int b) {return a > b ? b : a;
}int integerReplacement(int n) {if(n == 1) return 0;if(n % 2 == 0) {return integerReplacement(n / 2) + 1;}return 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
}

第六题 938. 二叉搜索树的范围和

https://leetcode.cn/problems/range-sum-of-bst/description/
题目中给的是二叉搜索树,特点就是左小右大,因此如果当前root的val满足条件则将val加到return中,再加上左右子树满足条件的val和。
如果root的val大于high,则需要向左子树(小的一端)递归;
反之小于low向右子树递归;

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int rangeSumBST(struct TreeNode* root, int low, int high) {if(root == NULL) return 0;if(root->val > high) {return rangeSumBST(root->left, low, high);}if(root->val < low) {return rangeSumBST(root->right, low, high);}return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low ,high);
}

第八题 LCR 175. 计算二叉树的深度

https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int max(int a, int b) {return a > b ? a : b;
}int calculateDepth(struct TreeNode* root) {if(root == NULL) return 0;return max(calculateDepth(root->left), calculateDepth(root->right)) + 1;
}

第九题 104. 二叉树的最大深度

这一题和上一题一样
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int max(int a, int b) {return a > b ? a : b;
}int maxDepth(struct TreeNode* root) {if(root == NULL) return 0;return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

第十题 226. 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL) return NULL;struct TreeNode* left = invertTree(root->left);struct TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;
}

相关文章:

【九日集训】第九天:简单递归

递归就是自己调用自己&#xff0c;例如斐波那契数列就是可以用简单递归来实现。 第一题 172. 阶乘后的零 https://leetcode.cn/problems/factorial-trailing-zeroes/description/ 这一题纯粹考数学推理能力&#xff0c;我这种菜鸡看了好久都没有懂。 大概是这样的思路&#x…...

Prime 1.0

信息收集 存活主机探测 arp-scan -l 或者利用nmap nmap -sT --min-rate 10000 192.168.217.133 -oA ./hosts 可以看到存活主机IP地址为&#xff1a;192.168.217.134 端口探测 nmap -sT -p- 192.168.217.134 -oA ./ports UDP端口探测 详细服务等信息探测 开放端口22&#x…...

Java 如何正确比较两个浮点数

看下面这段代码&#xff0c;将 d1 和 d2 两个浮点数进行比较&#xff0c;输出的结果会是什么&#xff1f; double d1 .1 * 3; double d2 .3; System.out.println(d1 d2);按照正常逻辑来看&#xff0c;d1 经过计算之后的结果应该是 0.3&#xff0c;最后打印的结果应该是 tru…...

Qt 如何操作SQLite3数据库?数据库创建和表格的增删改查?

# 前言 项目源码下载 https://gitcode.com/m0_45463480/QSQLite3/tree/main # 第一步 项目配置 平台:windows10 Qt版本:Qt 5.14.2 在.pro添加 QT += sql 需要的头文件 #include <QSqlDatabase>#include <QSqlError>#include <QSqlQuery>#include &…...

【Hadoop】分布式文件系统 HDFS

目录 一、介绍二、HDFS设计原理2.1 HDFS 架构2.2 数据复制复制的实现原理 三、HDFS的特点四、图解HDFS存储原理1. 写过程2. 读过程3. HDFS故障类型和其检测方法故障类型和其检测方法读写故障的处理DataNode 故障处理副本布局策略 一、介绍 HDFS &#xff08;Hadoop Distribute…...

【Python-随笔】使用Python实现屏幕截图

使用Python实现屏幕截图 环境配置 下载pyautogui包 pip install pyautogui -i https://pypi.tuna.tsinghua.edu.cn/simple/下载OpenCV包 pip install opencv-python -i https://pypi.tuna.tsinghua.edu.cn/simple/下载PyQT5包 pip install PyQt5 -i https://pypi.tuna.tsi…...

Sun Apr 16 00:00:00 CST 2023格式转换

Date date new Date(); log.info("当前时间为:{}",date); //yyyy-MM-dd HH:mm:ss SimpleDateFormat sdf new SimpleDateFormat(DateUtils.YYYY_MM_DD_HH_MM_SS); String dateTime s…...

使用mongodb实现简单的读写操作

本文适合初学者&#xff0c;特别是刚刚安装了mongodb数据库的朋友&#xff0c;或在atlas刚拿到免费集群的朋友。 拿到数据库&#xff0c;心情很激动&#xff0c;手痒难耐。特别想向数据库插入几条数据库试试。即使是深夜完成了安装&#xff0c;也忍不住想去完成这些操作。看到…...

C语言实现Cohen_Sutherland算法

前提简要&#xff1a; 算法简介&#xff1a; 编码算法是最早、最流行的线段裁剪算法&#xff0c;该算法采用区域检验的方法&#xff0c;能够快速有效地判断一条线段与裁剪窗口的位置关系&#xff0c;对完全接受或完全舍弃的线段无需求交&#xff0c;即可直接识别。 算法思想&…...

MySQL进阶_EXPLAIN重点字段解析

文章目录 第一节.准备1.1 版本信息1.2 准备 第二节.type2.1 system2.2 const2.3 eq_ref2.4 ref2.5 ref_or_null2.6 index_merge2.7 unique_subquery2.8 range2.9 index2.10 all 第三节. Extra3.1 No tables used3.2 No tables used3.3 Using where3.4 No matching min/max row3…...

视图层与模板层

视图层 1 视图函数 一个视图函数&#xff0c;简称视图&#xff0c;是一个简单的Python 函数&#xff0c;它接受Web请求并且返回Web响应。响应可以是一张网页的HTML内容&#xff0c;一个重定向&#xff0c;一个404错误&#xff0c;一个XML文档&#xff0c;或者一张图片. . . 是…...

MySQL数据库——触发器-案例(Insert类型、Update类型和Delete类型)

目录 表结构准备 插入数据触发器 代码 测试 修改数据触发器 代码 测试 删除数据触发器 代码 测试 通过触发器记录 tb_user 表的数据变更日志&#xff0c;将变更日志插入到日志表user_logs中&#xff0c;包含增加&#xff0c;修改&#xff0c;删除。 表结构准备 根据…...

快速创建桌面端(electron-egg)

介绍 | electron-egg electron-egg: 一个入门简单、跨平台、企业级桌面软件开发框架。 electron-egg是一个基于Electron和Egg.js的框架&#xff0c;可以用于快速构建跨平台的桌面应用程序。 1.兼容平台&#xff1a;electron-egg可以在Windows、MacOS和Linux等多个平台上运行…...

docker配置redis插件

docker配置redis插件 运行容器redis_6390 docker run -it \ --name redis_6390 \ --privileged \ -p 6390:6379 \ --network wn_docker_net \ --ip 172.18.12.19 \ --sysctl net.core.somaxconn1024 \ -e TIME_ZONE"Asia/Shanghai" -e TZ"Asia/Shanghai"…...

前端入口教程_web01

web标准 记得看&#xff01; html&#xff1a;表示整个页面 head&#xff1a; titile&#xff1a; body&#xff1a; 常用标签 1.标题标签 2.段落标签 3.换行标签 4.文本格式化标签 5. 和 标签 6.图像标签 相对路径–用来插自己本地的图片 #### 绝对路径–用来插网上找的图…...

Win7 SP1 x64 Google Chrome 字体模糊

1 打开 Google Chrome &#xff0c;地址栏输入 chrome://version/ &#xff0c;字体模糊。 2 Microsoft Update Catalog 搜索更新 kb2670838&#xff0c;下载&#xff0c;安装&#xff0c;重启电脑。 3 打开 Google Chrome&#xff0c;地址栏输入 chrome://version/ &#xff0…...

read()之后操作系统都干了什么

首先说明三个参数 file文件 buff从内存中开辟一段缓冲区用来接收读取的数据 size表示这个缓冲区的大小 有关file的参数&#xff1a; 状态&#xff1a;被打开 被关闭权限&#xff1a;可读可写最重要的是inode: 他包含了 文件的元数据(比如文件大小 文件类型 文件在访问前需要加…...

YoloV8改进策略:Swift Parameter-free Attention,无参注意力机制,超分模型的完美迁移

摘要 https://arxiv.org/pdf/2311.12770.pdf https://github.com/hongyuanyu/SPAN SPAN是一种超分网络模型。SPAN模型通过使用参数自由的注意力机制来提高SISR的性能。这种注意力机制能够增强重要信息并减少冗余,从而在图像超分辨率过程中提高图像质量。 具体来说,SPAN模…...

Python----练习:使用面向对象实现报名系统开发

第一步&#xff1a;分析哪些动作是由哪些实体发出的 学生提出报名 学生提供相关资料 学生缴费 机构收费 教师分配教室 班级增加学生信息 于是&#xff0c;在整个过程中&#xff0c;一共有四个实体&#xff1a;学生、机构、教师、班级&#xff01;在现实中的一个具体的实…...

1.什么是html

1.什么是html什么是html&#xff1f; 一.基础信息 英文名字&#xff1a;HyperText Markup Language 中文名字&#xff1a;超文本标记语言 简称&#xff1a;html 文件格式&#xff1a;.htm 或 .html 结尾 作用&#xff1a;描述网页的语言。通过各种各样的标签&#xff0c;组…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...