Leetcode HOT150

55. 跳跃游戏

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false

示例 1

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

思路:贪心思想。非常巧妙。一个变量代表我们最远跳到哪里。另一个变量。用来更新我们在这个路程中间实际上能跳转到的最大距离。比如用2,3,1,1,4举例。一开始最大跳转是到下边2的位置。那么我更新从1到2区间最大的位置。然后到index2的时候,我们就知道这一段区间,我们所能跳转的最大位置,然后更新维护这个变量。

class Solution {public boolean canJump(int[] nums) {int maxStep = 0;int end = 0;for(int i =0;i<nums.length;i++){maxStep = Math.max(maxStep,nums[i]+i);if(i==end){end = maxStep;if(end>=nums.length-1){return true;}}}return false;}
}

274 H指数

在这里插入图片描述

思路:

class Solution {public int hIndex(int[] citations) {int[] temp = new int[1000];for (int i = 0; i < citations.length; i++) {temp[citations[i]]++;}int sum = 0;for (int i = temp.length -1 ; i >= 0; i--) {sum += temp[i];if (sum >= i ) {return i ;}}return 1 ;    }}

134. 加油站

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。
贪心思想:gas[i]-cost[i]。最终gas-cost >0。如果小于0,说明肯定回不来。class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum = 0;int min = Integer.MAX_VALUE;int minIndex = -1;for(int i = 0; i < gas.length; i++){sum = sum + gas[i] - cost[i];if(sum < min && sum < 0){min = sum;minIndex = i;}}if(sum < 0) return -1;return (minIndex + 1 )%gas.length;}
} 

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求,给这些孩子分发糖果:

  • 每个孩子至少分配到 1 个糖果。
  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目

示例 1:

