算法手记1

一.NC313 两个数组的交集

牛客网题目链接(点击即可跳转):NC313 两个数组的交集

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 最开始想的是先用set去重然后再排序,然后再用双指针遍历这两数组就可以了.但是考虑到这个题型属于从一个数组里找某个数是否存在,用哈希就很合适啊,所以就先把其中一个数组放哈希表里,再遍历另一个数组去查就好了,查到了的结果放set里,或者查到一个从哈希表里删掉一个,都能达到去重的效果.

解题代码:

本题解题代码如下:

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

二.AB5 点击消除

牛客网题目链接(点击即可跳转):NC313 两个数组的交集

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 经典括号匹配的变形题,变数在于要顺序输出栈里剩余元素,为了方便可以用一个string来模拟栈操作,单纯用栈的话就还得多一步把栈里元素倒出来的操作,用string可以直接输出.

解题代码:

本题解题代码如下:

#include <iostream>
using namespace std;

int main() 
{
    string s, ret;
    cin >> s;
    for (auto e : s) 
    {
        if (ret.empty() == false && e == ret[ret.size() - 1])
            ret.pop_back();
        else
            ret.push_back(e);
    }
    ret.empty() == true ? cout << 0 : cout << ret;
}

结语

说点啥好呢...今天这两道题学到的最重要的东西就是要灵活运用数据结构,题目不难,但是利用数据结构把题变得非常简单还是没有想到,第一道用哈希找,明显比排序再双指针遍历时间复杂度低.第二道就是要对数据结构知其性而不拘于型,谁说栈的特性一定要用栈来实现?string明显更有利于得到结果.所以说一切都要灵活变通,加油,慢慢一天天进步吧!