算法——哈希王

242.有效的字母异位词

力扣题目链接(opens new window)

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

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

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

说明: 你可以假设字符串只包含小写字母。

class Solution {
public:bool isAnagram(string s, string t) {int a[27];for(int i=0;i<s.size();i++){a[s[i]-'a']++;}for(int i=0;i<t.size();i++){a[t[i]-'a']--;}for(int i=0;i<26;i++){if(a[i]!=0) return false;}return true;}};

没什么难的,用桶的思想。

349. 两个数组的交集

力扣题目链接(opens new window)

题意:给定两个数组,编写一个函数来计算它们的交集。

349. 两个数组的交集

说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> reuslt =new HashSet<>();Set<Integer> reuslt1 =new HashSet<>();for(int i=0;i<nums1.length;i++){reuslt.add(nums1[i]);}for(int i=0;i<nums2.length;i++){if(  reuslt.contains(nums2[i])){reuslt1.add(nums2[i]);}}return reuslt.stream().mapToInt(x->x).toArray();}
}

创建两个Set,两次遍历,利用Set的特性即可,哈希法适合的场景是快速从一堆数找到一个数。stream方法要非常了解能节省很多时间。

第202题. 快乐数

力扣题目链接(opens new window)

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

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

如果 n 是快乐数就返回 True ;不是,则返回 False 。

示例:

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

class Solution {public int getNumber(int x){int sum = 0;while(x>0){int val =x % 10;sum+=val*val;x/=10;}return sum;}public boolean isHappy(int n) {Set<Integer> result= new HashSet<>();while(n!=1 && !(result.contains(n))){result.add(n);n =getNumber(n);}     return n==1;}
}

这题也较为简单,就是套了个快乐数的壳子,本质上还是Set 的模板题,while里的逻辑要注意一下,当n!=1 并且 set里面没有这个值的话把值给添加到Set中去,反之当n==1或者set里面已经有这个值了说明进入死循环了可以直接跳出判断结果了。还要注意去一个整数各个位置的操作。

1. 两数之和

力扣题目链接(opens new window)

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

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

HashMap 的模板题,没什么好说的 

第454题.四数相加II

力扣题目链接(opens new window)

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。

例如:

输入:

  • A = [ 1, 2]
  • B = [-2,-1]
  • C = [-1, 2]
  • D = [ 0, 2]

输出:

2

解释:

两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int sum =0;Map<Integer,Integer> s1 =new HashMap<>();for(int num1:nums1){for(int num2:nums2){int val =num1+num2;s1.put(val,s1.getOrDefault(val,0)+1);}}for(int num3:nums3){for(int num4:nums4){int val =-(num3+num4);if(s1.containsKey(val)) sum+=s1.get(val);}}return sum;}
}

题目里面没有说到要去重,所以不能用set,只能用map,它的value表示出现了几次,最后的结果就要加上几次。s1.getOrDefault(val,0)+1 表示去拿val 的值如果没有就把他设成0,有的话就返回key为val的value。

383. 赎金信

力扣题目链接(opens new window)

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意:

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int a[]=new int[26];for(int i=0;i<ransomNote.length();i++){a[ransomNote.charAt(i)-'a']++;}for(int i=0;i<magazine.length();i++){a[magazine.charAt(i)-'a']--;}for(int i=0;i<26;i++){if(a[i]>0) return false;}return true;}
}

和第一题差不多的,要注意这里是用第二个字符串组成第一个字符串,那么第二个字符串的各个字母数量可以大于等于第一个的各个字母数量。 

第15题. 三数之和

力扣题目链接(opens new window)

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result =new ArrayList<>();Arrays.sort(nums);if(nums[0]>0) return result;for(int i=0;i<nums.length;i++){if(i>0 && nums[i]==nums[i-1]) continue; //去重,相同数值的i只能保存一次int left =i+1;int right = nums.length-1;while(left<right){int val =nums[i]+nums[left]+nums[right];if(val>0) right--;else if(val<0) left++;else{result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right && nums[left]==nums[left+1]) left++;while(left<right && nums[right]==nums[right-1]) right--;left++;right--;}}}return result;}
}

双指针

其实这道题目使用哈希法并不十分合适,因为在去重的操作中有很多细节需要注意,在面试中很难直接写出没有bug的代码。

而且使用哈希法 在使用两层for循环的时候,能做的剪枝操作很有限,虽然时间复杂度是O(n^2),也是可以在leetcode上通过,但是程序的执行时间依然比较长 。

接下来我来介绍另一个解法:双指针法,这道题目使用双指针法 要比哈希法高效一些,那么来讲解一下具体实现的思路。

动画效果如下:

15.三数之和

拿这个nums数组来举例,首先将数组排序,然后有一层for循环,i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0,我们这里相当于 a = nums[i],b = nums[left],c = nums[right]。

