丨阿伟丨 - 个人主页动态

2025-09-18 15:35

题目链接 求表达式 f(n)结果末尾0的个数 题目描述 输入一个自然数 ，求表达式  的结果末尾有几个连续的 ？ 解题思路 一个数末尾连续  的个数，取决于其质因数分解中因子  的个数。由于 ，并且在阶乘的质因数分解中，因子  的数量总是远多于因子  的数量，因此问题等价于求解  的质因数分解中总共有多少个因子 。  是一个连乘积，根据对数性质（这里是指数性质）， 中因子  的总数等于每一项  中因子  的数量之和。 令  表示  末尾  的个数，也即  中因子  的数量。则题目所求为：  直接计算每个  再求和效率较低。我们可以换一个角度来统计。 考虑  的另一种表示形式：   中因子  的...

0 点赞评论收藏

2025-09-18 15:33

广东技术师范大学 C++

题解 | #每K个一组反转链表#

题目链接 每K个一组反转链表 题目描述 给出一个链表，每  个节点一组进行翻转，并返回翻转后的链表。  是一个正整数，它的值小于或等于链表的长度。如果节点总数不是  的整数倍，那么将最后剩余节点保持原有顺序。 说明：  你需要自行定义链表结构，将输入的数据保存到你的链表中； 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换； 你的算法只能使用常数的额外空间。  解题思路 这个问题要求以  个节点为一组，对链表进行分段反转。核心在于分组、反转和链接三个步骤的循环。我们可以使用迭代的方法来解决，这样可以保证空间复杂度为 。   设立哑节点 (Dummy Node)：为了简化对头节点的操...

0 点赞评论收藏

2025-09-18 15:14

广东技术师范大学 C++

题解 | #幼儿园分班#

题目链接 幼儿园分班 题目描述 一个大班有 N 位小朋友，需要分成两个小班。现在有 M 个请求，每个请求的形式为 (u, v)，表示小朋友 u 和 v 不希望在同一个班。 需要判断是否存在一种分班方案，能够满足所有 M 个请求。如果可以，输出 1，否则输出 0。 解题思路 这是一个经典的图论问题，可以被抽象为二分图判定 (Bipartite Graph Checking)。 1. 问题建模   我们将每个小朋友看作图中的一个节点 (Node)。   对于每个请求 (u, v)，我们在节点 u 和节点 v 之间连接一条边 (Edge)。这条边表示 u 和 v 之间存在“冲突关系”，不能被分到同一...

0 点赞评论收藏

2025-09-18 15:05

广东技术师范大学 C++

题解 | #查询满足区间的记录#

题目链接 查询满足区间的记录 题目描述 给定一批订单记录，每条记录包含订单号、入店时间和离店时间。 再给定一个时间点 A，需要在这批记录中找出所有满足 入店时间 <= A <= 离店时间 的记录。 要求：   单次查询时间复杂度控制在 O(logN)。   输出符合条件的订单号，并按升序排列。   如果找不到，输出字符串 "null"。   解题思路 这是一个典型的区间查询问题，要求在指定的时间点 A 找出所有包含该点的区间。O(logN) 的时间复杂度要求提示我们需要使用排序 + 二分查找的策略，而不是简单的线性扫描。 1. 核心思想 一个简单的线性扫描方法是...

0 点赞评论收藏

2025-09-18 14:57

广东技术师范大学 C++

题解 | #LRU Cache#

题目链接 LRU Cache 题目描述 设计并实现一个 LRU (Least Recently Used - 最近最少使用) 缓存机制。它应该支持以下操作： get 和 put。  int get(int key): 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 void put(int key, int value): 如果键不存在，则写入键值对。如果键已存在，则更新其值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据。  特殊规则:  get(key) 或 put 一个新的 key，都算作一次“使用”。 put 一个已存在的 key 来更新其值，不算作...

0 点赞评论收藏

2025-09-18 14:53

广东技术师范大学 C++

题解 | #游游的旅行#

