【算法题解答·七】哈希

【算法题解答·七】哈希

接上文【算法方法总结·七】哈希的一些技巧和注意事项


哈希相关题目如下:

349. 两个数组的交集

  • 一个哈希 set1 用来保存数组1的值,一个哈希 resSet 用来保存相交的值
class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();for (int i : nums1) { // 遍历数组1set1.add(i);}for (int i : nums2) { // 遍历数组2if (set1.contains(i)) { // 数组2中也存在则加入resSet.add(i);}}int[] arr = new int[resSet.size()];int j = 0;for (int i : resSet) {arr[j++] = i;}return arr;}
}

1. 两数之和

class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2]; // 返回值if (nums == null || nums.length == 0) {return res;}Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int t = target - nums[i];if (map.containsKey(t)) { // 包含关键字 tres[1] = i;res[0] = map.get(t); // 得到关键字的 valuebreak;} else {map.put(nums[i], i); // 加入 map}}return res;}
}

454.四数相加II

计算有多少组满足

  • 首先定义 一个HashMapkeyab两数之和,valueab两数之和出现的次数
  • 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。
  • 定义int变量count,用来统计 a + b + c + d = 0 出现的次数。
  • 再遍历大C和大D数组,找到如果 0-(c+d)map中出现过的话,就用countmapkey对应的value也就是出现次数统计出来。
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<>();// 遍历 A和Bfor (int i : nums1) {for (int j : nums2) {int sum = i + j;// map.getOrDefault(sum, 0)如果存在sum返回其value,否则返回0map.put(sum, map.getOrDefault(sum, 0) + 1);}}// 遍历 C和Dfor (int i : nums3) {for (int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

15. 三数之和

  • 因为 不可包括重复 的三元组,使用 哈希法,去重过程 不好处理

  • 使用 双指针法 要比 哈希法 高效一些,而且要求 返回的是数值 的话,就可以使用 双指针法

18. 四数之和

  • 15.三数之和 是同一个思路,多一层 for 循环,

  • 对于 15.三数之和 双指针法就是将原本暴力O(n^3)的解法,降为O(n^2)的解法,
    18.四数之和 的双指针解法就是将原本暴力O(n^4)的解法,降为O(n^3)的解法

49.字母异位词分组

  • 先把 "bac" 转化为 [b,a,c]sort 排序后再转回字符串 "abc",为它的 key
  • 先把 "bca" 转化为 [b,c,a]sort 排序后再转回字符串 "abc",为它的 key
  • 上述两者 key 相同
// sort 得到 key,相同的 key 加入同一个列表中
class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 排序法Map<String, List<String>> map = new HashMap<>();// 遍历数组中的每个字符串for (String str : strs) {char[] ss = str.toCharArray(); // 转为字符数组Arrays.sort(ss); // 排序得到其 keyString key = String.valueOf(ss); // 字符数组 -> 字符串List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str); // 结果中加入当前字符串map.put(key, list); // 更新 map}return new ArrayList<List<String>>(map.values());}
}

128.最长连续序列

  • 先找到起点 x,如果 x-1 也在 set 中,说明 x 不是起点
  • 找到起点后,循环查看 set 中是否有下一个数
