LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
目录
- 7 两数之和
- 题目描述:
- 解题思路与代码
- 暴力解法:
- 解法一:二分查找
- 解法二:双指针
- 2 斐波那契数列
- 题目描述:
- 解题思路与代码
- 解法一:暴力递归
- 解法二:去重递归
- 解法三:双指针迭代
7 两数之和
题目描述:
给定一个升序排列的整数数组 numbers ,从数组中找出两个数满足相加之和等于目标数 target 。
假设每个输入只对应唯一的答案,而且不可以重复使用相同的元素。
返回两数的下标值,以数组形式返回
解题思路与代码
暴力解法:
public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];}
时间复杂度:O(N的平方)
空间复杂度:O(1)
哈希表:将数组的值作为key存入map,target - num作为key
public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target - nums[i]), i};}map.put(nums[i], i);}return new int[0];}
时间复杂度:O(N)
空间复杂度:O(N)
解法一:二分查找
先固定一个值(从下标0开始),再用二分查找查另外一个值,找不到则固定值向右移动,继续二分查找
public int[] twoSearch(int[] numbers, int target) {for (int i = 0; i < numbers.length; ++i) {int low = i, high = numbers.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (numbers[mid] == target - numbers[i]) {return new int[]{i, mid};} else if (numbers[mid] > target - numbers[i]) {high = mid - 1;} else {low = mid + 1;}}}}
时间复杂度:O(N * logN)
空间复杂度:O(1)
解法二:双指针
左指针指向数组head,右指针指向数组tail,head+tail > target 则tail 左移,否则head右移
public int[] twoPoint(int[] numbers, int target) {int low = 0, high = numbers.length - 1;while (low < high) {int sum = numbers[low] + numbers[high];if (sum == target) {return new int[]{low + 1, high + 1};} else if (sum < target) {++low;} else {--high;}}return new int[]{-1, -1};}
时间复杂度:O(N)
空间复杂度:O(1)
2 斐波那契数列
题目描述:
求取斐波那契数列第N位的值。
斐波那契数列:每一位的值等于他前两位数字之和。前两位固定
解题思路与代码
解法一:暴力递归
public static int calculate(int num){if(num == 0 ){return 0;}if(num == 1){return 1;}return calculate(num-1) + calculate(num-2);}
解法二:去重递归
递归得出具体数值之后、存储到一个集合(下标与数列下标一致),后面递归之前先到该集合查询一次,如果查到则无需递归、直接取值。查不到再进行递归计算

public static int calculate2(int num){int[] arr = new int[num+1];return recurse(arr,num);}private static int recurse(int[] arr, int num) {if(num == 0 ){return 0;}if(num == 1){return 1;}if(arr[num] != 0){return arr[num];}arr[num] = recurse(arr,num-1) + recurse(arr,num-2);return arr[num];}
解法三:双指针迭代
基于去重递归优化,集合没有必要保存每一个下标值,只需保存前两位即可,向后遍历,得出N的值

