🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境:Visual Studio 2022
目录
一.NC313 两个数组的交集
题目详情:
题目思路:
解题代码:
二.AB5 点击消除
题目详情:
题目思路:
解题代码:
结语
一.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();elseret.push_back(e);}ret.empty() == true ? cout << 0 : cout << ret; }
结语
说点啥好呢...今天这两道题学到的最重要的东西就是要灵活运用数据结构,题目不难,但是利用数据结构把题变得非常简单还是没有想到,第一道用哈希找,明显比排序再双指针遍历时间复杂度低.第二道就是要对数据结构知其性而不拘于型,谁说栈的特性一定要用栈来实现?string明显更有利于得到结果.所以说一切都要灵活变通,加油,慢慢一天天进步吧!
