【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题)完成,后续会持续调整;查阅过程中若遇到问题欢迎留言或私信交流。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

matplotlib 设置标签和图例

常用标签 xlabel&#xff1a;x轴标签名称。 ylabel&#xff1a;y轴标签名称。 title&#xff1a;图像标题。 设置x和y轴的刻度&#xff1a;xticks和yticks。 nums np.arange(0, 1.3, 0.01)# 设置标题 plt.title("title") # 设置横坐标信息 plt.xlabel("x-…

复杂度计算实例

1.常见时间复杂度计算举例 实例1 实例1基本操作执行了2N10次&#xff0c;通过推导大O阶方法知道&#xff0c;时间复杂度为 O(N) 实例2 实例2基本操作执行了MN次&#xff0c;有两个未知数M和N&#xff0c;时间复杂度为 O(NM) 实例3 实例3基本操作执行了100次&#xff0c;通过…

C++学习笔记(二):C++是如何运行的

C是如何运行的 include 预处理语句&#xff0c;在编译前就会被处理。 main函数 程序入口。 #include <iostream>int main() {std::cout << "Hello World!" << std::endl;std::cin.get();return 0; }Visual Studio 解决方案平台指的是编译的代码的…

探索微信小程序框架的精华——高质量的优秀选择

目录 引言&#xff1a; 1. 框架性能 2. 开发者工具支持 3. 文档和社区支持 4. 扩展能力 5. 使用率和稳定性 结语&#xff1a; 引言&#xff1a; 微信小程序作为一种轻量级、高效便捷的应用形式&#xff0c;已经在移动应用领域占据了重要地位。而其中&#xff0c;选择一个…

Nussbaumer Transform 以及 Amortized FHEW bootstrapping

参考文献&#xff1a; [Nuss80] Nussbaumer H. Fast polynomial transform methods for multidimensional DFTs[C]//ICASSP’80. IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 1980, 5: 235-237.[SV11] Smart N P, Vercauteren F. Full…

C++ 配合图形库实现画线效果

#include<stdio.h> #include <conio.h> #include<math.h> #include <graphics.h> // 引用图形库头文件 #define N 12 int List[N][N];void draw() {for (int i 0; i < N; i) {int x 200 * cos(2 * 3.14 * i / N);int y 200 * sin(2 * 3.1…

归并排序 merge Sort + 图解 + 递归 / 非递归

归并排序(merge sort)的主要思想是&#xff1a;将若干个有序序列逐步归并&#xff0c;最终归并为一个有序序列二路归并排序(2-way merge sort)是归并排序中最简单的排序方法 &#xff08;1&#xff09;二路归并排序的递归实现 // 二路归并排序的递归实现 void merge(vector&l…

Ocelot:.NET开源API网关提供路由管理、服务发现、鉴权限流等功能

随着微服务的兴起&#xff0c;API网关越来越常见。API网关是连接应用程序和用户之间的桥梁&#xff0c;就像一个交通指挥员&#xff0c;负责处理所有进出应用的数据和请求&#xff0c;确保安全、高效、有序地流通。 今天给大家推荐一个.NET开源API网关。 01 项目简介 Ocelot…

家居美学:将水离子壁炉融入你的现代装饰

当谈及家居装饰和壁炉选择时&#xff0c;水离子雾化壁炉是一个备受瞩目的话题。水离子雾化壁炉的美学价值&#xff0c;还为室内装饰带来全新的维度。它甚至能够激发室内装饰的灵感。 水离子雾化壁炉是现代美学的标志&#xff0c;融合了简洁、线条清晰的设计。这种壁炉常常采用不…

osg点云加载与渲染

目录 效果 laslib 关键代码 完整代码 效果 las点云读取使用了laslib这个库。 laslib 关键代码 {// 这里演示读取一个 .txt 点云文件const char* lasfile path.c_str();std::ifstream ifs;ifs.open(lasfile, std::ios::in | std::ios::binary);liblas::ReaderFactory f;libl…

给CAD中添加自定义菜单CUIX

本文以AutoCAD2020为例&#xff0c;介绍如何添加自定义菜单。 打开AutoCAD2020&#xff0c;在命令行执行CUI并回车&#xff0c;出现菜单 进入菜单编辑界面 点击传输&#xff0c;然后新建 在菜单上右键&#xff0c;添加自定义菜单 点击保存&#xff0c;即可存为cuix文件。之后…

if,switch语句

1.if public class IfDemo1 {public static void main(String[] args) {// 目标&#xff1a;掌握if分支三种形式的用法和执行流程// 需求&#xff1a;测量用户体温&#xff0c;发现高于37度就报警double temperature 38.5;if (temperature > 37){System.out.println("…

基于PHP的设云尘资讯网站设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

JUC包下面的四大天王+线程池部分知识

一)Semphore:限流器用我就对了 Java中信号量Semphore是把操作系统原生的信号量封装了一下&#xff0c;本质就是一个计数器&#xff0c;描述了 可用资源的个数&#xff0c;主要涉及到两个操作 如果计数器为0了&#xff0c;继续Р操作&#xff0c;就会出现阻塞等待的情况 P操作:申…

Ribbon 负载均衡原理和策略

目录 一、Ribbon 是什么 二、Ribbon 负载均衡原理 三、Ribbon 负载均衡策略 四、Ribbon的应用场景 一、Ribbon 是什么 Ribbon是一个开源的、基于HTTP和TCP的客户端负载均衡工具&#xff0c;它提供了一个简单的、基于配置的负载均衡策略&#xff0c;可以帮助开发人员更轻松…

苹果M3处理器跑分曝光,单核无敌!

10月底&#xff0c;苹果发布了全新的M3、M3 Pro、M3 Max芯片以及搭载M3系列芯片的3款新硬件&#xff0c;包括&#xff1a;新款24英寸iMac、新款14/16英寸MacBook Pro。 根据苹果官方介绍&#xff0c;M3系列芯片基于台积电3纳米工艺打造&#xff0c;采用全新图形处理器架构&…

【电工基础】

电工基础 11.1 简介1.2 电路作用1.3 电路模型1.4 电流定义1.5 电压定义1.6 电动势1.7 电阻元件1.7.1 电阻元件定义1.7.2 电阻原件的特性1.7.31.7.4 1.81.91.10 345 1 1.1 简介 电源外部&#xff0c;正电荷移动的方向是由电源正极向电源负极方向&#xff0c;负电荷移动的方向是…

C语言--输入10个数字,要求输出其中值最大的元素和该数字是第几个数

今天小编带大家了解一下什么是“打擂台”算法。 一.思路分析 可以定义一个数组arr&#xff0c;长度为10&#xff0c;用来存放10个数字&#xff0c;设计一个函数Max&#xff0c;用来求两个数中的较大值&#xff0c; 定义一个临时变量tmparr[0],保存临时最大的值&#xff0c;下标…

MySQL数据库基础和操作

&#x1f34e; 博客主页&#xff1a;&#x1f319;披星戴月的贾维斯 &#x1f34e; 欢迎关注&#xff1a;&#x1f44d;点赞&#x1f343;收藏&#x1f525;留言 &#x1f347;系列专栏&#xff1a;&#x1f319; MYSQL数据库 &#x1f319;请不要相信胜利就像山坡上的蒲公英一…

平衡树相关笔记

引入 二叉查找树 二叉查找树&#xff08;Binary Search Tree&#xff09;&#xff0c;又名二叉搜索树。满足以下性质&#xff1a; 对于非空的左子树&#xff0c;左子树点权值小于根节点。对于非空的右子树&#xff0c;左子树点权值大于根节点。二叉查找树的左右子树均是二叉…