当前位置：首页 > article >正文

【C++】 —— 笔试刷题day_1

article 2025/3/12 17:25:16

为了锻炼自己写代码的思路，开始每日刷题，加油！！！

第一题数字统计

在这里插入图片描述

题目要求：

给定一个范围 [L , R] 求出数字L在该区间内出现的次数。（其中1<=L<=R<=10000）

算法思路：

在这里插入图片描述

代码：

#include<iostream>
 using namespace std;

 int main()
 {
    int L,R;
    cin>>L>>R;
    int count =0;
    for(size_t i = L;i<=R;i++)
    {
        int tmp = i;
        while(tmp)
        {
            if(tmp %10 == 2)
            {
                count++;
            }
            tmp/=10;
        }
    }
    cout<<count<<endl;
    return 0;
 }

第二题两个数组的交集

在这里插入图片描述

题目要求：

给定两个整数数组，返回这两个数组的交集（共同的元素）

注意： 多个相同的元素，只算一个。

算法思路：

利用nums1中的数据，映射出哈希表，然后遍历nums2，如果存在于nums1中相同的元素，就插入到要返回的数组（vector中）。

注意： 这里可以使用STL的容器，也可以使用简单的数组来模拟哈希表；这里就用数组来模拟哈希表。

在这里插入图片描述

代码：

class Solution {
public:
    bool arr[1001] = {0};
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // write code here
        for(auto e:nums1)
        {
            arr[e] = true;
        }
        vector<int> ret;
        for(auto e:nums2)
        {
            if(arr[e])
            {
                ret.push_back(e);
                arr[e] = false;
            }
        }

        return ret;
    }
};

第三题点击消除

在这里插入图片描述

题目要求：

输入一个字符串，每一次消除相邻位置相同的字符（删除之后前后的字符就相邻了）；就比如：字符串"abbac"，删除"bb"后就变成了"aac"，此时"aa"就相邻了，还需要继续删除；最后结果就是"c"。

算法思路：

这个题，以至于这种类型的题都可以使用栈这个数据结构来写，思路如下：

遍历字符串，如果栈为空或者字符串中元素不等于栈顶元素，就入栈；否则就出栈。最后如果栈为空就表示完全删除后没有字符了。

如果栈不为空，那栈中数据就是最后的字符串（注意： 栈中从栈顶到栈底与最后结果是相反，需要进行相关操作输出正确的顺序）。

这里可以使用栈这个数据结构（STL中栈容器），也可以使用其他数据结构或者数组来模拟栈。
在这里插入图片描述

代码：

这里写两个代码，一个是直接使用栈结构的，另一个就用数组（string）模拟栈结构。

栈结构：

#include<iostream>
#include<stack>

using namespace std;

int main()
{
    string str;
    stack<char> s1;
    cin>>str;
    for(auto ch:str)
    {
        if(s1.empty() || ch != s1.top())
        {
            s1.push(ch);
        }
        else {
            s1.pop();
        }
    }
    if(s1.empty())
    {
        cout<<'0';
        return 0;
    }
    stack<char> s2;
    while(!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    while(!s2.empty())
    {
        cout<<s2.top();
        s2.pop();
    }
    return 0;
}

数组模拟栈结构：

#include <iostream>
using namespace std;

int main() {
    string str;
    cin>>str;
    string ret;
    for(auto ch: str)
    {
        if(ret.size()==0||ret[ret.size()-1]!=ch)
        {
            ret.push_back(ch);
        }
        else 
        {
            ret.pop_back();
        }
    }
    if(ret.empty())
    {
        cout<<'0';
        return 0;
    }
    cout<<ret;
    return 0;
}