哈希表与统计——594、350、554、609、454(2简3中)

news/2024/9/19 4:55:02/ 标签: 数据结构, 哈希算法

594. 最长和谐子序列(简单)

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

解法一、哈希统计

如果不存在键,放入1。如果存在键,更新数量。如果存在num+1或者-1的键,更新最大值。

class Solution {public int findLHS(int[] nums) {HashMap<Integer,Integer> hm = new HashMap<>();int max = 0;for(int num : nums){if(!hm.containsKey(num)){hm.put(num,1);}else{hm.put(num,hm.get(num) + 1);}if(hm.containsKey(num+1)){max = Math.max(max,hm.get(num) + hm.get(num+1));}if(hm.containsKey(num-1)){max = Math.max(max,hm.get(num) + hm.get(num-1));}}return max;}
}

 

解法二、排序+滑动窗口

滑窗和双指针做法到底什么差别orzzzz

class Solution {public int findLHS(int[] nums) {Arrays.sort(nums);int n = nums.length, ans = 0;for (int i = 0, j = 0; j < n; j++) {while (i < j && nums[j] - nums[i] > 1) i++;if (nums[j] - nums[i] == 1) ans = Math.max(ans, j - i + 1);}return ans;}
}


350. 两个数组的交集 II(简单)

给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。 

解法一、排序

class Solution {public int[] intersect(int[] nums1, int[] nums2) {List<Integer> res = new LinkedList<>();Arrays.sort(nums1);Arrays.sort(nums2);int i = 0,j = 0;int n1 = nums1.length,n2 = nums2.length;while(i < n1 && j < n2){while(i < n1 && j < n2&& nums1[i] < nums2[j])i++;while(i < n1 && j < n2 && nums1[i] > nums2[j])j++;while(i < n1 && j < n2 && nums1[i] == nums2[j]){res.add(nums1[i]);i++;j++;}}int[] r = new int[res.size()];for(int k = 0;k < res.size();k++){r[k] = res.get(k);}return r;}
}

 

 解法二、哈希

不过其实感觉如果是哈希的话,直接用数组(桶计数)就挺好的,遍历一个++,遍历另一个--

class Solution {public int[] intersect(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return intersect(nums2, nums1);}Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums1) {int count = map.getOrDefault(num, 0) + 1;map.put(num, count);}int[] intersection = new int[nums1.length];int index = 0;for (int num : nums2) {int count = map.getOrDefault(num, 0);if (count > 0) {intersection[index++] = num;count--;if (count > 0) {map.put(num, count);} else {map.remove(num);}}}return Arrays.copyOfRange(intersection, 0, index);}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/intersection-of-two-arrays-ii/solutions/327356/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

554. 砖墙(中等)

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同(也就是一个单位高)但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。

给你一个二维数组 wall ,该数组包含这堵墙的相关信息。其中,wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ,并且返回 穿过的砖块数量 。

解法一、哈希表

本质上还是统计题。需要转化思维,算穿过的砖最少,也就是算穿过缝隙最多。例如,对于用例

wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

相当于统计1/3/5/6 、 3/4/6 、 1/4/6 、 2/6 、 3/4/6 、 1/4/5/6 中除了6以外,哪个数字出现最多,这个数字也就是代码里面的max。要注意对于不在边缘划线的条件,需要通过哈希表移除最大值的方式达到,而不能在最后的for循环里设置if。

此外有个细节:多写一个循环遍历哈希表值里最大值,比在第一个for里算要快。

class Solution {public int leastBricks(List<List<Integer>> wall) {int num = wall.size();int max = 0,sum = 0;HashMap<Integer,Integer> hm = new HashMap<>();for(List<Integer> bricks : wall){sum = 0;for(int brick : bricks){sum+=brick;if(!hm.containsKey(sum)){hm.put(sum,1);}else{hm.put(sum,hm.get(sum) + 1);}}}hm.remove(sum);for(int t : hm.values()){max = Math.max(max,t);}return num - max;}
}

 

 
609. 在系统中查找重复文件(中等)

给你一个目录信息列表 paths ,包括目录路径,以及该目录中的所有文件及其内容,请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。

