算法手记1

🦄个人主页:修修修也

🎏所属专栏:刷题

⚙️操作环境: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明显更有利于得到结果.所以说一切都要灵活变通,加油,慢慢一天天进步吧!