首页 > 编程语言 >代码随想录算法训练营Day5 | 哈希表理论基础、242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和

代码随想录算法训练营Day5 | 哈希表理论基础、242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和

时间:2024-09-16 10:20:36浏览次数:15  
标签:202 哈希 int 元素 随想录 ++ 数组 new 两数

哈希表理论基础

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。

数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:

哈希表1

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

哈希函数

哈希函数通过特定编码方式,可以将其他数据格式转化为不同的数值,映射到哈希表上的索引数字。

哈希表2

如果hashCode得到的数值大于哈希表的大小,此时为了保证映射出来的索引数值都落在哈希表上,对数值做一个取模的操作。

哈希碰撞

如图所示,小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞

哈希表3

哈希碰撞有两种解决方法, 拉链法和线性探测法。

拉链法

将发生冲突的元素都存储在链表中,这样就可以通过索引找到冲突元素。

哈希表4

拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,一定要保证tableSize大于dataSize,依靠哈希表中的空位来解决碰撞问题。

冲突的位置放了第一个元素,那么就向下找一个空位放置另一个元素的信息。所以要求tableSize一定要大于dataSize ,不然哈希表上没有空置的位置来存放冲突的数据了。如图所示:

哈希表5

常见哈希结构

使用哈希法来解决问题的时候,一般选择如下三种数据结构:

  • 数组
  • set (集合)
  • map(映射)

242.有效的字母异位词

题目

242. 有效的字母异位词 - 力扣(LeetCode)

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

**注意:**若 st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

示例1:

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

示例2:

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

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • st 仅包含小写字母

思路

视频讲解:242.有效的字母异位词

代码随想录:有效的字母异位词

数组其实就是一个简单的哈希表,本题中字符串只有小写字符,可以定义一个数组,来记录字符串s、t里字符出现的次数。

s中每出现一次某字母,数组中相应位置++,t中每出现一次某字母,数组中相应位置–:

242.有效的字母异位词

遍历字符串的时候,可以通过字母和 ‘a’ 的相对ASCII码获取相应下标。

字符串遍历完之后再遍历一次数组,检查数组中各元素是否为0。

题解

独立题解:

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash = new int[26];
        //使用.chatAt获取相应下标的字符
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i) - 'a']--;
        }
        for (int j = 0; j < 26; j++) {
            if (hash[j] != 0)
                return false;
        }
        return true;
    }
}

349.两个数组的交集

题目

349. 两个数组的交集 - 力扣(LeetCode)

给定两个数组 nums1nums2 ,返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

示例1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]

示例2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

思路

视频讲解:349. 两个数组的交集

代码随想录:两个数组的交集

Java中的HashSet的常用方法总结-CSDN博客

HashSet是没有重复元素且无序的集合。

由题要求输出去重且不考虑顺序,可使用HashSet:

set哈希法

另外,题目给出提示:数组长度为1到1000,元素值为0到1000,所以也可以使用数组作为哈希表。

题解

独立题解:

使用数组+HashSet解决

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash = new int[1001];
        Set<Integer> hashset = new HashSet<Integer>();
        for (int i : nums1) {
            hash[i]++;
        }
        for (int i : nums2) {
            if (hash[i] > 0) {
                hashset.add(i);
            }
        }
        int[] res = new int[hashset.size()];
        int index = 0;
        for (int i : hashset) {
            res[index++] = i;
        }
        return res;
    }
}

参考题解:

使用哈希数组解决

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;
        List<Integer> resList = new ArrayList<>();
        for(int i = 0; i < 1002; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);
        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;
    }
}

202.快乐数

题目

202. 快乐数 - 力扣(LeetCode)

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

「快乐数」 定义为:

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

如果 n快乐数 就返回 true ;不是,则返回 false

示例1:

输入:n = 19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例2:

输入:n = 2
输出:false

思路

代码随想录:快乐数

由题,所有非快乐数计算后都会陷入死循环,即求得的sum一定会有重复值。

而快乐数的sum不会有重复值。

涉及出现次数,考虑用哈希表,又要求元素不能重复,考虑使用HashSet。

双指针法:由于所有非快乐数都会陷入死循环,所以该题可以类比 142. 环形链表 II - 力扣(LeetCode)

使用快慢指针,快指针每次移动一个距离,慢指针每次移动两个距离,如果两个指针相遇则说明不是快乐数。

img

题解

独立题解:

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> hashset = new HashSet<>();
        while (n != 1) {
            int sum = 0;
            while (n != 0) {
                int a = n % 10;
                n /= 10;
                sum += a * a;
            }
            if (hashset.contains(sum)) {
                return false;
            } else {
                hashset.add(sum);
                n = sum;
            }
        }
        return true;
    }
}

快慢指针:

(偷的

class Solution {
    //获取下一个值的方法
     public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
    
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        //循环直到 得到1/快慢指针相遇
        while (fast != 1 && slow != fast) {
            //慢指针移动一次
            slow = getNext(slow);
            //快指针移动两次
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }
}

1.两数之和

题目

1. 两数之和 - 力扣(LeetCode)

给定一个整数数组 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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

思路

视频讲解:1.两数之和

代码随想录:两数之和

Java HashMap | 菜鸟教程 (runoob.com)

当需要查询一个元素是否出现过或者一个元素是否在集合里的时候,第一时间想到哈希法。

本题中不但需要存放遍历过的元素,还需要知道这个元素对应的下标,因此本题需要使用到key value结构,用key存放元素值,value存放元素下标,所以需要使用HashMap结构。

需要明确两点:

  • map用来做什么
  • map中key和value分别表示什么

map用来存放我们访问过的元素,因为遍历数组时,需要记录之前遍历过的元素和对应的下标,这样才能找到与当前元素之和等于target的元素。

因为返回值是下标,所以value存放数组元素下标,key存放元素值。

在遍历数组的时候,只需要在map中查询是否有和当前元素匹配的数值,如果有,就返回答案,如果没有,就把当前遍历的元素放进map中,因此map存放的是已经访问过的元素。

过程一 过程二

题解

独立题解:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashmap = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int a = target - nums[i];
            if (hashmap.containsKey(a)) {
                res[0] = i;
                res[1] = hashmap.get(a);
                return res;
            } else {
                hashmap.put(nums[i], i);
            }
        }
        return null;
    }
}

标签:202,哈希,int,元素,随想录,++,数组,new,两数
From: https://blog.csdn.net/jiabao0520/article/details/142299337

相关文章

  • WEB-API+.NET+CRUD+SSMS(VS2022)
    1.使用VS2022创建一个web-api项目,根目录如下:其中TestCode.cs写model实体类,Controller编写控制器2.实体类Item,编写对应的属性点击查看代码publicclassItem{[Required]publicintId{get;set;}[Required]publicintFieldID{get;set;}......
  • VMware ESXi 7.0U3q macOS Unlocker 集成驱动版更新 OEM BIOS 2.7 支持 Windows Serve
    VMwareESXi7.0U3qmacOSUnlocker集成驱动版更新OEMBIOS2.7支持WindowsServer2025VMwareESXi7.0U3qmacOSUnlocker&OEMBIOS2.7集成网卡驱动和NVMe驱动(集成驱动版)ESXi7.0U3标准版集成Intel网卡、RealtekUSB网卡和NVMe驱动请访问原文链接:h......
  • [ACTF2020 新生赛]Upload
    启动靶机,发现有前端验证先绕过前端验证,在burp中尝试发现验证在文件名后缀,且会重命名文件名发现.ini能上传但是会被重命名,既然不像前端显示只有三种格式能上传,这里我们寻找能绕过的后缀尝试发现phtml能上传成功//PHTML扩展名是PHP的一个模块,它允许在HTML文件中使用PHP......
  • Kali Linux 2024.3 发布下载 - 领先的渗透测试发行版
    KaliLinux2024.3发布(Multipletransitions)-领先的渗透测试发行版ThemostadvancedPenetrationTestingDistribution请访问原文链接:https://sysin.org/blog/kali-linux/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgKaliLinux2024.3已经可以下载,发行......
  • 第六届机器人与智能制造技术国际会议 (ISRIMT 2024) 2024 6th International Symposiu
    文章目录一、会议详情二、重要信息三、大会介绍四、出席嘉宾五、征稿主题六、咨询一、会议详情二、重要信息大会官网:https://ais.cn/u/vEbMBz提交检索:EICompendex、IEEEXplore、Scopus大会时间:2024年9月20-22日大会地点:中国-江苏常州-河海大学常州校区三、大会......
  • 【保奖思路】2024年华为杯研赛F题保奖思路(点个关注,后续会更新)
    您的点赞收藏是我继续更新的最大动力!一定要点击文末的卡片,那是获取资料的入口!现分享2023年华为杯研赛F题高质量思路,供大家学习:问题1思路2023华为杯研究生数学建模F题问题1:如何有效应用双偏振变量改进强对流预报,仍是目前气象预报的重点难点问题。请利用题目提供的数据,建立......
  • 【保奖思路】2024年华为杯研赛F题保奖思路(点个关注,后续会更新)
    您的点赞收藏是我继续更新的最大动力!一定要点击文末的卡片,那是获取资料的入口!现分享2023年华为杯研赛F题高质量思路,供大家学习:问题1思路2023华为杯研究生数学建模F题问题1:如何有效应用双偏振变量改进强对流预报,仍是目前气象预报的重点难点问题。请利用题目提供的数据,建立......
  • 【AI学习】陶哲轩在 2024 年第 65 届国际数学奥林匹克(IMO)的演讲:AI 与数学
    陶哲轩在2024年第65届国际数学奥林匹克关于AI和数学的演讲,很有意思。陶哲轩的讲话语速太快了,足见其聪明!AI用于数学的一些方面:陶哲轩介绍到刚刚被数学家接受并开始普及的方法:形式化证明辅助工具。形式化证明辅助工具是用于验证论证是否真正正确的语言,可以验证某个论......
  • 2024CSP-J初赛全真模拟卷选择题篇(原创,难度偏简单)
    注意,本卷由再临TSC原创,禁止转载!本卷难度偏简单,若想要通过初赛本卷应拿80+分左右查看答案的方法:if(设备=="PC"){    把光标移到答案上面,选中答案,就会显示();}elseif(设备==移动端b||设备==平板){    把答案复制,找到随便一个地方粘贴即可();}else{......
  • P7831 [CCO2021] Travelling Merchant
    妙妙题。题意给定\(n\)点\(m\)边的单向无自环图,每条边有权值\(r_i,p_i\),表示要经过这条边要有至少\(r_i\)的收益,经过这条边之后会获得\(p_i\)的收益。对每个点求出从该点出发能不停止的行走初始需要获得至少多少的收益。无解输出-1。\(n,m\le2\times10^5\)分析不......