代码随想录算法训练营第六天|242 有效的字母异位词 349 两个数组的交集 202 快乐数 1 两数之和

文章目录

  • 哈希表
  • 242 有效的字母异位词
    • 思路
    • 代码
    • 总结
  • 349 两个数组的交集
    • 思路
    • 代码
    • 总结
  • 202 快乐数
    • 思路
    • 代码
    • 总结
  • 1 两数之和
    • 思路
    • 代码
    • 总结

哈希表

哈希碰撞:拉链法(链表)线性探测法(顺序向后)
std::unordered_map, std::unordered_set:增删效率和查询效率都是O(1)
判断一个元素是否出现过 -> 哈希法
牺牲空间换时间,使用额外的数组,set或map存放数据

242 有效的字母异位词

思路

若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
考虑用map结构,key为字母,value是出现次数
map中字母不能重复

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (char c : s) {
            int num = c - 'a';
            record[num] ++;
        } 
        for (char c: t) {
            int num = c - 'a';
            record[num] --;
        }
        for (int i = 0; i < 26; i++) {
            if(record[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

总结

  1. 一开始我下意识用的是map,但是看了书发现是用数组,因为数组占用空间小,速度也比较快

349 两个数组的交集

思路

使用set
本题后面 力扣改了 题目描述 和 后台测试数据,增添了 数值范围:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
所以就可以 使用数组来做哈希表了, 因为数组都是 1000以内的。
直接使用set 不仅占用空间比数组大,而且速度要比数组慢,set把数值映射到key上都要做hash计算的。

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> s;
        for (auto num : nums1) {
            s.insert(num);
        }
        for (auto num : nums2) {
            if (s.find(num) != s.end()) {
                // 找到交集
                result.insert(num);
            }
        }
        return vector<int>(result.begin(),result.end());
    }
};

总结

  1. 主要是最终结果也需要用hashset,防止结果中有重复的
  2. vector<int>(s.begin(), s.end())这种写法以前没写过,记忆

202 快乐数

思路

这题自已先写的时候没思路
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法了。

代码

class Solution {
public:
    int getSum(int n) {
        int sum = 0;
        while (n) {
            int i = n%10;
            sum += (i*i);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> s;
        while (n) {
            n = getSum(n);
            if (n == 1) {
                return true;
            }
            if (s.find(n) != s.end()) {
                return false;
            }
            else {
                s.insert(n);
            }
        }
        return false;
    }
};

总结

  1. 对于set的使用不熟练(总是忘记要声明元素类型)

1 两数之和

思路

在这里插入图片描述
再来看一下使用数组和set来做哈希法的局限。

  1. 数组的大小是受限制的,而且如果元素很少,而哈希值太大会造成内存空间的浪费。
  2. set是一个集合,里面放的元素只能是一个key,而两数之和这道题目,不仅要判断y是否存在而且还要记录y的下标位置,因为要返回x 和 y的下标。所以set 也不能用。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result(2);
        unordered_map<int,int> m;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int tmp = target - num;
            if (m.find(tmp) != m.end()) {
                int key = m[tmp];
                result[0] = i;
                result[1] = key;
            }
            else {
                m.insert({num,i});
            }
        }
        return result;
    }
};

总结

  1. unordered_map中查找value:int value = map[key];

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/9949.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

nacos集群搭建

1.本实验使用四台centos7主机&#xff0c;均关闭防火墙和selinux服务 2.数据库选择 不推荐使用nacos自带的嵌入式数据库derby&#xff0c;因为需要保证数据的一致性&#xff0c;本集群使用mysql数据库&#xff0c;因为nacos自带的嵌入式数据库derby是每个nacos服务一个数据库…

Vue - 超详细 Element 组件库主题颜色进行 “统一全局“ 替换,将默认的蓝色主题色更换为其他自定义颜色(保姆级教程,简易且标准全局替换主题色)

前言 网上的文章可以用乱七八糟来形容了,各种奇葩的引入、安装各种东西,本文提供简洁且符合官方标准的解决方案。 Element UI 默认主题色是蓝色,很可能与我们设计稿不一致(比如设计稿是绿色主题), 这时候问题就出现了,难不成每个组件都要来一遍颜色样式覆盖? 绝对不可…

Python 进阶指南(编程轻松进阶):四、起个好名字

原文&#xff1a;http://inventwithpython.com/beyond/chapter4.html 计算机科学中最困难的两个问题是命名事物、缓存失效引起错误."这个经典的笑话&#xff0c;出自利昂班布里克之手&#xff0c;并基于菲尔卡尔顿的一句话&#xff0c;包含了一个真理的核心&#xff1a;很…

第2章 微服务架构的构建

2.1搭建父工程 第一步:新建maven工程,java8 第二步:设置字符编码 第三步:注解激活生效 2.2父工程的pom文件 <?xml version="1.0" encoding="UTF-8

十分钟教你部署一个属于自己的chatgpt网站

&#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是阿牛&#xff0c;全栈领域优质创作者。&#x1f61c;&#x1f4dd; 个人主页&#xff1a;馆主阿牛&#x1f525;&#x1f389; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4d…

Http和Https

http和https的区别 开销&#xff1a;HTTPS 协议需要到 CA 申请证书&#xff0c;一般免费证书很少&#xff0c;需要交费&#xff1b;资源消耗&#xff1a;HTTP 是超文本传输协议&#xff0c;信息是明文传输&#xff0c;HTTPS 则是具有安全性的 ssl 加密传输协议&#xff0c;需要…

【二分汇总】

下面是三个模板&#xff0c;第一个是最容易理解的&#xff0c;第二三个需要背一下&#xff0c;基本满足所有二分题目 // 二分&#xff0c;查target的位置&#xff0c;最容易理解的 int bsearch_0(int[] nums, int l, int r) {while (l < r){int mid (l r) / 2;if (nums[m…

