算法刷题之数组篇
题目一:两数之和
给出一个整型数组 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工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...