小红的校招笔试 [题目链接](https://www.nowcoder.com/practice/15eb5f67d766438fb85aa11984edd88f) 思路 小红参加校招笔试，已知所有人的成绩，通过率为 50%（向下取整），需要判断小红是否通过。 关键规则  通过人数：，即前  名通过。 并列通过：如果有多人与第  名分数相同，这些人全部通过。 特判：只有 1 人时直接通过（因为 ，需要特殊处理）。  做法 将所有成绩降序排序，找到第  名的分数作为通过线（threshold = a[k-1]，0 索引）。小红的分数  通过线即通过。 并列规则不需要额外处理——只要小红分数  通...

小红的回文子串 [题目链接](https://www.nowcoder.com/practice/10121932b5c74142b4e54f2972520c95) 思路 给定一个长度为  的字符串  和一个正整数 ，统计  中有多少个长度为  的连续子串是回文串。 暴力枚举 长度为  的连续子串共有  个，起始下标从  到 。对于每个子串，用双指针从两端向中间逐字符比对，判断是否为回文串。 具体步骤：  枚举起始位置 ，范围 ； 对子串 ，令 ，逐步比较  和 ； 若所有对称位置字符都相同，则计数加 1。  样例演示 输入 ，字符串 abaaa：  ：子串 aba，a == a，b 是中心 ...

小红修道路 [题目链接](https://www.nowcoder.com/practice/b22011bdda6f43ddb9a34933ea5d737f) 思路 有一个  个点  条边的无向图，小红计划修  条从 1 号点出发的道路。每条计划道路指定了终点  和长度 。问：最多能少修多少条路，使得从 1 号点到其他所有点的最短距离不变？ 关键观察 把所有计划修的道路也当做边加到图里，跑一遍 Dijkstra，得到每个点的最短距离 。 对于一条计划道路 ：  如果 ，它根本不在任何最短路上，一定可以省掉。 如果 ，它可能是到达  的最短路径之一。但如果存在其他方式也能用  的代价到达 ，那...

小红的矩阵 [题目链接](https://www.nowcoder.com/practice/c77b7301464f4cfcacc9492a3c999f65) 思路 给一个  的矩阵，第  行第  列的元素为 ，求矩阵中第  小的元素。 暴力行不通 如果  很大，我们没法真的把所有  个元素排序——那可能有  个数。 二分答案 换个角度想：如果我们猜一个值 ，能不能快速算出矩阵里有多少个元素 ？ 对于第  行，元素分别是 。其中  的有  个。把所有行加起来就得到总个数： $$ 这个求和只需要  时间。 二分框架  如果 ，说明答案 ，缩小右边界。 如果 ，说明答案 ，抬高左边界。  二分范...

月考成绩 [题目链接](https://www.nowcoder.com/practice/a607d73208a043a6ab73aecb1c49e63a) 思路 每位同学有语文、数学、英语三科成绩。如果存在另一位同学总分比自己高，但至少有一科成绩比自己低，则该同学会产生优越感。求有多少同学会产生优越感。 条件转化 对同学 ，优越感条件为：存在同学 ，满足  且 ( 或  或 )。 取反来看，同学  不会产生优越感，当且仅当：  没有任何同学总分比自己高，或者 所有总分比自己高的同学，三科成绩都分别  自己。  条件 2 等价于：总分严格高于  的所有同学中，语文最小值 ，数学最小值 ，英语...

判断数组是否包含重复的字符串 [题目链接](https://www.nowcoder.com/practice/aec7ce39075142719339a0e77115f4f3) 思路 本题要求判断一组字符串中是否存在重复。 哈希集合判重 最直接的方法是利用哈希集合（HashSet）：依次读入每个字符串，尝试将其加入集合。如果加入失败（说明集合中已存在该字符串），则存在重复，输出 true；如果所有字符串都能成功加入，则无重复，输出 false。 等价地，也可以先把所有字符串读入数组，比较数组长度和去重后集合大小是否相等。 样例演示  输入 hello world：两个不同的字符串，集合大小等...

小阅的阅读计划 [题目链接](https://www.nowcoder.com/practice/3fab21c915b74a15a591d6c8ce5735ff) 思路 本题是经典的 0/1 背包问题。有  本书，每本书有一个花费 （所需阅读积分）和价值 （收益），总共有  个阅读积分，每本书最多选一次，求能获得的最大价值。 动态规划 定义  表示恰好使用  个阅读积分时能获得的最大价值。初始时 ，其余为 。 对于每本书 ，从大到小枚举容量 （从  到 ），进行转移： $$ 为什么要倒序枚举？ 因为是 0/1 背包，每本书只能选一次。如果正序枚举， 可能已经包含了当前这本书的贡献，相当于同一...

智能机器人 [题目链接](https://www.nowcoder.com/practice/c2f86680fc9241f2a0659b95d8d3d6e2) 思路 本题是经典的迷宫最短路径问题：在  的网格中，从起点 s 到终点 e，每次可以上下左右移动一步，# 不可通行，求最少步数，不可达输出 。 为什么用 BFS？ 每一步的代价都是 （无权图），BFS 天然保证第一次到达某个格子时的步数就是最短步数。这是 BFS 的核心性质：按层扩展，层数即距离。 具体做法  遍历网格，找到起点 s 和终点 e 的坐标。 用一个  的距离数组 dist，初始化为 （表示未访问），将起点距离设为  并入...

小红的旅游攻略 [题目链接](https://www.nowcoder.com/practice/75744bcb2731427393cf65e513a27a68) 思路 小红最多选择 3 个相邻的景点，按顺序写进攻略。总时间（浏览时间 + 交通时间）不超过 ，要使总价值最大。 分情况讨论 由于最多选 3 个景点，我们可以按选择的景点数量分三种情况枚举： 情况一：选 1 个景点  总花费为 ，总价值为 。遍历所有景点即可。 情况二：选 2 个相邻景点  枚举每条边 ，总花费为 ，总价值为 。 情况三：选 3 个景点  三个景点形成一条路径 ，其中  是中间节点， 和  都是图中的边。 总花费 ...

小红直播 [题目链接](https://www.nowcoder.com/practice/3df5f72717a344019124a646c045579c) 思路 简单模拟题。按天顺序处理，每天先上班再直播：  上班  小时，焦虑度增加 ； 直播  小时，焦虑度减少 ； 如果焦虑度变为负数，将其置为 。  遍历所有  天后输出最终焦虑度即可。 样例演示 ，上班时间 ，直播时间 ：  第 1 天：，直播后 。 第 2 天：，直播后 。 第 3 天：，直播后 。  输出 。 代码    C++   Java   Python3   JavaScript   #include <bits/s...

小红背单词 [题目链接](https://www.nowcoder.com/practice/b3d0fa1c43c44e0580654cb93c1bfdb9) 思路 题意理解 小红按顺序背单词。如果她当前已经记住了  个单词，那么她需要遇到某个未记住的新单词  次才能记住它。  初始 ，第一个未见过的单词只需出现  次就能记住。 记住第一个后 ，下一个未记住的单词需要出现  次。 以此类推。  已经记住的单词再次出现时直接跳过，不需要任何处理。 模拟过程 从前到后扫描单词序列，用一个哈希表记录每个未记住的单词当前出现了多少次，用一个集合记录已经记住的单词。 对于当前单词 ：  如果  已经记...

小红的回文串 [题目链接](https://www.nowcoder.com/practice/b0c3a7aecb0a47ab865602585f4402a7) 思路 题目允许对字符串进行三种操作：拆分（'w' -> 'vv'，'m' -> 'nn'）、轴对称（'b' <-> 'd'，'p' <-> 'q'）、翻转（'b' <-> 'q'，'d' <-> 'p'，'n' <-> 'u'）。问经过若干次操作后，字符串能否变成回文串。 等价字符分析 通过轴对称和翻转操作，可以得到以下等价关系：  'b' 可以变成 'd'（轴...

小红的矩阵 [题目链接](https://www.nowcoder.com/practice/df690022406d4e8d8594890f3e109cde) 思路 简单模拟题。读入一个  的矩阵，统计所有元素中个位数为  的个数。 判断一个整数  的个位是否为 ，只需检查 x % 10 == 9 即可。 遍历矩阵中每一个元素，对满足条件的计数，最后输出计数结果。 代码 [sol-C++] #include <bits/stdc++.h> using namespace std; int main(){ int n, m; scanf("%d%d", &amp...

小红的好数组 [题目链接](https://www.nowcoder.com/practice/b8c3a24867c246f7a04da28e5da646ee) 思路 问题转化 "好数组"定义为存在至少一个长度为 3 的非降序连续子数组，即存在某个  使得 。我们需要通过最少的修改次数，使数组中不存在任何这样的三元组。 定义相邻对的关系：（ 或 ）。那么出现"坏三元组"等价于存在连续两个 。因此目标是：修改最少的元素，使得  数组中没有连续的两个 。 关键观察：修改一个元素的效果 修改  时，可以自由选择新值，从而控制 （ 与  的关系）和 （ 与  ...