C++算法题 - 哈希表

目录

  • 383. 赎金信
  • 205. 同构字符串
  • 290. 单词规律
  • 242. 有效的字母异位词
  • 49. 字母异位词分组
  • 1. 两数之和
  • 202. 快乐数
  • 219. 存在重复元素Ⅱ
  • 128. 最长连续序列

383. 赎金信

LeetCode_link

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

提示：
1 <= ransomNote.length, magazine.length <= 10^5
ransomNote 和 magazine 由小写英文字母组成

思路：用哈希表

class Solution {
private:
    unordered_map<char, int> hash;
public:
    bool canConstruct(string ransomNote, string magazine) {
        int n = ransomNote.size(), m = magazine.size();
        init_hash(magazine);
        for(int i = 0; i < n; i++){
            if(!delete_hash(ransomNote[i])){
                return false;
            }
        }
        return true;
    }
    void init_hash(string s){
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = 1;
            }else{
                hash[s[i]] ++;
            }
        }
    }
    bool delete_hash(char c){
        if(hash.find(c) != hash.end()){
            if(hash[c] > 1){
                hash[c] --;
            }else{
                hash.erase(c);
            }
            return true;
        }
        return false;
    }
};

思路：思路差不多，用数组，但是时间快一点，空间节省一点
在这里插入图片描述

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int n = ransomNote.size(), m = magazine.size();
        int find[26] = {0};
        for(int i = 0; i < m; i++){
            int num = magazine[i] - 'a';
            find[num] ++;
        }
        for(int i = 0; i < n ; i++){
            if(!delete_find(find, ransomNote[i])){
                return false;
            }
        }
        return true;
    }
    bool delete_find(int find[], char c){
        int num = c - 'a';
        if(find[num] > 0){
            find[num] --;
            return true;
        }
        return false;
    }
};

205. 同构字符串

LeetCode_link

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:
输入：s = “egg”, t = “add”
输出：true

示例 2：
输入：s = “foo”, t = “bar”
输出：false

示例 3：
输入：s = “paper”, t = “title”
输出：true

提示：
1 <= s.length <= 5 * 10^4
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

思路：用哈希表正反映射，因为key是唯一的，但是value不是，所以需要前后两遍。防止"aab"和"aaa"在单向的时候也会映射成功。

class Solution {
private:
    unordered_map<char, char> hash;
public:
    bool isIsomorphic(string s, string t) {
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = t[i];
            }else{
                if(hash[s[i]] != t[i]){
                    return false;
                }
            }
        }
        hash.clear();
        for(int i = 0; i < n; i++){
            if(hash.find(t[i]) == hash.end()){
                hash[t[i]] = s[i];
            }else{
                if(hash[t[i]] != s[i]){
                    return false;
                }
            }
        }
        return true;
    }
};

290. 单词规律

LeetCode_link

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:
输入: pattern = “abba”, s = “dog cat cat dog”
输出: true

示例 2:
输入:pattern = “abba”, s = “dog cat cat fish”
输出: false

示例 3:
输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false

提示:
1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

思路：和上题一样，只不过不能使用同一个哈希表了，因为两侧的数据类型不一样

class Solution {
private:
    unordered_map<char, string> hash_cs;
    unordered_map<string, char> hash_sc;
public:
    bool wordPattern(string pattern, string s) {
        int n = pattern.size(), m = s.size();
        int i = 0;
        int words = 0;
        int start = 0;
        while(i < m && words < n){
            while(s[i] != ' ' && i < m)  i++;
            string cut = s.substr(start, i - start);
            if(hash_cs.find(pattern[words]) == hash_cs.end()){
                hash_cs[pattern[words]] = cut;
            }else{
                if(hash_cs[pattern[words]] != cut){
                    return false;
                }
            }
            if(hash_sc.find(cut) == hash_sc.end()){
                hash_sc[cut] = pattern[words];
            }else{
                if(hash_sc[cut] != pattern[words]){
                    return false;
                }
            }
            words ++;
            i ++;
            start = i;
        }
        if(i < m || words < n)  return false;
        return true;

    }
};

242. 有效的字母异位词

LeetCode_link

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

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

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

提示:
1 <= s.length, t.length <= 5 * 10^4
s 和 t 仅包含小写字母

思路：哈希表统计一个字符串中字符出现的次数，然后再用这个哈希表检查另一个字符串

