首页 > 其他分享 >day06 - 哈希表part01

day06 - 哈希表part01

时间:2023-08-15 11:12:02浏览次数:60  
标签:map set return nums part01 day06 int result 哈希

242. 有效的字母异位词

讲解

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length())
            return false;
        map<char, int> map_s;
        map<char, int> map_t;
        for(int i=0; i<s.length(); i++)
            map_s[s[i]]++;
        for(int i=0; i<t.length(); i++)
            map_t[t[i]]++;
        
        //字符数相同,逐个比较
        for(int i=0; i<t.length(); i++){
            if(map_s[t[i]] != map_t[t[i]])
                return false;
        }
            
        return true;

        /*
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0,说明字符串s和t是字母异位词
        return true;
        */
    }
};

 349. 两个数组的交集

详解

c++ set map基础

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

 

202. 快乐数

详解

class Solution {
public:
    map<int, int> map_square;
    map<int, int> map_exists;

    unordered_set<int> set_list;

    bool b_find = false;

    //map 方法
    int split_map(int n){
        if(n == 1){
            b_find = true;
            return 0;
        }
        if(map_exists[n] == 1)
            return 0;
        map_exists[n] = 1;

        int result = 0;
        while(n>0){
            int a = n % 10;
            result += map_square[a];
            n = n / 10;
        }
        
        cout << result << endl;
        return result;
    }

    //set 方法
    int split_set(int n){
        if(n == 1){
            b_find = true;
            return 0;
        }
        if(set_list.find(n) != set_list.end())
            return 0;
        set_list.insert(n);

        int result = 0;
        while(n>0){
            int a = n % 10;
            result += map_square[a];
            n = n / 10;
        }
        
        cout << result << endl;
        return result;
    }

    bool isHappy(int n) {
        for(int i=0; i<=9; i++)
            map_square[i] = i*i;
        //int result = split_map(n);
        int result = split_set(n);
        while(result != 0){
            result = split_set(result);
        }
        return b_find;
    }
};

 

1. 两数之和

详解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // int size = nums.size();
        // for(int i=0; i<size; i++){
        //     for(int j=i+1; j<size; j++){
        //         if(nums[i] + nums[j] == target){
        //             return {i, j};
        //         }
        //     }
        // }
        // return {};

        //map 方法
        map<int, int> map_result;
        for(int i=0; i<nums.size(); i++)
            map_result[nums[i]] = i;//map的key是值,value是下标
        for(int i=0; i<nums.size(); i++){
            if(map_result[target - nums[i]] && map_result[target - nums[i]] != i) //不能自己相加
                return {i, map_result[target - nums[i]]};
        }
        return {};

        /*
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素,并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对,就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
        */
    }
};

 

标签:map,set,return,nums,part01,day06,int,result,哈希
From: https://www.cnblogs.com/zqh2023/p/17629361.html

相关文章

  • day03 - 链表part01
    203. 移除链表元素/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,ListNode*next):v......
  • 考研数据结构——每日一题[哈希表]
    840.模拟散列表维护一个集合,支持如下几种操作:Ix,插入一个数x;Qx,询问数x是否在集合中出现过;现在要进行N次操作,对于每个询问操作输出对应的结果。输入格式第一行包含整数N,表示操作数量。接下来N行,每行包含一个操作指令,操作指令为Ix,Qx中的一种。输出格式对于每......
  • 鲁棒图像哈希
    鲁棒图像哈希标题页:鲁棒图像哈希目录页一、背景介绍图像哈希的概念、意义和应用场景图像哈希面临的问题与研究现状二、关键技术概述基于局部和全局特征的哈希基于特征降维的哈希基于统计特征的哈希基于学习的哈希基于深度学习的哈希方法三、典型算法案例基于Zernik......
  • 字符串哈希
    没有模的版本constintN=1000010;constintm=131;constintmod=1e9+7;intn,T;chars[N];intf[N],p[N];intmain(){ scanf("%s",s+1);n=strlen(s+1); p[0]=1; for(inti=1;i<=n;i++){ f[i]=f[i-1]*m......
  • 20天 hot 100 速通计划-day06
    链表142.环形链表II给定一个链表的头节点head,返回链表开始入环的第一个节点。如果链表无环,则返回null。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引......
  • LRU机制:哈希表+双向链表 [labuladong-刷题打卡 day9]
    今天的知识点LRU缓存机制的实现。学过计组都知道LRU算法(leastrecentlyused最近最少使用算法)是资源管理中的常用算法。那么他是如何实现的呢?LRU原理和Redis实现146.LRU缓存此题算是对LRU机制的一个简化。为了使查找删除在O(1)中实现,我们结合哈希表和双向链表各自在查找和......
  • [代码随想录]Day12-二叉树part01
    今天的题目就是二叉树的前中后序遍历,目前只写了递归方法,之后再补迭代方法。题目:144.二叉树的前序遍历思路:前序遍历:根-左-右代码1:递归,递归情况下只需要改变递归的顺序即可实现前中后序遍历。/***Definitionforabinarytreenode.*typeTreeNodestruct{*Va......
  • c++ std::hash<std::string> 字符串哈希函数
    msvc采用了FNV-1a的哈希算法//众所周知std::string就是一个basic_string<char>template<class_Elem,class_Traits,class_Alloc>structhash<basic_string<_Elem,_Traits,_Alloc>>{_CXX17_DEPRECATE_ADAPTOR_TYPEDEFStypedefbasic_string<_......
  • C#.NET 国密SM3 HASH 哈希 与JAVA互通 ver:20230803
    C#.NET国密SM3HASH哈希与JAVA互通ver:20230803 .NET环境:.NET6控制台程序(.netcore)。JAVA环境:JAVA8,带maven的JAVA控制台程序。 简要解析:1:明文输入参数都需要string转byte[],要约定好编码,如:UTF8。2:输出参数:byte[],在传输时需要转为string,要约定好编码,如:16进......
  • [代码随想录]Day09-栈与队列part01
    题目:232.用栈实现队列思路:因为go没有栈和队列的类型,直接自己写就行了。比较简单的实现,具体看代码中的注释。代码:typeMyQueuestruct{numbers[]int}funcConstructor()MyQueue{returnMyQueue{numbers:[]int{}}}func(this*MyQueue)Push(xint){......