题目链接 游游的旅行 题目描述 在一个由 N 个景点和 M 条路径组成的无向图中，游游和小伙伴计划进行一次为时 T 分钟的旅行。   每个景点 i 有一个游览耗时 time[i]，并能为游游和小伙伴分别增加 joy1[i] 和 joy2[i] 的愉悦度。   每条路径连接两个景点，并有相应的通行耗时。   旅行开始时，他们会等概率地从 N 个景点中随机选择一个作为起点。   每到达一个景点，他们会先花费时间游览该景点并获得愉悦度。之后，他们会查看所有与当前景点直接相连的下一个景点，找出那些“来得及游玩”（即剩余时间足够支付路程耗时和下一个景点的游览耗时）的景点，并从这些景点中等概率随机选择一个...

0 点赞评论收藏

2025-09-18 14:35

广东技术师范大学 C++

题解 | #火车站台#

题目链接 火车站台 题目描述 在一条直线上有若干个城市，从左到右依次编号。存在 n 条火车路线，每条路线从城市 Y 出发，到达城市 X，其中 Y > X。火车会沿途停靠在 [X, Y-1] 区间内的所有城市。 我们需要找出所有城市中，停靠火车线路数最多的那个城市的停靠数是多少。 解题思路 1. 问题转化 这个问题可以被抽象为：给定 n 个左闭右开区间 [X_i, Y_i)，求数轴上哪个点被最多的区间所覆盖，并返回这个最大覆盖数。 2. 暴力解法 (及其问题) 一个直观的想法是创建一个数组 counts 来记录每个城市的停靠次数。数组的大小为最大城市编号。 对于每条路线 (X, Y)，我们...

0 点赞评论收藏

2025-09-18 14:33

广东技术师范大学 C++

题解 | #链式边权#

题目链接 链式边权 题目描述 n 个点连成一条链，编号从 1 到 n。第 i 条边连接点 i 和 i+1。 每个点 i 有一个点权 a[i]。 第 i 条边的权重 w[i] 定义为：满足 x <= i 且 y > i，并且 a[x] != a[y] 的点对 (x, y) 的数量。 给定所有点的点权，请求出所有 n-1 条边的权重。 解题思路 这是一个计数问题。对于每一条边 i，我们需要计算它左右两侧点权不同的点对数量。 1. 核心思想：正难则反 直接计算“不同”的点对数量比较复杂。我们可以换一个思路： w[i] = (总点对数) - (点权相同的点对数)  总点对数：对于第 i 条...

0 点赞评论收藏

2025-09-18 14:10

广东技术师范大学 C++

题解 | #商品交易#

题目链接 商品交易 题目描述 珐达采按顺序经过 n 个国家，在第 i 个国家，某种商品的价格为 A[i]。 在每个国家，他可以做三件事之一：  花费 A[i] 买入一件商品。 卖出一件手中的商品，获得 A[i]。 什么都不做。  限制条件是：他手中最多只能持有一件商品。 求两个目标：  他能获得的最大总收益是多少。 在获得最大收益的前提下，最少的交易次数是多少。  解题思路 这是一个典型的动态规划问题，类似于“买卖股票”系列问题。我们需要同时优化两个目标：最大化收益和最小化交易次数。 1. 第一部分：最大化收益 我们可以定义两个DP状态数组：  dp[i][0]：表示在第 i 天（访问第 i ...

0 点赞评论收藏

2025-09-18 14:06

广东技术师范大学 C++

题解 | #字符串替换#

题目链接 字符串替换 题目描述 给定一个仅由小写字母 x 和 y 组成的字符串。 一次操作可以将字符串中的一个子串 xy 替换为 yyx。 求至少需要多少次替换，才能让字符串中不存在子串 xy？结果需要对 10^9 + 7 取模。 解题思路 (修正版) 这是一个巧妙的递推问题。关键在于选择正确的遍历方向。从左到右处理会导致复杂的依赖关系，而从右到左处理则可以建立一个清晰的递推模型。 1. 核心思想：从右向左的动态规划 最终的目标字符串形态必然是所有 y 都在所有 x 的左边（形如 yy...yxx...x）。这意味着每一个 x 都必须移动到每一个 y 的右边。 我们从右向左遍历字符串，并维护两...

0 点赞评论收藏

2025-09-18 14:01

广东技术师范大学 C++

题解 | #时间转换#