一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下:

  • "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着,在目录 root/d1/d2/.../dm 下,有 n 个文件 ( f1.txtf2.txt ... fn.txt ) 的内容分别是 ( f1_contentf2_content ... fn_content ) 。注意:n >= 1 且 m >= 0 。如果 m = 0 ,则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串:

  • "directory_path/file_name.txt"

 解法一、哈希

(备注写在前面)官方做法里的键值对是String--List<String>

遍历给的字符串组,对于每一个固定的字符串,用空格分割。此时的temp[0]是地址,之后的都是文件名和内容。把内容context作为键存入哈希,值则是对应的list中下标,方便每个文件找到自己在res中的位置。

这里有一个问题:如果重复时再存的话,第一次重复需要存两个,其余只需要存一个。所以不妨逆向思维,先把所有的都存进去,再删去不重复的(即size == 1)。

但是,尤其对于size == 1情况下的删除细节,也出过很多问题。最初时尝试了for的int i循环,但由于一边遍历一边删,它的size很快就变小了,也就是会访问过界。第二次时尝试了for-each循环,结果报错java.util.ConcurrentModificationException

        for(List<String> list : res){if(list.size() == 1)res.remove(list);}

 经检查,发现是遍历器和remove的删除问题,事故原因溯至轮子(源码)的某个值更新出现差错。于是再进行优化。解决方法有两种,两种都依旧是for的int i循环①每次删除操作后,i--②从后往前遍历。

class Solution {public List<List<String>> findDuplicate(String[] paths) {List<List<String>> res = new LinkedList<>();HashMap<String,Integer> hm = new HashMap<>();for(String s : paths){String[] temp = s.split(" ");for(int i = 1;i < temp.length;i++){String context = temp[i].substring(temp[i].indexOf('(')+1);StringBuilder sb = new StringBuilder();sb.append(temp[0]).append('/').append(temp[i].substring(0,temp[i].indexOf('(')));if(hm.containsKey(context)){//如果已经存在res.get(hm.get(context)).add(sb.toString());//取出对应}else{//放进去hm.put(context,res.size());List<String> tempList = new LinkedList<>();tempList.add(sb.toString());res.add(tempList);}}}for(int i = res.size()-1;i >= 0;i--){if(res.get(i).size() == 1)res.remove(i);}return res;}
}

454. 四数相加 II(中等)

给你四个整数数组 nums1nums2nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解法一、哈希

两两分组判断,时间复杂度O(n^2)

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> hm = new HashMap<>();int res = 0;for(int num1 : nums1){for(int num2 : nums2){int sumAB = num1 + num2;if(!hm.containsKey(sumAB)){hm.put(sumAB,1);}else{hm.put(sumAB,hm.get(sumAB)+1);}}}for(int num3 : nums3){for(int num4 : nums4){int sumCD = -num3-num4;if(hm.containsKey(sumCD)){res+= hm.get(sumCD);}}}return res;}
}

 

解法二、桶排序

时间复杂度差太多了。。第一个for循环之前确认范围,第一个for循环统计数量,第二个for循环查找符合条件的数量并加入res。原理没变,数据结构优化了

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int[] n1 = getMaxMin(nums1);int[] n2 = getMaxMin(nums2);int[] n3 = getMaxMin(nums3);int[] n4 = getMaxMin(nums4);int maxSum = Math.max(n1[0] + n2[0], -n3[1] - n4[1]);int minSum = Math.min(n1[1] + n2[1], -n3[0] - n4[0]);int[] map = new int[maxSum - minSum + 1];for (int i : nums1) {for (int j : nums2) {map[i + j - minSum] ++ ;}}int count = 0;for (int i : nums3) {for (int j : nums4) {count += map[- i - j - minSum];}}return count;}public int[] getMaxMin (int[] nums) {int[] num = Arrays.copyOf(nums, nums.length);Arrays.sort(num);int min = num[0];int max = num[nums.length - 1];return new int[] {max, min};}
}

 


碎碎念

  • 594重要的思路转换——能够删除任何数,就是能够选择任何想要的数。滑动窗口很有意思,虽然没搞懂和双指针根本上的差别。应该只是基于双指针实现?这附近埋个思考。
  • 554的思路转换很有意思。技术力感觉还好,配得上中等题。
  • 609写起来太冗余复杂了,但是也很有趣。确实感觉到细节处理能力上升了,而且一开始打好代码框架确实很重要
  • 454看了下题解才学会二二分组来着。
  • 其实还有个18,但是太难了,今天没睡午觉有点困,不想做。。

http://www.ppmy.cn/news/1520953.html

相关文章

吴恩达深度学习笔记:卷积神经网络(Foundations of Convolutional Neural Networks)1.9-1.10

目录 第四门课 卷积神经网络&#xff08;Convolutional Neural Networks&#xff09;第一周 卷积神经网络&#xff08;Foundations of Convolutional Neural Networks&#xff09;1.9 池化层&#xff08;Pooling layers&#xff09;1.10 卷 积 神 经 网 络 示 例 &#xff08; …

如何为零售行业构建有效的勒索病毒防御体系

在数字化转型的浪潮中&#xff0c;零售业越来越多地依赖于网络技术来提升客户体验和运营效率。然而&#xff0c;这也使得零售商面临着网络安全的新挑战&#xff0c;尤其是勒索软件攻击。勒索软件是一种恶意软件&#xff0c;它会加密受害者的数据&#xff0c;并要求支付赎金以换…

kubernetes 中 利用yaml文件部署应用

目录 1 用yaml文件部署应用有以下优点 1.1 声明式配置&#xff1a; 1.2 灵活性和可扩展性&#xff1a; 1.3 与工具集成&#xff1a; 2 资源清单参数介绍 2.1 获得资源帮助指令explain 2.2 编写示例 2.2.1 示例1&#xff1a;运行简单的单个容器pod 2.2.2 示例2&#xff1a;运行…

电路基础 ---- 旁路电容与去耦电容的区别

1. 旁路电容&#xff08;Bypass Capacitor&#xff09; 功能&#xff1a; 旁路电容主要用于为电路中的高频噪声提供一个低阻抗路径&#xff0c;以防止这些高频噪声进入电源线。它通过旁路高频信号&#xff08;如电源中的噪声或电路切换产生的尖峰信号&#xff09;来稳定电压。…

互惠链接对于SEO来说是好是坏?

什么是互惠链接&#xff1f; 互惠链接是两个网站之间的双向链接。 网站 A 链接到网站 B&#xff0c;网站 B 也链接回网站 A。 例如&#xff0c;两个网站都发布对彼此有利且与各自受众相关的内容。每个网站都认识到对方内容的价值&#xff0c;从而建立相互链接。 互惠链接对…

.NET/C#⾯试题汇总系列:基础语法

1. 字符串中string strnull和string str""和string strstring.Empty的区别&#xff1f; string str null;&#xff1a;这种方式声明了一个字符串变量str&#xff0c;并将其初始化为null。这意味着str不指向任何实际的字符串对象。如果你试图访问str的属性或方法&…

XXL-JOB分布式任务调度教程(持续更新~)

先大致声明一下流程&#xff08;具体细节在下面哦~&#xff09; 步骤&#xff1a; 1.下载xxl-job并配置以及启动 2.导入对应maven坐标 3.配置对应的配置文件以及编写对应的配置类config 4.编写要触发的方法并且给方法打上XXlJob("")注解 5.设置xxl-Job平台上的任务 …

C#数组中的Rank,GetUpperBound(), GetLength()

Rank-数组的秩&#xff0c;一维数组的Rank1&#xff1b;二维数组的Rank2&#xff1b; GetUpperBound()--获取每一维的索引的上限&#xff0c; 比如int[4,5], 那么GetUpperBound(0) 3; GetUpperBound(1) 4 ; 所以 对于二维数组来说 GetUpperBound(0)1行数&#xff1b; G…

基于STM32设计的智能安防系统(微信小程序)(218)

文章目录 一、前言1.1 项目介绍【1】开发背景【2】项目实现的功能【3】项目硬件模块组成1.2 设计思路【1】整体设计思路【2】整体构架【3】微信小程序开发思路1.3 项目开发背景【1】选题的意义【2】可行性分析【3】参考文献【4】摘要【5】项目背景1.4 开发工具的选择【1】设备端…

