当前位置: 首页 > news >正文

LeetCode初级算法题:两数之和+斐波拉契数列多种java解法

目录

  • 7 两数之和
    • 题目描述:
    • 解题思路与代码
      • 暴力解法:
      • 解法一:二分查找
      • 解法二:双指针
  • 2 斐波那契数列
    • 题目描述:
    • 解题思路与代码![请添加图片描述](https://img-blog.csdnimg.cn/d06a95d7989b4794bd7f5f02fbd6f87e.png)
      • 解法一:暴力递归
      • 解法二:去重递归
      • 解法三:双指针迭代

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 两数之和题目描述&#xff1a;解题思路与代码暴力解法&#xff1a;解法一&#xff1a;二分查找解法二&#xff1a;双指针2 斐波那契数列题目描述&#xff1a;解题思路与代码![请添加图片描述](https://img-blog.csdnimg.cn/d06a95d7989b4794bd7f5f02fbd6f87e.png)解法一&…...

测试1:测试相关概念

1.测试相关概念 1.1.测试概念 1.1.1.需求 符合正式文档规定的条件和权能&#xff0c;包括用户需求和软件需求 它们之间的的转换是&#xff1a;沟通 用户需求和软件需求的区别&#xff1a; 能否指导开发人员开发&#xff0c;测试人员编写测试用例 1.1.2.缺陷Bug 与正确的…...

2.19 索引和事务

一.联合查询面试问题:聚合查询与联合查询的区别聚合查询是行与行之间的数据加工聚合函数 :count,sum,avg...group by 进行分组,指定列的值,相同的记录合并到同一个组,每个组又可以分别进行聚合查询分组还可以指定条件筛选,如果分组之前指定条件 用where,如果对分组之后指定条件…...

算法导论【摊还分析】—聚合分析、核算法、势能法

算法导论【摊还分析】—聚合分析、核算法、势能法聚合分析核算法势能法假定我们对一个数据结构执行一个由 n 个操作组成的操作序列&#xff0c;当 i 严格为 2 的幂时&#xff0c;第 i 个操作的代价为 i&#xff0c;否则代价为 1 聚合分析 总共有n个操作&#xff0c;1,2,4.....…...

【LeetCode】剑指 Offer 08. 二叉树的下一个节点 p65 -- Java Version

题目链接&#xff1a;无题目链接&#xff0c;不知道为啥力扣上找不到这一题。 1. 题目介绍&#xff08;08. 二叉树的下一个节点&#xff09; 题目&#xff1a;给定一个二叉树和其中的一个节点&#xff0c;请找出中序遍历顺序的下一个节点并且返回。注意&#xff0c;树中的节点…...

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 装箱与拆箱 装箱&#xff1a;基本类型->包装类&#xff1b; 拆箱&#xff1a; 包装类->基本类型 public class Integer01 {public static void main(String[] args) {//演示int <--> Integer 的装箱和拆箱//jdk5前是手动装箱和拆箱//手动装箱 in…...

linux shell 入门学习笔记3 shebang

shebang 计算机程序中&#xff0c;shebang指的是出现在文本文件的第一行前两个字符#! 在Unix系统中&#xff0c;程序会分析shebang后面的内容&#xff0c;作为解释器的指令&#xff0c;例如 以#!/bin/sh 开头的文件&#xff0c;程序在执行的时候会调用/bin/sh&#xff0c;也就…...

写作小课堂:简历模版【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作为一个热门的概念&#xff0c;近年来频频出现在各大技术社区和媒体的文章中&#xff0c;备受行业大咖的追捧&#xff0c;也吸引了很多吃瓜群众的围观。 那么&#xff0c;DevOps是什么呢&#xff1f; 有人说它是一种方法&#xff0c;也有人说它是一种工具&#…...

深入讲解Kubernetes架构-租约

分布式系统通常需要租约&#xff08;Lease&#xff09;&#xff1b;租约提供了一种机制来锁定共享资源并协调集合成员之间的活动。 在 Kubernetes 中&#xff0c;租约概念表示为 coordination.k8s.io API 组中的 Lease 对象&#xff0c; 常用于类似节点心跳和组件级领导者选举等…...

微信小程序学习第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 中的变量不需要声明。每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 在 Python 中&#xff0c;变量就是变量&#xff0c;它没有类型&#xff0c;我们所说的"类型"是变量所指的内存中对象的类型。 等号&…...

RPA落地指南:什么是RPA

什么是RPA RPA在企业中起什么作用并扮演什么角色呢&#xff1f;想要充分了解RPA&#xff0c;我们需要知道RPA的相关概念、特点、功能以及能解决的问题。接下来对这些内容进行详细介绍。 1.1 RPA的3个核心概念 RPA的中文译名是“机器人流程自动化”&#xff0c;顾名思义&…...

跨域问题的三种解决办法

我们平时对于前后端联调的项目&#xff0c;以下的错误是经常常见的&#xff0c;我们查看浏览器报错&#xff1a; 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风格的字符串&#xff0c;而string本质上是一个类。 与c语言不同&#xff0c;string是一个类&#xff0c;类内部封装了char*&#xff0c;管理这个字符串&#xff0c;是一个char型的容器。在根本上与c语言字符串是一致的。 在string类内部封装了很…...

[软件工程导论(第六版)]第6章 详细设计(复习笔记)

文章目录6.1 结构程序设计6.2 人机界面设计6.3 过程设计的工具6.3.1 程序流程图&#xff08;程序框图&#xff09;6.3.2 盒图&#xff08;N-S图&#xff09;6.3.3 PAD图&#xff08;问题分析图&#xff09;6.3.4 判定表6.3.5 判断树6.3.6 过程设计语言6.4 面向数据结构的设计方…...

RabbitMQ核心内容:实战教程(java)

文章目录一、安装二、入门1.分类2.核心概念3.工作原理4.六大模式三、模式一&#xff1a;"Hello World!"1.依赖2.生产者代码3.消费者代码四、模式二&#xff1a;Work Queues1.工作原理2.工具类代码&#xff1a;连接工厂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月份&#xff0c;微信更改了获取头像昵称的规则&#xff0c;回收了原有 wx.getUserProfile 中的部分能力&#xff0c;为了减小对【微点记账】小程序的影响&#xff0c;长达半年未做任何更新&#xff0c;今天为了增加这个聊天机器人的功能&#xff0c;不得不重新查…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...