题目链接 时间转换 题目描述 给定一个12小时制的时间字符串（例如 08:03:45PM），请将其转换成24小时制的时间字符串（例如 20:03:45）。 特殊规则说明：  午夜 12:00:00AM 对应24小时制的 00:00:00。 中午 12:00:00PM 对应24小时制的 12:00:00。  解题思路 这是一个简单的字符串处理和逻辑判断问题。核心在于正确处理小时部分的转换，分钟和秒钟部分保持不变。 我们可以将输入字符串 HH:MM:SSAM 或 HH:MM:SSPM 分为三个部分来处理：  小时 HH 分钟和秒 MM:SS 上午/下午标识 AM 或 PM  转换的逻辑可以根据标识...

0 点赞评论收藏

2025-09-18 14:00

广东技术师范大学 C++

题解 | #计数器#

题目链接 计数器 题目描述 一个计数器的工作方式如下：   在  时，显示数字 。   在接下来的每个时刻，数字减 ，直到变为 。   当数字变为  后，在下一个时刻，计数器会重置，新显示的数字是上一个计数周期初始值的两倍。然后重复第2步。   例如：   ，值分别为 。（周期1，初始值为3）   ，值重置为 。   ，值分别为 。（周期2，初始值为6）   ，值重置为 。   给定一个时刻 ，求出该时刻计数器显示的值。 解题思路 这是一个规律探索问题。由于  的范围非常大（可达 ），我们不能通过模拟来求解，必须找出其中的数学规律。 1. 分析计数周期 我们来分析每个周期的初始值和起始时刻： ...

0 点赞评论收藏

2025-09-18 13:56

广东技术师范大学 C++

题解 | #非整除集合#

题目链接 非整除集合 题目描述 给定一个由正整数组成的集合 S，以及一个整数 K。 需要找出一个最大的子集，使得该子集中任意两个数字的和都不能被 K 整除。输出这个最大子集的元素数量。 解题思路 这个问题的核心在于模运算。一个数 a 加上一个数 b 的和能否被 K 整除，完全取决于它们各自对 K 的余数。 (a + b) % K == 0 等价于 (a % K + b % K) % K == 0。 这启发我们将原问题从处理可能很大的整数，转化为处理 0 到 K-1 范围内的余数。 1. 核心思想：按余数分组 我们可以遍历一次输入集合，用一个频率数组（或哈希表）counts 来统计每个余数（从 ...

0 点赞评论收藏

2025-09-18 13:45

广东技术师范大学 C++

题解 | #回文数索引#

题目链接 回文数索引 题目描述 给定一个仅由小写字母组成的字符串。 请找出一个位置（下标从0开始），删掉那个字母之后，字符串变成回文。  题目保证，如果字符串本身不是回文，则总会有一个合法的解。 如果给定的字符串已经是一个回文串，那么输出-1。  解题思路 本题是经典回文判断的变种，最高效的解法是使用双指针。 核心思想 我们使用两个指针，一个从字符串的开头 l 开始，另一个从结尾 r 开始，同时向中间移动并比较对应位置的字符。   寻找不匹配点：  当 s[l] 和 s[r] 相等时，说明这对字符符合回文的要求，我们可以继续向内收缩指针（l++, r--）。 当第一次遇到 s[l] != s[...

0 点赞评论收藏

2025-09-18 13:44

广东技术师范大学 C++

题解 | #最佳配对#

题目链接 最佳配对 题目描述 给定两个长度为 N 的整型数组 A 和 B。如果 A[i] == B[j]，则 (i, j) 可构成一个配对。 一个“最佳配对集合”是指一系列配对，其中 A 和 B 的每个索引最多只出现一次。 你的任务是修改 B 中的一个元素，使得“最佳配对集合”的规模（即配对数量）最大。输出这个最大数量。 解题思路 这个问题的核心在于分析单次修改操作对总配对数的影响。我们可以通过频率统计和贪心分析，在接近线性的时间内找到最优解。 1. 计算初始配对数 首先，如果不做任何修改，能形成的最大配对数是多少？ 对于任意一个数值 v，它在 A 中出现了 countA[v] 次，在 B 中...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：