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

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n