力扣每日一练(24-1-20)
大脑里的第一想法是排列组合,直接给出超级准确的最优解。
但不适用,hhh
只要连续的n个元素大于或者等于target就可以了
题目比自己想象的要好解决
解法是使用滑动窗口算法。这个算法的基本思想是维护一个窗口,使得窗口内的元素总和大于等于目标值,然后尝试缩小窗口以找到最小的满足条件的子数组。
Python
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)ans = n + 1start = 0end = 0total = 0while end < n:total += nums[end]while total >= target:ans = min(ans, end - start + 1)total -= nums[start]start += 1end += 1return 0 if ans == n + 1 else ans
C#
public class Solution {public int MinSubArrayLen(int target, int[] nums) {int n = nums.Length;int ans = n + 1;int start = 0;int end = 0;int total = 0;while (end < n) {total += nums[end];while (total >= target) {ans = Math.Min(ans, end - start + 1);total -= nums[start];start++;}end++;}return ans == n + 1 ? 0 : ans;}
}
解法的时间复杂度是O(n),因为每个元素最多被访问两次。
二分查找法
在这个问题中,O(n)的滑动窗口解法已经是最优解法,因为它只需要遍历一次数组。然而,如果你想要实现一个O(n log n)的解法,你可以使用二分查找的方法。这种方法的基本思想是先计算累积和数组,然后对每个累积和,使用二分查找找到最小的索引j,使得sum[j] - sum[i] >= target。
以下是这个方法的Python实现:
Python
import bisectclass Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)ans = n + 1sums = [0] * (n + 1)for i in range(1, n + 1):sums[i] = sums[i - 1] + nums[i - 1]for i in range(1, n + 1):to_find = target + sums[i - 1]bound = bisect.bisect_left(sums, to_find)if bound != len(sums):ans = min(ans, bound - (i - 1))return 0 if ans == n + 1 else ans
C#
public class Solution {public int MinSubArrayLen(int target, int[] nums) {int n = nums.Length;int ans = n + 1;int[] sums = new int[n + 1];for (int i = 1; i <= n; i++) {sums[i] = sums[i - 1] + nums[i - 1];}for (int i = 1; i <= n; i++) {int to_find = target + sums[i - 1];int bound = Array.BinarySearch(sums, to_find);if (bound < 0) {bound = ~bound;}if (bound <= n) {ans = Math.Min(ans, bound - (i - 1));}}return ans == n + 1 ? 0 : ans;}
}
相关文章:

力扣每日一练(24-1-20)
大脑里的第一想法是排列组合,直接给出超级准确的最优解。 但不适用,hhh 只要连续的n个元素大于或者等于target就可以了 题目比自己想象的要好解决 解法是使用滑动窗口算法。这个算法的基本思想是维护一个窗口,使得窗口内的元素总和大于等于目…...

Pytest系列(2) - assert断言详细使用
前言 与unittest不同,pytest使用的是python自带的assert关键字来进行断言assert关键字后面可以接一个表达式,只要表达式的最终结果为True,那么断言通过,用例执行成功,否则用例执行失败 assert小栗子 想在抛出异常之…...

CodeWave智能开发平台--03--目标:应用创建--10初级采购管理系统总结
摘要 本文是网易数帆CodeWave智能开发平台系列的第14篇,主要介绍了基于CodeWave平台文档的新手入门进行学习,实现一个完整的应用,本文主要完成10初级采购管理系统总结 CodeWave智能开发平台的14次接触 CodeWave参考资源 网易数帆CodeWave…...

外包干了4个月,技术退步明显.......
先说一下自己的情况,大专生,18年通过校招进入武汉某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...

图片批量建码怎么用?每张图片快速生成二维码
当我们需要给每个人分别下发对应的个人证件类图片信息,比如制作工牌、荣誉展示或者负责人信息展示时,现在都开始使用二维码的方法来展示员工信息。那么如何快速将每个人员的信息图片分别制作成二维码图片呢,最简单的方法就是使用图片批量建码…...
时间复杂度的排序
在计算机科学中,不同的算法有不同的时间复杂度。以下是一些常见的时间复杂度,并按照它们的增长速度从低到高排序: O(1) - 常数时间复杂度: 表示算法的执行时间是固定的,不随输入规模的增加而变化。例如,直接…...
js控制浏览器前进、后退、页面跳转
在JavaScript中,你可以使用 window 对象的 history 对象来控制浏览器的历史记录。以下是一些常用的方法: 前进和后退: window.history.forward(): 前进到历史记录中的下一个页面。window.history.back(): 返回历史记录中的上一个页面。window…...

