题解： 考察点：贪心，动态规划，单调栈 常见错误： 如果除去输入只实现一个类的话，这是一个很经典的面试题目，很多同学在面试中都遇到过。但是因为这里的输入跟大家熟知的不太相同，很多同学拿着无从下手。其实面对这种没有给定个数的输入数据，有很多读入方法，其中最常见的就是当成字符串，以按照一行来读入，然后对字符串进行解析。但是最快的读入方法还是推荐使用。每次读入 1​ byte​ 的数据，并将其转换为类型的函数，且速度很快，可以用“读入字符——转换为整型”来代替缓慢的读入。同时在读入中修改只对数字有效，而略过","，我们一般称这种方法为读入优化，有关于更多的知识，可以上OI-wiki去学习。 方法一：...

字符串价值 题目难度：中等 知识点：数学逻辑，字符串，数组 解题思路：每一次减去当前字符串中出现次数最多的字符，重复K次后，即可得到价值最小的字符串。 方法一 使用优先队列。首先定义一个数组，用于存储字符串中每一个字符出现的次数，然后定义一个优先队列对每一个字符出现的次数由大到小进行排列，每一次循环，对次数最大的数字减一，直至循环到第k次为止，计算所有字符串出现的次数，最后将所有次数的平方和相加。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scann...

