本文主要是介绍强化训练:day1,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 前言
- 1. 数字统计
- 1.1 题目描述
- 1.2 解题思路
- 1.3 代码实现
- 2. 两个数组的交集
- 2.1 题目描述
- 2.2 解题思路
- 2.3 代码实现
- 3. 点击消除
- 3.1 题目描述
- 3.2 解题思路
- 3.3 代码实现
- 总结
前言
为了提升自己的编码能力,我决定展开持续N天的训练计划,计划是每天写最少三道编程题,来训练自己,同时为了加强理解,决定以博客的形式,将自己的做题过程记录下来,即为进一步加强做题思路,也为了后续方便复习。(我是C++选手,因此我的题解都是C/C++写的,对于其他的语言,看看解题思路就好了)
1. 数字统计
1.1 题目描述
做题链接:BC153 [NOIP2010]数字统计
1.2 解题思路
这个题不需要什么技巧,只需要依次枚举每一个数据,然后进行统计每个数据里面有多少个2。我们可以封装一个函数,来实现统计一个数中出现多少个2,这样写可以使程序更加清晰分明。
对于一个数,我们可以先%10,得到个位上的数,然后判断是否为2,是的话进行统计。然后再除10,将个位上的数字去掉,继续判断十位上的数字,依次类推,统计出一个数的各个位上的数字是否为2。然后返回这个数2一共出现了多少次。
1.3 代码实现
#include <iostream>
using namespace std;
int solve(int n) {int ret = 0;while (n) {if (n % 10 == 2) ret++;n /= 10;}return ret;
}
int main() {int l, r;cin >> l >> r;int ret = 0;for (int i = l; i <= r; i++) {ret += solve(i);}cout << ret;return 0;
}
2. 两个数组的交集
2.1 题目描述
做题链接:NC313 两个数组的交集
2.2 解题思路
本题我是使用了两个哈希表来解决的,先用一个哈希表来统计数组1的所有元素,再用第二个哈希表统计出数组2的所有元素,这一步即时完成了去重,也是完成了能够快速查找的功能。
然后依次枚举第一个哈希表中的元素,用第二个哈希表进行查找,如果找到了就添加到最终的返回结果中。因此一个循环下来就可以解决问题了。
2.3 代码实现
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums1 int整型vector* @param nums2 int整型vector* @return int整型vector*/vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;unordered_set<int> hash;unordered_set<int> hash1;for (int i = 0; i < nums1.size(); i++) {hash.insert(nums1[i]);}for (int i = 0; i < nums2.size(); i++) {hash1.insert(nums2[i]);}for (auto x : hash) {if (hash1.count(x)) ret.push_back(x);}return ret;}
};
3. 点击消除
3.1 题目描述
做题链接:AB5 点击消除
3.2 解题思路
一开始我的想法是,先通道到尾循环一遍,找到所有相邻且相同的字符,然后进行消除。然后当消除一次后,有可能会再次出现相邻且相同的字符(比如:abba),因此需要继续从头循环,知道找不到相邻且相同的字符。
然后……,想法是好的,现实是残酷的,思路没问题,但是由于数据量太大,超时了,当时也是崩溃了……。这个思路的时间复杂度是O(n^2)的,因为需要从头到尾遍历好多遍,因此我们要从降低时间复杂度的角度换一种方法解决问题。
这个方法就是利用栈,当栈为空的时候,字符直接进栈。不为空时,与栈顶元素进行判断,如果相同就将栈顶元素出栈,如果不相同就将该元素进栈,继续判断下一个字符。(这个过程比较简单,我就不画图了,后续遇到难以凭空想象的题解,我会画图来帮助理解。)这样我们只需要O(n)的时间复杂度就可以解决问题了。
3.3 代码实现
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{stack<char> s;string str;cin >> str;for(int i = 0; i < str.size(); i++){if(s.empty()){s.push(str[i]);}else{if(str[i] == s.top()) s.pop();else s.push(str[i]);}}string ret;while(!s.empty()){ret += s.top();s.pop();}// 由于栈是后进先出的,所以我们得到是结果是相反的,需要逆置一下reverse(ret.begin(),ret.end());// 处理最后结果是空的情况,为空的话要输出的是0,不是空字符串if(ret.size() != 0) cout << ret;else cout << 0;return 0;
}
总结
一开始需要从易到难了,不然真就是从入门到入土了……,第一天的还是比较简单,主要是第三题第一次写的时候超时了,还是后续看了别人的题解才想到这个方法,因此我的目标是:难题会做就行,简单题要用更少的时空复杂度来完成。
第一天的内容就到此结束了,希望自己可以坚持下去,也希望能与大家共同进步,如果大家发现有什么错误的地方,可以私信或者评论区指出喔。我会继续坚持训练的,共勉!!!那么本期就到此结束,让我们下期再见!!觉得不错可以点个赞以示鼓励!!
这篇关于强化训练:day1的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!