首页 > 其他分享 >day5代码随想录

day5代码随想录

时间:2023-12-04 11:48:55浏览次数:40  
标签:std map set key 代码 day5 随想录 哈希 unordered

哈希表理论基础;242.有效的字母异位词349. 两个数组的交集202. 快乐数1. 两数之和

来源:代码随想录 (programmercarl.com)

6.2 哈希冲突 - Hello 算法 (hello-algo.com)

1哈希表理论基础

又称散列表

一般哈希表都是用来快速判断一个元素是否出现集合里。

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法

1.1哈希函数

  1. 通过某种哈希算法 hash() 计算得到哈希值。
  2. 将哈希值对桶数量(数组长度)capacity 取模,从而获取该 key 对应的数组索引 index

1.2哈希碰撞

2个输入元素都索引到了相同的输出位置,称为哈希碰撞

解决方法

  • 扩容哈希表

「负载因子 load factor」是哈希表的一个重要概念,其定义为哈希表的元素数量除以桶数量,用于衡量哈希冲突的严重程度,也常作为哈希表扩容的触发条件

  • 改良哈希表数据结构,使得哈希表可以在出现哈希冲突时正常工作
  • 仅在必要时,即当哈希冲突比较严重时,才执行扩容操作。

1.2.1 链式地址

image-20231204095526802

1.2.2 开放寻址

1. 线性探测

image-20231204095637640

2. 平方探测

平方探测与线性探测类似,都是开放寻址的常见策略之一。当发生冲突时,平方探测不是简单地跳过一个固定的步数,而是跳过“探测次数的平方”的步数,即 1,4,9,… 步。

3. 多次哈希

顾名思义,多次哈希方法使用多个哈希函数f1(x)、f2(x)… 进行探测。

1.3 三种哈希算法的数据结构

1.3.1 数组

1.3.2 set(集合)

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 O(log n) O(log n)
std::multiset 红黑树 有序 O(logn) O(logn)
std::unordered_set 哈希表 无序 O(1) O(1)

红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

1.3.3 map(映射)

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

2 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

2.1 思路

暴力法:2层for循环

数组哈希表法:以空间换时间,定义一个26大小的数组,记录在字符串s中出现的字母次数,在字符串t中做减法,如果数组全为空,就说明是字母异位词。(包含完全相同的情况)

2.2 代码

/**
 * @file hash_2.h
 * @author nrt ([email protected])
 * @brief 有效的字母异位词
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include <iostream>

using namespace std;
class Solution {
public:
    bool isAnagram(string s, string t){
        int A[26] = {0};
        //字符串s计字符出现次数。做加法
        for(int i =0; i < s.size(); i++){

            A[s[i] - 'a'] ++;
        }
        //字符串t计字符出现次数,做减法
        for(int j = 0; j < t.size(); j++){
            A[t[j] - 'a'] --;
        }
        //不为零,就说明有字符不同
        for(int x = 0; x < 26 ; x++){
            if(A[x] != 0){
                return false;
            }

            return true;
        }
        
    }

};

3 两个数组的交集

给定两个数组,编写一个函数来计算它们的交集。

3.1 思路

主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。

3.2 unordered_set

无序集合(unordered_set)是一种使用哈希表实现的无序关联容器,其中键被哈希到哈希表的索引位置,因此插入操作总是随机的。

​ 无序集合上的所有操作在平均情况下都具有常数时间复杂度O(1),但在最坏情况下,时间复杂度可以达到线性时间O(n),这取决于内部使用的哈希函数,但实际上它们表现非常出色,通常提供常数时间的查找操作。

3.3 代码

/**
 * @file hash_3.h
 * @author nrt ([email protected])
 * @brief 3 两个数组的交集
 *          给定两个数组,编写一个函数来计算它们的交集。
 *          学会使用一种哈希数据结构:unordered_set
 * @version 0.1
 * @date 2023-12-04
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#include <vector>
#include <unordered_set>


using namespace std;
class Solution{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        //数组1的头到尾
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2){
            if(nums_set.find(num) != nums_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());

    }



};

4.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

如果 n 是快乐数就返回 True ;不是,则返回 False 。

image-20231204105458198

4.1 思路

​ 判断sum是否重复出现就可以使用unordered_set。

​ 这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。

4.2 代码

/**
 * @file hash_4.h
 * @author nrt ([email protected])
 * @brief 快乐数
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include<iostream>
#include<unordered_set>

using namespace std;

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n){
        int sum = 0;
        while (n)
        {
            sum = (n%10) * (n%10);
            n = n/10;
        }
    }
    bool isHappy(int n) {
        unordered_set<int> result_set;
        while(1){
            int sum = getSum(n);
            if(sum == 1){
                return true;
            }

            if (result_set.find(sum) != result_set.end()) {
                return false;
            } else {
                result_set.insert(sum);
            }
            n = sum;
        }
    }

};

5. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

5.1 思路

本题,我们不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适

5.2 unordered_map

C++总结(7):STL无序容器之unordered_set、unordered_map、unordered_multiset、unordered_multimap详解-CSDN博客

5.3 代码

/**
 * @file hash_5.h
 * @author nrt ([email protected])
 * @brief 两数之和
 * @version 0.1
 * @date 2023-12-04
 * 
 * @copyright Copyright (c) 2023
 * 
 */
