面试算法之哈希专题

赎金信

在这里插入图片描述

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {// 小写字母int r_cnt[26];int m_cnt[26];for(int i = 0; i< magazine.size(); i++) {m_cnt[magazine[i]-'a']++; // 统计}// 对比for(int i = 0; i< ransomNote.size(); i++) {if(m_cnt[ransomNote[i]-'a']) {m_cnt[ransomNote[i]-'a']--;} else {return false;}}return true;}
};
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {// 小写字母int r_cnt[26];int m_cnt[26];for(int i = 0; i< magazine.size(); i++) {m_cnt[magazine[i]-'a']++; // 统计}// 对比for(int i = 0; i< ransomNote.size(); i++) {if(m_cnt[ransomNote[i]-'a']) {m_cnt[ransomNote[i]-'a']--;} else {return false;}}return true;}
};

同构字符串

在这里插入图片描述

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char,char> s_map;unordered_map<char,char> t_map;int s_size = s.size();int t_size = t.size();if(s_size != t_size) {return false;} for(int i = 0; i< s_size; i++) {char x = s[i];char y = t[i];if((s_map.count(x) && s_map[x] != y) || (t_map.count(y) && t_map[y] != x)) {return false;}s_map[x] = y;t_map[y] = x;}return true;    }
};

收获

了解了一下 有关于 unordered_map 中 count 函数的使用
s_map.count(x) 就是 键为 x 的个数

逐步解析
在这里插入图片描述

方法二
思路

通过 match 建立关系
通过 count 记录 t[i] 是否已经有映射

