题目 给定一个长度为 的数组 ，其元素只有 0 和 1。最多可以将数组中 个元素从 0 改为 1。问：更改后，只包含元素 1 的所有子数组中，最长的子数组长度。 解题思路 尺取法 使用双指针来确定一个移动窗口 。 如果窗口内 0 的个数小于等于 ，则将 右移，扩大窗口，并更新最大长度 ，直至 0 的个数大于 。 如果窗口内 0 的个数超过了 ，则将 右移，直至窗口内 0 的个数小于等于 ，继续步骤 1，直到遍历完数组中的所有元素。 C++代码 class Solution { public: /** * * @param n int整型 *...

题目 牛牛有一个长度为 n 的字符串，他想进行循环右移 k 位的操作，求他最少对这个字符串进行几次区间反转操作能实现循环右移 k 位呢。给定一个字符串长度 n 和循环右移次数 k，求最少反转次数。假设字符串每一位都不同。 解题思路 令 ，三步翻转法： 将数组第 项进行对称翻转，即对数组前 项进行翻转； 将数组第 项进行对称翻转，即对数组后 项进行翻转； 将数组第 项进行对称翻转，即对整个数组进行翻转。 所得数组即为循环右移 项的结果。 例如，字符串 12345678，想要进行循环右移 3 位的操作，可以执行： 先将字符串前 5 个字符进行翻转，得 54321678。 再将...

题目 在遥远的斯卡布罗集市，有机分子只能由 C, H, O 三种元素组成。根据珂学家们的探测，一个 C 原子的式量为 13，一个 H 原子的式量为 1，一个 O 原子的式量为 17。一个有机分子的式量恰为各个原子的式量的总和。 对于有机分子式给出如下定义： 有机分子式只可能包含数字、括号和 C, H, O 三种元素标记； 数字只能出现在元素标记或右括号的右边，代表该元素（或括号内的分子式）重复出现的次数； 数字只可以是不包含前导零的正整数； 如果一个元素右侧没有数字，那么表示该元素只出现一次； 括号内包含非空的有机分子式，但该有机分子式不再嵌套括号。 例如 (HH)3H(H)、CO2、CH...

题目 我们认为，假如一句话里含有 2 ，那么这句话很二次元。同时，QQ 群里的二次元浓度由二次元话的数量的占比决定。现在 Sabit 给你看了一眼群里的聊天记录，希望可以知道群里的二次元浓度是多少。 解题思路 使用 string 库中的 getline() 函数读取一行字符串。使用变量 cnt 记录二次元话的数量。 C++代码 #include<iostream> #include<iomanip> using namespace std; int main(){ int T, n; cin >> T; string words; ...

题目 上课的时候总有一些同学和前后左右的人交头接耳。不过，班主任发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 对同学上课时会交头接耳。同学们在教室中坐成了 行 列，坐在第 行第 列的同学的位置是 。为了方便同学们进出，在教室中设置了 条横向的通道， 条纵向的通道。班主任为了减少上课时交头接耳的学生，她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。 解题思路 记录行 与行 之间交头接耳的学生的对数。 记录列 与列 之间交...

题目 牛牛用 playfair 加密信息。加密过程中的 都由 来代替。playfair 加密算法首先需要绘制密码表，密码表是一个 的矩阵，开始由密钥按顺序排列，其余按照未出现的字母顺序。若密钥中含有重复字母需要将重复字母去掉，若有 用 来代替。 加密明文需要符合以下规则：将明文中每两个字母组成一对，若成对后是两个相同字母或留下一个字母无法成对，则不进行变化直接放入密文中。明文对 在同一行，对应密文对 分别为紧靠 右端的字母，最后一列右端对应第一列。明文对 在同一列，对应密文对 分别为紧靠 下方的字母，最后一行下方对应第一行。明文对 不在同一行且不在同一列，对应密文对 ...

题目 给定 n 个数，对每个数可以进行 +1 或 -1 操作，但对于每一个数，该操作最多只能执行一次。目标是：使用最少的操作次数，将这几个数构造成一个等差数列。如果完全不能构造成功，就输出 -1。 解题思路 枚举序列 b 中前 2 个数的操作，每个数有 3 种操作（+1，-1，+0），所以共有 9 种情况。每种情况确定了一个等差数列，因为等差数列的首元素 a1 和公差 d 已确定。判断后面的数是否符合这个等差数列。 C++代码 class Solution { public: /** * 返回最少多少次操作后能使这几个数变成一个等差数列，如果完全不能构造成功，就返回-1 ...

题目 给定 n 个瓶子以及 n 个瓶子中的含水量，牛牛要求瓶子中的水最少为 x，所以他打算对这些瓶子里的水进行重新分配。牛牛的分配规则是：每次可以选择多个瓶子，将里面的水平均分配到已选择的瓶子中。求最多可以有多少个瓶子满足牛牛的要求？ 解题思路 按瓶子中的含水量从大到小对瓶子序列 进行排序。从头到尾遍历瓶子。 如果瓶子的含水量 ，满足要求， 加一，并将多余的水 累加计入 中。 如果瓶子的含水量 ，判断剩余的水加当前瓶子中的水是否满足要求，如果满足， 加一，剩余水量为 ；否则，跳出循环，因为后面的瓶子含水量更少。 最后，返回 。 C++代码 class Solution { publi...

题目 牛牛有一个边长为 1 的正六边形，只要牛牛一推它就可以一直滚下去，正六边形左下角为 A。如图是正六边形翻滚一次的情况。给定正六边形翻滚次数 k，求 A 点翻滚轨迹长度。 解题思路 第 1 次翻滚的轨迹长度为 ，其中 。第 2 次翻滚的轨迹长度为 ，其中 。第 3 次翻滚的轨迹长度为 ，其中 。第 4 次翻滚的轨迹长度为 ，其中 。第 5 次翻滚的轨迹长度为 ，其中 。第 6 次翻滚的轨迹长度为 0，因为此时的滚动是以 A 点为圆心的。翻滚完成后，A 点位于六边形左下角。 先计算六边形翻滚的完整的周期（即点 A 从六边形左下角翻滚至六边形左下角）次数 n。再计算剩余的翻滚次数的轨迹长度。...

题目 给定一个文本串 s，再给两个串 a、b，文本串中的 a 都转换成 b，转换后的字符不再参与转换，输出最终的文本串。 解题思路 先在文本串 s 中寻找子串 a，记录下标。然后，从右向左将文本串 s 中的子串 a 替换成 b。 C++代码 #include<iostream> #include<vector> using namespace std; int main(){ string s, a, b; cin >> s >> a >> b; vector<int> indices; ...

题目 给定一个有 𝑁 个点的树，每条边的长度有一个边权，现在定义 𝑑𝑖𝑠(𝑖,𝑗) 代表第 𝑖 个点到第 𝑗 个点的距离模 2 之后的结果。问有多少 (𝑖,𝑗,𝑘) 满足，𝑑𝑖𝑠(𝑖,𝑗) = 𝑑𝑖𝑠(𝑗,𝑘) = 𝑑𝑖𝑠(𝑖,𝑘)。 解题思路 可以将两点的距离转换成到根节点的距离。可以任意选一个节点作为根节点，比如节点 1。 要么是 0，要么是 1。 同理，要使 ，则要 。同理，要使 ，则要 。综上，当 时，由 。 使用 DFS 算法计算从根节点 1 到每个节点的距离，并统计每种距离的数目。 表示 的节点数。 根据数学的排列，得出...

题目 小明现在要追讨一笔债务，已知有 n 座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为 1 的城市，欠债人位于编号为 n 的城市。小明每次从一个城市到达另一个城市需要耗时 1 天，而欠债人每天都会挥霍一定的钱，等到第 k 天后（即第 k+1 天）他就会离开城 n 并再也找不到了。小明必须要在他离开前抓到他（最开始为第 0 天），同时希望自己的行程花费和欠债人挥霍的钱的总和最小，请计算一下最小总和。 解题思路 使用 BFS 算法。 表示与编号为 的城市连接的城市。 表示从城市 到城市 这条道路中需要支付的...

题目 牛牛来到训练场里闯关，他的宝剑的耐久度降到了 2，这意味着牛牛最多只能打倒 2 只怪兽，否则将会被淘汰。训练场的地图可以看作一棵以 1 为根节点的树，训练场的终点为这棵树的叶子结点，树上的每个结点最多有一只怪兽，结点与结点间的边上没有怪兽。每一个有怪兽的结点上牛牛都需要打倒怪兽才算安全，并且牛牛一旦选定好打怪路线之后便不能走回头路。请问牛牛有多少种到达终点且不被淘汰的路径。 解题思路 使用 DFS 算法。 到达某个点时，判断此时的宝剑耐久度是否大于等于 0 且是否是叶子节点，若是，则累加计入 。 C++代码 /** * struct Point { * int x; * ...

题目 给定一个没有重复元素的数组 a，将数组内第 n 大的数字和第 m 大的数（从大到小排序）交换位置后返回数组。 解题思路 因为题目已说明数组 a 没有重复元素，所以可以使用 map 数据结构记录每个元素的下标，同时将数组中的元素按照从小到大排序。遍历 mp 中的元素，使用 k 表示它是第 k 大的元素，如果 k 与 n 或 m 相等，记录它们的下标，最后交换元素，返回数组 a。 C++代码 class Solution { public: /** * * @param a int整型vector 原始数组a * @param n int整型 第n大 ...