算法练习day7

四数相加II

代码随想录 0454.四数相加II

454. 四数相加 II - 力扣(LeetCode)

(用时:0.5小时)

思路

本道题是需要在四个数组中,各找一个数,这些数加起来能够等于0,那么就是答案元组。各个数组的数字元组中的位置是固定的,0001和1000是不同的答案。

普通的解法一般是四重循环遍历,逻辑简单粗暴就不再赘述。

这道题可以用哈希表配合进行求解。

  • 先算前两个数组元素相加的结果,将他们的结果存入哈希表中,这里是一个二重循环。

    对于前两个数而言,1 2和2 1他们的和虽然都是3,但是情况是不一样的,属于3的情况出现了两次。题目要输出答案元组的个数,因此选择使用hashset。

  • 接着再算后两个数组元素相加结果,通过hashset查找前两个数的和中符合条件的,组成一个完整的答案元组。在此过程中用计数器累加即可。

错误

思路理解的差不多,但是在写的时候,一些细节方面还是出了问题:

  1. 累加时,累加的数值出现问题。

  2. (疑问)hashset的key和value取什么

个人理解如下:

  • (疑问)hashset的key和value取什么

    hashset是用来记录前两个数字的和出现情况的。那么key应该是两个数字的和,value应该是这个和出现的频率(次数)。

  • 累加时,累加的数值出现问题。

    前面说了,hashset记录的是前两个数字的和出现的频率,那么在累加的时候,应该是要加上频率(次数)而非单纯的加一。

代码实现

hashset实现:

public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4)
{int ans = 0, temp;Dictionary<int, int> dic = new Dictionary<int, int>();
​//记录前两位相加的结果出现的频率foreach (int num1 in nums1){foreach (int num2 in nums2){if(dic.ContainsKey(num1 + num2)){dic[num1 + num2]++;}else{dic.Add(num1 + num2, 1);}}}
​//计算后两位相加的结果,通过这个结果与最终结果的差值查找是否有前两位的和匹配foreach(int num3 in nums3){foreach(int num4 in nums4){temp = 0 - num3 - num4;
​if(dic.ContainsKey(temp)){ans+= dic[temp];}}}
​return ans;
}

赎金信

代码随想录 0383.赎金信

383. 赎金信 - 力扣(LeetCode)

(用时:0.3小时)

思路

本题和前面一道四数相加II有点像,只是这道题的变成了两个。

magazine 中的每个字符只能在 ransomNote 中使用一次,那么就不是查看元素出现的频率,而是单纯查看是否出现即可。

字母一共26个(题目假设只看小写)并不多,故用数组实现哈希表。

错误

这道题是比较简单的题,但是在一些细节方面还是出了问题:

  1. 看错题,以为是要查看字母出现的频率。

  2. 要先处理magazine再处理ransomNote。

个人理解如下:

  • 看错题,以为是要查看字母出现的频率。

    这个问题就没什么好说的了。。。查看字母的频率用键值对结构(dictionary)、查看字母是否出现用hashset。数组结构两种都可以用,用数组要看这个表会有多大。

  • 要先处理magazine再处理ransomNote。

    题目意思是检验ransomNote的字母在magzine的情况(magazine 中的每个字符只能在 ransomNote 中使用一次)。那么magzine要么是包含ransomNote的关系(返回true),要么就是不匹配的关系(返回false)。

    先得得到magzine的元素,再探究ransomNote所有的元素是否在ransomNote出现,且magzine的字母只用一次。

代码实现

/// <summary>
/// 哈希数组实现
/// </summary>
/// <param name="ransomNote"></param>
/// <param name="magazine"></param>
/// <returns></returns>
public bool CanConstruct(string ransomNote, string magazine)
{int[] hash = new int[26];
​for (int i = 0; i < magazine.Length; i++){hash[magazine[i] - 'a']++;}
​for (int i=0;i<ransomNote.Length;i++){hash[ransomNote[i] - 'a']--;}
​for (int i=0;i<hash.Length;i++){if (hash[i]<0){return false;}}
​return true;
}

