算法刷题之数组篇
题目一:两数之和
给出一个整型数组 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工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