【长文阅读】MAMBA作者博士论文<MODELING SEQUENCES WITH STRUCTURED STATE SPACES>-Chapter1
Gu A. Modeling Sequences with Structured State Spaces[D]. Stanford University, 2023. 本文是MAMBA作者的博士毕业论文,为了理清楚MAMBA专门花时间拜读这篇长达330页的博士论文,由于知识水平有限,只能尽自己所能概述记录,并适…...

Unity3D学习之UI系统——GUI
文章目录 1. 前言2. 工作原理和主要作用3. 基础控件3.1 重要参数及文本和按钮3.1.1 GUI 共同点3.1.2 文本控件3.1.3 按钮控件 3.2 多选框和单选框3.2.1 多选框3.2.2 单选框3.2.3 输入框3.2.4 拖动条 3.3 图片绘制和框3.3.1 图片3.3.2 框绘制 4 工具栏和选择网格4.1 工具栏4.2 选…...
用户ssh正确密码登陆均报错Permission denied, please try again.处理方法
我的一台虚拟机IP是:192.168.59.133任何服务器使用任何用户ssh均报错,甚至连自己都不能ssh自己。 不能使用任何工具连接上该服务器 使用ssh连接自己的127.0.0.1和localhost都权限拒绝错误 ssh报错如下 任何服务器ssh报错内容均一样:报错内…...

IO、NIO、IO多路复用
IO是什么? IO分为两类,它们之间是有区别的,而且有很大的区别;1. 文件系统的IO 也叫本地io,就是和磁盘或者外围存储设备进行读写操作,外围设备有USB、移动硬盘等等;2. 网络的IO 将数据发送给对方…...

探索FTP:原理、实践与安全优化
引言 在正式开始讲解之前,首先来了解一下文件存储的类型有哪些。 DAS、SAN和NAS是三种不同的存储架构,分别用于解决不同场景下的数据存储需求。 DAS (Direct Attached Storage 直接附加存储):DAS 是指将存储设备(如硬盘&#x…...

git中的语法和术语含义
目录 第一章、git常用术语1.1)文件状态1.2)git常用术语的含义 第二章、git文件状态解析2.1)从git init开始:Untracked(未跟踪)2.2)git add fileName后:Staged(已暂存&…...

java SECS管理系统 将逐步推出 SECS 客户端(Passive) 管理系统 SECS快速开发平台 springboot secs开发平台
SECS管理系统 这是一套SECS客户端(Passive),可以直接连接PLC设备,支持Modbus、三菱MC、欧姆龙Fine、OPC-UA、西门子S7设备等通信。 企业已经有了EAP软件,但是设备没有SECS通信功能,这时候可以使用这套框架,直接连接设备ÿ…...

使 a === 1 a === 2 a === 3 为 true 的几种“下毒“方法
前言 这算得上是近些年的前端网红题了,曾经对这种网红题非常抵触,认为非常没有意义。 看到了不少人有做分享,有各种各样的方案,有涉及到 JS 非常基础的知识点,也不得不感叹解题者的脑洞之大。 但是,拿来…...

Canny边缘检测 双阈值检测理解
问题引入 我们用一个实际例子来引入问题 import cv2 import numpy as npimgcv2.imread("test.png",cv2.IMREAD_GRAYSCALE) # 修改图像大小 show cv2.resize(img,(500,500))v1cv2.Canny(show,120,250) v2cv2.Canny(show,50,100)# 连接图像 res np.hstack((v1,v2)…...

自动化测试:5分钟了解Selenium以及如何提升自动化测试的效果
在快节奏的技术世界里,自动化测试已经成为确保 Web 应用程序质量和性能的重要手段。自动化测试不仅加快了测试过程,还提高了测试的重复性和准确性。Selenium,作为领先的自动化测试工具之一,为测试人员提供了强大的功能来模拟用户在…...

【MySQL】——关系数据库标准语言SQL(大纲)
🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:…...

力扣hot100 最长有效括号 动态规划
Problem: 32. 最长有效括号 文章目录 思路Code 思路 👨🏫 参考题解 Code ⏰ 时间复杂度: O ( n ) O(n) O(n) 🌎 空间复杂度: O ( n ) O(n) O(n) class Solution {public int longestValidParentheses(String s){int n s.length();…...
@RequestBody注解基础
RequestBody RequestBody注解一般与post方法使用。 一个请求中只能存在一个RequestBody注解。 RequestBody 用于接收前端传递给后端的json字符串中的数据。(处理json格式的数据) 语法格式: (RequestBody Map map) (RequestBody Object obje…...

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 如果用户登录尝试失败次…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...

Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...