HJ100 题解 | #等差数列# 题意分析  给出一个等差数列的首项和公差，我们需要求解前n项的和。  思路分析 直接模拟   我们直接按照题目的意思进行模拟，从1-n循环，然后用一个变量更新每一项，累加到答案即可。   代码如下  从1-n进行枚举，时间复杂度为O(n)O(n)O(n) 过程中只使用了少数几个变量，空间复杂度为O(1)O(1)O(1)    #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ int now=2; // now记录当前项的数 in...

HJ99 题解 | #自守数# 题意分析  给你一个数字，需要你找出在这个数字范围内的正整数中，自守数的个数。自守数是指一个数的平方的尾数等于该数自身的自然数。  思路分析 寻找规律   对于自守数，我们可以发现，如果这个数字是自守数，那么这个数的平方减去这个数得到的数的后面一定有这么多个0。比如5这个数字，5的平方是25，25-5=20，后面又一个0，5的位数也是1位，所以这个数字是自守数。其他的也可以发现也满足这个规律。但是这里要注意的一个情况是比如0和1这种情况，这种最后减下来一定是0，需要进行特判。   综上，我们就得到了我们的求解方法，我们先对n已被的每个数字进行枚举，然后，将这个数...

HJ97 题解 | #记负均正# 题意分析  给一个数组，需要找到这个数组里面的负数的个数和正数的平均数。  思路分析  直接模拟即可。我们遍历这个数组，如果是正数，那么用一个变量sum统计，同时累加个数，如果是负数，那么就只要累加负数，最后即可得到最后的结果。这里求正数的平均数的时候要注意的是除数为0的情况，不然可能出现段错误。   C++  代码如下  需要遍历整个数组，时间复杂度为O(n)O(n)O(n) 只用了少数几个变量进行求解，空间复杂度为O(1)O(1)O(1)    #include<bits/stdc++.h> using namespace std; int m...

HJ96 题解 | #表示数字# 题意分析  给你一个字符串，需要你将这个字符串的所有整数的前后加上*，其他字符的相对顺序保持不变。  思路分析   思路比较简单，为了方便处理第一个和最后一个字符串的特殊情况，我们先在初始的字符串的前后各添加一个无关字符x,然后我们对这个字符串进行遍历.  我们每遍历一个字符，先判断这个字符是否是非数字字符，然后再判断这个字符的前面是否是数字字符。如果满足，那么说明这个字符的前面是一个整数，我们在这个字符的前面加上一个*即可。 我们每遍历一个字符，先判断这个字符是否是数字字符，然后再判断这个字符的前面是否是非数字字符。如果满足，那么说明这个字符的后面是一个整数...

HJ94 题解 | #记票统计# 题意分析  给你n个字符串，我们定义这些字符串都是合法的，然后，我们另外输入一些字符串，我们需要判断这些统计合法的字符串的具体个数，记录不合法的字符串的个数。  思路分析  我们用哈希表存储每个字符串，然后对于输入的字符串，先判断是否是合法的字符串，如果是合法的字符串，然后对应的哈希表自增1，否则非法的投票的个数自增。   写法一 C++法  这里我们使用unordered_map来作为哈希表对字符串进行哈希。 代码如下  对字符串，我们哈希存储所有的字符串的长度，然后，我们的解题过程都是一重循环进行遍历，所以总的时间复杂度为O(n)O(n)O(n) 我们需要...

HJ93 题解 | #数组分组# 题意分析  给你一个数组，数组中所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出truetruetrue；不满足时输出falsefalsefalse。  思路分析  首先，我们来分析题目，我们先按照题目的要求进行分组，我们可以发现，3的倍数的数和5的倍数的数放的位置是固定了的。那么我们在分完组之后，得到了两个集合，一个是3的倍数的集合,我们把集合的元素的和记为sum3sum3sum3，一个是5的倍数的集合,我们把元素的和记为sum5sum5sum5，...

HJ92 题解 | #在字符串中找出连续最长的数字串# 题意分析  给出一个字符串，我们需要将其中长度最长的数字子串输出，同时最后用一个逗号分隔，然后输出这个最长的字符串的长度。如果有多个最长字符串，按照顺序输出即可。  思路分析  这个题目，我们需要遍历这个字符串的每个字符，然后处理出这个字符串的数字子串，这个地方我们可以用一个临时的字符串收集，一旦遇到一个不是数字字符的就立马将之前的字符收集起来，然后将临时字符串情况。最后，我们收集到了所有的数字子串。然后进一步处理即可。  写法一  这种写法，我先把所有的字符串存进一个结构体里面，然后我们将这个结构体的小于运算符进行重载，长度长的优先级高...

