代码随想录算法训练营第七天| 454.四数相加II、383.赎金信、15.三数之和、18.四数之和

本文主要是介绍代码随想录算法训练营第七天| 454.四数相加II、383.赎金信、15.三数之和、18.四数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

系列文章目录


目录

  • 系列文章目录
  • 454.四数相加II
    • 使用HashMap法
  • 383.赎金信
    • 哈希解法(数组)
  • 15.三数之和
    • 双指针法
  • 18.四数之和
    • 双指针法


454.四数相加II

题解:该题和1.两数之和的方法是一样的,这个题的难点在于keyvalue分别是什么。key是相加的值,value是这个值出现的次数。怎么计算这个值出现的次数又是另一个难点了。需要用到Map接口的getDoDefault方法,getOrDefault(key,0):找到key对应的value,如果key不存在,就返回0

使用HashMap法

import java.util.HashMap;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer, Integer> map = new HashMap<>();//统计两个数组中的元素之和,同时统计出现的次数,放入mapfor (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {int sum = nums1[i] + nums2[j];
/*                if (!map.containsKey(sum)) {//如果没加过该keymap.put(sum, 1);} else {//加过该key则替换value值,将value+1map.put(sum, map.get(sum) + 1);}*/map.put(sum, map.getOrDefault(sum, 0) + 1);}}//统计剩余的两个元素的和,在map中找是否存在相加为0的情况,同时记录次数int count = 0;for (int i = 0; i < nums3.length; i++) {for (int j = 0; j < nums4.length; j++) {int sum = nums3[i] + nums4[j];if (map.containsKey(-sum)) {count += map.get(-sum);}}}return count;}
}
//leetcode submit region end(Prohibit modification and deletion)

注:统计key值出现的次数,有两种方法改变value值。
①利用只能加入一个key,若重复加入key则替换value来实现。

if (!map.containsKey(sum)) {//如果没加过该keymap.put(sum, 1);
} else {//加过该key则替换value值,将value+1map.put(sum, map.get(sum) + 1);
}

②通过getDoDefault方法实现。(快一些)

map.put(sum, getOrDefault(sum, 0) + 1);

383.赎金信

题解:因为两个字符串都是由小写字母组成的,所以说数据的范围是确定的,那么就可以用数组结构。用每个字符对应其数组下标,数组值就是每个字母出现的次数,最后遍历另一个字符串,需要的字母就-1,最后看结果数组的是否有负值,有负值说明字母是不够的,返回false

哈希解法(数组)