class Solution {
private:
    unordered_map<char, int> hash;
public:
    bool isAnagram(string s, string t) {
        int n = s.size(), m = t.size();
        if(n != m)  return false;
        init_hash(s);
        for(int i = 0; i < m; i++){
            if(!delete_hash(t[i])){
                return false;
            }
        }
        return true;
    }
    void init_hash(string s){
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = 1;
            }else{
                hash[s[i]] ++;
            }
        }
    }
    bool delete_hash(char c){
        if(hash.find(c) == hash.end()){
            return false;
        }else{
            if(hash[c] > 1){
                hash[c] --;
            }else{
                hash.erase(c);
            }
        }
        return true;
    }
};

49. 字母异位词分组

LeetCode_link

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:
输入: strs = [“”]
输出: [[“”]]

示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路：思路打开，哈希表的value位置可以放容器，用key存放排序后的string，这样，相同的排序后的字符串被放在了一起。

class Solution {
private:
    unordered_map<string, vector<string>> hash;
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> rec;
        int n =strs.size();
        for(int i = 0; i < n; i++){
            string sort_s = strs[i];
            sort(sort_s.begin(), sort_s.end());
            hash[sort_s].push_back(strs[i]);
        }
        for(auto it = hash.begin(); it != hash.end(); it++){
            rec.push_back(it -> second);
        }
        return rec;
    }
};

1. 两数之和

LeetCode_link

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

思路：边找边建哈希表，值作为key，下标作为value。面对有相同值的情况，因为题目中说明只会有唯一解，所以相同值的情况只存在于这俩个相同值同时是答案，因此，当遍历到相同值中的第二个时，就已经可以得到答案。

class Solution {
private:
    unordered_map<int, int> hash;
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(hash.find(target - nums[i]) != hash.end()){
                return {i, hash[target - nums[i]]};
            }else{
                hash[nums[i]] = i;
            }
        }
        return {};
    }
};

202. 快乐数

LeetCode_link

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false

提示：
1 <= n <= 231 - 1

思路：只要历史数字不是1就记录下来，因为是1就是结果了，如果不是1而且还在历史记录中，那就不是快乐数。

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

219. 存在重复元素Ⅱ

LeetCode_link

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

思路：和两数之和思路差不多

class Solution {
private:
    unordered_map<int, int> hash;
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(hash.find(nums[i]) != hash.end() && i - hash[nums[i]] <= k){
                return true;
            }else{
                hash[nums[i]] = i;
            }
        }
        return false;
    }
};

128. 最长连续序列

LeetCode_link

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

思路：

class Solution {
private:
    unordered_map<int, int> hash;
public:
    int longestConsecutive(vector<int>& nums) {
        init_hash(nums);
        int l = 0;
        for(auto it = hash.begin(); it != hash.end(); it++){
            if(it->second == 1) continue;
            int lo = 1;
            int left = it->first - 1;
            int right = it->first + 1;
            it->second = 1;
            while(hash.find(left) != hash.end()){
                hash[left] = 1;
                lo ++;
                left --;
            }
            while(hash.find(right) != hash.end()){
                hash[right] = 1;
                lo ++;
                right ++;
            }
            l = max(l, lo);
        }
        return l;
    }
    void init_hash(vector<int> nums){
        int n = nums.size();
        for(int& i : nums){
            if(hash.find(i) == hash.end()){
                hash[i] = 0;
            }
        }
    }
};

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

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

相关文章

道合顺传感新品上市！高性能氢气传感器DSB14-G3K-J详解

道合顺传感新品上市！高性能氢气传感器DSB14-G3K-J详解

道合顺传感高性能氢气传感器DSB14-G3K-J正式发布&#xff01;超强抗干扰能力优势明显。应对氢气安全挑战、高性能氢气传感器国产化、为储能保驾护航。 氢气&#xff0c;作为现今能源领域中的新贵&#xff0c;在储能行业中应用广泛且备受瞩目。但氢气易燃、易爆特性使其在生产、…
阅读更多...
gradle.properties 中文字符乱码问题

gradle.properties 中文字符乱码问题