这部分是表示, 不存在 s[i] 的映射, 但是发现 t[i] 已经做好映射了 ( count[t[i]] > 0 ) 直接返回 false

  			if (match[s[i]] == '\0') { // 如果当前字符没有映射关系if (count[t[i]] == 0) { // 如果当前字符在t中没有出现过match[s[i]] = t[i]; // 建立映射关系count[t[i]] = 1; // 将该字符在t中的出现次数加1}elsereturn false; // 如果当前字符在t中已经出现过,则返回false}

在这里插入图片描述
图解
在这里插入图片描述

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, char> match; // 用于存储字符之间的映射关系unordered_map<char, int> count; // 用于记录字符在t中出现的次数for (int i = 0; i < s.size(); i++) {if (match[s[i]] == '\0') { // 如果当前字符没有映射关系if (count[t[i]] == 0) { // 如果当前字符在t中没有出现过match[s[i]] = t[i]; // 建立映射关系count[t[i]] = 1; // 将该字符在t中的出现次数加1}elsereturn false; // 如果当前字符在t中已经出现过,则返回false}else { // 如果当前字符已经有映射关系if (match[s[i]] != t[i]) { // 如果映射关系不正确return false; // 返回false}}}return true; // 所有字符都满足同构条件,返回true}
};
class Solution {
public:bool wordPattern(string pattern, string s) {unordered_map<string,char> s_patterMap;unordered_map<char, string> pattern_sMap;// 遍历int p_len = pattern.size();int left = 0;int right = 0;for(int i = 0; i< p_len ; i++) {if(left >= s.size()) {return false;}// 遍历while(right < s.size() && s[right] != ' ') right++;// 右边界 right string str = s.substr(left, right-left);if(s_patterMap.count(str) && s_patterMap[str] != pattern[i]) {return false;}if(pattern_sMap.count(pattern[i]) && pattern_sMap[pattern[i]] != str) {return false;}s_patterMap[str] = pattern[i];pattern_sMap[pattern[i]] = str;left = right + 1;right = left;}if(right < s.size()) {return false;} else {return true;}}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

树与二叉树之间的转换

树转化成二叉树&#xff1a;兄弟相连留长子 1.加线&#xff1a;在兄弟之间加一条线 2.抹线&#xff1a;对每个结点&#xff0c;除了其左孩子外&#xff0c;去除其与其余孩子之间的关系 3.旋转&#xff1a;以树的根结点为轴心&#xff0c;将整树顺时针转45 二叉树转化成为树…

Day65:代码随想录训练营总结

两个月的算法训练营之旅圆满落幕&#xff0c;回首这段时光&#xff0c;我深感自己错过了许多早日成长的机会&#xff0c;如今不禁懊悔没有更早地报名参与。 这段充实的日子里&#xff0c;我遵循着训练营精心设计的计划&#xff0c;攻克了上百道力扣题目。从最初对编程语法的生…

react18【实战】tab切换,纯前端列表排序(含 lodash 和 classnames 的安装和使用)

技术要点 动态样式 className{tabItem ${currentType item.value && "active"}}安装 lodash npm i --save lodash使用 lodash 对对象数组排序&#xff08;不会改变源数组&#xff09; _.orderBy(dataList, "readNum", "desc")src\De…

如何正确使用防静电擦拭纸以确保产品质量

在现代工业生产中&#xff0c;防静电擦拭纸扮演着至关重要的角色&#xff0c;它们被广泛应用于各种电子产品、精密仪器以及其他对静电敏感的领域。然而&#xff0c;要想确保防静电擦拭纸发挥最佳效果&#xff0c;正确的使用方法至关重要。下面优斯特将介绍如何正确使用防静电擦…

调试代码问题汇总

1.最常见的就是数据库密码不对。根据调试视频将你的数据库密码设置正确&#xff0c;数据库密码是数字的优先直接连如果不成功可以加个双引号或者单引号。 提示&#xff1a;java.sql.SQLException: Access denied for user rootlocalhost (using password: YES) 2.原本配置好的…

什么是HTTP/2?

HTTP/2&#xff08;原名HTTP 2.0&#xff09;即超文本传输协议第二版&#xff0c;使用于万维网。HTTP/2主要基于SPDY协议&#xff0c;通过对HTTP头字段进行数据压缩、对数据传输采用多路复用和增加服务端推送等举措&#xff0c;来减少网络延迟&#xff0c;提高客户端的页面加载…

C++ -- 函数重载 、引用、 内联函数、auto、基于范围的for循环、指针空值nullptr

目录 1.函数重载 1.1函数重载: 1.2函数重载需要注意&#xff1a; 1.3函数重载的一些特殊情况 1.4为什么C语言不支持函数重载&#xff0c;C支持函数重载&#xff1f;底层逻辑是&#xff1f; 2.引用 2.1 引用特性 2.2 常引用 2.3 权限问题&#xff08;权限放大&#xff0c;…

QT:QT与操作系统

文章目录 信号槽与事件QT多线程概述原理完成倒计时程序 UDP回显服务器服务端客户端 信号槽与事件 在之前的信号槽中&#xff0c;已经有了一个基本的认识&#xff0c;那么对于QT中事件的理解其实就非常的类似&#xff0c;当用户进行某种操作的时候&#xff0c;就会触发事件&…

【洛谷】动态规划之最长公共子序列

前言&#xff1a; 本系列目的是记录日常所刷的题&#xff0c;有的是自己想出来的题&#xff0c;有的是看了大佬题解后想明白的题 题目 P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 前提&#xff1a; 两个排列都是1到n的排列&#xff0c;说…

linux安装 mysql

环境&#xff1a;centOS8 一、安装 1 安装wget库 sudo yum -y install wget 2. 安装 mysql 换yum源 亲测成功&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 换yum源 1.下载对应版本的repo文件 wget -O CentOS-Base.repo http://mirrors…

ESLint: Unexpected ‘debugger‘ statement.(no-debugger)(debugger报红)

ESLint: Unexpected debugger statement.(no-debugger) 解决办法&#xff1a; 找到.eslintrc.js文件中rules的no-debugger更改为0即可

200-500人规模工厂网络方案(中小企业网络)

一、方案概述 工厂一般有单独的弱电房&#xff0c;类似这种 里面采用的方案如下&#xff1a; 主要考虑有线、无线、财务、办公、访客等业务&#xff0c;便于维护管理和后续扩容 还需要 Wi-Fi覆盖零死角高速率&#xff0c;工作不卡顿 同时考虑AV反病毒、IPS入侵防御、用户准…

【LLama】Llama3 的本地部署与lora微调(基于xturn)

系列课程代码文档&#xff08;前2节课可跳过&#xff09;&#xff1a;https://github.com/SmartFlowAI/Llama3-Tutorial 课程视频&#xff1a;https://space.bilibili.com/3546636263360696/channel/series XTuner &#xff1a;https://github.com/InternLM/xtuner/blob/main/R…

内网安全-代理Socks协议路由不出网后渗透通讯CS-MSF控制上线简单总结

我这里只记录原理&#xff0c;具体操作看文章后半段或者这篇文章内网渗透—代理Socks协议、路由不出网、后渗透通讯、CS-MSF控制上线_内网渗透 代理-CSDN博客 注意这里是解决后渗透通讯问题&#xff0c;之后怎么提权&#xff0c;控制后面再说 背景 只有win7有网&#xff0c;其…

对XYctf的一些总结

对XYctf的一些总结 WEB 1.http请求头字段 此次比赛中出现的&#xff1a; X-Forwarded-For/Client-ip&#xff1a;修改来源ip via&#xff1a;修改代理服务器 还有一些常见的字段&#xff1a; GET&#xff1a;此方法用于请求指定的资源。GET请求应该安全且幂等&#xff0c…

C++ 如何进阶?

一、C基础&#xff08;3个月&#xff09; 1、面向对象的三大特性&#xff1a;封装、继承、多态 2、类的访问权限&#xff1a;private、protected、public 3、类的构造函数、析构函数、赋值函数、拷贝函数 4、移动构造函数与接贝构造函数对比 5、深接贝与浅贝的区别 6、空…

超标量处理器设计:重排序缓存(ROB)

★超标量处理器的很多地方用到了重排序缓存&#xff0c;但是我对它不是很了解&#xff0c;所以我整理一下重排序缓存的知识点。 重排序缓存(ROB)在确保乱序执行的指令能够正确地完成和提交(Commit)&#xff0c;也可以用来寄存器重命名。 ROB是一个先进先出的表&#xff0c;每个…

教你解决PUBG绝地求生游戏中闪退掉线无法重连回去的问题

《绝地求生》&#xff08;PUBG&#xff09;&#xff0c;作为一款在全球范围内掀起热潮的战术竞技游戏&#xff0c;以其栩栩如生的战场环境和令人心跳加速的生存冒险博得了广大玩家的青睐。然而&#xff0c;一些玩家在经历了一场惊心动魄的对局后&#xff0c;却面临了一个不大不…

uniapp video 层级覆盖

层级覆盖 cover-view组件 我这里做了个判断 监听全屏时隐藏按钮 根据项目需求自行更改

汉诺塔问题和爬楼梯(递归)

感谢大佬的光临各位&#xff0c;希望和大家一起进步&#xff0c;望得到你的三连&#xff0c;互三支持&#xff0c;一起进步 个人主页&#xff1a;LaNzikinh-CSDN博客 c语言基础_LaNzikinh篮子的博客-CSDN博客 文章目录 一.爬楼梯问题二.汉诺塔问题总结 一.爬楼梯问题 假设你正…