【LeetCode】每日一题:最大子数组和
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。
解题思路
要注意最小值是整个前缀,主要是cumsum然后按照买卖股票的思路做的,但是边界处理很容易错,可以以最开始几个边界来判定初始值,这个方法挺好用的。
AC代码
class Solution:def maxSubArray(self, nums: List[int]) -> int:minres = 0res = -infpre = 0for index in range(len(nums)):pre += nums[index]res = max(res, pre - minres)minres = min(minres, pre)return res
官方思路
动态规划
注意动态规划的重点是以i结尾的最大子串,只有加上结尾这个条件才能写递归式。
我们需要两个变量,一个变量用来记录上一个递归结果,其应该为单独上一个数或者上一个数加上前面一段。这里的变量逻辑和cumsum的前缀和逻辑是有区别的。
class Solution:def maxSubArray(self, nums: List[int]) -> int:res = nums[0]pre = 0for n in nums:pre = max(pre + n, n)res = max(res, pre)return res
二分法
线段树的思想,第一次看到,需要维护四个变量,分辨是非左端点最大值,有点点最大值,整区间值和区间内最大值,这个思路其实像是多道二分法题目的合并了,这种做法的好处在于可以存储任意区间的结果。如果需要多次输出结果,这种方法的优势就比较明显了。
class Solution {
public:struct Status {int lSum, rSum, mSum, iSum;};Status pushUp(Status l, Status r) {int iSum = l.iSum + r.iSum;int lSum = max(l.lSum, l.iSum + r.lSum);int rSum = max(r.rSum, r.iSum + l.rSum);int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);return (Status) {lSum, rSum, mSum, iSum};};Status get(vector<int> &a, int l, int r) {if (l == r) {return (Status) {a[l], a[l], a[l], a[l]};}int m = (l + r) >> 1;Status lSub = get(a, l, m);Status rSub = get(a, m + 1, r);return pushUp(lSub, rSub);}int maxSubArray(vector<int>& nums) {return get(nums, 0, nums.size() - 1).mSum;}
};相关文章:
【LeetCode】每日一题:最大子数组和
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组是数组中的一个连续部分。 解题思路 要注意最小值是整个前缀,主要是cumsum然后按照买卖股票的思路做的&a…...
什么是进程?
前言👀~ 上一章我们介绍了计算机组成的入门知识,了解这些之后,今天来聊聊进程 进程 PCB pcb中的常见属性 进程调度 进程的状态 进程的优先级 上下文 记账信息 虚拟地址空间 如果各位对文章的内容感兴趣的话,请点点小赞&a…...
后端返回base64文件流下载
后端返回base64文件流: 前端处理: downloadTemplate () {this.$API.downloadTemplate().then(({ data }) > {const binaryString atob(data) // 解码base64字符串const byteArray new Uint8Array(binaryString.length) // 创建一个Uint8Arrayfor (let i 0; i…...
云原生面试
云原生面试 Kubernetes原理Kubernetes 如何保证集群的安全性。简述 Kubernetes 准入机制简述Kubernetes Secret 有哪些使用方式简述Kubernetes PodSecurityPolicy机制简述Kubernetes PodSecurityPolicy机制能实现哪些安全策略简述Kubernetes 网络策略原理简述Kubernetes 数据持…...
深度学习入门2—— 神经网络的组成和3层神经网络的实现
由上一章结尾,我们知道神经网络的一个重要性质是它可以自动地从数据中学习到合适的权重参数。接下来会介绍神经网络的概要,然后再结合手写数字识别案例进行介绍。 1.神经网络概要 1.1从感知机到神经网 我们可以用图来表示神经网络,我们把最…...
tensorflow学习:错误 InternalError: Dst tensor is not initialized
tensorflow学习:错误 InternalError: Dst tensor is not initialized_dst tensor is not initialized.-CSDN博客https://blog.csdn.net/wanglitao588/article/details/77033659...
Docker环境安装anythingllm
拉镜像 docker pull mintplexlabs/anythingllm建目录 export STORAGE_LOCATION$HOME/anythingllm && \ mkdir -p $STORAGE_LOCATION && \ touch "$STORAGE_LOCATION/.env"检查目录具有写权限 # 为目录anythingllm赋写权限 chmod 777 anythingllm 启…...
FEC 向前纠错编码
随写,看的有点杂,简单记一下。 应该叫ReedSolomon FEC RS算法简单来讲就是,根据已有数据,构造模型,然后根据模型判纠错? 简单来讲,两点确定一条直线,直线直线上的点都会满足 y kx…...
【jupyter notebook】解决打不开以及安装扩展插件的问题
文章目录 问题描述问题 1解决问题 2解决 问题描述 问题 1 在自定义的虚拟环境下,安装 jupyter notebook 6.4.12 版本时,报以下错误: 解决 查了一些 解决方法,执行以下命令即可解决: conda install traitlets5.9.0 …...
Perl文件句柄深度解析:掌握文件操作的核心
Perl中的文件句柄是进行文件输入输出操作的关键。它们提供了一种机制,允许Perl脚本打开文件、读写数据、定位文件指针,以及关闭文件。理解文件句柄的使用对于编写高效的Perl脚本至关重要。本文将深入探讨Perl文件句柄的概念、使用方法和最佳实践。 1. 文…...
Tomcat 下载部署到 idea
一、下载Tomcat Tomcat 是Apache 软件基金会(Apache Software Foundation)下的一个核心项目,免费开源、并支持Servlet 和JSP 规范。属于轻量级应用服务器,在中小型系统和并发访问用户不是很多的场合下被普遍使用,是开发…...
FutureTask如何使用?
FutureTask是Java中的一个具体类,它实现了RunnableFuture接口,该接口结合了Runnable和Future的功能。FutureTask可以用于表示一个可以取消的异步计算。FutureTask非常适合用于与Executor框架一起使用,但也可以单独使用。 FutureTask的基本用…...
Webpack: 如何借助预处理器、PostCSS 等构建现代 CSS 工程环境
概述 在开发 Web 应用时,我们通常需要编写大量 JavaScript 代码 —— 用于控制页面逻辑;编写大量 CSS 代码 —— 用于调整页面呈现形式。问题在于,CSS 语言在过去若干年中一直在追求样式表现力方面的提升,工程化能力薄弱ÿ…...
一篇文章告诉你如何正确使用chatgpt提示词
在chatgpt大火的时候,出现了一波学习chatgpt提示词的热潮,互联网出现很多了使用的学习提示词的课程。其中我觉得斯坦福大学教授吴恩达博士推出prompt engineer课最全面。接下来总结他课程中正确使用提示词工程的方法。 1. 明确目标 明确你希望ChatGPT完…...
qt基于QGraphicsView的屏幕旋转
一、代码实现 实现代码示例 MainWindow2 w;QGraphicsScene *scene new QGraphicsScene;QGraphicsProxyWidget *gw scene->addWidget(&w);// 旋转角度gw->setRotation(90);QGraphicsView *view new QGraphicsView(scene);//view->resize(1024, 600);//scene-&g…...
一个土木工程专业背景的开发者,讲述开源带给他的力量
在前段时间我们举办的“TDengine Open Day”第一季技术沙龙中,TDengine 应用研发高级工程师谭雪峰进行的“开源之路:程序员的成长与探索”主题分享获得了众多参会者的好评。谭雪峰从自身独特的职业发展经历出发,分享了自己在开源领域的种种收…...
express+vue在线im实现【四】
往期内容 expressvue在线im实现【一】 expressvue在线im实现【二】 expressvue在线im实现【三】 本期示例 本期总结 支持了音频的录制和发送,如果觉得对你有用,还请点个免费的收藏与关注 下期安排 在线语音 具体实现 <template><kl-dial…...
【Qt 实现3D按钮】
要在Qt中实现3D按钮,你可以使用QML和Qt 3D模块。这是一个简单的例子,展示了如何在Qt中创建一个3D按钮: 首先,确保你的系统中已经安装了Qt 3D模块。在命令行中输入以下命令检查: qmlscene --version如果没有安装&…...
8.每日LeetCode-笔试题,交替打印数字和字母
代码地址:interview-go: Go高级面试总结 问题描述 交替打印数字和字母 使用两个 goroutine 交替打印序列,一个 goroutine 打印数字, 另外一个 goroutine 打印字母, 最终效果如下: 12AB34CD56EF78GH910IJ1112KL…...
UE5近战对抗系统Tutorial
文章目录 BP_Character 组合攻击Notify State 检测攻击BP_Character 攻击反馈BP_Character 生命系统BP_Character 死亡效果BP_Character 武器系统BP_Enemy 初始化和行为树 BP_Character 组合攻击 首先我们获取攻击动画,在这里使用的是 Easy Combo Buffering 的攻击…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...
C++--string的模拟实现
一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现,其目的是加强对string的底层了解,以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量,…...
Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合
无论是python,或者java 的大型项目中,都会涉及到 自身平台微服务之间的相互调用,以及和第三发平台的 接口对接,那在python 中是怎么实现的呢? 在 Python Web 开发中,FastAPI 和 Django 是两个重要但定位不…...