class Solution {public boolean canConstruct(String ransomNote, String magazine) {//剪枝if (ransomNote.length() > magazine.length()) {return false;}int[] record = new int[26];//遍历第一个字符串,通过record数据记录 magazine里各个字符出现次数for (int i = 0; i < magazine.length(); i++) {record[magazine.charAt(i) - 'a']++;}/*//遍历ransomNote+判断数组值是否为负for (int i = 0; i < ransomNote.length(); i++) {if(--record[ransomNote.charAt(i)-'a']<0){//只要有一个数组值为负数,就返回falsereturn false;}}*/// 遍历ransomNote,在record里对应的字符个数做--操作for (int i = 0; i < ransomNote.length(); i++) {record[ransomNote.charAt(i) - 'a']--;}//判断数组值是否为负for (int i = 0; i < record.length/*ransomNote.length()*/; i++) {// 如果小于零说明ransomNote里出现的字符,magazine没有if (record[i]/*record[ransomNote.charAt(i) - 'a']*/ < 0) {return false;}}return true;}
}

在这里插入图片描述
注:从字符到数组下标的映射比较耗时间,故最后判断数组值是否为负时直接遍历record数组即可,不要再映射了。


15.三数之和

题解:在同一个数组中找一个三个数(这三个数的下标不同),相加和为0这个三元组不能重复,但里面的元素可以重复。如果数组是 [0,0,1,1,-1,-1,-2],则 [0,1,-1][0,1,-1]不合法,但是[1,1,-2]合法。

双指针法

import java.util.ArrayList;
import java.util.Arrays;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public List<List<Integer>> threeSum(int[] nums) {//注意题目中方法要求返回<List<Integer>>泛型List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);// 找出a + b + c = 0// a = nums[i], b = nums[left], c = nums[right]for (int i = 0; i < nums.length; i++) {// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) {return result;}//去重a//一定要有i>0条件,因若i=0,此时nums[i-1]=-1,数组越界异常if (i > 0 && nums[i] == nums[i - 1]) {continue;//跳过本次循环进入下次循环,不能i++因还会执行本次循环}int left = i + 1;int right = nums.length - 1;while (left < right) {//剪枝:排序之后如果最后一个元素小于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if(nums[right]<0){System.out.println("1111");return result;}if (nums[i] + nums[left] + nums[right] > 0) {right--;} else if (nums[i] + nums[left] + nums[right] < 0) {left++;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (left < right && nums[right] == nums[right - 1]) right--;while (left < right && nums[left] == nums[left + 1]) left++;right--;left++;}}}return result;}
}
//leetcode submit region end(Prohibit modification and deletion)

注:①题目中方法要求返回<List<Integer>>泛型,故在创建ArrayList时要注意。
Arrays类里面包含了一系列静态方法,用于管理或操作数组,故调用sort方法对数组进行自然排序。
在这里插入图片描述
③剪枝操作:排序后,在遍历数组时,

  1. 如果三个数中最小的数即a=nums[i]已经>0,则已不可能三个数之和为0,故可直接退出。

           for (int i = 0; i < nums.length; i++) {//剪枝:排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) {return result;}...}
    
  2. 如果最后一个元素c=nums[right]已经<0,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了。

           while (left < right) {//剪枝:排序之后如果最后一个元素小于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if(nums[right]<0){System.out.println("1111");return result;}...}
    

④对a进行去重时,一定要有i>0条件,因若i=0,此时nums[i-1]=-1,数组越界异常。
在这里插入图片描述
⑤对b=nums[left],c=nums[right]的去重操作。

  1. 放在找到三元组之前,[0,0,0] 的情况,可能直接导致 right<=left 直接退出循环了,此时还没加入一个三元组,从而漏掉了[0,0,0]这种三元组。

    while (left < right) {// 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组/*while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;*/if (...)...
    }
    
  2. 去重逻辑应该放在找到一个三元组之后,对b、c去重。此时判断right是否与左边元素相等,若相等则跳过该左边的元素;判断left是否与右边元素相等,若相等则跳过该右边的元素。最后两行的 right--; left++;不管b、c有没有重复都得有,其意味着三元组此时已经=0,不论单独移动哪一边,都不会再有=0的情况了,故必须得同时移动。
    在这里插入图片描述

  3. 很多同学写本题的时候,去重的逻辑多加了 对rightleft 的去重:nums[right] == nums[right + 1]其实比较的还是当前right指针即right + 1与左边元素right,因前面有个 right--;,已经将right指针左移了,此时指向的是左边元素。nums[left] == nums[left - 1]同理。

    while (right > left) {if (nums[i] + nums[left] + nums[right] > 0) {right--;// 去重 rightwhile (left < right && nums[right] == nums[right + 1]) right--;} else if (nums[i] + nums[left] + nums[right] < 0) {left++;// 去重 leftwhile (left < right && nums[left] == nums[left - 1]) left++;} else {}
    }
    

    在这里插入图片描述
    因此时是在!=0的条件下去重的,不论是right还是left,即使去重了,去重后得到的rightleft指针还是指向三元组!=0的元素。

在这里插入图片描述


18.四数之和

双指针法

在这里插入图片描述


这篇关于代码随想录算法训练营第七天| 454.四数相加II、383.赎金信、15.三数之和、18.四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/807208

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu