首页 > 编程语言 >Offer必备算法14_哈希表_五道力扣题详解(由易到难)

Offer必备算法14_哈希表_五道力扣题详解(由易到难)

时间:2024-03-16 18:33:00浏览次数:41  
标签:hash 14 nums Offer 由易到难 元素 示例 vector 哈希

目录

①力扣1. 两数之和

解析代码

②力扣面试题 01.02. 判定是否互为字符重排

解析代码

③力扣217. 存在重复元素

解析代码

④力扣219. 存在重复元素 II

解析代码

⑤力扣49. 字母异位词分组

解析代码

本篇完。


①力扣1. 两数之和

1. 两数之和

难度 简单

给定一个整数数组 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
  • 只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

    }
};

解析代码

        事先将数组内的元素下标绑定在⼀起存入哈希表中,然后直接在哈希表中查找每⼀个元素的 target - nums[i] ,就能快速的找到目标和的下标。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash; // 数组元素和下标
        for(int i = 0; i < nums.size(); ++i)
        {
            auto it = hash.find(target - nums[i]);
            if(it != hash.end())
                return {it->second, i};
            hash[nums[i]] = i;
        }
        return {-1, -1}; // 照顾编译器
    }
};

②力扣面试题 01.02. 判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排

难度 简单

给定两个由小写字母组成的字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。

示例 1:

输入: s1 = "abc", s2 = "bca"
输出: true 

示例 2:

输入: s1 = "abc", s2 = "bad"
输出: false

说明:

  • 0 <= len(s1) <= 100
  • 0 <= len(s2) <= 100
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {

    }
};

解析代码

        当两个字符串的长度不相等的时候,是不可能构成互相重排的,直接返回 false。

        如果两个字符串能够构成互相重排,那么每个字符串中各个字符出现的次数⼀定是相同的。因此,可以分别统计出这两个字符串中各个字符出现的次数,然后逐个比较是否相等即可。这样的话,就可以选择哈希表来统计字符串中字符出现的次数。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if(s1.size() != s2.size())
            return false;
        int hash[26] = {0};
        for(auto& e : s1) // s1元素全部进入哈希表
        {
            hash[e - 'a']++;
        }
        for(auto& e : s2) // 判断哈希表中有没有s2元素
        {
            hash[e - 'a']--;
            if(hash[e - 'a'] < 0)
                return false;
        }
        return true;
    }
};

③力扣217. 存在重复元素

217. 存在重复元素

难度 简单

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。

示例 1:

输入:nums = [1,2,3,1]
输出:true

示例 2:

输入:nums = [1,2,3,4]
输出:false

示例 3:

输入:nums = [1,1,1,3,3,4,3,2,4,2]
输出:true

提示:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {

    }
};

解析代码

        至少两次的意思就是数组中存在着重复的元素,因此可以无需统计元素出现的数目。仅需在遍历数组的过程中,检查当前元素是否在之前已经出现过即可。

        因此可以利用哈希表,仅需存储数组内的元素。在遍历数组的时候,一边检查哈希表中是否 已经出现过当前元素,一边将元素加入到哈希表中。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for(auto& e : nums)
        {
            if(hash.count(e)) // 如果哈希表中存在此元素
                return true;
            hash.insert(e);
        }
        return false;
    }
};

④力扣219. 存在重复元素 II

219. 存在重复元素 II

难度 简单

给你一个整数数组 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 {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {

    }
};

解析代码

        快速定位到两个信息: 两个相同的元素 这两个相同元素的下标。 因此,可以使用哈希表,令数组内的元素做 key 值,该元素所对应的下标做 val 值,将数组元素和下标绑定在⼀起,存到哈希表中。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 元素和下标
        for(int i = 0; i < nums.size(); ++i)
        {
            if(hash.count(nums[i])) // 如果哈希表中存在此元素
            {
                if(hash[nums[i]] - i <= k) // 如果此元素下标与当前下标的差<=k
                    return true;
            }
            hash[nums[i]] = i; // 覆盖前面的也没事,因为找<=k的
        }
        return false;
    }
};

⑤力扣49. 字母异位词分组

49. 字母异位词分组

难度 中等

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

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

示例 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] 仅包含小写字母
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
    }
};

解析代码

        互为字母异位词的单词有⼀个特点:将它们排序之后,两个单词应该是完全相同的。 所以可以利用这个特性,将单词按照字典序排序,如果排序后的单词相同的话,就划分到同一组中。

        这时我们就要处理两个问题:

  • 排序后的单词与原单词需要能互相映射
  • 将排序后相同的单词划分到同⼀组

