题目链接 建物流中转站 题目描述 给定一个二维平面网格，1 代表房子，0 代表空地。 需要找到一个空地来修建一个物流中转站，使得这个中转站到所有房子的曼哈顿距离之和最小。  曼哈顿距离：。 如果能修建，返回最小的距离和。 如果网格中没有空地，返回 -1。  解题思路 这是一个经典的优化问题，可以通过维度分离和动态规划的思想，在  的时间内高效解决，其中  是网格的边长。 1. 核心思想：维度分离 我们希望最小化的目标函数是所有房子到中转站 (r, c) 的距离之和 S：  这个公式可以被拆分为两个完全独立的一维问题：  这意味着，我们可以独立地计算如果中转站建在第 r 行的总行距，和建在第 c...

题目链接 连续子数组最大和 题目描述 输入一个整型数组（数组里可能有正数、负数和零），求其中一个连续子数组（最少包含一个元素）的和的最大值。 要求时间复杂度为 。 解题思路 这是一个非常经典的算法问题，最优解法是使用动态规划或一种称为“Kadane's Algorithm”的在线处理思想，可以在一次遍历中解决问题。 核心思想： 我们从头到尾遍历数组，同时维护两个变量：  current_max：表示以当前元素结尾的连续子数组的最大和。 global_max：表示到目前为止，在所有子数组中发现的最大和，也就是我们最终的答案。  状态转移逻辑： 当我们遍历到数组的第 i 个元素 a[i] 时，我们...

题目链接 墙壁划线 题目描述 一块矩形墙壁由  块尺寸为  的瓷砖构成。 现在要从墙壁的左上角向右下角、右上角向左下角划两条对角线。 请问，这两条对角线与所有瓷砖的边界线（包括墙壁外边界）总共产生了多少个交点？ 解题思路 这是一个有趣的几何计数问题，其解法不依赖于瓷砖的具体尺寸  和 ，而只与瓷砖的行列数  和  有关。 问题的关键是精确理解题目要求：计算对角线与瓷砖边界线相交形成的点有多少个。这意味着，两条对角线自身的交点（矩形中心），只有当它恰好落在某条边界线上时，才被计数。 我们可以将问题分解：  计算单条对角线与网格线（瓷砖边界）的交点数。 使用容斥原理合并两条对角线的结果，处理共同的...

题目链接 小红购物 题目描述 小红准备买  件物品，第  件物品的价格是 。 另外，小红有  种优惠券，第  种优惠券的信息为 ，表示：买一件价格不小于  的商品时，可以减去  的价格。  每件商品最多只能用一次优惠券。 每种优惠券可以用多次（用于不同的商品）。  小红想知道，自己买下全部  件商品最少需要花多少钱？ 解题思路 这是一个典型的贪心问题。我们的目标是最小化总花费，这等价于最大化总折扣。 1. 单件商品的最优策略 对于任何一件商品，要想让它的最终价格最低，我们就应该为它匹配一张能提供最大折扣的、并且可用的优惠券。 一张优惠券  对于价格为  的商品是“可用”的，当且仅当 。 因此，...

题目链接 小红的顺子 题目描述 小红有一个长度为  的数组 ，其中的元素是  到  的排列中移除了一个数后得到的。 求这个数组能构成的顺子的最大长度。 顺子的定义为：一个序列中的数是连续递增的整数。例如，[1, 2, 3] 和 [8, 9] 都是顺子。 解题思路 这个问题的核心是找出给定数字集合中，最长的连续整数序列的长度。 例如，对于输入 1 2 4 5，我们拥有的数字集合是 {1, 2, 4, 5}。在这个集合中，最长的连续整数序列是 1, 2 和 4, 5，它们的长度都是2，所以最大长度是2。 原始数组中元素的顺序并不影响我们能构成的顺子，因此，最直接的解法是：   排序：首先对输入的数...

题目链接 小红的魔法药剂 题目描述 小红需要  种不同的魔法药剂。 她可以花  的价格购买第  种红色版本的魔法药剂。 她也可以用第  种和第  种红色版本的药剂来配置出第  种蓝色版本的药剂。 小红想知道，她最少需要花多少钱才能得到从 1 到  所有种类的魔法药剂（红色或蓝色均可）。 解题思路 这是一个典型的贪心问题，其核心在于每个决策都是独立的。 对于  到  的每一种魔法药剂 ，我们都有两种获取它的方式：  直接购买红色版：成本为 。 配置蓝色版：成本为 ，其中  和  是配置第  种药剂所需的两种红色药剂的编号。  关键在于，为某一种药剂做出选择（是购买还是配置）并不会影响到其他任何药...

题目链接 Y型树 题目描述 给定  个顶点，你可以用这些顶点构成一棵树。 如果这棵树恰好只有三个叶子节点（度为1的节点），我们称之为“Y型树”。 请问，用这  个顶点可以构建出多少种不同的Y型树？ 结果需要对  取模。 解题思路 1. 问题解读：有标号 vs. 无标号 虽然题目提到了“顶点”，通常在图论中暗示顶点是带标号的，但题目的样例揭示了问题的本质。  对于 ，如果顶点有标号，我们可以任选一个点作为中心（度为3），剩下3个点作为叶子。这样有  种不同的树。但这与样例输出“1”矛盾。 对于 ，样例输出“2”。  这说明题目实际上是在问，有多少种结构上不同（同构）的Y型树，即这是一个无标号图的...