// 用 HashSet,查找元素方便,如果x-1也在set里,继续遍历直到没有x-1时,x为起点
class Solution {public int longestConsecutive(int[] nums) {int ans = 0;Set<Integer> st = new HashSet<>();// 把数组转换为哈希集合for (int num : nums) {st.add(num);}for (int x : st) {// 如果 x-1 在集合中,继续if (st.contains(x - 1)) {continue;}// x 是起点int y = x + 1; // 下一个数while (st.contains(y)) {y++;}// 循环结束后,y-1 是最后一个在哈希集合中的数ans = Math.max(ans, y - x);}return ans;}
}

算法题解答系列

【算法题解答·一】二分法
【算法题解答·二】双指针法
【算法题解答·三】滑动窗口
【算法题解答·四】字符串操作
【算法题解答·五】链表操作
【算法题解答·六】栈队列堆
【算法题解答·七】哈希

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

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

相关文章

Ubuntu22.04虚拟机里安装Yolov8流程

1. 安装pytorch sudo apt install nvidia-cuda-toolkit nvcc --version # 官方适配地址&#xff1a;https://download.pytorch.org/whl/torch/import torch print(torch.__version__) print(torch.cuda.is_available())2. 安装环境 # cuDNN 安装&#xff1a;https://develop…

stm32第五天按键的基础知识

一&#xff1a;按键连接示意图 按键控制LED灯 软件设计流程 初始化系统 o 初始化GPIO外设时钟 o 初始化按键和LED的引脚 • 检测按键输入电平来控制LED灯 o SW2控制灯开 。 SW3控制灯关 1&#xff1a;key.c工程 #include"key.h" #include"stm32f10x.h"v…

Xposed模块开发:运行时修改技术

1. Xposed框架核心原理 1.1 运行时架构解析 Android ART Hook机制&#xff1a; graph TD A[目标APP进程] --> B{系统Zygote} B -->|加载Xposed| C[XposedBridge] C --> D[模块1] C --> E[模块2] D --> F[Hook目标方法] E --> F 1.1.1 核心组件交…

【Python学习笔记】一些关于多线程,xls文件读取,PyQt5,PyInstaller打包等问题的解决方案记录

背景&#xff1a; 最近利用休息时间写了个小型exe程序&#xff0c;主要涉及的技术点有&#xff1a;多线程&#xff0c;读取xls文件&#xff0c;基于PyQt5的简单GUI页面&#xff0c;利用PyInstaller打包成exe。虽然有ChatGPT等协助&#xff0c;但难免还是在开发过程中遇到了一些…

基于javaweb的SpringBoot智能相册管理系统图片相册系统设计与实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…

【AI知识管理系统】(一)AI知识库工具测评

嘿,朋友们!🧐你们有没有想过,咱们平日里那些一闪而过的知识笔记、各种碎片化的idea,记录下来之后都是怎么管理的呀? 还有啊,咱们读过的那些书,大家会不会随手写点东西记录一下呢?📝要知道,如果不写的话,很可能过不了多久就全忘得一干二净啦。 😭那多年前记下的…

JVM并发编程AQSsync锁ReentrantLock线程池ThreadLocal

并发编程2 synchronized锁实现**AQS****ReentrantLock实现****JUC 常用类**池的概念 ThreadLocalThreadLocal原理内存泄露强引用:软引用弱引用虚引用ThreadLocal内存泄露 synchronized锁实现 synchronized是一个关键字,实现同步,还需要我们提供一个同步锁对象,记录锁状态,记录…

C++从入门到入土(八)——多态的原理

目录 前言 多态的原理 动态绑定与静态绑定 虚函数表 小结 前言 在前面的文章中&#xff0c;我们介绍了C三大特性之一的多态&#xff0c;我们主要介绍了多态的构成条件&#xff0c;但是对于多态的原理我们探讨的是不够深入的&#xff0c;下面这这一篇文章&#xff0c;我们将…

自带多个接口,完全免费使用!

做自媒体的小伙伴们&#xff0c;是不是经常为语音转文字的事儿头疼&#xff1f; 今天给大家推荐一款超实用的语音转文字软件——AsrTools&#xff0c;它绝对是你的得力助手&#xff01; AsrTools 免费的语音转文字软件 这款软件特别贴心&#xff0c;完全免费&#xff0c;而且操…

国内首款载重1吨级无人运输机TP1000首飞成功 2026年投入应急救援

大湾区经济网珠海快讯&#xff0c;据央视新闻报道&#xff0c;3月15日上午&#xff0c;国内首款载重1吨级大型无人运输机TP1000在山东成功首飞。该机由中国民航适航标准完全自主研发&#xff0c;起飞重量3.3吨&#xff0c;满载航程达1000公里&#xff0c;具备智能空投功能&…

设计模式Python版 访问者模式

文章目录 前言一、访问者模式二、访问者模式示例 前言 GOF设计模式分三大类&#xff1a; 创建型模式&#xff1a;关注对象的创建过程&#xff0c;包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、原型模式和建造者模式。结构型模式&#xff1a;关注类和对象之间的组…

(性能测试)性能测试工具 2.jmeter的环境搭建 3jmeter元件和4使用实例 5jmeter元件和参数化

目录 性能测试工具 性能测试工具 jemeter环境搭建 jmeter的常用目录介绍 jmeter修改语言和主题--jmeter界面的汉化 jmeter元件 jmeter元件和组件的介绍 jmeter的作用域原则 jmeter的执行顺序 案例&#xff1a;执行顺序 jmeter使用案例 jmeter线程组的介绍 jmeter…

书摘 ASP.NET Core技术内幕与项目实战:基于DDD与前后端分离

IT行业的发展瞬息万变,新技术层出不穷,很多技术人员出于个人兴趣、个人职业发展等考虑而选择一些流行的新技术,他们会把各种复杂的架构模式、高精尖的技术都加入架构中,这增加了项目的复杂度、延长了交付周期、增加了项目的研发成本。有些技术并不符合公司的情况,最后项目…

Spring Cloud 负载均衡(Ribbon)- 流量管理与服务调用优化

一、Spring Cloud Ribbon 概述 1、什么是 Spring Cloud Ribbon&#xff1f; Spring Cloud Ribbon 是一个基于客户端的负载均衡器&#xff0c;其核心目标是为微服务架构中的服务调用提供智能流量分发能力。与传统的服务端负载均衡&#xff08;如 Nginx&#xff09;不同&#x…

内网环境安装dlv,本地远程调试go

背景&#xff1a;内网环境(服务器)下安装dlv,本地通过dlv调试编译后的go代码。 可以配合观看: 【dlv远程调试-哔哩哔哩】 https://b23.tv/NqPZ5q9 内网安装dlv步骤 1、dlv安装: &#xff08;我额服务器和内网的go都是1.21以上&#xff09; # 先在有网络的环境下&#xff08…

C# MVC项目部署II后错误,403禁止访问:访问被拒绝问题处理

C# MVC项目部署II后错误&#xff0c;403禁止访问&#xff1a;访问被拒绝问题处理 问题如下&#xff1a; 解决办法&#xff1a; 1. 应用程序池要选v4.xx&#xff0c;托管模式选“集成” 2. 把asp.net 4.xx安装在iis上&#xff0c;方法&#xff1a; cd \Windows\Microsoft .NE…

基于Flask的东方财富网股票数据可视化分析系统

【大数据】基于Flask的东方财富网股票数据可视化分析系统 &#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统能够高效地从东方财富网抓取股票数据&#xff0c;并通过Python的强大数据处理能…

整形在内存中的存储(例题逐个解析)

目录 一.相关知识点 1.截断&#xff1a; 2.整形提升&#xff1a; 3.如何 截断&#xff0c;整型提升&#xff1f; &#xff08;1&#xff09;负数 &#xff08;2&#xff09;正数 &#xff08;3&#xff09;无符号整型&#xff0c;高位补0 注意&#xff1a;提升后得到的…

HarmonyOS第26天:应用发布与推广全攻略:从0到1走向市场

一、引言:开启 HarmonyOS 应用之旅 在数字化时代的浪潮中,HarmonyOS 以其独特的分布式理念和强大的跨设备协同能力,为应用开发领域开辟了一片崭新的天地。随着 HarmonyOS 市场份额的稳步增长,其生态设备数量已突破 9 亿大关,吸引了超过 254 万开发者投身其中 ,成为了开发…

【操作系统安全】任务4:Windows 系统网络安全实践里常用 DOS 命令

目录 一、引言 二、网络信息收集类命令 2.1 ipconfig 命令 2.1.1 功能概述 2.1.2 实例与代码 2.2 ping 命令 2.2.1 功能概述 2.2.2 实例与代码 2.3 tracert 命令 2.3.1 功能概述 2.3.2 实例与代码 三、网络连接与端口管理类命令 3.1 netstat 命令 3.1.1 功能概述…