三数之和

代码随想录 0015.三数之和

15. 三数之和 - 力扣(LeetCode)

(用时:1小时)

思路

和前面的四数相加II不同,本道题是在一个数组中找答案,答案元组不能重复(例如123 和321其实是一个元组)

本题的重点在于去重。

题目是在哈希表章节出现的,去重、唯一性第一反应是用哈希表做。卡哥并没有讲解哈希的方法,因为去重很麻烦

  • 哈希的思路应该是先求出前两项a+b的和,再通过答案和哈希表查找第三项c是否存在。

  • 哈希的结构中,hashset是只记录是否存在,不记录存在次数的,那么可能出现,1 2 1,而1只出现过一次,同一个元素被多次使用。此时感觉可以用键值对的类型来记录出现次数?

  • 但是如果要记录次数,就得配合其他的变量使用。比如让某个数字使用了一次值就--,这是循环一轮时的操作,在新一轮的值又得恢复原本的值。。。这里就很麻烦。

  • 此外,用记录出现次数的键值对类型来做也要额外去重(这里就是卡哥说的去去重麻烦),额外对答案列表中重复的元组去重。

  • 去重的方式其实就是来个二重循环,定一个元组,然后对其他的元组进行遍历比较。这里元组中数字的顺序还不一样,意味着if的条件不能单纯的num1[i]==num2[i]这种,还得处理。

卡哥讲授的是双指针的方法。

  • 一重循环探索确定第一项数字a。

  • 循环中用left和right分别对数字a后的区域进行收缩判断。

  • 这个方法的数组要是有序的。

  • 这中间加上数字a的去重和剪枝操作。

总结来说:

  • 先对数组排序,这里的思路是认为数组升序。

  • 排序后,最外层的循环遍历数字a的情况。

    遍历过程中对数字a进行去重,如果此时a的数值已经出现过了,那就向后遍历(因为是有序的,重复的数字会连续出现)。

    还可以对数字a剪枝。题目的和固定为是0,那么如果数字a大于0,那么该数组不可能会有答案元组(因为是升序的,数字a是三个数字中最小的)

  • 在确定数字a后,用left和right分别表示数组后续剩下的区域,对这块区域进行收缩。

  • 收缩过程中,如果找到了合适的值就可保留下来。

    若nums[i] + nums[left] + nums[right] == 0,表示这组答案是可以的,记录下来即可,然后两个指针一起收缩。 若<0,表示目前的有值有点小,那么让left++即可(数组升序) 若>0,表示目前的有值有点大,那么让right--即可(同理)

  • 收缩过程中,要对left和right对应的值进行去重。

    相同的数值是连续出现的,让left和right指向的值和相邻值不同,即可达到去重的目的。

    需要注意的是,去重是在该答案已经有了的情况下才需要对left和right接下来的值进行去重。这说明left和right的去重是要在答案元组被记录下来后的(卡哥提到的“先记录下来再去重”)

疑问点

看完视频和讲解,对解法还是有一些质疑:

  1. 疑问1:为什么找到答案时,双指针同时收缩?

  2. 疑问2:right和left的去重逻辑和双指针收缩顺序的问题?

  3. 疑问3(错误):数字a的剪枝

个人理解如下:

  • 为什么找到答案时,双指针同时收缩?

    找到答案后,i、left和right的值都是固定的。如果只是收缩left或right,加法式子中其中两个加数不变,那么另一个加数的值也应该是固定的,那么此时这组答案应该有了就重复了。

  • right和left的去重逻辑和双指针收缩顺序的问题?

    这里个人认为放在前后都行。

    卡哥是先去重,再收缩。收缩比较的是left和left+1(right和right-1)。我个人是right和left的去重逻辑放在双指针收缩前,收缩比较的是left和left-1(right和right+1)。这里顺序与收缩逻辑对应一下就可以了。

  • 数字a的剪枝

    这里在写程序时也出现了错误(但是因为是前一天做的,现在忘了这里是怎么错的。。。放上来当作巩固吧)。结果要求是0,数组是升序,那么如果第一个数都大于了0,此数组中想要三个数相加为0是无解的。