利用语言提供的容器的强大的功能就能实现这两点:

  • 将排序后的字符串( string )当做哈希表的 key 值
  • 将字母异位词数组( vector<string> )当成 val 值。
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(auto& e : strs)
        {
            string tmp = e;
            sort(tmp.begin(), tmp.end()); // 排序后异位次的key值都相等了
            hash[tmp].push_back(e);
        }

        vector<vector<string>> ret;
        for(auto& [x, y] : hash) // 范围for得到两个值的用法
        {
            ret.push_back(y);
        }
        return ret;
    }
};

本篇完。

下一篇是简单多问题dp类型的动态规划,下下篇是字符串类型的OJ。

标签:hash,14,nums,Offer,由易到难,元素,示例,vector,哈希
From: https://blog.csdn.net/GRrtx/article/details/136544025

相关文章

  • P4211 [LNOI2014] LCA 题解
    link切入这道题,首先要思考所有LCA的分布特征。显然,对于任意\(\text{LCA}(i,j)\),都满足LCA是\(i,j\)的祖先。那么对于一个询问,可以找到所有\(i\in[l,r]\)的祖先,还可以找所有\(z\)的祖先。明显,找\(z\)的祖先会方便很多:它们都分布在\(z\)到根节点的那条链上,这应......
  • abc214D 全部路径最大边权之和
    给定一颗包含n个顶点的树,第i条边连接u[i]和v[i],边权为w[i]。记f(i,j)表示顶点i到j的简单路径上边权的最大值,求$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(i,j)$。2<=n<=1e5;1<=u[i],v[i]<=n;1<=w[i]<=1e7对于每条边,考虑以它作为最大边权的路径数,为两侧节点数的乘积,数点可以用并......
  • 首师大附中集训D5日报(20231214)-总结部分
    今天做了6道题,还可以,剩下的基本是一点都不会了,太难了,等我理解再深刻一点再回来做一下吧今天有几道题是完全靠自己想出来的了,挺好一会把前几天的专题再补一下昨天的做题的讲题彻底打醒了我,我什么都不是,我照我需要达到的高度差远了我来这里不就是为了这个的吗既然经受了大幅度......
  • 酷睿i9 14900hx参数 i914900hx核显什么水平
    i914900hx采用Intel7制程工艺,有24核心,其中8个高性能核心,16个高效能核心,共32线程,P核心最大睿频5.8GHz,全核最大睿频5.2GHz;E核心最大睿频/全核心最大睿频4.1GHz,L2缓存32MB、L3缓存36MB,TDP55W,最大可配置功耗为157W,内存支持DDR55600MHz。i914900hx怎么样这些点很重要 http:/......
  • CF145C Lucky Subsequence 题解
    首先,我们对这个幸运数进行分析,发现:\(10^9\)以内只有\(1023\)个幸运数,即\(\sum\limits_{i=0}^92^i\)个。考虑对幸运数和非幸运数分类讨论。幸运数部分:01背包裸题,\(dp_{i,j}\)表示前\(i\)个幸运数里选了\(j\)个,转移方程为\(dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\tim......
  • LibreOJ 4114 「联合省选 2024」迷宫守卫
    因为最后的比较方式是字典序,可以明确肯定是贪心的先让第一个数尽量大,然后是第二个数尽量大,以此类推。考虑到如果选出了第一个数,那么按照其\(\text{dfs}\)的方式,相当于是把根到这个树的链删掉了,变成了许多颗子树,然后在按照\(\text{dfs}\)遍历这几个子树的顺序依次在子树中类似......
  • 141. 环形链表c
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/boolhasCycle(structListNode*head){structListNode*slow=head;structListNode*fast=head;while(fast&&fast->......
  • 14. I2C读取EEPROM
    一、AT24C02简介  AT24C02是一个2Kbit的串行EEPROM存储器,内部含有256个字节。在24C02里面还有一个8字节的页写缓冲器。该设备的通信方式I2C,通过其SCL和SDA与其他设备通信,芯片的引脚图如下图所示。  上图中有一个WP,这个是写保护引脚,接高电平只读,接地允许......
  • 【LeetCode 1466】重新规划路线
    题目描述原题链接:LeetCode.1466重新规划路线解题思路路线网形成一棵树,说明每个节点都参与两条路线,或作为起点或作为终点;要想所有城市都可以通往城市0,必须要把所有逆向的路线都变更一次方向,逆向路线总数量即为答案;朴素BFS版本从城市0出发,遍历每个从已通城市出发的......
  • 2014-2023年各地级市空气质量指数AQI指数日度数据
    2014-2023年各地级市空气质量指数AQI指数日度数据1、时间:2014-2023.3.82、来源:https://www.qweather.com/air/beiliu-101300903.htm3、指标:统计日期、地区编码ID、地区代码、地区名称、AQI指数、空气质量级别、首要污染物4、样本量:100W+5、范围:300+地级市6、指标解释:空......