题解 难度：中等难度 知识点：贪心 排序 数学逻辑 贪心选择 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 【注】对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解对。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 本题思路： 例：3 ...

题解 难度：简单 知识点：数学逻辑 题目解析 题目的意思是将输入数组在空数组b上进行n次下面的操作：第i次操作时1）将输入数组的第i个数字放到b的末尾2）将b数组逆序 例子：输入数组为1234    操作次数 b 逆序后的b    第1次 1 1   第2次 12 21   第3次 213 312   第4次 3124 4213   方法一：模拟操作 复杂度：时间复杂度为o(n),空间复杂度为o(n) 求逆序太繁琐，时间花费比较多，那么可以定义一个头尾都可以插入数据的双向deque来简化操作，观察上面的例子，第i个数字插入b的时候（1<=i<=n），i如果为偶数，则在b的最后面插入...

题解 难度：简单 知识点：数学逻辑 由于钱可以换水果，但是水果不能换钱。在钱不换水果的情况下：f代表水果的最大值天数d/x代表当前的钱维持房租的最大值天数 所以有两种情况：  如果f>=d/x，这个时候因为水果不能换钱，所以d/x就是能维持的最大天数 如果f<d/x，这个时候可以通过钱换水果来增加天数：所以能维持的最大天数为(d+p*f)/(x+p)  #include<iostream> using namespace std; int main() { long x, f, d, p; cin >> x >> f >> d &gt...

题解 难度：简单 知识点：排序 数学逻辑 思路： 1.首先将n个元素存放在动态数组x中，对其进行从小到大排序。 2.通过x[1]-x[0]计算出d,采用for循环判断动态数组中两个相邻的数的差x[i]-x[i-1]与d是否相同：若不相等即不能构成等差数列，无需对之后的数进行判断，提前退出循环。 3.怎么判断是否提前退出循环？定义flat变量，在进入循环之前赋值为1，在循环过程中，若出现x[i]-x[i-1]与d不相等，将flat赋值为0，然后通过break退出循环。 4.在循环之后，判断flat值，若为1输出：Possible，若为0输出：Impossible。 #include<ios...

题解 难度：偏难 知识点：BFS 状态压缩 队列 思路： 如果不存在钥匙和锁的情况：（理解BFS过程） （将例子中的小写字母看为1，大写字母看为0）构成数组G[5][5]  起始位置G[0][1]，因此得到b[0][1]=0  【注】辅助数组b[i][j]用来记录从起始位置到坐标（i，j)一共的步数。初始需要将其赋值为-1，表示走到该位置需要的最少步数还没有得到。  从初始位置G[0][1],进行上下左右搜索，即G[0][0],G[0][2],G[1]1判断其值是否为1，如果时路表示从起始走一步即可达，因此将b[0][2]=1,b[1][1]=1。 继续对G[0][2]和G[1][1]上下左右...

题解 难度：中等 知识点：暴力求解 棋子只能上下左右移动，所以移动的步数即操作次数为两个位置的曼哈顿距离坐标(x1,y1)的i点与坐标(x2,y2)的j点的曼哈顿距离为d(i,j)=|x1-x2|+|y1-y2| 本题是要求解棋盘上出现一个格子中至少k个棋子的最少操作。那这k个棋子出现在那个格子呢，最少的操作数可能出现在棋盘上的任何一个格子么？先来看个例子：先来看看一维的情况，如有四颗棋子x=[1,2,4,9]，要将这4颗棋子移到一个格子上，格子坐标范围为[1:10]，结果如下    四颗棋子都移到的格子 总步数    x=1 0+1+3+8=12   x=2 1+0+2+7=10   x=3...

删除重复字符 题目难度：简单 知识点：字符串 方法一 通过字符下标判断该字符是否需要输出。使用lastIndexOf()和indexOf()方法，其中lastIndexOf()表示字符在此字符串中最后一次出现的索引，indexOf()表示字符在此字符串中第一次出现的索引。定义一个StringBuffer用于存储输出结果。遍历字符串，判断该字符第一次和最后第一出现的下标是否一致，若一致，则添加该字符串到StringBuffer中，否则，继续判断当前下标是否与该字符第一次下标一致，若一致，则添加至StringBuffer中，直至循环结束。 import java.util.*; public cl...

