【LeetCode】挑战100天 Day10(热题+面试经典150题)

【LeetCode】挑战100天 Day10(热题+面试经典150题)

  • 一、LeetCode介绍
  • 二、LeetCode 热题 HOT 100-12
    • 2.1 题目
    • 2.2 题解
  • 三、面试经典 150 题-12
    • 3.1 题目
    • 3.2 题解

一、LeetCode介绍

在这里插入图片描述
LeetCode是一个在线编程网站,提供各种算法和数据结构的题目,面向程序员、计算机科学专业学生和技术爱好者等人群,旨在帮助他们提高算法和编程技能。LeetCode上的问题通常来自各种技术公司的面试题目,因此它也是程序员面试准备的重要资源之一。

LeetCode上的问题涵盖了各种难度级别,从入门级到专家级都有不同难度的题目可供练习。用户可以选择使用不同的编程语言提交答案,LeetCode能够对结果进行评估并返回测试结果。

除了题目外,LeetCode还提供了讨论区、排行榜等社区功能,用户可以在这里交流学习心得、解决疑难问题,并与其他用户比较自己的做题成绩。

挑战100天 AI In LeetCode是基于LeetCode题库,借助AI的能力进行解题、并学习其解题过程。

二、LeetCode 热题 HOT 100-12

2.1 题目

整数转罗马数字

罗马数字包含以下七种字符: IVXLCDM。字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如, 罗马数字 2 写做 II ,即为两个并列的 112 写做 XII ,即为 X + II27 写做  XXVII, 即为 XX + V + II 。通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:I 可以放在 V (5)X (10) 的左边,来表示 49X 可以放在 L (50)C (100) 的左边,来表示 4090C 可以放在 D (500)M (1000) 的左边,来表示 400900。
给你一个整数,将其转为罗马数字。示例 1:输入: num = 3
输出: "III"
示例 2:输入: num = 4
输出: "IV"
示例 3:输入: num = 9
输出: "IX"
示例 4:输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.提示:1 <= num <= 3999

2.2 题解

解题思路:

  1. 构建两个数组,一个存储数值,一个存储对应的罗马字符。
  2. 遍历数值数组,依次比较当前值与 num 的大小关系,如果当前值小于等于 num,则将对应的罗马字符追加到结果中,并将 num 减去当前值;否则继续遍历下一个数值。
  3. 重复上述过程直到 num 变为 0。

这种解法的关键在于利用贪心算法,每次尽量选择最大的符号作为组合,直到 num 变为 0。

public String intToRoman(int num) {int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};StringBuilder roman = new StringBuilder();int i = 0;while (num > 0) {if (num - values[i] >= 0) {roman.append(symbols[i]);num -= values[i];} else {i++;}}return roman.toString();}

在这里插入图片描述

三、面试经典 150 题-12

数组 / 字符串

3.1 题目

O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类:RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。
bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 falseint getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。示例:输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ,表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中,所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。提示:-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时,数据结构中 至少存在一个 元素。

3.2 题解

解题思路:

  1. 使用一个 List 存储集合中的元素,使用一个 Map 来存储元素到索引的映射。
  2. 插入元素时,判断 Map 中是否已存在该元素,如果不存在,则将元素插入到 List 的末尾,并在 Map 中记录该元素对应的索引。
  3. 删除元素时,先判断 Map 中是否存在该元素,如果存在,将要删除的元素与 List 最后一个元素交换位置,然后删除 List 的最后一个元素,并更新 Map 中最后一个元素的索引,最后移除 Map 中要删除的元素。
  4. 获取随机元素时,生成一个随机索引,然后返回 List 中对应索引的元素。

这种实现方式能够满足平均时间复杂度为 O(1) 的要求,因为 List 和 Map 的插入、删除和查找操作的平均时间复杂度都为 O(1)。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;public class RandomizedSet {private List<Integer> list;private Map<Integer, Integer> map;private Random random;public RandomizedSet() {list = new ArrayList<>();map = new HashMap<>();random = new Random();}public boolean insert(int val) {if (map.containsKey(val)) {return false;}list.add(val);map.put(val, list.size() - 1);return true;}public boolean remove(int val) {if (!map.containsKey(val)) {return false;}int index = map.get(val);int lastVal = list.get(list.size() - 1);list.set(index, lastVal);list.remove(list.size() - 1);map.put(lastVal, index);map.remove(val);return true;}public int getRandom() {int randomIndex = random.nextInt(list.size());return list.get(randomIndex);}
}