接下来如何移动left 和right呢, 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。

第18题. 四数之和

力扣题目链接(opens new window)

题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result =new ArrayList<>();Arrays.sort(nums);for(int i =0;i<nums.length;i++){//一重减枝if(nums[0]>=target && target>0) {return result;}//一重去重if(i>0 && nums[i]==nums[i-1]) continue;for(int j=i+1;j<nums.length;j++){if(nums[i]+nums[j]>target&&target>0&&nums[i]>0)  break; //二重剪枝//二重去重if(j>i+1 && nums[j]==nums[j-1]) continue;int left =j+1;int right =nums.length-1;while(left<right){long val =(long)nums[i]+nums[j]+nums[left]+nums[right];if(val>target){right--;}else if(val<target){left++;}else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(left<right && nums[left]==nums[left+1]) left++;while(left<right && nums[right]==nums[right-1]) right--;left++;right--;}}}}return result;}
}

四数之和,和15.三数之和 (opens new window)是一个思路,都是使用双指针法, 基本解法就是在15.三数之和 (opens new window)的基础上再套一层for循环。

但是有一些细节需要注意,例如: 不要判断nums[k] > target 就返回了,三数之和 可以通过 nums[i] > 0 就返回了,因为 0 已经是确定的数了,四数之和这道题目 target是任意值。比如:数组是[-4, -3, -2, -1]target-10,不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝,逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

15.三数之和 (opens new window)的双指针解法是一层for循环num[i]为确定值,然后循环内有left和right下标作为双指针,找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值,依然是循环内有left和right下标作为双指针,找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况,三数之和的时间复杂度是O(n^2),四数之和的时间复杂度是O(n^3) 。

那么一样的道理,五数之和、六数之和等等都采用这种解法。

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

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

相关文章

【Consul】注册Consul服务时报错404

【Consul】注册Consul服务时报错404 大家好 我是寸铁&#x1f44a; 总结了一篇golang注册Consul服务时报错404✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 问题背景 今天寸铁想注册一个服务到Consul服务中心&#xff0c;却发现报错了&#xff0c;错误码是404&#xff0c;下面和…

react中的useEffect的使用

目录 React的useEffect深度解析与实战应用 一、useEffect的基本使用 二、useEffect的依赖项数组 三、避免无限循环 四、使用清空函数进行清理 React的useEffect深度解析与实战应用 React Hooks 是 React 16.8 版本引入的新特性&#xff0c;它允许我们在不编写 class 的情况…

SQLiteC/C++接口详细介绍-sqlite3类(一)

上一篇&#xff1a;SQLiteC/C接口简介 下一篇&#xff1a;SQLiteC/C接口详细介绍&#xff08;二&#xff09; 引言&#xff1a; SQLite C/C 数据库接口是一个流行的SQLite库使用形式&#xff0c;它允许开发者在C和C代码中嵌入 SQLite 基本功能的解决方案。通过 SQLite C/C 数据…

Elasticsearch 通过索引阻塞实现数据保护深入解析

目录 前言 1、索引阻塞的种类 2、什么时候使用阻塞&#xff1f; 场景1&#xff1a;进行系统维护场景。 场景2&#xff1a;保护数据不被随意更改场景。 场景3&#xff1a;优化资源使用的场景。 场景4&#xff1a;遵守安全规则场景。 3、添加索引阻塞API 4、解除设置 AP…

吴恩达机器学习笔记 十八 制定一个性能评估标准 学习曲线 高偏差 高方差

一个模型的好坏的评估基准可以从下面几个方面考虑&#xff1a; 1.考虑人类在这个问题上的表现 2.对比竞争算法的表现 3.根据经验猜测 判断是高偏差还是高方差 训练样本数量越多&#xff0c;越难完美地拟合每个样本&#xff0c;因此 J_train 会逐渐增大一点点&#xff0c;但泛…

原创检测工具,高效了解文章质量

原创检测工具&#xff0c;高效了解文章质量&#xff01;想要知道一篇文章的质量怎么样&#xff0c;我们可以通过了解文章的原创度高低来分析&#xff0c;那么文章的原创度高低我们又是如何来知晓的呢&#xff1f;那当然是用原创检测工具去查询出来的。虽然我们可以把文章内容放…

20240309web前端_第一周作业_豆瓣电影

作业四&#xff1a;豆瓣电影 成果展示&#xff1a; 完整代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0…

Word转PDF保持图片原有清晰度

目录 1、需要的软件 2、配置Acrobat PDFMaker 3、配置Acrobat Distiller 4、更改Acrobat PDFMaker中的首选项 5、将word转换成pdf 1、需要的软件 利用Adobe Acrobat DC工具。 打开word&#xff0c;选择Acrobat的插件&#xff0c;选择首选项。 如果没有出现Acrobat插件也…

