当前位置: 首页 > news >正文

力扣每日一练(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)

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

Pytest系列(2) - assert断言详细使用

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

CodeWave智能开发平台--03--目标:应用创建--10初级采购管理系统总结

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

外包干了4个月,技术退步明显.......

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

图片批量建码怎么用?每张图片快速生成二维码

当我们需要给每个人分别下发对应的个人证件类图片信息&#xff0c;比如制作工牌、荣誉展示或者负责人信息展示时&#xff0c;现在都开始使用二维码的方法来展示员工信息。那么如何快速将每个人员的信息图片分别制作成二维码图片呢&#xff0c;最简单的方法就是使用图片批量建码…...

时间复杂度的排序

在计算机科学中&#xff0c;不同的算法有不同的时间复杂度。以下是一些常见的时间复杂度&#xff0c;并按照它们的增长速度从低到高排序&#xff1a; O(1) - 常数时间复杂度&#xff1a; 表示算法的执行时间是固定的&#xff0c;不随输入规模的增加而变化。例如&#xff0c;直接…...

js控制浏览器前进、后退、页面跳转

在JavaScript中&#xff0c;你可以使用 window 对象的 history 对象来控制浏览器的历史记录。以下是一些常用的方法&#xff1a; 前进和后退&#xff1a; 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作者的博士毕业论文&#xff0c;为了理清楚MAMBA专门花时间拜读这篇长达330页的博士论文&#xff0c;由于知识水平有限&#xff0c;只能尽自己所能概述记录&#xff0c;并适…...

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是&#xff1a;192.168.59.133任何服务器使用任何用户ssh均报错&#xff0c;甚至连自己都不能ssh自己。 不能使用任何工具连接上该服务器 使用ssh连接自己的127.0.0.1和localhost都权限拒绝错误 ssh报错如下 任何服务器ssh报错内容均一样&#xff1a;报错内…...

IO、NIO、IO多路复用

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

探索FTP:原理、实践与安全优化

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

git中的语法和术语含义

目录 第一章、git常用术语1.1&#xff09;文件状态1.2&#xff09;git常用术语的含义 第二章、git文件状态解析2.1&#xff09;从git init开始&#xff1a;Untracked&#xff08;未跟踪&#xff09;2.2&#xff09;git add fileName后&#xff1a;Staged&#xff08;已暂存&…...

java SECS管理系统 将逐步推出 SECS 客户端(Passive) 管理系统 SECS快速开发平台 springboot secs开发平台

SECS管理系统 这是一套SECS客户端(Passive)&#xff0c;可以直接连接PLC设备,支持Modbus、三菱MC、欧姆龙Fine、OPC-UA、西门子S7设备等通信。 企业已经有了EAP软件&#xff0c;但是设备没有SECS通信功能&#xff0c;这时候可以使用这套框架&#xff0c;直接连接设备&#xff…...

使 a === 1 a === 2 a === 3 为 true 的几种“下毒“方法

前言 这算得上是近些年的前端网红题了&#xff0c;曾经对这种网红题非常抵触&#xff0c;认为非常没有意义。 看到了不少人有做分享&#xff0c;有各种各样的方案&#xff0c;有涉及到 JS 非常基础的知识点&#xff0c;也不得不感叹解题者的脑洞之大。 但是&#xff0c;拿来…...

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以及如何提升自动化测试的效果

在快节奏的技术世界里&#xff0c;自动化测试已经成为确保 Web 应用程序质量和性能的重要手段。自动化测试不仅加快了测试过程&#xff0c;还提高了测试的重复性和准确性。Selenium&#xff0c;作为领先的自动化测试工具之一&#xff0c;为测试人员提供了强大的功能来模拟用户在…...

【MySQL】——关系数据库标准语言SQL(大纲)

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…...

力扣hot100 最长有效括号 动态规划

Problem: 32. 最长有效括号 文章目录 思路Code 思路 &#x1f468;‍&#x1f3eb; 参考题解 Code ⏰ 时间复杂度: O ( n ) O(n) O(n) &#x1f30e; 空间复杂度: O ( n ) O(n) O(n) class Solution {public int longestValidParentheses(String s){int n s.length();…...

@RequestBody注解基础

RequestBody RequestBody注解一般与post方法使用。 一个请求中只能存在一个RequestBody注解。 RequestBody 用于接收前端传递给后端的json字符串中的数据。&#xff08;处理json格式的数据&#xff09; 语法格式&#xff1a; ​(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过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

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

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

归并排序:分治思想的高效排序

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

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…...