【笔试强训】day1

1.数字统计

题目链接：[NOIP2010]数字统计_牛客题霸_牛客网

思路：枚举L到R之间的数字，将这个数字进行判断含有几个2，统计2的个数即可解决。判断一个数字含有几个2可以逐位判断。数据范围：1~10000，用int即可。

时间复杂度：O（N）        空间复杂度：O（1）

代码：

#include 
using namespace std;
 
int L, R;
 
int main() 
{
    scanf("%d%d", &L, &R);
    int ret = 0;
    for (int i = L; i <= R; i++)
    {
        int temp = i;
        while (temp)
        {
            if (temp % 10 == 2)    ret++;
            temp /= 10;
        }
    }
    cout << ret;
 
    return 0;
}

2.两个数组的交集

题目链接：两个数组的交集_牛客题霸_牛客网

思路：用hash表来标记数组1出现过的元素，若出现过则标记为1，然后数组2中的元素如果在hash表中已经标记过了，则加入到ret中，并且在hash表中标记为2，表示这个元素已经是公共元素了。因为要考虑：{1,2,3,3}，{1,2,3}；{1,2,3}，{1,2,3,3}这些情况。数据范围：length 1~1000，val 1~1000，所以hash表只需开1001个空间即可。（max（num1（val），nums2（val）），然后开最大值的空间也可）

时间复杂度：O（N）        空间复杂度：O（1）

代码：

class Solution 
{
    int hash[1001];
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums1 int整型vector 
     * @param nums2 int整型vector 
     * @return int整型vector
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        for (auto &a : nums1)
            hash[a] = 1;
        for (auto &b : nums2)
            if (hash[b] == 1)
            {
                ret.push_back(b);
                hash[b] = 2;
            }
        return ret;
    }
};

然后发现只过了7,8个测试用例，为啥呢？

请看VCR

打印一下hash表中的值，发现并不全是0，所以要加memset(hash, 0, sizeof(hash));或者定义为全局的时候int hash[1001] = {0};或者将hash改为局部变量，放到intersection函数中，vector hash(1001);这样也可过。

3.点击消除

题目链接：点击消除_牛客题霸_牛客网

思路：模拟一下，a        a-b        a-b-b ->a        a-c;这不就是典型的栈模吗？数据范围：1~3000000。

时间复杂度：O（N）         空间复杂度：O（N）

代码：

#include 
#include 
#include 
using namespace std;
 
int main() 
{
    string str;
    cin >> str;
    stack<char> st;
    for (int i = str.size() - 1; i >= 0; i--)
    {
        if (st.empty())//一定要有这一步！因为核心是判断栈顶元素和str[i]比较是否相等，所以为空的时候没有栈顶元素，会越界。
            st.push(str[i]);
        else
        {
            if (st.top() == str[i])
                st.pop();
            else
                st.push(str[i]);
        }
    }
    if (st.empty())
    {
        cout << 0;
        return 0;
    }
    while (!st.empty())
    {
        cout << st.top();
        st.pop();
    }
 
    return 0;
}

也可以用字符串来模拟栈，代码如下：

#include 
using namespace std;
 
int main() 
{
    string str1, str2;
    cin >> str1;
    for (auto& e : str1)
    {
        if (str2.size() != 0 && str2.back() == e)//出元素
            str2.pop_back();
        else//入元素
            str2.push_back(e);
    }
    cout << (str2.size() == 0 ? "0" : str2) << endl;
    
    return 0;
}