我用AS开发Android应用。在gradle.properties中输入中文&#xff0c;再次打开时&#xff0c;发现中文变成了&#xff1f;&#xff1f;&#xff1f;。上网查询&#xff0c;发现了一个解决办法&#xff1a; 在菜单File-Settings-Editor-File Encodings中&#xff0c;将“Default…
阅读更多...
【复习笔记】FreeRTOS(五)时间片调度

【复习笔记】FreeRTOS(五)时间片调度

本文是FreeRTOS复习笔记的第五节&#xff0c;时间片调度。 上一篇文章&#xff1a; 【复习笔记】reeRTOS(四) 列表项的插入和删除 文章目录 1.时间片调度简介1.1. 运行过程 二、实验设计三、测试例程四、实验效果 1.时间片调度简介 FreeRTOS支持多个任务同时拥有一个优先级&am…
阅读更多...
春藤实业启动SAP S/4HANA Cloud Public Edition项目，与工博科技携手数字化转型之路

春藤实业启动SAP S/4HANA Cloud Public Edition项目，与工博科技携手数字化转型之路

3月11日&#xff0c;广东省春藤实业有限公司&#xff08;以下简称“春藤实业”&#xff09;SAP S/4HANA Cloud Public Edition&#xff08;以下简称“SAP ERP公有云”&#xff09;项目正式启动。春藤实业董事长陈董、联络协调项目经理慕总、内部推行项目经理陈总以及工博董事长…
阅读更多...
数仓建模—数据架构

数仓建模—数据架构

数仓—数据架构 为了在企业决策中使用数据，数据必须经过整个数据平台的各个阶段。整个过程是什么样子的，从开始到结束？原始形式的数据是如何转化为可导致商业决策的见解的？这些问题可以通过数据架构来回答。 数据架构是指记录组织所有数据资产的模型、规则和标准。它映射…
阅读更多...
Web前端-JavaScript

Web前端-JavaScript

黑马程序员JavaWeb开发教程 文章目录 一、js引入方式1、内部脚本2、外部脚本 二、js基础语法1、书写语法&#xff08;1&#xff09;基本语法&#xff08;2&#xff09;输出语句 2、变量&#xff08;1&#xff09;变量&#xff08;2&#xff09;注意事项 3、数据类型、运算符、流…
阅读更多...
spring-数据处理及跳转

spring-数据处理及跳转

结果跳转方式 ModelAndView 设置ModelAndView对象 , 根据view的名称 , 和视图解析器跳到指定的页面 . 页面 : {视图解析器前缀} viewName {视图解析器后缀} <!-- 视图解析器 --> <bean class"org.springframework.web.servlet.view.InternalResourceViewRes…
阅读更多...
Java定时任务

Java定时任务

一、java.util.Timer java.util.Timer 类允许您在未来的某个时间执行一个任务&#xff0c;或者在一定的时间间隔执行任务。您可以创建一个 Timer 实例&#xff0c;并调用其 schedule() 方法来安排任务的执行。这种方式比较简单&#xff0c;但在高并发环境下可能不够灵活。 1.…
阅读更多...
Git学习与码云实战

Git学习与码云实战

Git学习与码云实战 Git安装 概述&#xff1a; Git 是一个开源的分布式版本控制系统&#xff0c;可以有效、高速的处理从很小到非常大的项目版本管理&#xff0c;是目前使用范围最广的版本管理工具。 下载安装&#xff1a; 下载地址&#xff1a;https://git-scm.com/ 下载后傻瓜…
阅读更多...
李彦宏：开源模型会越来越落后

李彦宏：开源模型会越来越落后

李彦宏&#xff1a;开源模型会越来越落后 昨天听完的李总讲座 大家以前用开源觉得开源便宜&#xff0c;其实在大模型场景下&#xff0c;开源是最贵的。所以&#xff0c;开源模型会越来越落后。 ——李彦宏 至于开源还是闭源&#xff0c;这和企业的利益息息相关。 随着科技的迅猛…
阅读更多...
双向链表详解

双向链表详解

一.双向链表结构 我们一般所说的双向链表是带头循环双向链表&#xff0c;这里的带头更我们之前的头节点不是一回事。带头链表里的头节点&#xff0c;实际上为哨兵位&#xff0c;哨兵位的头节点种是不存放任何有效数据的&#xff0c;只是站在这里起到放哨的作用。 哨兵位的意义…
阅读更多...
【C++从练气到飞升】08---模板

【C++从练气到飞升】08---模板

