【C++笔试强训】如何成为算法糕手Day1
第一题：两个数组的交集
牛客网题目链接：两个数组的交集_牛客题霸_牛客网 (nowcoder.com)
给定两个整数数组分别为nums1nums1, nums2nums2，找到它们的公共元素并按返回。
数据范围：
1≤nums1.length,nums2.length≤10001≤nums1.length,nums2.length≤1000 1≤nums1[i],nums2[i]≤10001≤nums1[i],nums2[i]≤1000
解题思路：对于本题本人共有三种思路，第一种为暴力遍历循环法，第二种为数组下标法，第三种为哈希法。
暴力循环法：
- 如果两个数组的当前元素相等，那么我们需要检查结果数组
ans。如果ans为空，或者ans的最后一个元素与当前相等的元素不一致，我们就将这个相等的元素添加到ans中。之后，两个输入数组和结果数组的索引都向前移动一位。 - 如果两个数组的当前元素不相等，那么我们比较这两个元素的大小。将较小元素所在数组的索引向前移动一位，因为在已排序的数组中，如果较小数组中存在与较大元素相等的元素，它必然位于当前较小元素之后。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ans;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int len1 = nums1.size();
int len2 = nums2.size();
// index1, index2作为遍历nums1 和 nums2的下标，index作为结果数组的下标
int index1 = 0, index2 = 0, index = 0;
while(index1 < len1 && index2 < len2){
if(nums1[index1] == nums2[index2]){
if(ans.size()==0 || ans[index-1] != nums2[index2]){ //为了避免插入重复数据
ans.push_back(nums1[index1]);
index1++;
index2++;
index++;
}else{
index1++;
index2++;
}
}
else if(nums1[index1] < nums2[index2]){
index1++;
}
else{
index2++;
}
}
return ans;
}
};哈希法 ：
- 初始化一个名为
result的数组，该数组用于存储两个数组共有的交集元素。 - 创建一个名为
arr的数组，用于标记数组num1中的元素是否出现过。具体做法是将num1中的元素num1[i]作为arr的索引，例如如果数组中有元素2，则设置arr[2]为1，以此记录元素2在num1中出现过。 - 遍历数组
num2，将num2中的每个元素作为索引去访问数组arr，检查arr对应位置的值是否为1。如果为1，说明这个元素在num1中也出现过，因此它是num1和num2的交集元素。将该元素添加到result数组中，并且在这个过程中，result数组会自动去重，因为重复的元素不会被再次添加。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
int arr[1004]={0};
for(int i=0;i<nums1.size();i++){
arr[nums1[i]]=1;
}
for(int i=0;i<nums2.size();i++){
if(arr[nums2[i]]==1){
result.insert(nums2[i]);
}
}
return vector<int>(result.begin(), result.end());
}
};数组下标法：
利用数组下标记录出现重复的数字，是一个类似于哈希算法的方法。但时间和空间复杂度都过于高了。
#define max 100000
class Solution {
public:
int a[max][2];
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(),s=nums2.size();
vector<int> v;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[nums1[i]][0]=1;
}
for(int i=0;i<s;i++){
a[nums2[i]][1]=1;
}
for(int i=0;i<max;i++){
if(a[i][0]==1&&a[i][1]==1){
v.push_back(i);
}
}
return v;
}
};第二题：点击消除
牛客网做题链接：E-点击消除_牛客小白月赛25 (nowcoder.com)
牛牛拿到了一个字符串。 他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。 但相同而不相邻、不相同的相邻字母都是不可以被消除的。 牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？
输入描述:
一个字符串，仅由小写字母组成。（字符串长度不大于300000）
输出描述:
一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。
我们可以借鉴括号匹配的思路来解决这个问题。在这个方法中，我们使用一个字符串str来模拟栈的行为，以便于我们进行操作和输出。以下是具体步骤：
- 初始化一个字符串
str作为我们的“栈”，用于存储和操作字符。 - 另一个字符串
s用来接收我们需要处理的输入字符串。 - 开始遍历字符串
s中的每个字符，进行以下操作：如果str的最后一个字符（即栈顶字符）与当前遍历到的s中的字符相同，那么我们将str的最后一个字符删除（相当于执行出栈操作）。如果不相同，则将当前遍历到的字符添加到str的末尾（相当于执行入栈操作）。 - 当遍历完整个字符串
s后，字符串str中剩下的字符就是经过消除后的最终结果。
#include <iostream>
#include <string>
using namespace std;
int main() {
string str,s;
cin >> s;
for(auto i : s)
{
if(str.size() && str.back() == i) //str不为空且与s相等
{
str.pop_back();
}
else
{
str.push_back(i);
}
}
if(str.empty()) //判断为空的输出情况
cout << "0" << endl;
cout << str;
}第三题：统计数字
牛客网做题链接：[NOIP2007]统计数字 (nowcoder.com)
题目描述：
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
输入描述:
第1行是整数n，表示自然数的个数。 第2~n+1行每行一个自然数。
输出描述:
输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开
利用给出的范围当作循环的起始点和到达点，计算出个、十、百分位上的数字2。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int L, R;
while(cin >> L >> R)
{
int cnt = 0;
for(int i = L; i <= R; i++)
{
int j = i;
while(j)
{
if(j % 10 == 2) cnt++;
j /= 10;
}
}
cout << cnt << endl;
}
return 0;
}学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
腾讯云开发者