HJ91 题解 | #走方格的方案数# 题意分析  一个很经典的题目，给出一个二维矩阵，从左上角走到右下角，每次只能往右走或者往下走，问我们有多少种走的方案？  思路分析 解法一 动态规划  我们发现，假设我们某一个时刻走到了位置(i,j)(i,j)(i,j),那么，我们如何求到达这个位置的情况的数目呢？     所以我们可以很容易得到状态转移方程,dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]。   代码如下  二维循环，先进行行的遍历，再进行列的遍历，更新每...

NC159 题解 | #最小生成树# 题意分析  给出一张图，图上有n个节点，m条路，现在，我们需要计算将所有的点构成一个连通图所需要的最小的代价，题目会给出某两个结点之间的成本，需要我们最小化总的成本。  思路分析  我们首先很明确的知道这个就是需要我们求出图上的一棵最小生成树。我们发现，我们可以还是按照求单源最短路的思想去求解。其实求一棵最小生成树，就类似于我们将图上面的n个结点汇聚成一个点，这里也可以看作是一个集合，就是原来的图上有n个集合，现在我们需要将n个集合转化为一个集合。这里我们还是按照一个贪心的思想去求解。我们发现，为了使最后的代价最小化，我们只需要找尽可能小的边去连接我们这些...

NC158 题解 | #单源最短路# 题意分析  给出一张有向图，需要我们计算出从1号结点到达n号结点的最短的距离。  大意分析   这个是一个很明显的一个模板题，相信大家在数据结构课程上都学过，现在就让我们来温习一遍。这个其实也可以理解为一种贪心的思想吧。我们从一号结点开始进行拓展，先找到离1号结点最短距离同时没有被访问过的点。然后我们进行扩展，我们不断更新从1号结点到达每个结点的最短的距离，这样，我们可以很容易证明，我们最多只需要扩展n次就可以得到我们最后想要的结果。因为我们在寻找没有访问过的点的时候，最多就是遍历n个结点，而且，我们从一号结点到达n号结点最多也只需要n-1步到达。   接...

NC161 题解 | #二叉树的中序遍历# 题意分析  给你一棵二叉树，需要你给出这棵二叉树的中序遍历的序列。  思路分析  这是一个很经典的题目，主要的考察点就是DFS递归的思想，首先，我们需要知道什么是中序遍历？中序遍历就是先遍历二叉树的左子树，然后遍历二叉树的根节点，然后遍历二叉树的右子树。对于左右子树，同样执行这样的操作即可。最后得到的就是中序遍历的序列。    我们可以看到，具体的命名是根据根节点的被遍历的顺序决定的，这个方便记忆.  写法一 C++  代码如下  所有的节点都需要被遍历一遍，时间复杂度为O(n) 每次递归都需要开辟栈空间，递归的次数为树的高度，所以空间复杂度为O(l...

NC160 题解 | #二分查找-I# 题意分析  在一个升序，没有重复元素的序列里面找到一个固定的目标值，返回这个下标，没有就返回-1  思路分析 解法一 循环遍历  直接对整个数组进行暴力求解，遍历整个数组即可。 代码如下  遍历的时间复杂度为O(n)O(n)O(n) 过程中只用了少数几个变量，空间复杂度为O(1)O(1)O(1)    class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @retur...

NC157 题解 | #单调栈# 题意分析  给我们一个数组，我们需要找出每个位置左边和右边最近的比这个位置的数字小的数的位置、如果没有。那么就用-1表示。  思路分析 暴力模拟  这里，我们先直接按照题目的意思进行暴力模拟，我们遍历整个数组，对于寻找左边的位置，我们从这个位置的前一个位置进行枚举，找到第一个小于的数字直接退出。右边的同理。 代码如下  利用双重循环进行求解，总的时间复杂度为O(n2)O(n^2)O(n2) 过程中只用了少数几个变量，空间复杂度为O(1)O(1)O(1)    class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请...

NC140 #排序# 题意分析  一个面试经常会问的题目，考察基本的排序。给我们一个序列，需要我们将这个数进行从小到大排序。  思路分析  这种题目算是一个很经典的题目，这里介绍两种高效的排序方法。其思想都是利用递归进行实现的。  快速排序法  快速排序的思想就是我们先设定一个基准，然后将这个要排序的区间里面的数字比它小的扔到左边，比他大的扔到右边。然后进行递归的操作，从而达到了排序的目的。 分为以下三步   选择一个基准   以基准为中心，将序列划分为左右两个子序列，序列左边的都比这个数字小，序列右边的都比这个数字大   递归到序列长度为1或者序列为空就结束       代码如下  递归的次...