判断题 题目难度：简单 知识点：数学逻辑 方法一 解题思路：最高的考试分数为考试中正确题目的最大数量加错误题目的最大数量。当考试中猜测为对的题目数t大于实际正确的题目数a时，a为正确题目的最大数量，(n-t)为错误题目的最大数量，当考试中猜测为对的题目数t小于实际正确的题目数a时，t为正确题目的最大数量，(n-a)为错误题目的最大数量。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner in=new Scanner (System.in); int n=in.nextIn...

DNA序列 题目难度：中等 知识点：数学逻辑、宽度优先遍历 方法一 采用宽度优先遍历，得到长度为i的子串的所有排列，比较字符串中是否存在全部子串，若全部存在，则继续下一个长度的子串的遍历，否则，i即为字符串中没有包含所有该长度的子串，输出i，循环结束。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { String str = sc.next(); //i...

题解 题目难度：简单 知识点：字符串、数组、栈 分析： 因为题目本身是针对合法字符串求深度，省去了判断字符串是否合法的步骤，所以该题较简单，下面给出2种解法 方法1： 利用数组，统计到当前位置Xi时连续左括号的长度 import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner ...

题解 题目难度：中等 知识点：LCS（最长公共子序列问题），动态规划 分析： 本题实际是要找出s的最长子序列，看到这个问题就应该想到利用动态规划去解决。一般是找s1、s2两个字符串中的最长子序列，那么该题中就可以遍历s,以每个字符位置作为分割点，将s分割成s1和s2两个字符串，利用动态规划去求解s1和s2中的最长子序列，结果存储在dp[i][j]的二维数组中。对于dp数组，下标从1开始对应字符串中的0下标对应的字符。通过上面一个dp数组表，就可以算出最长子序列长度为3  import java.util.Scanner; public class Main { public static vo...

题解 题目难度：简单 知识点：数学问题，二分算法 分析： 针对本题，有两种方法，一种利用数学思想，较为直接粗暴的搜索；另一种方法可以利用二分法来解决 方法1: 针对本题，第一想法是通过暴力的方法利用数学思路解答，给出sum的值求原值x（如果存在则为x,否则x=-1）,那么sum = x+(1/10)x+(1/100)x+…。以例子sum= 564为例计算，x≈508，与真实结果509相差很少，可以通过从508开始往后展开n个元素的搜索，这样也可以在一定程度上减少搜索范围。因为sum的范围在[1, 10^18]，所以要适当扩大搜索范围，在这个数据范围中n取100。 import java.uti...

题解 题目难度：hard 知识点：迷宫搜索类问题，利用BFS找到最短路径。 分析： 将人所在位置与箱子所在位置以及所走步数看作整体，新建节点Node。首先初始位置入队，通过移动不断将还没有经过的下一位置节点入队，直至找到箱子之前箱子的位置是不变的；当人找到箱子之后（即在箱子的一侧，上下左右），开始推箱子往另一侧走（下上右左），此时人和箱子的位置都开始移动，直至走到终点或无路可走结束。本题可以分为2个过程：（具体实现思想见代码中注释）① 人在找到箱子之前单独移动，箱子原地不动；在这个过程中，人要从“S”走到箱子“0”的旁边（上下左右）。② 人找到箱子之后和箱子一起向“另一侧”移动，..S0.. ...

题解 难度：较难 知识点：动态规划，数学逻辑 题目分析  CNumber就是一个山形状的整数，例如121，123421，18910这些数，都是先变大后变小，相邻数字间只能有大于或小于的关系，不能等于，CNumber最少3位数 CCNumber就是两个紧邻的山构成的整数，意思就是这个数可以分为两个子整数，这两个子整数都是CNumber，能够分解到的CNumber之间不能共用数字，并且必须紧邻，CCNumber最少6位数比如12121，那么分解为121和121共用了数字1，所以12121不是CCNumber比如1211121，那么分解为121和121，但是中间多余一个1，所以1211121也不是C...