&#x1f388;个人主页&#xff1a;库库的里昂 ✨收录专栏&#xff1a;C从练气到飞升 &#x1f389;鸟欲高飞先振翅&#xff0c;人求上进先读书。 目录 一、泛型编程 什么是泛型编程: 二、函数模板 1. 函数模板概念 2. 函数模板格式 3. 函数模板的原理 4. 函数模板的实例…
阅读更多...
Nginx part2.2

Nginx part2.2

目录 如何用Nginx搭建多网址服务器&#xff1f; 基于ip地址的虚拟主机 1. 先建立存储网页的目录 2.进行子配置 3.编写.conf文件 基于端口号的虚拟主机 基于域名的虚拟主机 如何用Nginx搭建多网址服务器&#xff1f; 有些网站&#xff0c;ip不同&#xff0c;域名不同&…
阅读更多...
格林兰岛和南极洲的流域边界文件下载

格林兰岛和南极洲的流域边界文件下载

&#xff08;1&#xff09;南极流域系统边界和掩蔽区 下图显示了由戈达德冰面高程小组使用ICESat数据开发的南极分水岭。我们对西南极冰盖&#xff08;系统18-23和1&#xff09;、东南极冰盖&#xff08;系统2-17&#xff09;和南极半岛&#xff08;系统24-27&#xff09;的定…
阅读更多...
案例与脚本实践：DolphinDB 轻量级实时数仓的构建与应用

案例与脚本实践：DolphinDB 轻量级实时数仓的构建与应用

DolphinDB 高性能分布式时序数据库&#xff0c;具有分布式计算、事务支持、多模存储、以及流批一体等能力&#xff0c;非常适合作为一款理想的轻量级大数据平台&#xff0c;轻松搭建一站式的高性能实时数据仓库。 本教程将以案例与脚本的方式&#xff0c;介绍如何通过 Dolphin…
阅读更多...
LevelDB源码阅读笔记（1、整体架构）

LevelDB源码阅读笔记（1、整体架构）

LevelDB源码阅读笔记&#xff08;1、整体架构&#xff09; LeveDB源码笔记系列&#xff1a; LevelDB源码阅读笔记&#xff08;0、下载编译leveldb&#xff09; LevelDB源码阅读笔记&#xff08;1、整体架构&#xff09; 前言 对LevelDB源码的博客&#xff0c;我准备采用总…
阅读更多...
ragflow知识库使用案例

ragflow知识库使用案例

参考： https://github.com/infiniflow/ragflow/blob/main/README_zh.md 支持丰富的文件类型，包括 Word 文档、PPT、excel 表格、txt 文件、图片、PDF、影印件、复印件、结构化数据, 网页等。 运行步骤： 1、确保 vm.max_map_count 不小于 262144 【更多】： 如需确认 vm.…
阅读更多...
【大数据】分布式文件系统HDFS

【大数据】分布式文件系统HDFS

目录 1.什么是分布式文件系统 2.HDFS的特点 3.HDFS的核心概念 4.HDFS的体系结构 5.HDFS的配置建议 6.HDFS的局限性 7.HDFS的存储机制 7.1.数据冗余机制 7.2.错误与恢复 8.HDFS数据读写过程 1.什么是分布式文件系统 分布式文件系统是整个大数据技术的基础&#xff0c…
阅读更多...
单位个人信息宣传这样投稿审核轻松出稿快

单位个人信息宣传这样投稿审核轻松出稿快

在我担任单位信息宣传员的初期阶段,每月的对外信息宣传任务就像一座大山横亘在前,尤其是与媒体对接、投稿发表的工作,更是充满了挑战与艰辛。那段时光,我如同一个摸索前行的独行者,在浩瀚的媒体海洋中“摸着石头过河”。 我曾经花费大量的时间逐一查找各类媒体联系方式,通过电话…
阅读更多...
短视频去水印解析接口 可测试

短视频去水印解析接口 可测试

短视频解析聚合接口80多个热们短视频平台。可测试 接口开发文档&#xff1a; 返回格式&#xff1a; JSON 请求方式&#xff1a; GET/POST 示例请求地址&#xff1a;https://www.dspqsy.vip/spapi?keykey&url短视频url 请求参数说明&#xff1a; 字段必填类型说明url是…
阅读更多...
最新文章

Copyright @ 2022~2023