代码随想录算法训练营第七天| 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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.