在这里插入图片描述

至此,挑战100天 AI In LeetCode Day10(热题+面试经典150题)完成,后续会持续调整;查阅过程中若遇到问题欢迎留言或私信交流。

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

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

相关文章

kubeadm部署k8s及高可用

目录 CNI 网络组件 1、flannel的功能 2、flannel的三种模式 3、flannel的UDP模式工作原理 4、flannel的VXLAN模式工作原理 5、Calico主要组成部分 6、calico的IPIP模式工作原理 7、calico的BGP模式工作原理 8、flannel 和 calico 的区别 Kubeadm部署k8s及高可用 1、…

Python读取csv文件并绘制曲线

前言 有时候我们的数据保存在csv文件中&#xff0c;但是想要更加直观的看出数据的好坏&#xff0c;最好利用matplotlib来画出曲线图 数据准备 我的数据格式如下&#xff1a; 在画图时&#xff0c;我需要把第一行去掉 # 去除第一个元素 xdata xdata.drop(xdata.index[0])…

Longhorn跨AZ实现存储高可用

Longhorn跨AZ实现存储高可用 longhorn基础组件功能及其作用这里就不做介绍了 方案一 Longhorn跨AZ的高可用的就是一个PVC的replicas 均匀打散的不同的AZ区域之间&#xff0c;这样当某个AZ挂掉后&#xff0c;engine会立即使用另外一个数据副本&#xff0c;并重建这个副本&…

Java TreeMap

TreeMap 是一个基于 key 有序的 key value 散列表。 map 根据其键的自然顺序排序&#xff0c;或者根据 map 创建时提供的 Comparator 排序不是线程安全的key 不可以存入null底层是基于红黑树实现的 TreeMap 的类结构图&#xff1a; 实现了 NavigableMap 接口&#xff0c;Na…

MATLAB的编程与应用,匿名函数、嵌套函数、蒙特卡洛法的掌握与使用

目录 1.匿名函数 1.1.匿名函数的定义与分类 1.2.匿名函数在积分和优化中应用 2.嵌套函数 2.1.嵌套函数的定义与分类 2.2.嵌套函数彼此调用关系 2.3.嵌套函数在积分和微分中应用 3.微分和积分 4.蒙特卡洛法 4.1.圆周率的模拟 4.2.计算N重积分&#xff08;均匀分布&am…

20道高频JavaScript面试题快问快答

※其他的快问快答&#xff0c;看这里&#xff01; 10道高频Qiankun微前端面试题快问快答 10道高频webpack面试题快问快答 20道高频CSS面试题快问快答 20道高频JavaScript面试题快问快答 30道高频Vue面试题快问快答 面试中的快问快答 快问快答的情景在面试中非常常见。 在面试过…

竞赛选题 深度学习疲劳驾驶检测 opencv python

文章目录 0 前言1 课题背景2 实现目标3 当前市面上疲劳驾驶检测的方法4 相关数据集5 基于头部姿态的驾驶疲劳检测5.1 如何确定疲劳状态5.2 算法步骤5.3 打瞌睡判断 6 基于CNN与SVM的疲劳检测方法6.1 网络结构6.2 疲劳图像分类训练6.3 训练结果 7 最后 0 前言 &#x1f525; 优…

idea 2023 设置启动参数、单元测试启动参数

找到上方的editconfigration&#xff0c; 如下图&#xff0c;如果想在启动类上加&#xff0c;就选择springboot&#xff0c;如果想在单元测试加&#xff0c;就选择junit 在参数栏设置参数&#xff0c;多个参数以空格隔开 如果没有这一栏&#xff0c;就选择就可以了。 然后&…

数字马力笔试面试复盘

笔试——10月9日19&#xff1a;00 单选&#xff1a;30题 16.如何获取AJAX 请求的响应状态码? A通过AJAX对象的 statusCode 属性获取 B通过AJAX对象的responseText 属性获取C通过AJAX对象的status 属性获取 D通过AJAX对象的responseCode属性获取 答案&#xff1a;可以通过AJAX…

