算法刷题之数组篇
题目一:两数之和
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)
方法一,双层for遍历:
不过,这种方法在牛客网上执行的时候报超时错误
import java.util.*;
public class Solution {/*** * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {// write code hereint n = numbers.length;int[] res = {-1, -1};//遍历数组for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {//判断相加值是否为targetif (numbers[i] + numbers[j] == target) {res[0] = i+1;res[1] = j+1;//返回值return res;}}}return res;}
}
复杂度分析:
- 时间复杂度:O(n^2) 遍历两次数组
- 空间复杂度:O(1) 未申请额外空间
方法二,hash表
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param numbers int整型一维数组* @param target int整型* @return int整型一维数组*/public int[] twoSum (int[] numbers, int target) {HashMap<Integer, Integer> map = new HashMap<>();//遍历数组for (int i = 0; i < numbers.length; i++) {if (map.containsKey(target - numbers[i])) {// 这里题目要求下标在数组中升序排列,这里这样放直接就满足了题意,因为数据A肯定先放入map,后面containsKey判断得出的数据B的下标i肯定大于数据A下标return new int[] {map.get(target - numbers[i]) + 1, i + 1};} else {map.put(numbers[i], i);}}throw new IllegalArgumentException("No solution");}
}
复杂度分析:
- 时间复杂度:O(n) 一次遍历hash索引查找时间复杂度为O(1)
- 空间复杂度:O(n) 申请了n大小的map空间
题目二:最接近的三数之和
描述
给定一个数组 nums 和一个目标值 target ,请问从 nums 中选出三个数,使其之和尽量接近目标数,即三数之和与目标数只差绝对值尽可能小。
返回满足题面要求的三数之和。
数据范围:数组长度满足3≤n≤300 ,数组中的值满足 ∣nums[i]∣≤1000 ,目标值满足∣target∣≤10^4 ,可以保证只有一个结果。
方法一,暴力三层循环
循环累加,计算三个数之和与目标值target差值绝对值最小
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int ClosestSum (int[] nums, int target) {// write code hereint sum_min = Integer.MAX_VALUE;int result=0;for(int i=0;i<nums.length-2;i++){for(int j=i+1;j<nums.length-1;j++){for(int k=j+1;k<nums.length;k++){int sum=nums[i]+nums[j]+nums[k];if(Math.abs(sum-target)<sum_min){sum_min=Math.abs(sum-target);result=sum;}}}}return result;}
}
方法二,先排序再循环
数组在没有排序之前不容易实现某种算法,排序完之后,在固定第一个数字的情况下,通过与之后数据中头尾数据相加得sum,与target求差,循环比对差距大小。同时头尾数据会根据与target大小做调整,当sum>target时,尾数据下标-1,当sum<target时,头数据下标+1,sum=target,则可以直接返回。
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param nums int整型一维数组* @param target int整型* @return int整型*/public int ClosestSum (int[] nums, int target) {// write code here// 排序Arrays.sort(nums);// 记录结果int res = nums[0] + nums[1] + nums[2];for (int i = 0; i < nums.length - 2; i++) {// 头尾数据下标int start = i + 1;int end = nums.length - 1;while (start < end) {int sum = nums[i] + nums[start] + nums[end];//每次头尾数据变更之后,比对差值大小if (Math.abs(sum - target) < Math.abs(res - target)) {res = sum;}if (sum > target) {end--;} else if (sum < target) {start++;} else {return sum;}}}return res;}
}
相关文章:
算法刷题之数组篇
题目一:两数之和 给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。 (注:返回的数组下标从1开始算起,保证target一定可以由数组里面2…...

TR转发路由器测评—云企业网实现跨地域跨VPC的网络互通测评实战【阿里云产品测评】
文章目录 一.转发路由器 Transit Router 测评1.1 准备阶段1.2 本文测评收获1.3 什么是云企业网实例、转发路由器实例和云数据传输服务 二.使用云企业网实现跨地域跨VPC的网络互通2.2 **测试连通性**2.3 网络拓扑如下: 心得:总结: 声明&#x…...

1.1美术理论基础
一、光影 物体呈现在人们眼前的时候,不同的受光面其明暗变化以及物体的影子。 1.什么是黑白灰 在美术中黑白灰指亮面、灰面、暗面,属于素描的三大面,主要体验一个物体的整体寿光过程。普遍存在于各种艺术和设计领域。黑白灰作品的出现&#x…...

【Java 基础】21 多线程同步与锁
文章目录 1.存在的问题2.使用同步解决问题1) synchronized2) volatile3) 锁 总结 用多线程过程中,有可能出现 多个线程同时处理(获取或修改等)同一个数据,这个时候就 会发生数据不同步的问题, 因此出现了同步和锁来…...

Python语言基础知识(一)
文章目录 1、Python内置对象介绍2、标识符与变量3、数据类型—数字4、数据类型—字符串与字节串5、数据类型—列表、元组、字典、集合6、运算符和表达式7、运算符和表达式—算术运算符8、运算符和表达式—关系运算符9.1、运算符和表达式— 成员测试运算符in9.2、运算符和表达式…...