React开源框架之Refine

React Refine 是一个基于 React 的开源框架&#xff0c;它旨在帮助开发者快速构建企业级后台管理系统&#xff08;Admin Panel&#xff09;。Refine 是由 Retax 演变而来&#xff0c;它提供了一套完整的解决方案&#xff0c;用于构建 CRUD&#xff08;创建、读取、更新、删除&a…

将python项目打包成一个可执行文件(包含需要的资源文件)

目标 项目源码是采用Python编写&#xff0c;代码中需要读取部分资源文件。现在需要将项目打包成一个exe文件&#xff0c;没有其他任何多余文件&#xff0c;仅1个exe文件。 打包 安装pyinstaller 在自己项目的虚拟环境中&#xff0c;安装pyinstaller。注意一定要是虚拟环境&…

PostgreSQL的repmgr工具介绍

PostgreSQL的repmgr工具介绍 repmgr&#xff08;Replication Manager&#xff09;是一个专为 PostgreSQL 设计的开源工具&#xff0c;用于管理和监控 PostgreSQL 的流复制及实现高可用性。它提供了一组工具和实用程序&#xff0c;简化了 PostgreSQL 复制集群的配置、维护和故障…

【专项刷题】— 字符串

1、最长公共前缀 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 解法一&#xff1a;两两比较字符串解法二&#xff1a;比较每一个字符串的同一位图解&#xff1a;代码&#xff1a; class Solution {public String longestCommonPrefix(String[] strs) {String ret …

集成电路学习:什么是IDE集成开发环境

IDE&#xff1a;集成开发环境 IDE&#xff0c;全称“Integrated Development Environment”&#xff0c;即集成开发环境&#xff0c;是一种用于提供程序开发环境的应用程序。它集成了代码编写、分析、编译、调试等多种功能于一体的开发软件服务套&#xff0c;为开发者提供了一个…

采用基于企业服务总线(ESB)的面向服务架构(SOA)集成方案实现统一管理维护的银行信息系统

目录 案例 【题目】 【问题 1】(7 分) 【问题 2】(12 分) 【问题 3】(6 分) 【答案】 【问题 1】解析 【问题 2】解析 【问题 3】解析 相关推荐 案例 阅读以下关于 Web 系统设计的叙述&#xff0c;在答题纸上回答问题 1 至问题 3。 【题目】 某银行拟将以分行为主体…

微博视频无水印下载的方法

在如今的数字时代&#xff0c;社交媒体平台如微博已经成为人们分享日常生活、获取新闻和娱乐内容的重要渠道。我们时常会在刷微博时看到一些有趣的视频图片&#xff0c;或是名人的访谈&#xff0c;或是搞笑的短片&#xff0c;有时甚至是一些珍贵的历史资料。这些视频不仅内容丰…

一个“改造”的工厂背后:中国电商的AI重构

电商行业需要更加注重交易的本质&#xff0c;即提供高质量的产品和服务&#xff0c;保护消费者权益&#xff0c;促进公平竞争&#xff0c;提高透明度。 电商产业应该回归到交易、流通和成交这些基本层面&#xff0c;而不是仅仅依赖于价格竞争或者服务的过度承诺。 而大模型所…

R18 XR :NR L2 enhancement

这篇主要看下为支持XR,L2都有哪些增强。主要分3个部分:(1)additionalBS-TableAllowed和Delay Status Report(DSR) (2)UE assistance info for UL traffic information (3) PDU set discard。正文开始: 为了增强 XR 上行资源的调度,引入了以下改进: (1)一个额外的buffer s…

css重置样式表 reset.css 格式化默认css样式

css重置样式表 reset.css 格式化默认css样式 html, body, div, span, applet, object, iframe,h1, h2, h3, h4, h5, h6, p, blockquote, pre,a, abbr, acronym, address, big, cite, code,del, dfn, em, img, ins, kbd, q, s, samp,small, strike, strong, sub, sup, tt, var,b…

Django+Vue酒店推荐系统的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 需要的环境3.2 Django接口层3.3 实体类3.4 config.ini3.5 启动类3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平台Java领域优质创作者&…