排序 题目难度：简单 知识点：数学逻辑，数组 解题思路：将数组按照从小到大的顺序排序，新旧数组中数值不相同的的总位置数即为题中需要移动的个元素的个数。 方法一 首先创建一个新的数组，使用不断循环的方式将旧数组中的值赋给新的数组，完成数组的复制。然后对新数组进行排序，最后对比两个数组在同一位置处的数值是否相同，统计数值不同的数量。 import java.util.*; public class Main{ public static void main (String args[]){ Scanner in =new Scanner(System.in); while (in.hasNext(...

回文素数 题目难度：中等 知识点：数学逻辑，数组 解题思路：首先判断数字是否为回文，然后判断数字是否为素数，若都是，则为回文素数。下面具体介绍回文和素数的判断方法。 方法一 回文的判断方法：对数字取余得到个位数字，然后对该数字除以十后取余，得到十位上的数字，随后继续除以十后取余获得百位上的数字，直至数字为0时停止。将各个位上的倒着排列组成新的数字，判断新数字是否与原来的数字相等，若相等，则为回文。素数的判断方法：若待判断数字为n,由2至n-1共进行n-2次循环，判断该数字是否能被n整除，若能则不是素数，若都不能，则是素数。 import java.io.*; public class Main...

编程题2 题目难度：中等 知识点：数学逻辑，数组 解题思路：首先，找到初始房间。然后，计算每轮分配情况。最后，计算初始人数。我们分三种情况来讨论初始房间room_i的位置，其中最后一次被分配的房间为room_x，再分配后房间内最少人数为p_min。1.room_i在room_x之后。按照每轮分配原则，room_x+1和room_i之间被分配p_min个人，room_i向后绕回room_x的房间则被分配pmin+1个人，可以计算出room_i的初始人数为 p_min×n+[n-(room_i-room_x)]。2.room_i在room_x之前。同理，room_i+1到room_x之间被分配p_...

题解 难度：中等 知识点：字符串的最长子串问题 分析 方法1：利用下标位置的普通方法,分a、b两种情况处理（较简单） 利用字符下标计算间隔长度，遍历字符串s，以b换a举例：返回所有b的索引值保存在数组中，存为数组indexes=[idx1,idx2,…]，（a换b一样）。计算m个b的最大间隔区间，如果b的个数小于等于m，即字符串中不足m个b，全部将他们替换成a即可；否则取“indexes[i]- indexes[i-m-1]-1”的长度的最大值max即为最大连续的相同字符的子串长度，但要注意首位元素的处理。 import java.util.ArrayList; import java.uti...

题解 难度：简单 知识点：数学问题 分析： 在本题中，踢赢比赛得一分，输了不等分也不见分，那么(1)总分一定等于n；同时要想是平局n%3=0；(2)还没有踢的比赛（n-k），要能弥补（d1+d2）的分数差，即n-k≥d1+d2；(3)满足以上两点的情况时，根据差值情况，有4种情况，如下：“1队>2队或1队<2队“ 与 “2队>3队或2队<3队”组合，假设1队的得分情况是m。① 当1队>2队，2队>3队时，3支队伍的得分情况是：m（max）m-d1m-d1-d2（min）  k=3m-2d1-d2在该情况下，1队得分最多，3队得分最少。要想达到平局，必须追上...

题解 难度：简单 知识点：字符串 整道题主要考察的就是字符串的知识和一些字符串函数，整体思路比较简单。现提供两种算法思路来解决问题。解题思路：因为要求输出的字符串要含有两个输入的字符子串，并且要求是最短的，那肯定是重复的部分越多越好，这样整个字符串就会越短。所以越早发现重复部分，结果越短。 方法一： 使用for循环，检查一下子从什么flag位置开始，后面的所有字符都可以从头匹配得到，此时这个位置的就是最近的，组合得到的字符即是最短的。 #include<iostream> #include<string> using namespace std; int main() ...

题解 难度：简单 知识点：数学逻辑 最大值只能出现在以下两种情况的较大值：  最大的三个正数的乘积 最小的两个负数*最大的正数的乘积  所以找出最大三个正数和最小的两个负数这5个数即可但是这道题要求时间复杂度o(n)，但是空间复杂度o(1)如果先把所有数存到数组中，然后排序找出这5个数，那么空间复杂度为o(n)所以不能将全部数存到数组再排序，只能在输入的过程中就把最大的三个数和最小的两个数存起来，最后比较最大值的组合即可 #include<iostream> #include<limits.h> using namespace std; int main() { int...

题解 难度：中等 知识点：数学逻辑 方法一：普通竖式 模拟数学中两个数相乘的步骤和思路，如图所示num1=123，num2=45可以看到1）num1的长度为L1，num2的长度为L2,那么乘积结果res的长度最长为L1+L2，因为结果的最高位的产生是num2的最高位与num1最高位的乘积的首位，所以res的长度为L1+L2-1，或者L1+L22）步骤：从num2的末位循环到首位，每位都与num1相乘，乘的结果要与res已存的结果相加。num2中数字的位置决定了该数与num1相乘的结果向左的移位，例如num2中的4，与num1的结果为492，但是492在与res相加时，是向左移了一位。 #inc...

题解 难度：中等难度 知识点：数学逻辑 思路： 依次判断：1.若是s[i]为“（”是，是得left++。 当s[i]为“）”时：如果left>0,说明该“）”可以和之前的“（”抵消，因此left--。若此时left=0,说明给“）”无法抵消因此right++。 2.最终left保留没有被抵消的“（”，right保留没有被抵消的“）”。Left+right为最终需要添加的符号数。  【注】如果直接对“（”和“）”进行计数操作，最终以abs(left-right)会发生错误。 例： ）（：此时若单纯计算left=1，right=1，abs(left-right)=0；Left+right=2...

题解 难度：中等难度 知识点：单调栈 单调栈： 那么单调栈有这样的性质：对于单调递增的栈，如果此时栈顶元素为 b，加入新元素 a 后进行更新时： 如果 a 大于 b，说明 a 在数组里不能再往左扩展了（由于单调栈的单调递增性质，b前面的元素均小于a），也就是说，如果从 a 在数组中的位置开始往左边遍历，则 a 一定是第一个比 b 大的元素； 如果 a 小于 b，说明在数组里，a 前面至少有一个元素不能扩展到 a 的位置(至少有b元素，因为b的值要大于a，如果此时再加入新的a，那么单调栈便不再单调，所以元素a此时不能压入栈顶，因为这并不是元素a"应该"在的位置，只有当元素a找到自己的位置时元素a...

题解 难度：中等难度 知识点：递推 数学逻辑 思路： 本题考察递推公式，1.本题将n无聊，m为不无聊。总共人数为s=n+m。每次从其中随机选出2个，将这两个数中的不无聊变成无聊，最终将s个人全部变成无聊。 2.假设当S个人中有K个人是不无聊，设平均需要f(K)次操作使得S个人全部变为无聊。每一次操作存在3种可能性： K个不无聊的人都没有被选中，任然存在K个人处于不无聊。概率为：C(s - k, 2)/C(s, 2) K个不无聊的人中选中了一个，此步后存在K-1个人处于不无聊。概率为：(s - k) * k / C(s, 2) K个不无聊的人种选中了2个人，此步后存在K-2个人处于不无聊。概率为...

题解 难度：中等 知识点：博弈 求余 博弈论： 二人或多人在平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜目标的理论。博弈论是研究互动决策的理论。博弈可以分析自己与对手的利弊关系，从而确立自己在博弈中的优势，因此有不少博弈理论，可以帮助对弈者分析局势，从而采取相应策略，最终达到取胜的目的。 如果使用递归，由于递推关系的依赖的状态太多，直接爆炸。 本题思路： 1.吃草规则的简化 吃4的整数次幂1、16、64、256、…，尾数有3种情况：1、4、6，模5之后只有1和4两种情况。即一次只能吃1 (mod 5) 或 4 (mod 5)数量的草。 2.基于简化后的吃草规则，面对数量为R的草堆...