代码实现

双指针法:

/// <summary>
/// 双指针法
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public IList<IList<int>> ThreeSumFun1(int[] nums)
{IList<IList<int>> ans = new List<IList<int>>();int left, right;
​Array.Sort(nums);
​for (int i = 0; i < nums.Length; i++){if (nums[i] > 0) return ans;
​if (i > 0 && nums[i] == nums[i - 1]) continue;
​left = i + 1;right = nums.Length - 1;
​while (left < right){if (nums[i] + nums[left] + nums[right] == 0){ans.Add(new List<int> { nums[i], nums[left], nums[right] });left++;right--;
​while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}else if (nums[i] + nums[left] + nums[right] < 0){left++;}else{right--;}}
​}return ans;
}

四数之和

代码随想录 0018.四数之和

18. 四数之和 - 力扣(LeetCode)

(用时:2小时)

思路

这道题的思路是在前一道三数之和的基础上的。

三数之和中,哈希法太过复杂,因此卡哥优先讲解的是双指针法,这道题依旧使用的是双指针法。由于多了一个数,因此循环需要多加一层。

本道题就是先确定前两个数字ab,然后依旧用left和right收缩。

错误

写的时候错了一些:

  1. 错误1:b剪枝操作的返回值出了问题

个人理解如下:

  • b剪枝操作的返回值出了问题

    在三数之和时,只有一层循环因此在剪枝时,直接让整个函数返回列表也是可以的。这个想法延续要了四数之和,四数之和的第一层循环是和三数一样,因此没有出问题,但是第二层循环不能这么写。

    以力扣报错的 -3, -2, -1, 0, 0, 1, 2, 3 这组数据为例。一共是8组答案,程序只判断出了7组,落了一组。经过调试,发现是在-2 0 0 2 这组答案出现后,后面一组的答案没有出现,下图是出现问题前记录的一组答案:

    image-20240510121123236

    接着往后继续调试,在某一步中,发现第二层循环对b的剪枝操作让函数直接跳出了。

    image-20240510121256764

    查看后发现,i和j下标对应的数组值相加后恰好大于target且他们也大于0。但是后续的-1 0 0 1也是一组答案,这里由于b剪枝的原因直接跳过了。这里就是问题所在。

    image-20240510121339577

代码实现

双指针法:

/// <summary>
/// 双指针法
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public IList<IList<int>> FourSumFun(int[] nums, int target)
{IList<IList<int>> ans = new List<IList<int>>();int left, right;
​Array.Sort(nums);for (int i=0;i<nums.Length;i++){//a剪枝操作if (nums[i] > 0 && nums[i] > target) break;
​//a去重操作if (i > 0 && nums[i] == nums[i - 1]) continue;
​for (int j=i+1;j<nums.Length;j++){//b剪枝操作if (nums[i] + nums[j] > 0 && nums[i] + nums[j] > target) break;
​//b去重操作if (j > i + 1 && nums[j] == nums[j - 1]) continue;
​left = j + 1;right = nums.Length-1;
​while(left<right){if (nums[i] + nums[j] + nums[left] + nums[right] == target){ans.Add(new List<int>() { nums[i], nums[j], nums[left], nums[right] });
​left++;right--;
​//去重while (left < right && nums[left] == nums[left - 1]) left++;
​//去重while (left < right && nums[right] == nums[right + 1]) right--;}else if (nums[i] + nums[j] + nums[left] + nums[right] < target){left++;}else{right--;}}}}
​
​return ans;
}

后记

前三道题是在昨天(5.9)写的,没来得及文字记录。最后一道题和文字记录都是今天(5.10)写的。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

slambook2,ch7编译问题

系统环境 ubuntu18&#xff0c;opencv就是默认和ros一起安装的版本,opencv3.2&#xff0c;sophus模板类和非模板类都安装了。 报错信息 主要的原因就是&#xff1a;里面的代码用的是模板类的sophus库&#xff0c;而我安装模板类sophus的时候没有像这篇博客一样Sophus库安装和…

璩静也是受害者

5月7日&#xff0c;“百度副总裁璩静称员工闹分手提离职秒批”话题登上了热搜。在短视频里&#xff0c;璩静是会连续出差50天的“公关人”&#xff0c;没有春节周末、没有假期&#xff0c;她会说“员工闹分手提离职我秒批&#xff0c;为什么要考虑员工的家庭”。有网友对其视频…

JWT生成RSA密钥文档

JWT生成RSA密钥文档 创建jwt文件夹 创建jwt文件夹 进入文件夹 进入jwt文件夹&#xff0c;输入cmd&#xff0c;如图 3、生成公钥私钥 keytool -genkeypair -alias pdm -keyalg RSA -keypass Gacrnd#123 -keystore pdm.jks -storepass Gacrnd#123 -alias&#xff1a;密钥的别名…

VMware虚拟机中ubuntu使用记录(8)—— 如何在Ubuntu18.04中安装运行非ROS版本的ORB_SLAM3跑官方数据集(全程手把手教学安装)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 ORB_SLAM3的介绍一、gitee下载ORB_SLAM3源码1. gitee导入gitHub仓库 二、安装支持C特性依赖三、安装Pangolin1. 安装Pangolin的依赖2. 下载编译 四、安装Eigen31.下…

ChatGPT未来可能应用于iPhone?

苹果接即将与OpenAI达成协议 ChatGPT未来应用于iPhone 前言 就在5月11日&#xff0c;苹果公司正与OpenAI进行深入讨论&#xff0c;计划在其最新的iOS操作系统中整合OpenAI的先进技术。这一举措是苹果公司在为其产品线融入更先进的人工智能功能所做努力的一部分。 目前情况双方…

全网最详细IOS系统APP上架教程(二)

上一篇讲解了IOS系统APP上架注册苹果开发者账号需要的材料、邓白氏编码的注册等&#xff0c;本文将继续讲解后续流程。 详细步骤 三、申请苹果开发者账号 在苹果手机上安装Apple Developer 打开Apple Developer&#xff0c;用之前注册好的Apple ID登录&#xff0c;输入姓名身…

收音机套件焊接和装调的总结

很早之前买了一个小收音机&#xff0c;今天翻出来焊接上。 还好&#xff0c;质量挺好的&#xff0c;电路板没有氧化。 一。静态电流 pcb上面留有ABCD四个测电流的位置。方便调试。 焊接后&#xff0c;V1电流偏大&#xff0c;如果电流过大&#xff0c;会导致R2的压降过大&am…

基于SpringBoot+Vue的笔记共享平台 免费获取源码

项目源码获取方式放在文章末尾处 项目技术 数据库&#xff1a;Mysql5.7/8.0 数据表&#xff1a;10张 开发语言&#xff1a;Java(jdk1.8) 开发工具&#xff1a;idea 前端技术&#xff1a;vue 后端技术&#xff1a;SpringBoot 功能简介 (有文档) 项目获取关键字&#…

机器人系统ros2-开发实践08-了解如何使用 tf2 来访问坐标帧转换(Python)

tf2 库允许你在 ROS 节点中查询两个帧之间的转换。这个查询可以是阻塞的&#xff0c;也可以是非阻塞的&#xff0c;取决于你的需求。下面是一个基本的 Python 示例&#xff0c;展示如何在 ROS 节点中使用 tf2 查询帧转换。 本教程假设您已完成tf2 静态广播器教程 (Python)和tf…

STM32(六):定时器PWM呼吸灯 (标准库函数)

前言 上一篇文章已经介绍了如何用STM32单片机中的TIMER定时器来控制LED灯的交替闪烁&#xff0c;实现了点灯的第五种方式。这篇文章我们来介绍一下如何用STM32单片机中的定时器的PWM波来实现LED的“呼吸”。 一、实验原理 关于定时器这边就不多加赘述&#xff0c;详细请看上…

selenium进行xhs图片爬虫:03获取一篇图文的图片

&#x1f4da;博客主页&#xff1a;knighthood2001 ✨公众号&#xff1a;认知up吧 &#xff08;目前正在带领大家一起提升认知&#xff0c;感兴趣可以来围观一下&#xff09; &#x1f383;知识星球&#xff1a;【认知up吧|成长|副业】介绍 ❤️感谢大家点赞&#x1f44d;&…

如何选择合适加密软件来保护信息资产|精选加密软件分析

五款加密软件对比分析&#xff0c;是一项复杂而必要的任务&#xff0c;旨在帮助用户选择最适合其需求的加密工具。在数字化时代&#xff0c;信息安全显得尤为重要&#xff0c;因此&#xff0c;对加密软件的评估与比较显得尤为关键。 首先&#xff0c;我们要考虑的是这些加密软件…

小程序分包

上传时主包不能过大&#xff0c;采用分包的方式&#xff0c;这里是taro框架 要访问的话

飞跨电容型的三电平(FC-NPC)逆变器simulink仿真模型

本人搭建了飞跨电容型的三电平逆变器simulink仿真模型&#xff0c;相较于二极管钳位型三电平逆变器而言&#xff0c;钳位二极管变为飞跨的电容。采用SPWM调制和均流均压控制&#xff0c;通过搭建仿真模型得到三电平波形。 三电平拓扑中的飞跨电容是指在电路的输出端使用电容来实…

代码随想录第五十天|最佳买卖股票时机含冷冻期、买卖股票的最佳时机含手续费

题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 最佳买卖股票时机含冷冻期与打家劫舍的题目有异曲同工之妙&#xff0c;主要是出现了天数的间隔&#xff0c;一次需要在买卖股票的最佳时机II 题目上做一点调整&#xff0c;代码如下&#xff1a; 如代码所示&…

逻辑卷管理-LVM

目录 1. LVM的基本概念 2. Linux下创建和管理LVM 3. 环境准备 4. 物理卷管理 4.1. 创建物理卷 4.2. 显示物理卷 4.3. 删除物理卷 4. 卷组管理 4.1. 创建卷组 4.2. 显示卷组 4.3. 扩展卷组 4.4. 缩减卷组 4.5. 删除卷组 4.6. 分割卷组 4.7 组合卷组 5. 逻辑卷管…

OpenGL导入的纹理图片错位

在OpenGL中导入图片的纹理照片的函数为 glTexImage2D(GL_TEXTURE_2D, 0, GL_RGB, p_w, p_h, 0, GL_BGR, GL_UNSIGNED_BYTE, pic_data);其中p_w, p_h为图片的宽和高&#xff0c;pic_data为指向图片存储空间的的地址(unsigned char *类型) 在OpenGL中图片默认是4字节对齐的&…

数据结构与算法===递归

文章目录 定义适用场景爬楼梯代码实现 小结 定义 递归(Recursion)是指函数的自身调用。 这个算法演变为了程序员之间的梗&#xff0c;所表达的意思近似于“套娃”&#xff0c;表示不断重复引用别人的话从而产生循环。 适用场景 这个应该很多的&#xff0c;像一些树的遍历&am…

【基于 PyTorch 的 Python 深度学习】5 机器学习基础(1)

前言 文章性质&#xff1a;学习笔记 &#x1f4d6; 学习资料&#xff1a;吴茂贵《 Python 深度学习基于 PyTorch ( 第 2 版 ) 》【ISBN】978-7-111-71880-2 主要内容&#xff1a;根据学习资料撰写的学习笔记&#xff0c;该篇主要介绍了机器学习的基本任务、机器学习的一般流程&…

Leetcode—295. 数据流的中位数【困难】

2024每日刷题&#xff08;132&#xff09; Leetcode—295. 数据流的中位数 实现代码 class MedianFinder { public:MedianFinder() {}void addNum(int num) {if(maxHeap.empty() || num < maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}if(maxHeap.size(…