C++的类与对象(三):构造函数、析构函数、对象的销毁顺序

目录 类的6个默认成员函数 构造函数 语法 特性 析构函数 特性 对象的销毁顺序​​​​​​​​​​​​​​ 类的6个默认成员函数 问题&#xff1a;一个什么成员都没的类叫做空类&#xff0c;空类中真的什么都没有吗&#xff1f; 基本概念&#xff1a;任何类在什么都不…

2024年最便宜的阿里云服务器购买图文教程,2核2G61元,2核4G99元

2024年&#xff0c;阿里云推出了多款价格非常便宜的云服务器和轻量应用服务器&#xff0c;其中轻量应用服务器2核2G3M带宽50G系统盘只要61元/1年&#xff0c;2核4G4M带宽60G系统盘只要165元/1年。云服务器2核2G3M带宽40G系统盘只要99元/1年&#xff0c;2核4G5M带宽80G系统盘只要…

功能测试转自动化测试好不好转型?

手工测试做了好多年&#xff0c;点点点成了每天必须做的事情。但是随着自动化测试趋势的日渐明显&#xff0c;以及受到薪资、技能的双重考验&#xff0c;掌握自动化测试成为了必备技能。 手工转自动化测试&#xff0c;不是一蹴而就的。“预先善其事&#xff0c;必先利其器”&a…

FTP,SFTP,FTPS,SSL,TSL简介,区别,联系,使用场景说明

文章目录 简介FTPFTPSSFTP加密场景选择FTPS还是SFTPFTP、SFTP、FTPS区别、联系和具体使用场景如何使用FTP、SFTP和FTPSSSLTLSSSL和TLS区别和联系&#xff0c;以及使用场景SSL和TLS技术上的区别一些问题隐式的TLS&#xff08;FTPS/SSL&#xff09;或者显式的TLS&#xff08;FTPS…

LeetCode 707. 设计链表 (JAVA)

1.题目 2. 思路分析 1.我们要设置一个虚拟头节点&#xff0c;因为这个虚拟头节点对于增加节点操作和删除节点操作都很方便。 2.仔细读题&#xff0c;题目中说链表中的节点下标是从0开始的。也就是说第一个节点下标为0。 3.增加节点和删除节点的操作我们都要获取到它前一个的节…

洗衣洗鞋店小程序对接水洗唛打印,一键预约,支付无忧

随着社会的进步和科技的发展&#xff0c;我们的生活幸福感与日俱增。为了让我们从琐碎中解脱出来&#xff0c;干洗店洗鞋店行业也日新月异。今天&#xff0c;我为大家推荐这款优秀的干洗店小程序系统&#xff0c;让您的洗衣洗鞋服务体验更上一层楼。 干洗店管理系统是一款专为洗…

HTML静态网页成品作业(HTML+CSS)——家乡漳州介绍设计制作(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…

css clip-path polygon属性实现直角梯形

2024.3.8今天我学习了如何用css实现直角梯形的效果&#xff0c; 效果&#xff1a; 具体实现原理&#xff1a; 一、需要三个div&#xff1a; 外面一个大的div&#xff0c;里面左右两个小的div 我们需要先把第一个div变成直角梯形&#xff1a; 大概是这样&#xff0c;设置好之…

conda PackagesNotFoundError

参考&#xff1a;https://wenku.csdn.net/answer/3u2f0vgdaj 报错&#xff1a;Solving environment: failed PackagesNotFoundError: The following packages are not available from current channels: 解决方法 ##添加channels conda config --add channels anaconda conda …

【CV论文阅读】【计算机视觉中的Transformer应用综述】(1)

0.论文摘要 摘要——自然语言任务的Transformer model模型的惊人结果引起了视觉社区的兴趣&#xff0c;以研究它们在计算机视觉问题中的应用。在它们的显著优点中&#xff0c;与递归网络例如长短期记忆&#xff08;LSTM&#xff09;相比&#xff0c;Transformer能够模拟输入序…

golang学习随便记16-反射

为什么需要反射 下面的例子中编写一个 Sprint 函数&#xff0c;只有1个参数&#xff08;类型不定&#xff09;&#xff0c;返回和 fmt.Fprintf 类似的格式化后的字符串。实现方法大致为&#xff1a;如果参数类型本身实现了 String() 方法&#xff0c;那调用 String() 方法即可…

C++ 有哪些流行的开发框架或库?

这是我在知乎上回答的一个问题&#xff0c;不到两周收藏数超过 500&#xff0c;点赞还不到 100&#xff0c;看来 C 程序员还是不少&#xff0c;且大家都想进步。 不过从“收藏”就是“学过”的这种风气来看&#xff0c;大概率只是扫一眼&#xff0c;然后放到收藏里吃灰了。 下面…