饲养员刷力扣题笔记---C++---更新中

饲养员刷力扣

以下内容我的总结，若有不对，欢迎指教，前面的后期刷完后会接着补充

29.集合set

特点：①无序（排序不固定）②元素不重复

因此，插入重复元素的时候还是只保存一次

判断以下是否是集合：

{1,2,3,3,2} 不是

{1,2,4} 有可能是 {1,4,2}

主要作用：

①检查某一个元素是否存在

②查找重复元素

set有：HashSet、LinklistSet、TreeSet
哈希集合的运作方式：先获取元素，通过哈希函数获取它的哈希值，再通过查找哈希表进行操作。

哈希冲突的解决方法：可以使用链表的方法。将next指针指向一个空间存储引起冲突的元素
set时间复杂度：

哈希集合是无序的吗，为什么哈希集合的输出是有序的

Python3 Set

# Python3 Set

class Test_set:
    def test(self):
        # 创建
        # 使用数组创建hash
        s = set()
        
        # 添加元素
        s.add(10)
        s.add(3)
        s.add(5)
        s.add(2)
        s.add(2)
        print(s)
        # {2,10,3,5}

        # 查找元素
        print (2 in s)
        # True

        # 删除元素
        s.remove(2)
        print(s)
        # {10,3,5}

        # Size
        len(s)

if __name__ == "__main__":
    test = Test_set()
    test.test()

C++ Set

#include //c++标准头文件，可以使用cout，cin等标准编译用法
#include // 使用set需要带上这个文件
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin、cout、map、set、vector
int main() {
    //定义
    set s;

    //添加元素
    s.insert(10);
    s.insert(3);
    s.insert(5);
    s.insert(2);
    s.insert(2);

    //{10,3,5,2}
    //遍历1:for
    for (int c : s) {
        cout << c << ' ';
    }
    cout << endl;


    //遍历2.1:使用迭代器
    set::iterator it;
    for (it = s.begin(); it != s.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;

    set::iterator it2;
    //遍历2.2：降序迭代器遍历
    for (it2 = --s.end(); it2 != --s.begin(); it2--) {
        cout << *it2 << ' ';
    }
    cout << endl;

    //遍历2.3：逆序迭代器遍历
    set::reverse_iterator rit;
    for (rit = s.rbegin(); rit != s.rend(); rit++) {
        cout << *rit << ' ';
    }
    cout << endl;

    //遍历3：使用foreach遍历
    for (auto it : s) {
        cout << it << ' ';
    }
    cout << endl;

    //查找元素
    cout << "是否包含元素2:" << s.count(2) << endl;  //返回1为真，存在

    //是否为空 
    cout << "是否为空" << s.empty() << endl;  //返回1为真，为空


    //删除元素
    s.erase(2);
    //清空集合
    //s.clear();

    //size
    s.size();//返回元素的个数
    return 0;
}

力扣 217 存在重复元素

使用map的时候是计算每一个数字出现的次数，使用set则更加简单，可以直接查找集合中是否有该元素

Python3 217

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        s= set()
        for num in nums:
            if num in s:
                return True
            s.add(num)
        return False

C++ 217

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        set s;
        for(int num : nums){
            if(s.count(num) == 1){
                return true;
            }
            s.insert(num);
        }
        return false;
    }
};

力扣 705 设计哈希集合

思路：设计一个在【0,1000000】的数组，数组中存放bool类型数组，索引就是数值，比如要是存在1，也就还是查找索引1对应的值为True

思考：占的空间大，然后要知道范围才知道需要多大的数组空间

Python 705

class MyHashSet:
    def __init__(self):
        self.hashset = [0]*1000001
            
    def add(self, key:int )-> None:
        self.hashset[key] = 1
    
    def remove(self, key:int) -> None:
        self.hashset[key] = 0
    
    def contains(self, key:int) -> None:
        if self.hashset[key] == 1:
            return True
        else:
            return False

c++ 705

class MyHashSet {
public:
    int *hashset;//[1000001] = {0};
    //  int* array = new int[100];
    MyHashSet() {
        //this->hashset = {0};
        this->hashset = new int[1000001];
    }
    
    void add(int key) {
        this->hashset[key] = 1;
    }
    
    void remove(int key) {
        this->hashset[key] = 0;
    }
    
    bool contains(int key) {
        if(this->hashset[key] == 1){
            return true;
        }
        else{
            return false;
        }
    }
};

暑期编程PK赛得CSDN机械键盘等精美礼品！

饲养员刷力扣题笔记---C++---更新中

C/C++/C#相关栏目本月热门文章