回收站清空了怎么恢复?数据恢复的 6 种方法

众所周知&#xff0c;计算机中的回收站是一个存储空间&#xff0c;用于存储从计算机系统中删除的所有文件、文件夹或数据。它是大多数计算机系统&#xff08;包括Windows、Mac等&#xff09;上的必备功能。当从计算机中删除文件或文件夹时&#xff0c;它会在回收站中存储指定的…

京东数据分析:2023年Q3户外鞋服市场分析报告(冲锋衣行业销售数据分析)

从露营、骑行、徒步、桨板、垂钓、飞盘、滑雪到如今的city walk&#xff0c;近两年户外运动已经成为了年轻人新的生活方式。户外运动的爆发也刺激了人们对于鞋服在穿搭、场景化、专业性功能等方向的需求&#xff0c;户外鞋服市场迎来增长。 而全国性的降温则带给目前的户外鞋服…

七个优秀微服务跟踪工具

随着微服务架构复杂性的增加&#xff0c;在问题出现时确定问题的根本原因变得更具挑战性。日志和指标为我们提供了有用的信息&#xff0c;但并不能提供系统的完整概况。这就是跟踪的用武之地。通过跟踪&#xff0c;开发人员可以监控微服务之间的请求进度&#xff0c;从而使他们…

关于Android Studio 同步Gradle失败的解决方案

&#xff08;1&#xff09;打开Android Studio的Settings找到Gradle的目录 &#xff08;2&#xff09;打开本地文件目录&#xff0c;找到对应的gradle版本&#xff0c;可以通过Index of /gradle/ 下载gradle压缩包。把目录中gradle-7.0.2-bin\一堆字符\ 下 的.lck 和.part文…

MATLAB中Arrow 属性说明

目录 颜色和样式 位置 Arrow 属性是箭头的外观和行为。 Arrow 属性控制 Arrow 对象的外观和行为。通过更改属性值&#xff0c;可以修改箭头的特定方面。使用圆点表示法查询和设置属性。 ar annotation("arrow"); c ar.Color; ar.Color "red"; 颜色和…

SpringCloudGateway--Sentinel限流、熔断降级

目录 一、概览 二、安装Sentinel 三、微服务整合sentinel 四、限流 1、流控模式 ①直接 ②关联 ③链路 2、流控效果 ①快速失败 ②Warm Up ③排队等待 五、熔断降级 1、慢调用比例 2、异常比例 3、异常数 一、概览 SpringCloudGateway是一个基于SpringBoot2.x的…

react 修改less文件后保存,内存溢出,项目崩溃问题解决

一、完整报错 一个很老的react项目&#xff0c;因为没有package-lock.json版本锁&#xff0c;导致拉下来的时候&#xff0c;安装的依赖版本冲突&#xff0c;好不容易启动起来&#xff0c;修改less文件后只要一保存&#xff0c;项目就会崩溃&#xff0c;需要重启&#xff0c;报…

一分钟秒懂人工智能对齐

文章目录 1.什么是人工智能对齐2.为什么要研究人工智能对齐3.人工智能对齐的常见方法 1.什么是人工智能对齐 人工智能对齐&#xff08;AI Alignment&#xff09;指让人工智能的行为符合人的意图和价值观。 人工智能系统可能会出现“不对齐”&#xff08;misalign&#xff09;的…

webpack提升构建速度

目录 配置优化减少 resolve 的解析把 loader 应用的文件范围缩小减少 plugin 的消耗选择合适的 devtool 使用工具thread-loaderDLLPlugin 流程优化拆分构建步骤拆分项目代码 版本更新总结 前端项目随着时间推移和业务发展&#xff0c;页面可能会越来越多&#xff0c;或者功能和…

Redis之哨兵模式

文章目录 前言什么是哨兵模式&#xff1f;1.概述2.作用3.测试4.优点5.缺点6.哨兵模式的全部配置 总结 前言 哨兵模式说白点就是&#xff1a;自动选举老大的模式。 什么是哨兵模式&#xff1f; 1.概述 主从切换技术的方法是∶当主服务器宕机后&#xff0c;需要手动把一台从服…