#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int, int> map;
            for(int i = 0; i < nums.size(); i++){
                auto iter = map.find(target - nums[i]);
                if(iter != map.end()){
                    return {iter->second, i};//iter->second
                }
                map.insert(pair<int,int>(nums[i], i));//pair
            }

            return {};

    }
};

总结:

需要学习C++的STL。对STL无序容器之unordered_set、unordered_map不熟悉。

代码复现不熟练。

标签:std,map,set,key,代码,day5,随想录,哈希,unordered
From: https://www.cnblogs.com/nrtnrt/p/17874555.html

相关文章

  • Vue3用户代码片段
    1.defineComponent语法{ "Printtoconsole":{ "prefix":"vue3", "body":[ "<template>", "<divclass=\"container\">", "", "</div>&q......
  • 【iOS源码混淆工具】iOS代码混淆工具
     主要功能IpaGuard是一款功能强大的ipa混淆工具,不需要iosapp源码,直接对ipa文件进行混淆加密。可对IOSipa文件的代码,代码库,资源文件等进行混淆保护。可以根据设置对函数名、变量名、类名等关键代码进行重命名和混淆处理,降低代码的可读性,增加ipa破解反编译难度。可以对图片,......
  • iOS代码混淆工具
    ​ iOS代码混淆工具......
  • Leetcode刷题day5-哈希表.异位词.交集.快乐数.两数和
    242.有效的字母异位词242.有效的字母异位词-力扣(LeetCode)给定两个字符串 _s_ 和 _t_ ,编写一个函数来判断 _t_ 是否是 _s_ 的字母异位词。注意:若 _s_ 和 _t_ 中每个字符出现的次数都相同,则称 _s_ 和 _t_ 互为字母异位词。示例 1:输入:s="anagram",......
  • emscripten 中c 代码引用外部js 函数
    主要是一个简单的学习,webassebly支持通过import调用环境的函数(比如调用浏览器或者nodejs中的一些方法)简单说明方法很多,包含了emscripten提供的调用js的宏,但是以下使用了一个emscripten提供的--js-library功能--js-library简单说明--js-library主要是实现emcc在编译的时......
  • 新建模块&新建用户表&修改代码生成器文件&新建菜单
    1.新建模块打开IDEA在项目结构中新建rome-hotel的一个springboot项目,什么依赖都不需要 在pom.xml文件中修改坐标,引用父坐标 在父级pom文件中将模块加入 在rome-admin中的pom文件中加入admin-hotel,这样就能带动这个模块启动 将包名修改成和rome-admin一样 再创建其......
  • 代码随想录算法训练营第5天 | lc242、lc349、lc202、lc1
    (本合集全部为Go语言实现)相关文章链接:242题解349202题解1题解相关视频链接:Leetcode242状态:秒了实现过程中的难点:对于元素固定是小写字母或类似的情况,可以使用数组,因为元素最大数量是固定的个人写法funcisAnagram(sstring,tstring)bool{iflen(s)!=len(t)......
  • C++分解质因数代码实现
    一、问题描述:什么叫做分解质因数?就是我们给定一个数字,把这个数字的是质数的因子按照从小到大的顺序排列出来,并输出每个质因子的个数。二、实现思路:就是我们从1~n/i这个范围内(i*i=n),如果找到了一个因子,使得n%i==0,那么我们就进一步除下去,直到无法满足n%i==0为止。这个时候,i一定......
  • R语言中的偏最小二乘回归PLS-DA|附代码数据
    原文链接:http://tecdat.cn/?p=8890原文出处:拓端数据部落公众号最近我们被要求撰写关于偏最小二乘回归PLS-DA的研究报告,包括一些图形和统计输出。主成分回归(PCR)的方法本质上是使用第一个方法的普通最小二乘(OLS)拟合来自预测变量的主成分(PC)。这带来许多优点:预测变量的数量实际......
  • R语言Outliers异常值检测方法比较|附代码数据
    原文链接:http://tecdat.cn/?p=8502原文出处:拓端数据部落公众号最近我们被客户要求撰写关于异常值检测的研究报告,包括一些图形和统计输出。识别异常值的方法有很多种,R中有很多不同的方法。 关于异常值方法的文章结合了理论和实践。理论一切都很好,但异常值是异常值,因为它们不遵......