Xilinx FPGA平台DDR3设计详解(三):DDR3 介绍
本文介绍一下常用的存储芯片DDR3,包括DDR3的芯片型号识别、DDR3芯片命名、DDR3的基本结构等知识,为后续掌握FPGA DDR3的读写控制打下坚实基础。 一、DDR3芯片型号 电路板上的镁光DDR3芯片上没有具体的型号名。 如果想知道具体的DDR3芯片型号&#…...
字典的遍历
字典不是有序的集合,就不能通过index来遍历了,那如何遍历字典呢? 方法一:直接用字典 for key in a_dict: print a_dict[key] 通过这样的结构可以的。 d {"liming" : 98, "wangli":95, "mali":90, "liping&q…...

Linux环境下的MySQL安装
文章目录 前提说明1.卸载内置环境2.检查系统安装包3.卸载这些默认安装包4.获取MySQL官方yum源5.安装MySQLyum源,对比前后yum源6.查看yum源是否生效7.安装MySQL服务8.查看相对应的配置文件9.启动服务10.查看启动服务11.登录方法一12.登录方法二13.登录方法三14.设置开…...
梦想与魔法:编程之路的挑战与荣耀
在年少轻狂的岁月里,我们都有过一些不切实际的梦想,渴望成为某种神奇的存在。我的梦想是成为一名神奇的码农,用键盘编织魔法,创造出炫酷的虚拟世界。然而,现实是残酷的,当我刚入门计算机领域时,…...

qt 5.15.2 主窗体菜单工具栏树控件功能
qt 5.15.2 主窗体菜单工具栏树控件功能 显示主窗体效果: mainwindow.h文件内容: #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include <QFileDialog> #include <QString> #include <QMessageBox>#inc…...

Day15——File类与IO流
1.java.io.File类的使用 1.1 File类的理解 File 类及本章下的各种流,都定义在 java.io 包下。一个 File 对象代表硬盘或网络中可能存在的一个文件或者文件目录(俗称文件夹),与平台无关。(体会万事万物皆对象…...

【Qt】QLineEdit显示输入十六进制,位数不足时按照规则填充显示及每两个字符以空格填充
问题 在实际开发中,有时候需要对输入进行限制,一是更加合理,二是防止出现误操作。 比如: 使用Qt进行应用程序开发时,对单行编辑框QLineEdit控件,设置只可输入十六进制。 限制输入的方式常用且经典的是使用…...

GPT 中文提示词技巧:参照 OpenAI 官方教程
前言 搜了半天什么 prompt engineering 的课,最后会发现 gpt 官方其实是有 prompt 教程的。因此本文主要是学习这篇教程。 概述 - OpenAI API 部分案例是参考:根据吴恩达老师教程总结出中文版prompt教程_哔哩哔哩_bilibili up主的内容。 一、尽可能清…...

原生微信小程序将字符串生成二维码图片
weapp-qrcode.js再最后 inde.ts中的内容 // pages/qrCode/index.ts // 引入weapp-qrcode.js文件 var QRCode require(../../utils/weapp-qrcode) Page({/*** 页面的初始数据*/data: {orderNo:"",imagePath:},/*** 生命周期函数--监听页面加载*/onLoad(options:any)…...
深入理解HTTPS加密协议
在现代网络环境中,数据安全和隐私保护至关重要。HTTPS(全称为HyperText Transfer Protocol Secure)是一种用于保障互联网通信安全的加密协议,它通过在HTTP协议的基础上添加SSL/TLS层来实现对数据的加密传输。本文将详细介绍HTTPS的…...

路径规划之PRM算法
系列文章目录 路径规划之Dijkstra算法 路径规划之Best-First Search算法 路径规划之A *算法 路径规划之D *算法 路径规划之PRM算法 路径规划之PRM算法 系列文章目录前言一、前期准备1.栅格地图2.采样3.路标 二、PRM算法1.起源2.流程3. 优缺点4. 实际效果 前言 之前提到的几种…...

深入理解数据在内存中是如何存储的,位移操作符如何使用(能看懂文字就能明白系列)文章超长,慢慢品尝
系列文章目录 C语言笔记专栏 能看懂文字就能明白系列 🌟 个人主页:古德猫宁- 🌈 信念如阳光,照亮前行的每一步 文章目录 系列文章目录🌈 *信念如阳光,照亮前行的每一步* 前言引子一、2进制和进制转化为什么…...

ArcGIS提示当前许可不支持影像服务器
1、问题: 在用ArcGIS上处理影像栅格数据时(比如栅格数据集裁剪、镶嵌数据集构建镶嵌线等)经常会出现。 无法启动配置 RasterComander.ImageServer <详信息 在计算机XXXXX上创建服务器对象实例失败 当前许可不支持影像服务器。 ArcGIS提示当…...

Android P 9.0 增加以太网静态IP功能
效果图 一、Settings添加以太网的配置: 1、vendor\mediatek\proprietary\packages\apps\MtkSettings\res\xml\network_and_internet.xml <com.android.settingslib.RestrictedPreferenceandroid:key"ethernet_settings"android:title"string/et…...

Android12之MediaCodec硬编解码调试手段(四十九)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...