public static int iterate(int num){if(num == 0 ){return 0;}if(num == 1){return 1;}int low = 0,high = 1;for(int i=2; i<= num; i++){int sum = low + high;low = high;high = sum;}return high;}
相关文章:
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
目录7 两数之和题目描述:解题思路与代码暴力解法:解法一:二分查找解法二:双指针2 斐波那契数列题目描述:解题思路与代码解法一&…...
测试1:测试相关概念
1.测试相关概念 1.1.测试概念 1.1.1.需求 符合正式文档规定的条件和权能,包括用户需求和软件需求 它们之间的的转换是:沟通 用户需求和软件需求的区别: 能否指导开发人员开发,测试人员编写测试用例 1.1.2.缺陷Bug 与正确的…...
2.19 索引和事务
一.联合查询面试问题:聚合查询与联合查询的区别聚合查询是行与行之间的数据加工聚合函数 :count,sum,avg...group by 进行分组,指定列的值,相同的记录合并到同一个组,每个组又可以分别进行聚合查询分组还可以指定条件筛选,如果分组之前指定条件 用where,如果对分组之后指定条件…...
算法导论【摊还分析】—聚合分析、核算法、势能法
算法导论【摊还分析】—聚合分析、核算法、势能法聚合分析核算法势能法假定我们对一个数据结构执行一个由 n 个操作组成的操作序列,当 i 严格为 2 的幂时,第 i 个操作的代价为 i,否则代价为 1 聚合分析 总共有n个操作,1,2,4.....…...
【LeetCode】剑指 Offer 08. 二叉树的下一个节点 p65 -- Java Version
题目链接:无题目链接,不知道为啥力扣上找不到这一题。 1. 题目介绍(08. 二叉树的下一个节点) 题目:给定一个二叉树和其中的一个节点,请找出中序遍历顺序的下一个节点并且返回。注意,树中的节点…...
Python 之 Pandas Series 数据结构
文章目录一、Series 结构二、数据结构 Series 创建1. 创建1.1 列表/数组作为数据源创建 Series1.2 字典作为数据源创建 Series1.3 通过标量创建2. 参数说明2.1 index 参数2.2 name 参数2.3 copy 参数三、Series 的索引/切片1. 下标索引2. 标签索引3. 切片四、Series 数据结构的…...
【java基础】Java常用类———包装类
包装类 wrapper 装箱与拆箱 装箱:基本类型->包装类; 拆箱: 包装类->基本类型 public class Integer01 {public static void main(String[] args) {//演示int <--> Integer 的装箱和拆箱//jdk5前是手动装箱和拆箱//手动装箱 in…...
linux shell 入门学习笔记3 shebang
shebang 计算机程序中,shebang指的是出现在文本文件的第一行前两个字符#! 在Unix系统中,程序会分析shebang后面的内容,作为解释器的指令,例如 以#!/bin/sh 开头的文件,程序在执行的时候会调用/bin/sh,也就…...
写作小课堂:简历模版【A4纸正反两面】(20230219)
文章目录 I 联系方式II 个人信息III 求职意向IV 工作经验2018年-11月-至今全城淘信息技术服务有限公司2017年07月-2018年-11月湖南微流网络科技有限公司2014年06月-2017年07月湖南高阳通联信息技术有限公司V 项目经验2018年11月-至今全城淘淘管家2017年10月-2018年11月ASO(机刷…...
一文搞懂 DevOps
前言 DevOps作为一个热门的概念,近年来频频出现在各大技术社区和媒体的文章中,备受行业大咖的追捧,也吸引了很多吃瓜群众的围观。 那么,DevOps是什么呢? 有人说它是一种方法,也有人说它是一种工具&#…...
深入讲解Kubernetes架构-租约
分布式系统通常需要租约(Lease);租约提供了一种机制来锁定共享资源并协调集合成员之间的活动。 在 Kubernetes 中,租约概念表示为 coordination.k8s.io API 组中的 Lease 对象, 常用于类似节点心跳和组件级领导者选举等…...
微信小程序学习第11天——Vant Weapp组件库、API Promise化、全局数据共享Mobx、分包
目录一、小程序对npm 的限制二、使用Vant Weapp组件库1、安装组件2、使用组件3、定制全局样式三、API Promise化1、下载miniprogram-api-promise2、引入3、使用四、全局数据共享五、分包1、分包概念2、使用分包3、独立分包4、分包预下载一、小程序对npm 的限制 在小程序中使用…...
Python3-基本数据类型
Python3 基本数据类型 Python 中的变量不需要声明。每个变量在使用前都必须赋值,变量赋值以后该变量才会被创建。 在 Python 中,变量就是变量,它没有类型,我们所说的"类型"是变量所指的内存中对象的类型。 等号&…...
RPA落地指南:什么是RPA
什么是RPA RPA在企业中起什么作用并扮演什么角色呢?想要充分了解RPA,我们需要知道RPA的相关概念、特点、功能以及能解决的问题。接下来对这些内容进行详细介绍。 1.1 RPA的3个核心概念 RPA的中文译名是“机器人流程自动化”,顾名思义&…...
跨域问题的三种解决办法
我们平时对于前后端联调的项目,以下的错误是经常常见的,我们查看浏览器报错: Access to XMLHttpRequest at http://localhost:63110/system/dictionary/all fromorigin http://localhost:8601 has been blocked by CORS policy: No Access…...
c++提高篇——string容器
一、string基本概念 string是C风格的字符串,而string本质上是一个类。 与c语言不同,string是一个类,类内部封装了char*,管理这个字符串,是一个char型的容器。在根本上与c语言字符串是一致的。 在string类内部封装了很…...
[软件工程导论(第六版)]第6章 详细设计(复习笔记)
文章目录6.1 结构程序设计6.2 人机界面设计6.3 过程设计的工具6.3.1 程序流程图(程序框图)6.3.2 盒图(N-S图)6.3.3 PAD图(问题分析图)6.3.4 判定表6.3.5 判断树6.3.6 过程设计语言6.4 面向数据结构的设计方…...
RabbitMQ核心内容:实战教程(java)
文章目录一、安装二、入门1.分类2.核心概念3.工作原理4.六大模式三、模式一:"Hello World!"1.依赖2.生产者代码3.消费者代码四、模式二:Work Queues1.工作原理2.工具类代码:连接工厂3.消费者代码4.生产者代码5.分发策略不公平分发预…...
RK356x U-Boot研究所(命令篇)3.7 pci与nvme命令的用法
平台U-Boot 版本Linux SDK 版本RK356x2017.09v1.2.3文章目录 一、设备树与config配置二、pci命令的定义三、nvme命令的定义四、pci与nvme命令的用法3.1 pci总线扫描3.2 nvme设备信息3.3 nvme设备读写一、设备树与config配置 RK3568支持PCIe接口,例如ROC-RK3568-PC: 原理图如…...
微信头像昵称获取能力的变化导致了我半年没更新小程序
背景 2022年9月份,微信更改了获取头像昵称的规则,回收了原有 wx.getUserProfile 中的部分能力,为了减小对【微点记账】小程序的影响,长达半年未做任何更新,今天为了增加这个聊天机器人的功能,不得不重新查…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
