leetcode每日刷题
Day18
Title45.jump(跳跃游戏 II)
解法一:动态规划
依然分三步走:
1.状态方程
2.dp[i]的意义
3.边界条件及初始值
优先思考第二个问题:
dp[i]表示到达i时需要的最少跳数
第一个问题:
dp[i+j]=min(dp[i]+1,dp[i+j])
为什么?我们要保证前面已经确定好为最小步数的情况下,让其从这个节点向下去跳,那么就需要去对比并更新到达该节点的最小距离,j的最远距离为x,即能从外层遍历节点出发所到达的最远距离。
第三个问题:
初始值全部为数组最大长度n,因为最远最远为一步一步跳,那么最远才需要跳n步,第一个值定位0,因为出发点就为索引号为0的地方。
class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""m=len(nums)dp=[m for _ in range(m)]dp[0]=0for i in range(m):x=nums[i]for j in range(x+1):if i+j<m :dp[i+j]=min(dp[i+j],dp[i]+1)return dp[m-1]
解法二:贪心算法
反向思考,如果要到达最后一个位置,那么最远最远从前面哪里起跳,如果可以从这个位置起跳,那么当前索引+x一定会超过position,此时怎么接着思考呢?更新position的位置为当前离最后一个位置最远的索引点,再依次类推,直到position被更新到索引0
class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""# 反向思考,如果要到达最后一个位置,那么最远最远从前面哪里起跳#如果可以从这个位置起跳,那么当前索引+x一定会超过position#此时怎么接着思考呢?更新position的位置为当前离最后一个位置最远的索引点,再依次类推,直到position被更新到索引0position=len(nums)-1step=0while position!=0:for i in range(len(nums)-1):if nums[i]+i>=position:position=istep+=1breakreturn step
解法三:正向检查的贪心
每一次尝试跳最远的距离,在所有当前可调节点当中进行比对,那个可以跳的最远就走那个
Title46.全排列
方法1:回溯法(方法非常好想出来,只是解题代码需要理清楚)
关于回溯法,进行以下步骤的思考
固定步骤
1.设置接受符合规则的结果列表,同时设置每轮迭代的存储列表
2.思考什么情况下向本轮结果集合当中添加新元素,同时思考迭代进行传递的值是什么
3.思考什么情况下将当前论的结果存入最终结果
class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""n = len(nums)res, path = [], []def dfs(i):if i == n:res.append(path[:])returnfor j in range(0,n):if nums[j] not in path:path.append(nums[j])dfs(i+1)path.pop()dfs(0)return res
Title47.全排列2 permuteUnique
方法1:回溯+剪枝
相较于上一个不可重复,这种可重复的更难
本题提供一种新的思路:当前轮的结果不需要一个新列表来存储,而是直接传递列表作为参数,可以避免回溯操作弹出时的复杂性。
剪枝操作的第二个条件难以理解:
本质上是为了避免同层中出现重复元素
- 初始状态:visited数组全为False,当前路径为空。
- 选择第一个元素:
- 可以选择索引0的1,或者索引1的1,或者索引2的2。
- 但是根据剪枝条件,当i=1时,nums[1] == nums[0],且visited[0]为False(因为还没有被访问过),所以会跳过i=1,不能选第二个1作为第一个元素。
- 因此,第一个元素只能是索引0的1或者索引2的2。
class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort() # 关键:排序使相同元素相邻res = []visited = [False] * len(nums) # 记录元素是否被使用过def backtrack(path):if len(path) == len(nums):res.append(path[:])returnfor i in range(len(nums)):# 剪枝条件:跳过已用元素 或 同一层中与前一个相同且未被使用的元素if visited[i] or (i > 0 and nums[i] == nums[i-1] and not visited[i-1]):continuevisited[i] = Truebacktrack(path + [nums[i]])visited[i] = Falsebacktrack([])return res
如果不采用第二个剪枝的条件,可以如下方式去写,但是时间消耗大幅度增加。
class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort() # 关键:排序使相同元素相邻res = []visited = [False] * len(nums) # 记录元素是否被使用过def backtrack(path):if len(path) == len(nums) and path[:] not in res:res.append(path[:])returnfor i in range(len(nums)):# 剪枝条件:跳过已用元素 或 同一层中与前一个相同且未被使用的元素if visited[i] :continuevisited[i] = Truebacktrack(path + [nums[i]])visited[i] = Falsebacktrack([])return res
Title48 rotate 旋转图像
方法一:用辅助数组旋转,最后再赋值回去,时空复杂度都挺高的,并且违背了题目不让使用额外数组的条件
class Solution(object):def rotate(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""n=len(matrix)n_matrix=[[0]*n for _ in range(n)]for i in range(n):for j in range(n):n_matrix[j][n-i-1]=matrix[i][j]matrix[:]=n_matrixreturn matrix
方法二:原地翻转
利用方法一的算法思想,如果我们直接原地更改matrix,那么会造成matrix[j][n-i-1]原本的值被覆盖,所以我们需要把该位置原本的值也保存起来去更改到他应该的位置,旋转90读,对应四个元素一次性直接修改到指定位置即可。关于i和j的取值,官方题解给的图非常清晰的解释了为什么
官方题解
class Solution:def rotate(self, matrix: List[List[int]]) -> None:n = len(matrix)for i in range(n // 2):for j in range((n + 1) // 2):matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \= matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]
Title49 字符异位词
方法一:排序(没想出来,下次再碰到肯定可以解决)
sorted后生成对应的字符串如果是异位词是唯一的,那么可以当做键。
class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""mp = {} for st in strs:key = ''.join(sorted(st))# 如果键不存在,手动初始化为空列表if key not in mp:mp[key] = []# 添加当前字符串到对应的列表中mp[key].append(st)return list(mp.values())
相关文章:
leetcode每日刷题
Day18 Title45.jump(跳跃游戏 II) 解法一:动态规划 依然分三步走: 1.状态方程 2.dp[i]的意义 3.边界条件及初始值 优先思考第二个问题: dp[i]表示到达i时需要的最少跳数 第一个问题: dp[ij]min(dp[i]1,dp[ij]) 为什么&am…...
Ubuntu安装Nginx
Ubuntu安装Nginx 由于 Ubuntu 的 apt 命令内置了 nginx 源,因此不用配置 apt 就可以直接下载安装: apt install nginx -y查看 nginx 是否启动: ps -ef |grep nginx如果没有启动则需要手动启动: nginx1. 配置Nginx 使用浏览器…...
Hadoop的序列化
(一)什么是序列化与反序列化 序列化就是把内存中的对象,转换成字节序列(或其他数据传输协议)以便于存储到磁盘(持久化)和网络传输。 反序列化就是将收到字节序列(或其他数据传输协议…...
拼多多商品详情接口爬虫实战指南
一、引言 在电商运营和数据分析中,获取商品详情数据是至关重要的一步。拼多多作为国内知名的社交电商平台,提供了丰富的商品详情接口,允许开发者通过API获取商品的详细信息。本文将详细介绍如何通过爬虫技术结合拼多多商品详情接口ÿ…...
python网络爬虫
一、Python爬虫核心库 HTTP请求库 requests:简单易用的HTTP请求库,处理GET/POST请求。aiohttp:异步HTTP客户端,适合高并发场景。 HTML/XML解析库 BeautifulSoup:基于DOM树的解析库,支持多种解析器…...
java线程安全-单例模式-线程通信
首先看看单例模式的写法 首先我们先来回顾一下饿汉式单例模式: class Singleton{private static Singleton singletonnew Singleton();private Singleton(){}public static Singleton getInstrance(){return singleton;} } public class Test{public static void …...
ASP.NET中将 PasswordHasher 使用的 PBKDF2 算法替换为更现代的 Scrypt 或 Argon2 算法
相关博文: .Net实现SCrypt Hash加密_scrypt加密-CSDN博客 密钥派生算法介绍 及 PBKDF2(过时)<Bcrypt(开始淘汰)<Scrypt< Argon2(含Argon2d、Argon2i、Argon2id)简介-CSDN博客 浅述.Net中的Hash算法(顺带对称、非对称…...
力扣刷题-热题100题-第34题(c++、python)
23. 合并 K 个升序链表 - 力扣(LeetCode)https://leetcode.cn/problems/merge-k-sorted-lists/?envTypestudy-plan-v2&envIdtop-100-liked 顺序合并 合并两个有序链表作为子函数,创建一个空链表,然后对含有多个链表的数组进…...
【SpringCloud】从入门到精通【上】
今天主播我把黑马新版微服务课程MQ高级之前的内容都看完了,虽然在看视频的时候也记了笔记,但是看完之后还是忘得差不多了,所以打算写一篇博客再温习一下内容。 课程坐标:黑马程序员SpringCloud微服务开发与实战 微服务 认识单体架构 单体架…...
如何给路由器配置代理IP?更改网络ip地址时出现错误怎么解决?
在现代网络环境中,无论是家庭用户还是企业用户,经常需要配置路由器以实现网络访问的灵活性和匿名性。其中,给路由器配置代理IP是一个常见的需求,尤其是在需要绕过地域限制、增强网络安全或进行匿名浏览时。然而,配置过…...
程序化广告行业(70/89):ABTester系统助力落地页优化实践
程序化广告行业(70/89):ABTester系统助力落地页优化实践 在程序化广告领域摸爬滚打多年,深知持续学习和知识共享的重要性。写这篇博客,就是希望能和大家一起深入探索程序化广告行业,共同学习、共同进步。今…...
远程监控系统项目里练习
1、项目目标 设备端: (1)基于stm32mp157开发板,裁剪linux5.10.10,完成ov5640摄像头移植; (2)完成用户层程序,完成对摄像头的控制及与云端服务的数据交互。 云端&…...
Spring Boot 通过全局配置去除字符串类型参数的前后空格
1、问题 避免前端输入的字符串参数两端包含空格,通过统一处理的方式,trim掉空格 2、实现方式 /*** 去除字符串类型参数的前后空格* author yanlei* since 2022-06-14*/ Configuration AutoConfigureAfter(WebMvcAutoConfiguration.class) public clas…...
设计模式 --- 观察者模式
设计模式 --- 观察者模式 什么是观察者模式观察者模式典型应用 --- C#中的事件使用观察者模式实现事件处理机制 什么是观察者模式 观察者模式(Observer Pattern)是一种行为型设计模式,用于在对象之间建立一对多的依赖关系。当一个对象&#x…...
组播网络构建:IGMP、PIM 原理及应用实践
IP组播基础 组播基本架构 组播IP地址 一个组播IP地址并不是表示具体的某台主机,而是一组主机的集合,主机声明加入某组播组即标识自己需要接收目的地址为该组播地址的数据IP组播常见模型分为ASM模型和SSM模型ASM:成员接收任意源组播数据&…...
Java常见的23种设计模式
Java常见的23种设计模式 大家好,我是钢板兽! 本文将系统梳理 Java 的设计模式,涵盖创建型、结构型和行为型三大类,结合定义、原理、优点、应用场景、示例代码,帮助你初步了解常见的23种设计模式。 一、设计模式分类…...
兔单B细胞单抗制备服务
1.兔单B细胞技术原理 兔单B细胞技术是近年来新发展的一类快速制备单克隆抗体的技术,是一种通过分离和单克隆化兔子体内的B细胞来制备单一来源的高特异性抗体的方法。基于流式细胞分选技术进行单B细胞单抗制备,利用每个B细胞只含有一个功能性重链可变区D…...
MySQL基础 [六] - 内置函数+复合查询+表的内连和外连
内置函数一般要用select调用 内置函数 日期函数 current_date函数 current_date函数用于获取当前的日期。如下: current_time函数 current_time函数用于获取当前的时间。如下: now函数 now函数用于获取当前的日期时间。如下: date函数 dat…...
nginx路径匹配的优先级
在 Nginx 配置中,当请求 /portal/agent/sse 时,会匹配 location ~* /sse$ 规则,而不是 location /portal。原因如下: 匹配规则解析 location ~* /sse$ ~* 表示 不区分大小写的正则匹配/sse$ 表示以 /sse 结尾的路径匹配结果&#…...
tcp/ip攻击及防范
作为高防工程师,我每天拦截数以万计的恶意流量,其中TCP/IP协议层攻击是最隐蔽、最具破坏性的威胁之一。常见的攻击手法包括: 1. SYN Flood攻击:攻击者发送大量伪造的SYN包,耗尽服务器连接资源,导致正常用…...
2025年3月中国电子学会青少年软件编程(Python)等级考试试卷(一级)答案 + 解析
更多真题在线练习系统:历年真题在线练习系统 一、单选题 1、下列哪个软件不能运行 Python 程序?( ) A、JupyterNotebook B、Pycharm C、原版的Scratch D、IDLE 正确答案:C 答案解析:本题考察的 Pyt…...
TreeMap 核心知识点与面试题解析
TreeMap 核心知识点与面试题解析 一、TreeMap 基础概念 TreeMap 是 Java 集合框架中基于 红黑树(Red-Black Tree) 实现的 Map,具有以下特点: 有序性:默认按 key 的自然顺序(Comparable)或自定…...
深入理解 DevOps 与 CI/CD:概念、流程及优势
在当今快速发展的数字化时代,软件开发和交付的速度与质量成为企业在激烈竞争中脱颖而出的关键因素。DevOps 和 CI/CD 作为现代软件开发领域的重要理念和实践,正深刻地改变着软件开发生命周期的运作方式。本文将深入探讨 DevOps 的概念,详细解析 CI/CD 的内涵、管道阶段以及实…...
Flutter BloC 架构入门指南
BLoC (Business Logic Component) 是 Flutter 中一种流行的状态管理架构,它可以帮助你将业务逻辑与 UI 分离,使代码更清晰、可测试性更强。 核心概念 1. BloC 的核心组件 Events:用户交互或系统事件(如按钮点击、网络请求完成&…...
OpenHarmony-AI调研
OpenHarmony-AI调研 文章目录 OpenHarmony-AI调研前言一、当前版本部署组件二、AI架构1.mindspore-lite2.ai_engine3.neural_network_runtime4.intelligent_voice_framework5.HDI驱动 三、应用1.命令行以及web运行deepseek-r12.与deepseek通过语音进行交互3.物品识别4.人脸识别…...
zk基础—zk实现分布式功能
1.zk实现数据发布订阅 (1)发布订阅系统一般有推模式和拉模式 推模式:服务端主动将更新的数据发送给所有订阅的客户端。 拉模式:客户端主动发起请求来获取最新数据(定时轮询拉取)。 (2)zk采用了推拉相结合来实现发布订阅 首先客户端需要向服务端注册自己关…...
Tips:用proxy解决前后端分离项目中的跨域问题
在前后端分离项目中,"跨域问题"是浏览器基于同源策略(Same-Origin Policy)对跨域请求的安全限制。当你的前端(如运行在 http://localhost:3000 )和后端(如运行在 http://localhost:8080 &#…...
JMeterPlugins-Standard-1.4.0 插件详解:安装、功能与使用指南
JMeterPlugins-Standard-1.4.0 是 Apache JMeter(一款流行的开源负载和性能测试工具)的插件包,它扩展了 JMeter 的功能,提供了更多监听器(Listeners)、采样器(Samplers)和辅助组件&a…...
JMeter 中,Token 和 Cookie 的区别及实际应用
在 JMeter 中,Token 和 Cookie 都是用于处理用户会话和身份验证的机制,但它们的 工作原理、存储方式 和 应用场景 有显著区别。以下是详细对比和实际应用指南: 1. 核心区别 特性Token (如 JWT、OAuth)Cookie存储位置通常存储在 HTTP 请求头(如 Authorization: Bearer <t…...
蓝桥杯真题——好数、R格式
目录 蓝桥杯2024年第十五届省赛真题-好数 【模拟题】 题目描述 输入格式 输出格式 样例输入 样例输出 提示 代码1:有两个案例过不了,超时 蓝桥杯2024年第十五届省赛真题-R 格式 【vector容器的使用】 题目描述 输入格式 输出格式 样例输入…...
JavaScript惰性加载优化实例
这是之前的一位朋友的酒桌之谈,他之前负责的一个电商项目,刚刚开发万,首页加载时间特别长,体验很差,所以就开始排查,发现是在首页一次性加载所有js导致的问题,这个问题在自己学习的时候并不明显…...
0_Pytorch中的张量操作
[引言]张量的概念 1.基本概念 张量是一个通用的多维数组,可以表示标量(0 维)、向量(1 维)、矩阵(2 维)以及更高维度的数据。张量是 PyTorch 中的核心数据结构,用于表示和操作数据。…...
Java面试43-常见的限流算法有哪些?
限流算法是一种系统保护策略,主要是避免在流量高峰导致系统被压垮,造成系统不可用的问题。 常见的限流算法有五种: 计数器限流,一般用在单一维度的访问频率限制上,比如短信验证码每隔60s只能发送一次,或者…...
牛客网:树的高度 ← 根节点为 0 号节点
【题目来源】 https://www.nowcoder.com/questionTerminal/4faa2d4849fa4627aa6d32a2e50b5b25 【题目描述】 现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度。 【输入格式】 输入的第一行表…...
Linux:进程程序替换execl
目录 引言 1.单进程版程序替换 2.程序替换原理 3.6种替换函数介绍 3.1 函数返回值 3.2 命名理解 3.3 环境变量参数 引言 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支),我们所创建的所有的子进程,执行的代码&#x…...
⑩数据中心M-LAG 实战
一、配置指导自己去看今天操作的是M-LAG 基础实验 二、配置代码信息回顾 ### 1、配置 M-LAG 系统 MAC 地址<H3C>system-view[H3C]m-lag system-mac ?H-H-H MAC address2a7a-53ee-0100 Bridge MAC address[H3C]m-lag system-mac### 2、配置 M-LAG 系统编号…...
delphi idtcpserver 搭建tcp ,ssl协议服务端
如果想用indy idtcpserver实现tcp ssl,那么正是你需要的 首先生成证书: 2、windows生成pem证书 - 站着说话不腰疼 - 博客园 有证书后 idtcpserver 用的三个证书, IdServerIOHandlerSSLOpenSSL1.SSLOptions.CertFile = ca.crt IdServerIOHandlerSSLOpenSSL1.SSLOptions.…...
如何实现外观模式?
一、模式理解(用快递驿站比喻) 想象你网购了5件商品,分别来自不同快递公司。 外观模式就像小区门口的快递驿站,你不需要知道中通怎么分拣、顺丰怎么运输,只要到驿站报取件码就能拿到所有包裹。 在前端开发中…...
深入解析 Linux 文件系统权限:从基础到高级实践
引言 在 Linux 系统中,文件系统权限是保障数据安全和多用户协作的核心机制。想象这样一个场景: 你的服务器上有多个团队共享项目文件 财务数据必须严格保密,仅允许指定人员访问 开发团队需要共同编辑代码,但禁止随意删除他人文…...
GZ036区块链卷一 EtherStore合约漏洞详解
题目 pragma solidity >0.8.3;contract EtherStore {mapping(address > uint) public balances;function deposit() public payable {balances[msg.sender] msg.value;emit Balance(balances[msg.sender]);}function withdraw() public {uint bal balances[msg.sender…...
医药流通行业批发公司IT运维转型:Prometheus+Grafana监控Spring Boot 3应用实践
一、引言:医药流通行业IT运维挑战与工具换代需求 在医药流通行业批发领域,业务的核心在于供应链的高效运转、订单处理的精准及时以及库存管理的动态平衡。随着互联网医疗的兴起和电商平台的渗透,传统医药批发企业正加速向数字化、智能化转型…...
编程助手fitten code使用说明(超详细)(vscode)
这两年 AI 发展迅猛,作为开发人员,我们总是追求更快、更高效的工作方式,AI 的出现可以说改变了很多人的编程方式。 AI 对我们来说就是一个可靠的编程助手,给我们提供了实时的建议和解决方,无论是快速修复错误、提升代…...
金融大模型
FinGPT 数据集:https://github.com/AI4Finance-Foundation/FinGPT/tree/master/fingpt/FinGPT-v3 FinGPT v3 系列是在新闻和微博情绪分析数据集上使用 LoRA 方法进行微调的LLM,在大多数金融情绪分析数据集上取得了最佳分数。 FinGPT v3.1 使用 chatgl…...
【Pandas】pandas DataFrame infer_objects
Pandas2.2 DataFrame Conversion 方法描述DataFrame.astype(dtype[, copy, errors])用于将 DataFrame 中的数据转换为指定的数据类型DataFrame.convert_dtypes([infer_objects, …])用于将 DataFrame 中的数据类型转换为更合适的类型DataFrame.infer_objects([copy])用于尝试…...
011_异常、泛型和集合框架
异常、泛型和集合框架 异常Java的异常体系异常的作用 自定义异常异常的处理方案异常的两种处理方式 泛型泛型类泛型接口泛型方法、通配符和上下限泛型支持的类型 集合框架集合体系结构Collection Collection集合Collection的遍历方式认识并发修改异常问题解决并发修改异常问题的…...
QTSql全解析:从连接到查询的数据库集成指南
概览 与数据库的有效集成是确保数据管理效率和应用性能的关键,Qt框架就提供了强大的QtSql模块,使得开发者能够轻松地进行数据库操作,包括连接、查询执行以及结果处理等 一、引入QtSql模块 首先,需要在项目中引入QtSql模块&…...
docker快捷打包脚本(ai版)
直接进入主题: 用这个脚本前提是你本地可以拉镜像仓库的镜像,并且在 本地有了,然后将所有的镜像tag写在一个文件中,和下面docker_tags.txt 对应,文件叫什么,脚本里对应改什么,给小白说的 #!/bi…...
分布式防护节点秒级切换:实战配置与自动化运维
摘要:针对DDoS攻击导致节点瘫痪的问题,本文基于群联AI云防护的智能调度系统,详解如何实现节点健康检查、秒级切换与自动化容灾,并提供Ansible部署脚本。 一、分布式节点的核心价值 资源分散:攻击者难以同时击溃所有节…...
TBE(TVM的扩展)
算子 张量 一个张量只有一种数据类型 在内存中只能线性存储,最终形成一个长的一维数组 晟腾AI的数据格式 AIPP是对我们常见的数据格式转化成AI core支持的数据格式 广播机制 TVM TBE的第一种开发方式:DSL TBE的第二种开发方式:TVM TBE的第…...
Jenkins配置的JDK,Maven和Git
1. 前置 在配置前,我们需要先把JDK,Maven和Git安装到Jenkins的服务器上。 (1)需要进入容器内部,执行命令:docker exec -u root -it 容器号/容器名称(2选1) bash -- 容器名称 dock…...