《花雕学AI》01:尝试使用新必应制作《雕爷学编程》的栏目介绍

跨年头尾三个月&#xff0c;花雕走完塔克拉玛干沙漠回来后&#xff0c;突然发现世界变了&#xff0c;微软投资的ChatGPT火起来了&#xff0c;特别是升级的ChatGPT4.0&#xff0c;更是异常火热&#xff01;这一个多月来&#xff0c;人工智能AI突然爆发&#xff0c;能做的事情太多…

HDFS学习笔记 【Namenode/数据块管理】

说明 Namenode关于数据块管理主要做两方面的事情。 文件系统对应数据块 数据块对应数据节点 Block的数据结构 通过Block&#xff0c;BlockInfo,BlocksMap,replica等数据结构表示数据块。 Block 唯一标识一个数据块 包含有比较方法&#xff0c;通过blockId进行比较 BlockI…

OpenAI-ChatGPT最新官方接口《AI绘图》全网最详细中英文实用指南和教程,助你零基础快速轻松掌握全新技术(三)(附源码)

ChatGPT-AI绘图Image generation Beta 图片生成前言IntroductionUsageGenerationsEdits 编辑VariationsLanguage-specific tips 特定语言提示Python 语言Using in-memory image data 使用内存中的图像数据Operating on image data 操作图像数据Error handlingNode.js 语言Using…

CSDN博客写作编辑器如何使用?

文章目录0、引言1、快捷键2、文字3、链接和代码4、注脚和注释5、公式6、表7、图0、引言 笔者阅读CSDN博客已有五年&#xff0c;从最初的学习跟随者&#xff0c;到现在的CSDN博客创造者&#xff0c;这其中的转变来源于自身发展的思考&#xff0c;有学的输入&#xff0c;又有创作…

手撕Twitter推荐算法

Twitter近期开源了其推荐系统源码[1,2,3]&#xff0c;截止现在已经接近36k star。但网上公开的文章都是blog[1]直译&#xff0c;很拗口&#xff0c;因此特地开个系列系统分享下。系列涵盖&#xff1a; Twitter整体推荐系统架构&#xff1a;涵盖图数据挖掘、召回、精排、规则多…

Python人工智能在气象中的实践技术应用

当今从事气象及其周边相关领域的人员&#xff0c;常会涉及气象数值模式及其数据处理&#xff0c;无论是作为业务预报的手段、还是作为科研工具&#xff0c;掌握气象数值模式与高效前后处理语言是一件非常重要的技能。WRF作为中尺度气象数值模式的佼佼者&#xff0c;模式功能齐全…

没有你 万般精彩皆枉然

​​没有你&#xff0c;万般精彩皆枉然。你&#xff0c;是栖息在某人心头之人&#xff0c;更是每一个无可替代的它。万物皆有灵&#xff0c;在不曾踟蹰的千里足迹下&#xff0c;觅得到&#xff1b;在大自然作家笔端浮游的辞藻间&#xff0c;看得透。 《没有你 万般精彩皆枉然》…

ESP32设备驱动-MAX30102脉搏血氧饱和度和心率监测传感器驱动

MAX30102脉搏血氧饱和度和心率监测传感器驱动 文章目录 MAX30102脉搏血氧饱和度和心率监测传感器驱动1、MAX30102介绍2、硬件准备3、软件准备4、驱动实现1、MAX30102介绍 MAX30102是一款集成脉搏血氧饱和度和心率监测生物传感器模块。 它包括内部 LED、光电探测器、光学元件和…

让你的three.js动起来

让你的three.js动起来 简介 本节主要是给实例添加动画效果&#xff0c;以及加了一些小插件用以实现帧率检测、gui可视化配置、动态监听屏幕大小变化刷新和鼠标操控功能。 引入的插件js&#xff1a; three.jsdat.gui.jsStats.jsTrackballControls.js 实际效果&#xff1a; …

Redis高可用高性能缓存的应用系列03 - 缓存过期淘汰策略LRU、LFU

概述 Redis高可用高性能缓存的应用系列的第3篇&#xff0c;主要介绍Redis缓存过期淘汰策略和内存淘汰策略回收的LRU和LFU的知识点进行说明。 Redis过期键删除策略 Redis设置key时&#xff0c;都会设置一个过期时间&#xff0c;那么当过期时间到了都是怎么处理的&#xff1f;…

不用但一定要懂 ---- iOS 之 响应链、传递链 与 手势识别

iOS 事件的主要由&#xff1a;响应连 和 传递链 构成。一般事件先通过传递链&#xff0c;传递下去。响应链&#xff0c;如果上层不能响应&#xff0c;那么一层一层通过响应链找到能响应的UIResponse。 响应链&#xff1a;由最基础的view向系统传递&#xff0c;first view ->…

初谈 ChatGPT

引子 最近&#xff0c;小编发现互联网中的大 V 突然都在用 ChatGPT 做宣传&#xff1a;“ChatGPT不会淘汰你&#xff0c;能驾驭ChatGPT的人会淘汰你”、“带领一小部分人先驾驭ChatGPT”。 确实&#xff0c;ChatGPT这个新生事物&#xff0c;如今被视为蒸汽机、电脑、iPhone 般的…

EfficientNet V2

目录 1. EfficientNet V1存在的问题 2. EfficientNet V2 的亮点 3. EfficientNet V2 网络架构 1. EfficientNet V1存在的问题 针对EfficientNet V1 &#xff0c;作者提出了以下的三个缺点 当训练图像的size很大时&#xff0c;网络中传递的特征图尺寸就会很大&#xff0c;这…