输入:ratings = [1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2:

输入:ratings = [1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这满足题面中的两个条件。
class Solution {public int candy(int[] ratings) {int n = ratings.length;int[] left = new int[n];int[] right = new int[n];left[0] = right[n-1] = 1;for(int i = 1; i < n; i++){if(ratings[i] > ratings[i - 1]){left[i] = left[i - 1] + 1;}else{left[i] = 1;}}int count = left[n - 1];for(int i = n - 2; i >= 0; i--) {if(ratings[i] > ratings[i + 1]){right[i] = right[i + 1] + 1;}else{right[i] = 1;}count += Math.max(left[i], right[i]);}return count;}
}

13. 罗马数字转整数

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。

总结;分析规律题目。观察IV这种。是下一个大于前一个。这个时候,减去当前这个就可以了。下一个是V,直接相加就可以了。

class Solution {Map<Character,Integer> map = new HashMap<>(){ {put('I',1);put('V', 5);put('X', 10);put('L', 50);put('C', 100);put('D', 500);put('M', 1000);}};public int romanToInt(String s) {int ans = 0;int len = s.length();for(int i =0;i<len;i++){int value = map.get(s.charAt(i));if(i<len-1 && value< map.get(s.charAt(i+1))){ans -= value;}else{ans += value;}}return ans;}
}

392. 判断子序列

给定字符串 st ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

进阶:

如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

致谢:

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1:

输入:s = "abc", t = "ahbgdc"
输出:true

示例 2:

输入:s = "axc", t = "ahbgdc"
输出:false

思路:双指针

class Solution {public boolean isSubsequence(String s, String t) {int left= 0,right= 0;while(left<s.length()&& right<t.length()){if(s.charAt(left)==(t.charAt(right))){left++;right++;}else{right++;}}return left== s.length();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/271445.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++ · 代码笔记3 · 引用

目录 前言011引用初探_引用与普通变量012引用初探_引用作为函数参数013引用初探_引用作为函数返回值014引用初探_引用返回局部函数造成的错误015引用初探_多级引用020引用与指针递增的区别030const与引用040使用const限定的函数形参引用 前言 本笔记所涉及到的编程环境与 《C …

怎么对接迅雷网盘拉新项目?迅雷网盘怎么做才有效果?

自网盘拉新项目上线以来&#xff0c;网盘市场日益繁荣&#xff0c;各大厂商纷纷进军这一领域。头条网盘、悟空网盘、UC网盘、迅雷网盘等都成为了各个推广达人喜欢的推广项目。其中&#xff0c;迅雷网盘凭借其稳定的服务、强大的功能和广泛的用户基础&#xff0c;成为了市场中的…

西门子S120故障报警F30003的解决办法总结

西门子S120故障报警F30003的解决办法总结 如下图所示&#xff0c;压机在回程时突然出现报警&#xff0c;故障代码为&#xff1a;30003&#xff0c; 如下图所示&#xff0c;查找手册可以看到F30003的报警分析为&#xff1a;直流母线欠压 如下图所示&#xff0c;本来想测量输入端…

三八妇女节智慧花店/自动售花机远程视频智能监控解决方案

一、项目背景 国家统计局发布的2023年中国经济年报显示&#xff0c;全年社会消费品零售总额471495亿元&#xff0c;比上年增长7.2%。我国无人零售整体发展迅速&#xff0c;2014年市场规模约为17亿元。无人零售自助终端设备市场规模超过500亿元&#xff0c;年均复合增长率超50%。…

如何阅读“计算机界三大神书”之一 ——《计算机程序的构造和解释》SICP

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; &#x1f40b; 希望大家多多支…

总结Redis的原理

一、为什么要使用Redis 缓解数据库访问压力mysql读请求进行磁盘I/O速度慢&#xff0c;给数据库加Redis缓存&#xff08;参考CPU缓存&#xff09;&#xff0c;将数据缓存在内存中&#xff0c;省略了I/O操作 二、Redis数据管理 2.1 redis数据的删除 定时删除惰性删除内存淘汰…

NHANES数据(复杂调查数据)亚组交互函数1.7(P for interaction)发布-纠正了目前的一个问题

大家好&#xff0c;有粉丝私信我说NHANES数据(复杂调查数据)亚组交互函数1.版本交互函数有点问题&#xff0c;我查看了一下&#xff0c;有个代码调用失效了。就是下面这个&#xff0c;本来我是这样调用数据的 ids<-match.call()$ids应该是由于R版本或者survy包升级后导致这…

基于sprinbgoot的火锅店管理系统(程序+数据库+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…

从新能源汽车行业自动驾驶技术去看AI的发展未来趋势

自动驾驶汽车关键技术主要包括环境感知、精准定位、决策与规划、控制与执行、高精地图与车联网V2X以及自动驾驶汽车测试与验证技术等。 &#x1f413; 自动驾驶技术 这是AI在汽车行业中应用最广泛的领域之一。自动驾驶技术利用AI算法和传感器来感知环境、识别障碍物&#xff0c…

mysql的语法总结2

命令&#xff1a; mysql -u 用户名 -p mysql登录 命令&#xff1a;create database u1 创建数据库u1 查询数据库 使用数据库u1 创建表department 查询表department ALTER TABLE 表名 操作类型&#xff1b; 操作类型可以有以下的操作&#xff1a; 添加列&#x…

[Redis]——Spring整合Redis(SpringDataRedis)

⭐准备工作&#xff1a; 确保Redis服务已启动idea开发环境 ⭐Redis整合步骤&#xff1a; 1.pom文件引入依赖 2.yml文件配置连接信息 3.修改Redis序列化方式 4.注入RedisTemplate 使用 小知识&#xff1a; Spring整合的Redis可以将Object对象自动序列化成字符串&#xff0…

【C++干货基地】面向对象核心概念 | 访问限定符 | 类域 | 实例化 | 类对象模型

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 引入 哈喽各位铁汁们好啊&#xff0c;我是博主鸽芷咕《C干货基地》是由我的襄阳家乡零食基地有感而发&#xff0c;不知道各位的…

【ETCD】简介安装常用操作---图文并茂详细讲解

目录 一 简介 1.1 etcd是什么 1.2. 特点 1.3. 使用场景 1.4 关键字 1.5 工作原理 二 安装 2.1 etcd安装前介绍 2.2 安装 2.3 启动 2.4 创建一个etcd服务 三 常用操作 一 简介 1.1 etcd是什么 etcd是CoreOS团队于2013年6月发起的开源项目&#xff0c;它的目标是构建…

【“双碳”目标】Acrel-2000Z分布式光伏发电监测系统解决方案

1 概述 “十四五”期间&#xff0c;随着“双碳”目标提出及逐步落实&#xff0c;本就呈现出较好发展势头的分布式光伏发展有望大幅提速。就“十四五”光伏发展规划&#xff0c;国家发改委能源研究所可再生能源发展中心副主任陶冶表示&#xff0c;“双碳”目标意味着国家产业结…

百度智能云发布专用向量数据库 VDB 1.0,全新设计内核开启性能狂飙

1 专用向量数据库应对未来业务挑战 向量数据库 向量检索 数据库 向量数据库大致可以分为 2 部分&#xff1a;向量数据的检索&#xff0c;以及向量数据的存储和管理。 向量数据库的性能&#xff0c;比如高 QPS、低延时等&#xff0c;使得业务能够更快的响应用户的查询请求…

神经网络(neural network)

在这一章中我们将进入深度学习算法&#xff0c;学习一些神经网络相关的知识&#xff0c;这些是有更加强大的作用&#xff0c;更加广泛的用途。 神经元和大脑(neurons and the brain): 我们对于我们的编程的进步主要来自我们对于大脑的研究&#xff0c;根据我们对于大脑的研究…

经典排序算法之希尔排序|c++代码实现||什么是希尔排序|如何代码实现

引言 排序算法c实现系列第4弹——希尔排序 算法介绍 希尔排序&#xff08;Shell Sort&#xff09;&#xff0c;也称递减增量排序算法&#xff0c;是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。该排序算法的基本思想是将原始序列分成若干个子序列&#xf…

Finetuning Large Language Models: Sharon Zhou

Finetuning Large Language Models 课程地址&#xff1a;https://www.deeplearning.ai/short-courses/finetuning-large-language-models/ 本文是学习笔记。 Goal&#xff1a; Learn the fundamentals of finetuning a large language model (LLM). Understand how finetu…

Scrapy与分布式开发(2.3):lxml+xpath基本指令和提取方法详解

lxmlxpath基本指令和提取方法详解 一、XPath简介 XPath&#xff0c;全称为XML Path Language&#xff0c;是一种在XML文档中查找信息的语言。它允许用户通过简单的路径表达式在XML文档中进行导航。XPath不仅适用于XML&#xff0c;还常用于处理HTML文档。 二、基本指令和提取…

pytorch续写tensorboard

模型训练到一半有 bug 停了&#xff0c;可以 resume 继续炼&#xff0c;本篇给出 pytorch 在 resume 训练时续写 tensorboard 的简例&#xff0c;参考 [1-3]&#xff0c;只要保证 writer 接收的 global step 是连着的就行。 Code import numpy as np from torch.utils.tensor…