题目链接 小红的蛋糕切割 题目描述 小红有一个  的矩形蛋糕，每个区域都有一个美味度。 她希望切割出一个正方形的小蛋糕给自己吃，剩下的部分给小紫吃。 她希望两人吃的部分的美味度之和尽可能接近。设小红吃的美味度之和为 ，小紫吃的为 ，请你输出  的最小值。 解题思路 这是一个在矩阵中寻找最优子结构的问题。我们可以通过问题转化和二维前缀和来高效解决。 1. 问题转化 设整个蛋糕的总美味度为 。 小红切走一块美味度为  的正方形，则小紫吃剩下的部分，其美味度 。 我们需要最小化 。 将  代入，得到：  因此，原问题转化为：遍历所有可能的正方形区域，计算其美味度之和 ，并找到使  最小的值。 2. ...

题目链接 小苯的区间删除 题目描述 给定一个长度为  的数组 ，他必须选择一个连续的区间  并将其删除。 剩下的前缀部分和后缀部分（如果存在）将按原顺序拼接在一起，形成一个新数组。 我们需要计算，有多少种不同的区间 （）的选择方案，可以使得最终拼接成的数组是单调不降的。 注意：空数组和只包含一个元素的数组也算作有序。删除整个数组也是一种合法的方案。 解题思路 这个问题要求我们统计满足特定条件的区间数量。暴力枚举所有  个区间并进行  的检查，总复杂度为 ，会超时。我们需要更高效的方法。 1. 结构分析 删除区间  后，留下的数组由前缀  和后缀  拼接而成。要使新数组有序，必须满足三个条件： ...

题目链接 小红的好数组 题目描述 小红定义一个数组为“好数组”，当且仅当这个数组至少存在一个长度为 3 的非降序子数组（连续的）。 小红可以进行多次操作，每次操作可以修改数组中的一个元素的值为任意整数。 小红想知道，至少需要操作几次，才可以把这个数组变成“不是好数组”。 解题思路 这个问题的目标是消除所有长度为 3 的非降序子数组。这是一个典型的动态规划问题，因为当前位置的决策依赖于之前的状态，并且我们需要求解一个最优值（最少操作次数）。 1. “不是好数组”的结构 一个数组“不是好数组”，意味着对于任意索引 ，都不满足 。 换句话说，一个“不是好数组”中，最长的连续非降序子数组的长度不能超过...

题目链接 分组 题目描述 有  个同学，老师要把他们分成若干组。 每个组的同学数量必须不少于 3 个人。 请问这  个同学最多可以分成多少组。 解题思路 这是一个简单的最优化问题，可以通过贪心策略来解决。 核心思想 我们的目标是最大化分组的数量。 为了让分出的组数最多，我们应该让每个组包含的人数最少。 根据题目要求，每个组的同学数量不少于 3 人，所以每个组的最少人数就是 3 人。 推导 因此，最优的策略就是尽可能多地分出“3人小组”。 对于  个同学，我们可以分出的小组数量就是  除以 3 的整数商。 例如，如果有 8 个同学，8 / 3 = 2。我们可以分出 2 个小组（比如一个 3 人组...

题目链接 小红的多彩糖葫芦 题目描述 小红有一串多彩糖葫芦，按从上到下的顺序由一个字符串表示。 她从上往下吃，但有一个强迫症：绝不会连续吃两个相同颜色的糖葫芦。 一旦她发现下一颗糖葫芦和刚吃过的颜色相同，她就会把整串都丢掉。 我们需要计算她最终会吃掉几颗糖葫芦。 解题思路 这是一个简单的模拟问题，我们只需要按照题目的描述，模拟小红吃糖葫芦的过程即可。 核心逻辑 我们可以从头开始遍历代表糖葫芦颜色的字符串，模拟小红的决策过程。   初始化：  如果字符串为空，小红一颗也吃不到，答案为 0。 如果字符串不为空，小红至少会吃第一颗。因此，我们可以设置一个计数器 eaten_count，初始值为 1。...

题目链接 小红的校招笔试 题目描述 共有  位同学参加校招笔试，给出了所有人的分数。 过线规则如下：  过线率为 50%，过线人数为  (向下取整)。 过线分数线为第  名同学的分数。 所有分数大于或等于过线分数线的同学都会过线。 如果只有 1 位同学，该同学必然过线。  小红是第一个输入分数的同学，问她最终是否能过线。 解题思路 这个问题的核心是确定“过线分数线”，然后将小红的分数与之比较。 1. 确定过线分数线 要找到第  名的分数，最直接有效的方法就是对所有分数进行排序。   我们将所有  个分数从高到低进行降序排列。   根据规则，过线人数为 （整数除法，自动向下取整）。   那么，分...

题目链接 小苯的比赛上分 题目描述 小苯有  个账号，初始分数分别为 。 他将进行  场比赛。根据名言“只要你永远使用分数最低的账号参赛，那么你的 max_score 将单调不降”，小苯在每场比赛前，都会选择当前所有账号中分数最低的一个去参赛。 第  场比赛会使参赛账号分数增加 。 我们需要计算并输出每场比赛结束后，小苯所有账号中的最高分是多少。 解题思路 这是一个动态模拟问题。我们需要维护一组不断变化的数据（账号分数），并高效地执行以下操作：  找到当前的最小值。 更新这个最小值（加上比赛得分）。 找到更新后的全局最大值。  由于比赛场次  和账号数量  都可能很大，简单的数组遍历（每场比赛...