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

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

今日任务

●  454.四数相加II

●  383. 赎金信

●  15. 三数之和

●  18. 四数之和

详细布置

454.四数相加II

建议:本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序执行效率,降低时间复杂度,当然使用哈希法 会提高空间复杂度,但一般来说我们都是舍空间 换时间, 工业开发也是这样。

题目链接:. - 力扣(LeetCode)

题目链接/文章讲解/视频讲解:代码随想录

暴力解:

四层循环遍历,每找到一种就累计一次(缺陷是最后一次的数组每次都需要遍历一遍)

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;for(int i=0;i<nums1.length;i++){for(int j=0;j<nums2.length;j++){for(int k=0;k<nums3.length;k++){for(int l=0;l<nums4.length;l++){if(nums1[i]+nums2[j]+nums3[k]+nums4[l] == 0){res++;}}}}}return res;}
优化:

利用分治,分别两两数组计算,变成两数之和的问题

// 优化思路: 分治处理,再利用map累计次数//public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer,Integer> map = new HashMap<Integer,Integer>();//汇总前两个数组,并用map记录累加和及相同累加和出现的次数for(int i:nums1){for(int j:nums2){int sum = i+j;map.put(sum,map.getOrDefault(sum,0)+1);}}for(int i:nums3){for(int j:nums4){int sum = i+j;if(map.containsKey(-sum)){res += map.get(-sum);}}}return res;}
       

383. 赎金信

建议:本题 和 242.有效的字母异位词 是一个思路 ,算是拓展题

题目链接:. - 力扣(LeetCode)

题目链接/文章讲解:代码随想录

ransomNote 和 magazine 由小写英文字母组成 -- 第一反应就是,可以用 s.charAt(i)-'a' 的方式 用 26 个数组来做为字典表

//ransomNote 和 magazine 由小写英文字母组成 -- 说明可以用 s.charAt(i)-'a' 的方式来记录对应的元素public boolean canConstruct(String ransomNote, String magazine) {int[] dirt = new int[26];for(int i=0;i<magazine.length();i++){dirt[magazine.charAt(i)-'a'] ++;}boolean res = true;for(int i=0;i<ransomNote.length();i++){if(dirt[ransomNote.charAt(i)-'a']-- ==0){res = false;break;}}return res;}

15. 三数之和

建议:本题虽然和 两数之和 很像,也能用哈希法,但用哈希法会很麻烦,双指针法才是正解,可以先看视频理解一下 双指针法的思路,文章中讲解的,没问题 哈希法很麻烦。

题目链接:. - 力扣(LeetCode)

题目链接/文章讲解/视频讲解:代码随想录

哈希解:

public List<List<Integer>> threeSum(int[] nums) {Map<String,List<Integer>> res = new HashMap<>();//key 累加和,val: 组成的元素的索引组合Map<Integer,List<List<Integer>>> map = new HashMap<>();int l=0;int r=1;while(l<r && l < nums.length -1 && r < nums.length){int sum = nums[l] + nums[r];List<List<Integer>> val = map.get(sum);if(val == null){val = new ArrayList();}List<Integer> son = new ArrayList(2);son.add(l);son.add(r++);val.add(son);map.put(sum,val); //每次右指针到头时,都需要重置左右指针if(r == nums.length ){l++;r = l+1;}}for(int i=0;i<nums.length;i++){if(map.containsKey(-nums[i])){List<List<Integer>> val = map.get(-nums[i]);for(List<Integer> list:val){if(!list.contains(i)){List<Integer> sonList = new ArrayList();sonList.add(nums[list.get(0)]);sonList.add(nums[list.get(1)]);sonList.add(nums[i]);String key = sonList.stream().sorted().map(Object::toString).collect(Collectors.joining());res.put(key,sonList);}}}}return new ArrayList<>(res.values());}

三指针解:

 /*** [-1,0,1,2,-1,-4]* 排序* [-4,-1,-1,0,1,2]*   p  l        r --> nums[l] + nums[r] < 0-(-4) ,即说明当前双指针对应元素的值偏小,又因为数组已经升序排序了,这个时候逐步右移l,*   p         l r --> 一直右移到最右侧,说明当前定点值太小,逐步右移定点P,再执行上述的操作过程*      p  l     r --> nums[l] + nums[r] = 0-(-1) ,满足条件,再逐步右移定点P,再执行上述的操作过程*        p  l   r --> nums[l] + nums[r] > 0-(-1) ,即说明当前双指针对应元素的值偏大,又因为数组已经升序排序了,这个时候逐步左移r*        p  l r   --> 当移动到 l + 1 位置时,nums[l] + nums[r] = 0-(-1),满足条件,再逐步右移定点P,再执行上述的操作过程*           p l r --> 当p点已经移动到了倒数第三位的时候,只需要计算最后三位的和即可(这里还有一个隐形条件,如果,定点已经到正数了则最右侧的值不管怎么加都是大于0的,这个时候直接跳出循环即可)* 输出:* [-1,-1,2]* [-1,0,1]** 核心思路:*    1.对数组进行排序,从最左侧定点之后,再通过双指针的方式依次遍历定点+1 与 len -1 对应位置的值* @param nums* @return*/public static List<List<Integer>> threeSum(int[] nums) {if(nums.length<3){return null;}//优先数组排序Arrays.sort(nums);if(nums[0] > 0){return null;}List<List<Integer>> ans = new ArrayList<>();int p = 0;//指定定点边界while(p < nums.length-1 && nums[p] <= 0){int target = 0-nums[p];//左指针int l = p+1;//右指针int r = nums.length -1;while(l<r){int c = nums[l] + nums[r];if(c < target){//即说明当前双指针对应元素的值偏小,又因为数组已经升序排序了,这个时候逐步右移ll++;}else if(c > target){//即说明当前双指针对应元素的值偏大,又因为数组已经升序排序了,这个时候逐步左移rr--;}else{//避免重复:如果l+1位置的值与l位置的一致,则继续右移才行while (l<r && nums[l]==nums[l+1]){ l++;}//避免重复:如果r-1位置的值与r位置的一致,则继续左移才行while (l<r && nums[r]==nums[r-1]){ r++;}//相等:则满足条件,添加元素List<Integer> list =  new ArrayList<>(3);list.add(nums[p]);list.add(nums[l]);list.add(nums[r]);ans.add(list);break;}}//右移定点p++;}return ans;}

18. 四数之和

建议: 要比较一下,本题和 454.四数相加II 的区别,为什么 454.四数相加II 会简单很多,这个想明白了,对本题理解就深刻了。 本题 思路整体和 三数之和一样的,都是双指针,但写的时候 有很多小细节,需要注意,建议先看视频。

题目链接:

题目链接/文章讲解/视频讲解:代码随想录

暴力四指针求解

public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重for (int j = i + 1; j < nums.length; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重int l = j + 1;int r = nums.length - 1;while (l < r) {if (r < nums.length - 1 && nums[r] == nums[r + 1]) { // 去重r--;} else if (l > j + 1 && nums[l] == nums[l - 1]) { // 去重l++;} else if ((long) nums[i] + nums[j] + nums[l] + nums[r] > target) { r--;} else if ((long) nums[i] + nums[j] + nums[l] + nums[r] < target) {l++;} else {res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));l++; r--;}}}}return res;}

通过递归回溯实现

LeetCode提交会超时,这里仅提供思路,回溯本质上是暴力解,需要挖掘条件尽可能去剪枝

 /*** 递归回溯实现:** @param nums* @param target* @return*/public  static  List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();if (nums == null || nums.length < 4) {return res;}//优先按从小到大排序Arrays.sort(nums);//极限问题//最大的四个数之和都比target小,则直接返回if(target > nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] + nums[nums.length - 4]){return res;}LinkedList<Integer> path = new LinkedList<>();Set<String> set = new HashSet<>();dfs(nums,res,set,path,target,0,0);return res;}/*** 递归回溯实现:*   回溯的关键在于什么时候 递 什么时候归,什么时候需要回溯,回溯到哪一步** @param nums* @param res 用于收集所有满足条件的解* @param path 用于收集或回溯当前的组合* @param set 用于避免收集到重复解* @param target* @param curSum* @param idx*/public static void dfs(int[] nums,List<List<Integer>> res,Set<String> set,LinkedList<Integer> path,int target,int curSum,int idx){//当前和大于目标了都终止(因为nums是从小到大排序的继续往后面找只会越来越大)if(curSum > target && path.size()>4){return;}//收集最终满足的结果:后面的就需要继续遍历了,因为nums是从小到大排序的,后面的元素只会越来越大,就算后一个元素等于前一个元素(对于本题来说也不需要解都是相同的)//又因为最终收集的结果是值并不是索引,且要求不重复,则需要判断当前的组合是否已经收集,如果已收集就不需要了if(path.size() == 4 && curSum == target){String key = path.stream().map(Object::toString).collect(Collectors.joining(","));if(set.contains(key)){return;}set.add(key);res.add(new ArrayList<>(path));return;}for (int i = idx; i < nums.length; i++) {//选择当前元素path.add(nums[i]);//累加组合元素之和curSum += nums[i];dfs(nums,res,set,path,target,curSum,i+1);//回溯//撤销选择path.removeLast();//撤销累加curSum -= nums[i];}}

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



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

相关文章

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