讨厌鬼的区间 [题目链接](https://www.nowcoder.com/practice/cd73e5d3f95949fb9664b26b0078b229) 思路 有三个区间 、、。两个人分别选择不同的区间，然后各自在自己的区间内选一个数，要求所选的数也必须在对方的区间内，使两数之和最大。 关键观察 两个人选了区间  和区间 （）后，他们各自选的数必须同时属于两个区间，即必须落在交集  中。 为了让两数之和最大，两人都应选交集中的最大值 ，此时和为 。 如果交集为空（即 ），则该组合无效。 枚举所有组合 三个区间中选两个不同的，共  种组合。对每种组合计算交集，若非空则记录 ，取所有有效...

讨厌鬼的数组构造 [题目链接](https://www.nowcoder.com/practice/883192b10c7a4527a469abe5967c7905) 思路 给定长度为  的序列 ，要求构造一个长度为  的序列 ，满足：   （ 从  开始编号） 所有  互不相同  确定候选值 对于位置 ，条件  等价于 。 设 ，若  则令 。则  的候选值为 。由于 ，当  时从  开始取。 贪心策略 关键观察：编号越大的位置，步长越大，可选的值越稀疏。因此应该优先给大编号的位置分配值，再给小编号的位置分配——小编号位置步长小，候选值密集，容易找到未被占用的值。 具体做法：从  到  倒序...

小红的圆构造 [题目链接](https://www.nowcoder.com/practice/3309f6e285f04c74a8ee4804210224ca) 思路 给定一个坐标为  的点（），要构造一个同时与两条坐标轴相切且经过该点的圆，输出两个解的半径（升序）。 圆的性质 与两条坐标轴都相切的圆，其圆心到  轴和  轴的距离都等于半径 。因此圆心坐标为 。 由于点  在第一象限（），只有圆心在  的情况才能使圆经过该点（其他象限的圆心会导致距离过大或无解）。 列方程 圆心 ，半径 ，经过点 ： $$ (x - r)^2 + (y - r)^2 = r^2 $$ 展开： $$ x^2 -...

小红的元音距离 [题目链接](https://www.nowcoder.com/practice/65409356ae9a43668ac23fb14c78372d) 思路 题目定义字符串的"权值"为最远两个元音字母之间的距离。如果元音数量不超过 1，权值为 0。要求删除一些字母，使剩余字符串的权值尽可能大，问最多能删除多少个字母。 关键观察 在剩余字符串中，权值 = 最后一个元音的位置 - 第一个元音的位置（位置是在剩余字符串中的下标）。删除一个处于首尾元音之间的字符，会让剩余字符串变短，权值减少 1。因此，首尾元音之间的字符不能删。 而首个元音之前、末尾元音之后的字符，对...

小红的数组构造 [题目链接](https://www.nowcoder.com/practice/8844c80d55534f4e99bc0c1184a052e8) 思路 构造一个长度为  的数组，要求所有元素互不相同，且  恰好等于 ，同时使元素之和最小。 关键观察 所有元素的 ，意味着每个元素都必须是  的倍数。设数组元素为 ，其中  为互不相同的正整数，且 （否则公因子可以提出来， 就会大于 ）。 要使总和  最小，只需让  尽量小。 最优构造 取 （即 ），此时：  元素互不相同。 ，所以原数组的 。 和 ，这已经是最小的  个不同正整数之和，不可能更小。  样例验证  ：数组为 ，和...

小红的不动点 题目描述 对于一个数组，如果一个元素的值等于它在数组中的出现次数，那么称这个元素是"不动点"。给定一个数组，求数组中有多少个不动点。 注意：答案统计的是元素个数而非不同值的个数。例如数组中有 3 个 3，且 3 恰好出现了 3 次，则这 3 个元素都是不动点，贡献 3 而非 1。 思路分析 本题是一道简单的哈希计数模拟题。  统计频次：遍历数组，用哈希表记录每个元素出现的次数。 逐一判定：再次遍历数组，对每个元素 ，若  等于其出现次数 ，则答案加 1。  示例推演 以示例 1 [2, 1, 2, 3, 3, 3] 为例：    值 出现次数 是否为不动点  ...

连续子数组最大和 [题目链接](https://www.nowcoder.com/practice/3e35a0679ec94df69e7db3b6e6bbf8fd) 思路 本题是经典"最大子数组和"（Kadane 算法）的变体：允许最多将一个元素替换为给定值 ，求连续子数组的最大和。 状态定义 用两个变量滚动更新即可，无需开数组：  ：以当前位置结尾的最大子数组和，未做任何替换； ：以当前位置结尾的最大子数组和，恰好替换了一个元素。  转移方程 对于位置 ： $$ 含义与标准 Kadane 完全一致——要么从当前位置重新开始，要么延续之前的子数组。 $$ 三种情况分别对应...

截断电话号码 [题目链接](https://www.nowcoder.com/practice/078d1abcb55648f687a78d87e4b3cb69) 思路 牛牛用带短横线的格式记录电话号码，号码后面会跟若干以 # 开头的备注。拨打电话时，需要去掉备注部分，只保留数字和短横线组成的电话号码。 观察规律 输入字符串的结构是：电话号码 备注...，其中电话号码由数字 0-9 和短横线 - 组成，备注以空格分隔、以 # 开头。 因此，从字符串开头开始，连续的数字和短横线就是我们要的电话号码。遇到第一个不是数字也不是短横线的字符（通常是空格），就停止。 方法一：正则表达式 用正则 ^[\d...

公式计算器 [题目链接](https://www.nowcoder.com/practice/b2ee481ca45c4c57b6ef5dfad1c86197) 思路 题目要求读入一个包含加、减、乘、幂四种运算的公式字符串，计算并输出结果。公式中可能出现 pow(a, b) 形式的幂运算。 Python / JavaScript：直接 eval Python 内置 pow 函数，直接 eval(input()) 即可完成全部计算。 JavaScript 中没有全局 pow，但有 Math.pow，因此将输入中的 pow( 替换为 Math.pow( 后再 eval 即可。 C++ / Java...

数字颠倒 [题目链接](https://www.nowcoder.com/practice/85e86ccfc6f248468aa7777affb834ca) 思路 题目要求将输入的整数颠倒后输出。注意样例 123000 的期望输出是 000321，而不是 321，说明翻转后的前导零需要保留。 因此不能把输入当作数字处理，而要当作字符串读入，直接反转字符串后输出即可。 步骤  将输入作为字符串读入。 反转该字符串。 输出反转后的结果。  复杂度  时间复杂度：，其中  为数字的位数。 空间复杂度：。  代码    C++   Java   Python3   JavaScript   #inc...

无穷大二叉树的最近公共祖先 [题目链接](https://www.nowcoder.com/practice/7db533ff46704fd3922c1b26d2cf6fd5) 思路 有一棵无穷大的满二叉树，结点按层序从 1 开始编号。给定两个结点  和 ，求它们的最近公共祖先（LCA）的编号。 满二叉树的性质 在按层序编号的满二叉树中，结点  的父结点编号为 。这是因为第  层有  个结点，编号从  到 ，左孩子编号为 ，右孩子编号为 。 求 LCA 的方法 利用父结点 =  这一性质，不断将编号较大的结点向上移动（除以 2），直到两个结点相遇：  若 ，令 ； 若 ，令 ； 当  时，即为...

牛牛逆序输出 [题目链接](https://www.nowcoder.com/practice/d981181ce18e4cce945fdf52daf037a1) 思路 给定一个正整数 （保证个位数不为 ），将其逆序输出。 做法 由于个位不为 ，逆序后不会出现前导零的问题，因此最简单的做法是将整数作为字符串读入，直接反转后输出。 各语言实现：  C++ 中用 std::reverse 原地反转字符串； Java 中用 StringBuilder.reverse()； Python 中用切片 [::-1]； JavaScript 中用 split('').reverse().join('')。 ...

牛牛的数组匹配 [题目链接](https://www.nowcoder.com/practice/3d3406f4a7eb4346b025cc592be5b875) 思路 给定数组 （长度 ）和数组 （长度 ），找出  中连续子数组之和与  最接近的那一段。若有多段同样接近，取起始位置最靠左的。 做法：前缀和 + 二分查找 设 ，（）。 子数组  的和为 。我们需要找使  最小的  对，即对每个起点 ，在  中找最接近  的值。 由于题目保证数组元素均为正整数，前缀和严格递增，因此可以用二分查找在  时间内定位最接近的位置。对每个 ，检查二分定位点及其左邻两个候选即可。 遍历所有起点 ，维护全...

快乐的字符串 [题目链接](https://www.nowcoder.com/practice/7f4875507c654debb8e02084edbc4fd7) 思路 本题是一道简单的字符串匹配题。给定一个字符串 ，判断其中是否包含以下四个子串之一：  cheerful glad happy pleased  只要包含任意一个，就输出 Yes，否则输出 No。 做法 直接使用语言内置的子串查找函数即可：  C++ 中用 string::find，返回值不等于 string::npos 表示找到； Java 中用 String.contains； Python 中用 in 运算符； JavaS...