2024.6.28刷题记录
目录
一、13. 罗马数字转整数
贪心
二、16. 最接近的三数之和
排序+指针
三、17. 电话号码的字母组合
dfs(深度优先搜索)
四、19. 删除链表的倒数第 N 个结点
1.模拟
2.前后同步指针
五、20. 有效的括号
栈
六、21. 合并两个有序链表
1.递归
2.迭代
一、13. 罗马数字转整数
贪心
class Solution:dict = {'I': 1, 'V': 5,'X': 10, 'L': 50,'C': 100, 'D': 500,'M': 1000}def romanToInt(self, s: str) -> int:# 贪心,若前面小于后面就相减n = len(s)ans = 0for i in range(n):if i == n - 1 or Solution.dict[s[i]] >= Solution.dict[s[i + 1]]:ans += Solution.dict[s[i]]else:ans -= Solution.dict[s[i]]return ans
二、16. 最接近的三数之和
排序+指针
又重新写了一遍这道题
class Solution:def threeSumClosest(self, nums: List[int], target: int):# 排序+ 指针nums.sort()if sum(nums[-3:]) <= target:return sum(nums[-3:])if sum(nums[:3]) >= target:return sum(nums[:3])ans1, ans2 = -math.inf, math.inf # 左右区域n = len(nums)for i in range(n - 2):x = nums[i]if x + nums[-2] + nums[-1] <= ans1 or \x + nums[i + 1] + nums[i + 2] >= ans2:# 剪枝# 最大值小于等于左端点# 最小值大于等于右端点continuej, k = i + 1, n - 1while j < k:cur = x + nums[j] + nums[k]if cur == target:return targetelif cur > target:ans2 = min(ans2, cur)k -= 1else:ans1 = max(ans1, cur)j += 1return ans1 if target - ans1 < ans2 - target else ans2
三、17. 电话号码的字母组合
dfs(深度优先搜索)
来自灵神题解(. - 力扣(LeetCode)),完全没想到。
MAPPING = "", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
# 元组class Solution:def letterCombinations(self, digits: str) -> List[str]:# dfsif not digits:return []n = len(digits)ans = []path = ['' for _ in range(n)] # path长度固定为ndef dfs(i: int) -> None:nonlocal nif i == n:# 搜索到末尾ans.append(''.join(path))returnfor c in MAPPING[int(digits[i])]:path[i] = c # 覆盖dfs(i + 1)dfs(0)return ans
四、19. 删除链表的倒数第 N 个结点
1.模拟
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:# 模拟# 先求长度l = 0cur = headwhile cur:l += 1cur = cur.nextdummy = ListNode(next = head) # 哨兵节点l -= n # 指到指定节点的前一个节点cur = dummywhile l > 0:cur = cur.nextl -= 1cur.next = cur.next.next # 更改连接return dummy.next
2.前后同步指针
来自灵神题解(. - 力扣(LeetCode))。很妙!
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:# 前后同步指针left = right = dummy = ListNode(next = head)for _ in range(n):# 右指针先走n位right = right.nextwhile right.next:# 走到指定节点的前一个节点,这里是right.nextleft = left.nextright = right.nextleft.next = left.next.nextreturn dummy.next
五、20. 有效的括号
栈
class Solution:def isValid(self, s: str) -> bool:# 栈st = []hash = {')': '(', '}': '{', ']': '['}for c in s:if c in hash:# 右括号if not st or hash[c] != st[-1]:return Falsest.pop()else:# 左括号st.append(c)return not st # 为空即对
六、21. 合并两个有序链表
1.递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 递归if not list1 or not list2:return list1 if list1 else list2if list1.val < list2.val:list1.next = self.mergeTwoLists(list1.next, list2)return list1else:list2.next = self.mergeTwoLists(list1, list2.next)return list2
2.迭代
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:# 迭代dummy = ListNode()cur = dummywhile list1 and list2:if list1.val <= list2.val:cur.next = list1cur = cur.nextlist1 = list1.nextelse:cur.next = list2cur = cur.nextlist2 = list2.nextcur.next = list1 if list1 else list2return dummy.next
完
感谢你看到这里!一起加油吧!
相关文章:
2024.6.28刷题记录
目录 一、13. 罗马数字转整数 贪心 二、16. 最接近的三数之和 排序指针 三、17. 电话号码的字母组合 dfs(深度优先搜索) 四、19. 删除链表的倒数第 N 个结点 1.模拟 2.前后同步指针 五、20. 有效的括号 栈 六、21. 合并两个有序链表 1.递归 …...
柔性数组(flexible array)
柔性数组从C99开始支持使用 1.柔性数组的概念 概念: 结构体中,结构体最后一个元素允许是未知大小的数组,这就叫[柔性数组]的成员 struct S {int n;char arr[]; //数组大小未知(柔性数组成员) }; 柔性数组的特点: 结构体中柔性…...
服务器配置路由
translator 在Linux系统中,通过ip route add命令添加的路由规则通常不会永久保存,它们只会在当前会话中生效。当系统重新启动后,这些临时添加的路由规则会丢失。 要求在开关机之后仍然保留这条路由,需要将路由规则永久保存。在大多…...
老生常谈问题之什么是缓存穿透、缓存击穿、缓存雪崩?举个例子你就彻底懂了!!
老生常谈问题之什么是缓存穿透、缓存击穿、缓存雪崩?举个例子你就彻底懂了!! 缓存穿透发生场景解决方案 缓存击穿解决方案 缓存雪崩发生场景解决方案 总结三者区分三者原因三者解决方案 想象一下,你开了一家便利店,店里…...
[code snippet] 生成随机大文件
[code snippet] 生成随机大文件 一个无聊的测试代码,因为要测试大文件的网络传输,就写了一个随机大文件生成脚本,做个备份。 基本上都是 GPT 生成的,哈哈。 C# 代码 namespace ConsolePlayground;internal class BigFileGenera…...
计算机网路面试HTTP篇三
HTTPS RSA 握手解析 我前面讲,简单给大家介绍了的 HTTPS 握手过程,但是还不够细! 只讲了比较基础的部分,所以这次我们再来深入一下 HTTPS,用实战抓包的方式,带大家再来窥探一次 HTTPS。 对于还不知道对称…...
如何不改变 PostgreSQL 列类型#PG培训
开发应用程序并在其背后操作数据库集群时,会遇到一个意想不到的问题是实践与理论、开发环境与生产之间的差异。这种不匹配的一个完美例子就是更改列类型。 #PG考试#postgresql培训#postgresql考试#postgresql认证 关于如何在 PostgreSQL(以及其他符合 SQ…...
RocketMQ快速入门:事务消息原理及实现(十)
目录 0. 引言1. 原理2. 事务消息的实现2.1 java client实现(适用于spring框架)2.2 springboot实现 3. 总结 0. 引言 rocketmq 的一大特性就是支持事务性消息,这在诸多场景中有所应用。在之前的文章中我们已经讲解过事务消息的使用࿰…...
Kotlin设计模式:深入理解桥接模式
Kotlin设计模式:深入理解桥接模式 在软件开发中,随着系统需求的不断增长和变化,类的职责可能会变得越来越复杂,导致代码难以维护和扩展。桥接模式(Bridge Pattern)是一种结构型设计模式,它通过…...
常用MQ消息中间件Kafka、ZeroMQ和RabbitMQ对比及RabbitMQ详解
1、概述 在现代的分布式系统和实时数据处理领域,消息中间件扮演着关键的角色,用于解决应用程序之间的通信和数据传递的挑战。在众多的消息中间件解决方案中,Kafka、ZeroMQ和RabbitMQ 是备受关注和广泛应用的代表性系统。它们各自具有独特的特…...
【UE5.3】笔记6-第一个简单小游戏
打砖块小游戏: 1、制造一面砖块组成的墙 在关卡中放置一个cube,放这地面上,将其转换成蓝图类,改名BP_Cube,更换砖块的贴图,按住alt键进行拷贝,堆出一面墙,复制出来的会很多,全选移动…...
LeetCode---402周赛
题目列表 3184. 构成整天的下标对数目 I 3185. 构成整天的下标对数目 II 3186. 施咒的最大总伤害 3187. 数组中的峰值 一、构成整天的下标对数目 I & II 可以直接二重for循环暴力遍历出所有的下标对,然后统计符合条件的下标对数目返回。代码如下 class So…...
循环冗余校验
循环冗余校验(Cyclic Redundancy Check,简称CRC)是一种广泛使用的错误检测编码技术,用于检测数据在传输或存储过程中是否发生错误。CRC通过在数据后面添加一个校验值(通常称为CRC码或CRC校验和)来实现错误检…...
resample sensor
resample sensor 的一个问题。 背景: 项目要求,发送多个数据到 sensor-hal 上去,发现无论怎样,在 sensor-hal 上都 只有一个数据。 resample sensor 是重新采样,这个怎么理解的,我的理解是: 假设 sensor 采…...
【Linux】多线程的相关知识点
一、线程安全 1.1 可重入 VS 线程安全 1.1.1 概念 线程安全:多个线程并发执行同一段代码时,不会出现不同的结果。常见对全局变量或者静态变量进行操作,并且没有锁的保护的情况下,会出现问题。重入:同一个函数被不同…...
Java反射详解
Java反射 一.什么是反射 我们使用的一些像框架,tomcat,或者一些其他的组件(jackson 对象–>json)。他们可以做到给他什么类名,就可以创建给定类的对象,并调用该对象的方法和属性。这是如何做到的? 当他们加载我们…...
Spring Boot与Apache Kafka集成的深度指南
Spring Boot与Apache Kafka集成的深度指南 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在现代分布式系统中,消息队列的作用愈发重要࿰…...
甄选版“论软件系统架构评估”,软考高级论文,系统架构设计师论文
论文真题 对于软件系统,尤其是大规模的复杂软件系统来说,软件的系统架构对于确保最终系统的质量具有十分重要的意义,不恰当的系统架构将给项目开发带来高昂的代价和难以避免的灾难。对一个系统架构进行评估,是为了:分析现有架构存在的潜在风险,检验设计中提出的质量需求,…...
uniapp开发企业微信内部应用
最近一直忙着开发项目,终于1.0版本开发完成,抽时间自己总结下在项目开发中遇到的技术点。此次项目属于自研产品,公司扩展业务,需要在企业微信中开发内部应用。因为工作中使用的是钉钉,很少使用企业微信,对于…...
0122__linux之eventfd理解
linux之eventfd理解-CSDN博客 Linux fd 系列 — eventfd 是什么?-CSDN博客...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
