代码随想录算法训练营第七天|454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和
打卡Day7
- 1.454.四数相加II
- 2.383. 赎金信
- 3.15. 三数之和
- 4.18. 四数之和
1.454.四数相加II
题目链接:四数相加II
文档讲解: 代码随想录
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer,Integer> map = new HashMap<>();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){res += map.getOrDefault((0 - i - j), 0);}}return res;}
}
2.383. 赎金信
题目链接:赎金信
文档讲解: 代码随想录
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];if(ransomNote.length() > magazine.length()){return false;}for(int i = 0; i < magazine.length(); i++){record[magazine.charAt(i) - 'a']++;}for(int i = 0; i < ransomNote.length(); i++){record[ransomNote.charAt(i) - 'a']--;}for(int i = 0; i < ransomNote.length(); i++){//判断不等于0是不对的,没有考虑到magazine中存在该字母出现更多次的情况if(record[ransomNote.charAt(i) - 'a'] < 0){return false;}}return true;}
}
//使用增强for
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];if(ransomNote.length() > magazine.length()){return false;}for(char i: magazine.toCharArray()){record[i - 'a'] += 1;}for(char i: ransomNote.toCharArray()){record[i - 'a'] -= 1;}for(int i: record){if(i < 0){return false;}}return true;}
}
3.15. 三数之和
题目链接:三数之和
文档讲解: 代码随想录
class Solution {public List<List<Integer>> threeSum(int[] nums) {//哈希法List<List<Integer>> res = new ArrayList<>();//需要对nums进行排序Arrays.sort(nums);for(int i = 0; i < nums.length; i++){//如果第一个元素大于0,则不可能存在三元组if(nums[i] > 0){return res;}//a去重if(i > 0 && nums[i] == nums[i - 1]){continue;}HashSet<Integer> set = new HashSet<>();for(int j = i + 1; j < nums.length; j++){//b去重if(j > i + 2 && nums[j] == nums[j - 1] && nums[j] == nums[j - 2]){continue;}int c = - nums[i] - nums[j];if(set.contains(c)){res.add(Arrays.asList(nums[i], nums[j], c));set.remove(c);//c去重}else{set.add(nums[j]);} }}return res;}
}
注意点:
(1)a 的去重:在两种方法中纠结,一是判断nums[i] == nums[i+1],一种是判断nums[i] == nums[i-1]。如果前者,那么存在遗漏情况,例如{-1,-1,2}。
(2)b 的去重:可以和 a 一样判断nums[j] == nums[j-1],从而跳过相同的b。但是这样子可能会遗漏情况,例如{0,0,0}。因此只有当当前的 b 和前两个 b 都相同时才跳过当前的 b。这样可以保证至少有一个 b 被使用,并且不会出现重复。
class Solution {public List<List<Integer>> threeSum(int[] nums) {//双指针法List<List<Integer>> res = new ArrayList<>();//需要对nums进行排序Arrays.sort(nums);for(int i = 0; i < nums.length; i++){if(nums[i] > 0){return res;} //a去重if(i >= 1 && nums[i] == nums[i - 1]){continue;}int left = i + 1;int right = nums.length - 1;while(left < right){//left和right是两个指针,与二分查找不一样int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right--;}else if(sum < 0){left++;}else{res.add(Arrays.asList(nums[i], nums[left], nums[right]));//去重while(left < right && nums[left] == nums[left + 1]){left++;}while(left < right && nums[right] == nums[right - 1]){right--;}right--;left++;}}} return res;}
}
两数之和不能用双指针法的原因:因为双指针法需要排序,而两数之和需要返回索引下标。
4.18. 四数之和
题目链接:四数之和
文档讲解: 代码随想录
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length; i++){//剪枝if(nums[i] > 0 && nums[i] > target){return res;}//去重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 left = j + 1;int right = nums.length - 1;while(left < right){long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];//防止溢出if(sum > target){right--;}else if(sum < target){left++;}else{res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));//去重while(left < right && nums[left] == nums[left + 1]){left++;}while(left < right && nums[right] == nums[right - 1]){right--;}left++;right--;}}}}return res;}
}
相关文章:
代码随想录算法训练营第七天|454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和
打卡Day7 1.454.四数相加II2.383. 赎金信3.15. 三数之和4.18. 四数之和 1.454.四数相加II 题目链接:四数相加II 文档讲解: 代码随想录 class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res 0;Map…...
Python和tkinter实现的字母记忆配对游戏
Python和tkinter实现的字母记忆配对游戏 因为这个小游戏用到了tkinter,先简要介绍一下它。tkinter是Python的标准GUI(图形用户界面)库,它提供了一种简单而强大的方式来创建图形界面应用程序。它提供了创建基本图形界面所需的所有工具,同时保…...
Leetcode Hot100之链表
1.相交链表 解题思路 快慢指针:分别求出两个链表的长度n1和n2,在长度较长的那个链表上,快指针先走n2 - n1,慢指针再出发,最后能相遇则链表相交 时间复杂度O(mn),空间复杂度O(1)代码# Definition for singl…...
5.9k!一款清新好用的后台管理系统!【送源码】
今天给大家分享的开源项目是一个优雅清新后台管理系统——Soybean Admin。 简介 官方是这样介绍这个项目的: Soybean Admin 使用的是Vue3作为前端框架,TypeScript作为开发语言,同时还整合了NaiveUI组件库,使得系统具有高可用性和…...
Vue-cli搭建项目----基础版
什么是Vue-cli 全称:Vue command line interface 是一个用于快速搭建Vue.js项目的标准工具,他简化了Vue.js应用的创建和管理过程,通过命令工具帮助开发者快速生成,配置和管理Vue项目. 主要功能 同一的目录结构本地调试热部署单元测试集成打包上线 具体操作 第一步创建项目:…...
python之__call__函数介绍
Python 中的 __call__ 方法是一种特殊的方法,它允许对象像函数一样被调用。当你创建一个对象并使用括号 () 调用它时,Python 会自动调用这个对象的 __call__ 方法。 1. 基本用法 下面是一个简单的例子: class MyClass:def __init__(self, value):self.value valued…...
【AI】生成式AI服务器最低配置
【背景】 考虑数据安全,又想用AI赋能企业内部的日常工作,答案只有一个,本地部署。 UI采用open-web-ui,模型用Ollama管理,在局域网做成SAAS服务。要组一个服务器,提供部门内部最多30个的API并发。以下为反复…...
2.Android逆向协议-了解常用的逆向工具
免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 内容参考于:微尘网校 上一个内容:1.Android逆向协议-环境搭建 常用的工具:AndroidKiller、jadx、JEB、IDA AndroidKiller…...
大数据------额外软件、插件及技术------Linux(完整知识点汇总)
Linxu 不同领域的主流操作系统 桌面操作系统 WindowsMAac OSLinux 服务器端操作系统 UNIX(付费)LinuxWindows Server(付费) 移动设备操作系统 Android(基于Linux开源)IOS(不开源) 嵌…...
iOS 其他应用的文件如何在分享中使用自己的应用打开
废话少说 一、第一步:先配置好plist文件 右击info.plist如下图文件打开 根据自己需要配置支持的文件类型,也可使用property List中配置,一样的 其他的文件可是参考文档:System-Declared Uniform Type Identifiers 可复制的代码&am…...
【编译原理必考大题】 推导构建语法树,写出语法树的短语,简单短语和句柄
写在最前 本文为编译原理重点考察大题之一,理论基础见专栏文章,0基础直接使用也可食用 文章目录 推导构造语法树1.语法树的概念2. 子树,短语,简单短语,句柄2.1 子树2.2 短语2.3 简单短语与句柄2.4 真题实战 推导构造语…...
redis服务介绍
redis 基础概念安装使用基础操作命令数据类型操作命令 管理和维护命令 基础概念 Remote Dictionary Server(Redis)远程字典服务器是完全开源免费的,用C语言编写的,遵守BSD开源协议,是一个高性能的(key/val…...
nodepad 中换行符、tab替换
1 nodepad 主要符号 换行符: \r\n(windows) tab: \t 2 展示符号 3 相互替换 tip:需要点击扩展 参考: https://blog.csdn.net/lijing742180/article/details/85174564...
常见的字符串函数(包含头文件string.h)和字符函数(2)
八. strstr函数 1.strstr的定义 char *strstr( const char *str1, const char *str2 ); ->1. strstr查找子串(str2)在字符串(str2)中第一次出现的位置,记录并返回该位置的指针,如果找不到,则返回NULL ->2. str1:查找字符…...
Python | Leetcode Python题解之第187题重复的DNA序列
题目: 题解: L 10 bin {A: 0, C: 1, G: 2, T: 3}class Solution:def findRepeatedDnaSequences(self, s: str) -> List[str]:n len(s)if n < L:return []ans []x 0for ch in s[:L - 1]:x (x << 2) | bin[ch]cnt defaultdict(int)for…...
SpringCloud分布式微服务链路追踪方案:Skywalking
一、引言 随着微服务架构的广泛应用,系统的复杂性也随之增加。在这种复杂的系统中,应用通常由多个相互独立的服务组成,每个服务可能分布在不同的主机上。微服务架构虽然提高了系统的灵活性和可扩展性,但也带来了新的挑战…...
首次线下联合亮相!灵途科技携手AEye、ATI亮相2024 EAC 易贸汽车产业大会
6月22日,2024 EAC 易贸汽车产业大会在苏州国际博览中心圆满落幕,泛自动驾驶领域光电感知专家灵途科技携手自适应高性能激光雷达解决方案全球领导者AEye公司(NASDAQ:LIDR)及光电器件规模化量产巨头Accelight Technologiesÿ…...
一文入门CMake
我们前几篇文章已经入门了gcc和Makefile,现在可以来玩玩CMake了。 CMake和Makefile是差不多的,基本上是可以相互替换使用的。CMAke可以生成Makefile,所以本质上我们还是用的Makefile,只不过用了CMake就不用再写Makefile了&#x…...
【LeetCode面试经典150题】117. 填充每个节点的下一个右侧节点指针 II
一、题目 117. 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode) 给定一个二叉树: struct Node {int val;Node *left;Node *right;Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个…...
RTDETR更换优化器——Lion
RTDETR更换Lion优化器 论文:https://arxiv.org/abs/2302.06675 代码:https://github.com/google/automl/blob/master/lion/lion_pytorch.py 简介: Lion优化器是一种基于梯度的优化算法,旨在提高梯度下降法在深度学习中的优化效果…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
