【Python 算法 1.线性枚举】
我装作漠视一切,以为这样就可以不在乎
—— 25.3.17
一、线性枚举的基本概念
1.时间复杂度
线性枚举的时间复杂度为 O(nm),其中 n是线性表的长度。m 是每次操作的量级,对于求最大值和求和来说,因为操作比较简单,所以 m为 1,则整体的时间复杂度是 O(n)的。这是因为线性枚举需要遍历列表中的每个元素。在处理大规模数据时,可能需要使用更高效的算法来提高搜索速度。
2.优化算法
二分查找:如果线性表已经排序,可以使用二分搜索来提高搜索效率。
哈希表:可以使用哈希表来存储已经搜索过的元素,避免重复搜索。
前缀和:可以存储前 i 个元素的和,避免重复计算。
双指针:可以从两头开始搜索,提升搜索效率。
二、实战
1.1550. 存在连续三个奇数的数组
给你一个整数数组
arr
,请你判断数组中是否存在连续三个元素都是奇数的情况:如果存在,请返回true
;否则,返回false
。示例 1:
输入:arr = [2,6,4,1] 输出:false 解释:不存在连续三个元素都是奇数的情况。示例 2:
输入:arr = [1,2,34,3,4,5,7,23,12] 输出:true 解释:存在连续三个元素都是奇数的情况,即 [5,7,23] 。提示:
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
方法一 线性枚举
思路与算法
遍历数组:代码通过一个
for
循环遍历数组arr
,从第二个元素开始,到倒数第二个元素结束。这样做的目的是为了确保在检查arr[i-1]
、arr[i]
和arr[i+1]
时不会越界。检查连续奇数:在每次循环中,代码检查当前元素
arr[i]
及其前一个元素arr[i-1]
和后一个元素arr[i+1]
是否都是奇数。这是通过取模运算% 2 == 1
来判断的。如果这三个元素都是奇数,则说明存在三个连续的奇数,函数立即返回True
。返回结果:如果遍历完整个数组都没有找到三个连续的奇数,则函数返回
False
。
class Solution:def threeConsecutiveOdds(self, arr: List[int]) -> bool:n = len(arr)for i in range(1, n - 1):if arr[i - 1] % 2 == 1 and arr[i] % 2 == 1 and arr[i+1] % 2 == 1:return Truereturn False
2.485. 最大连续 1 的个数
给定一个二进制数组
nums
, 计算其中最大连续1
的个数。示例 1:
输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3.示例 2:
输入:nums = [1,0,1,1,0,1] 输出:2提示:
1 <= nums.length <= 105
nums[i]
不是0
就是1
.
方法一 线性枚举
思路与算法
初始化变量:sumNum
:用于记录当前连续 1
的个数。maxNum
:用于记录遍历过程中找到的最长连续 1
的个数。
遍历数组:使用一个 for
循环遍历数组 nums
的每一个元素。如果当前元素是 0
,说明连续的 1
中断了,将 sumNum
重置为 0
。如果当前元素是 1
,将 sumNum
加 1
,表示当前连续 1
的个数增加了。更新最大值:在每次循环中,用 maxNum
记录当前找到的最长连续 1
的个数,通过 max(maxNum, sumNum)
实现。
返回结果:遍历结束后,maxNum
就是整个数组中最长的连续 1
的个数,将其返回。
class Solution:def findMaxConsecutiveOnes(self, nums: List[int]) -> int:n = len(nums)sumNum = 0maxNum = 0for i in range(n):if nums[i] == 0:sumNum = 0else:sumNum += 1maxNum = max(maxNum, sumNum)return maxNum
3.540. 有序数组中的单一元素
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足
O(log n)
时间复杂度和O(1)
空间复杂度。示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2示例 2:
输入: nums = [3,3,7,7,10,11,11] 输出: 10提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
方法一 线性枚举
思路与算法
特殊情况处理:如果数组长度为 1
,直接返回唯一的元素 nums[0]
,因为它一定是不重复的。
遍历数组:使用一个 for
循环遍历数组 nums
,从第二个元素开始,到倒数第二个元素结束(避免越界)。对于当前元素 nums[i]
,检查它是否与前后元素都不相等:如果 nums[i] != nums[i - 1]
且 nums[i] != nums[i + 1]
,则 nums[i]
就是唯一不重复的元素,直接返回。
边界情况处理:如果遍历结束后没有找到不重复的元素,说明不重复的元素可能在数组的边界:检查第一个元素 nums[0]
是否与第二个元素 nums[1]
不相等,如果是,则返回 nums[0]
。否则,返回最后一个元素 nums[n - 1]
。
class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]for i in range(1, n - 1):if nums[i] != nums[i - 1] and nums[i] != nums[i + 1]:return nums[i]if nums[0] != nums[1]:return nums[0]return nums[n - 1]
方法二 二分查找
题目要求设计出的算法必须满足 O(log n)
时间复杂度和 O(1)
空间复杂度
思路与算法
初始化指针:定义两个指针 l
和 r
,分别指向数组的起始位置和结束位置。
二分查找:在 while
循环中,计算中间位置 mid = (l + r) // 2
。
利用 mid ^ 1
来检查 nums[mid]
是否与它的配对元素相等:如果 mid
是偶数,mid ^ 1
就是 mid + 1
。如果 mid
是奇数,mid ^ 1
就是 mid - 1
。如果 nums[mid] != nums[mid ^ 1]
,说明不重复元素在 mid
的左侧,将 r
更新为 mid
。否则,说明不重复元素在 mid
的右侧,将 l
更新为 mid + 1
。
返回结果:当 l == r
时,循环结束,nums[l]
就是唯一不重复的元素。
^
是 按位异或(Bitwise XOR) 运算符。它的作用是对两个整数的二进制表示逐位进行异或运算,并返回结果。对于两个二进制位:
- 如果两个位相同(都是
0
或都是1
),结果为0
。- 如果两个位不同(一个是
0
,另一个是1
),结果为1
。
class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:n = len(nums)l, r = 0, n - 1while l < r:mid = (l + r) // 2if nums[mid] != nums[mid ^ 1]:r = midelse:l = mid + 1return nums[l]
相关文章:
【Python 算法 1.线性枚举】
我装作漠视一切,以为这样就可以不在乎 —— 25.3.17 一、线性枚举的基本概念 1.时间复杂度 线性枚举的时间复杂度为 O(nm),其中 n是线性表的长度。m 是每次操作的量级,对于求最大值和求和来说,因为操作比较简单,所以 …...
C# 嵌套类 详解
一个类在它的包容类外没有多大意义,就适合设计成嵌套类。 嵌套类:定义在另一个类内部的类。 包容类(外部类):包含嵌套类的类。 嵌套类的独特之处是可以为类自身指定private访问修饰符。 嵌套类能访问包容类的任何成…...
深度学习中学习率调整策略
学习率衰减策略是深度学习优化过程中的一个关键因素,它决定了训练过程中学习率的调整方式,从而影响模型收敛的速度和效果。不同的衰减策略在不同的任务和模型上可能有不同的表现,下面从我用到过的几个衰减策略进行记录,后续慢慢跟…...
基于Flask的东方财富网股票数据可视化分析系统
【大数据】基于Flask的东方财富网股票数据可视化分析系统 (完整系统源码开发笔记详细部署教程)✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统能够高效地从东方财富网抓取股票数据,并通过Python的强大数据处理能…...
卓越的用户体验需要智能内容
摘要:这篇文章指出静态文档已无法满足现代用户的需求,而智能内容则是构建卓越用户体验的关键。文章从智能内容的定义、优势和实际应用等方面进行了详细阐述,并强调了企业应积极拥抱智能内容,以提升客户满意度、降低成本并创造新的…...
c++基础知识-图论进阶
一、拓扑排序 1、基础知识 1)什么是拓扑排序 对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若,则u在线性序列中出现在v之前。 2)拓扑排序的操作方法 重复执行…...
Java 买百鸡问题
二阶买百鸡问题:母鸡5元一只,公鸡3元一只,35元可以有多少种买法刚好用完? package com.software.first;import java.util.Scanner;public class Test {public static void main(String[] args) {Scanner scan new Scanner(Syste…...
为什么手机上用 mA 和 mAh 来表示功耗和能耗?
在手机上,我们经常会看到 mA(毫安) 和 mAh(毫安时) 这两个单位,它们分别用来表示 功耗水平 和 能耗水平。为什么用这两个单位呢?其实这和电流、时间以及电池的特性有关。 1.mA(毫安…...
使用SDKMAN!安装springboot
在 Ubuntu 环境中使用 sdk install springboot 命令之前,您需要先安装 SDKMAN!(Software Development Kit Manager)。以下是详细的安装步骤: 安装 SDKMAN! 打开终端。 运行以下命令以安装 SDKMAN!: curl -s "htt…...
【AI学习从零至壹】Pytorch神经⽹络
Pytorch神经⽹络 神经网络简介神经元激活函数 神经网络神经⽹络的⼯作过程前向传播(forward) 反向传播(backward)训练神经⽹络 Pytorch搭建并训练神经⽹络神经⽹络构建和训练过程数据预处理构建模型优化器&提取训练数据训练样本 神经网络简介 神经元 在深度学习中&#x…...
Linux应用 / 驱动程序崩溃调试
文章目录 前言一、GDB 使用1. GDB 介绍2. Debug版本与Release版本3. 指令演示3.1 显示行号3.2 断点设置3.3 查看断点信息3.4 删除断点3.5 开启 / 禁用断点3.6 运行3.7 打印 / 追踪变量 4. 最常用指令 二、Linux 应用程序调试1. codedump 介绍2. 在 Linux 系统中使用 coredump2.…...
k8s集群-kubeadm init
为了使用阿里云的镜像源加速 kubeadm init 初始化 Kubernetes 集群的过程,你需要修改 kubeadm 的配置文件以指向阿里云提供的镜像仓库。以下是具体步骤: 1. 创建或编辑 kubeadm 配置文件 首先,创建一个 kubeadm 的配置文件(如果还…...
Python 视频爬取教程
文章目录 前言基本原理环境准备Python安装选择Python开发环境安装必要库 示例 1:爬取简单直链视频示例 2:爬取基于 HTML5 的视频(以某简单视频网站为例) 前言 以下是一个较为完整的 Python 视频爬取教程,包含基本原理…...
Linux应用软件编程(多任务:进程间通信)
一.进程间通信 同一主机下: (1)无名管道:pipe (2)有名管道:fifo (3)信号:异步通知机制 (4)共享内存&a…...
工厂方法模式和抽象工厂模式详解
由于工厂方法模式和抽象工厂模式有点类似,可以放着一块说下。 一、工厂方法模式 (Factory Method Pattern) 场景描述 假设需要实现一个跨平台日志系统,支持文件日志和数据库日志,且未来可能扩展其他日志方式。通过工厂方法模式,…...
js给后端发送请求的方式有哪些
在 JavaScript 中,有多种方式可以向后端发送请求,以下为你详细介绍: 1. XMLHttpRequest XMLHttpRequest 是最早用于在浏览器和服务器间进行异步通信的 API。虽然它使用起来相对复杂,但兼容性很好,能兼容较旧的浏览器…...
无人机吊舱模块更换技术难点分析!
一、模块更换的可行性 模块化设计的支持 部分吊舱采用模块化设计,允许根据任务需求更换传感器模块。例如,某些吊舱系统支持定制化组合,如“红外激光测距”或“可见光激光测距”等。这表明在硬件结构上,若吊舱预留了标准化的接…...
高数1.4 无穷小与无穷大
1.无穷小 1.1.定义 1.2 常规性质 2.无穷大 2.1 定义 2.无穷小与无穷大的关系...
深入理解MySQL数据库索引
深入理解MySQL数据库索引 个人主页:顾漂亮 1. 索引简介 1.1 索引是什么? MySQL的索引是一种数据结构,它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录,使得对表的查询可以通过对索引的搜…...
Spring 中 BeanPostProcessor 的作用和示例
一、BeanPostProcessor 的核心作用 1、作用 BeanPostProcessor 是 Spring Bean 实例级别的扩展接口,在 Bean 初始化前后对实例进行加工或替换。其核心功能包括: 修改 Bean 属性(如动态注入值、调整配置)。生成代理对象…...
图 最 短 路
Diikstra朴素 非负边权单源最短路顶点数最好小于1000少量数据结构知识和一点点的算法基础 算法描述 这个算法我们采用邻接矩阵来存储,有时候输入数据,并不是我们期待的那样,所以需要对数据做一些处理,也就是把图创建起来的过程…...
NA611系列WiFi串口服务器常见问题以及解决办法
NA611系列WiFi串口服务器是一款高性能、高可靠的工业级双频RS485 ⇌ WiFi数据双向透明传输的串口服务器。实现RS485串口数据通过WiFi实现设备联网数据交互,支持 IEEE 802.11 a/b/g/n 标准。WiFi串口服务器在连接、配置和使用过程中可能会遇到多种问题。以下是一些常…...
工程化与框架系列(36)--前端监控告警实践
前端监控告警实践 🔔 引言 前端监控是保障应用质量和用户体验的重要手段。本文将深入探讨前端监控的实现方案,包括性能监控、错误监控、用户行为监控等方面,以及相应的告警机制。 监控系统概述 前端监控系统主要包括以下方面:…...
【深度学习|目标检测】YOLO系列anchor-based原理详解
YOLO之anchor-based 一、关于anchors的设置二、网络如何利用anchor来训练关于register_buffer训练阶段的anchor使用推理阶段的anchor使用 三、训练时的正负样本匹配anchor匹配grid匹配 总结起来其实就是:基于anchor-based的yolo就是基于三个检测头的分支上的grids和…...
vue3+Ts+elementPlus二次封装Table分页表格,表格内展示图片、switch开关、支持
目录 一.项目文件结构 二.实现代码 1.子组件(表格组件) 2.父组件(使用表格) 一.项目文件结构 1.表格组件(子组件)位置 2.使用表格组件的页面文件(父组件)位置 3.演示图片位置 ele…...
【C/C++】文件句柄
什么是文件句柄? 文件句柄(File Handle)是操作系统中的一种抽象概念,它用来表示一个打开的文件或输入/输出设备。 文件句柄是程序与文件之间的桥梁,程序通过文件句柄来访问和操作文件的内容。 1. 文件句柄——作用 文…...
Matlab 基于专家pid控制的时滞系统
1、内容简介 Matlab 185-基于专家pid控制的时滞系统 可以交流、咨询、答疑 2、内容说明 略 在处理时滞系统(Time Delay Systems)时,使用传统的PID控制可能会面临挑战,因为时滞会导致系统的不稳定或性能下降。专家PID控制通过结…...
【高项】信息系统项目管理师(六)项目进度管理【3分】
项目进度管理是为了保证项目按时完成。对项目所需的各个过程进行管理,包括规划进度、定义活动、排列活动顺序、估算活动持续时间、制订项目进度计划和控制进度。小型项目中,定义活动、排列活动顺序、估算活动持续时间以及制订进度模型形成进度计划等过程的联系非常紧密,可以…...
通过MATLAB和Carsim进行联合仿真,利用强化学习实现自动驾驶人机控制权策略的详细步骤和示例代码
以下是一个通过MATLAB和Carsim进行联合仿真,利用强化学习实现自动驾驶人机控制权策略的详细步骤和示例代码: 步骤概述 Carsim配置:对Carsim进行必要的设置,包括车辆模型、道路场景等,并生成S - function接口。MATLAB环境搭建:在MATLAB中配置Carsim的S - function,并创建…...
iOS 模块化架构设计:主流方案与实现详解
随着 iOS 工程规模的扩大,模块化设计成为提升代码可维护性、团队协作效率和开发灵活性的关键。本文将探讨为什么需要模块化,介绍四种主流的模块化架构方案(协议抽象、依赖注入、路由机制和事件总线),并通过代码示例和对…...
PostreSQL指南-内幕探索-学习笔记-01-数据库集簇的逻辑与物理结构
目录 一、环境信息 二、参考内容 三、逻辑结构概念 四、物理结构概念 五、逻辑映射关系 1、数据库与oid映射关系 2、堆表对象与oid映射关系 五、物理映射关系 1、数据库与oid映射关系 2、堆表对象与oid映射关系 六、数据库文件布局 1、表格 2、postmaster.pid文件解…...
java使用(Preference、Properties、XML、JSON)实现处理(读写)配置信息或者用户首选项的方式的代码示例和表格对比
在Java应用程序中,处理应用首选项(preferences)有多种方法,包括使用java.util.prefs.Preferences类、属性文件(如.properties文件)、XML文件和JSON文件。下面是每种方法的详细说明和代码示例,最…...
spring动态代理是在生命周期的哪个阶段实现的
Spring AOP(面向切面编程)的动态代理是在 Bean 生命周期的 初始化后阶段 实现的,具体来说是在 BeanPostProcessor 的 postProcessAfterInitialization() 方法中完成的。下面我们来详细分析 Spring AOP 动态代理的实现位置及其工作原理。 1. S…...
Oracle静默安装方法
Web服务器上面的Linux一般是不会有图形界面的,所有通过图形界面来安装Linux的方式在没有图形界面的Linux上面是行不通的,我们要使用的安装方式叫做Linux的静默安装。即在没有图形界面的Linux上面安装。 1. 下载地址 http://www.oracle.com/technetwork…...
本地部署deepseek-r1建立向量知识库和知识库检索实践【代码】
目录 一、本地部署DS 二、建立本地知识库 1.安装python和必要的库 2.设置主目录工作区 3.编写文档解析脚本 4.构建向量数据库 三、基于DS,使用本地知识库检索 本地部署DS,其实非常简单,我写了一篇操作记录,我终于本地部署了DeepSeek-R1(图文全过程)-CSDN博客 安装…...
单词翻转(信息学奥赛一本通-1144)
【题目描述】 输入一个句子(一行),将句子中的每一个单词翻转后输出。 【输入】 只有一行,为一个字符串,不超过500个字符。单词之间以空格隔开。 【输出】 翻转每一个单词后的字符串,单词之间的空格需与原文一致。 【输入样例】 he…...
Python基础入门掌握(十三)
从基础到进阶,轻松掌握文件读写 目录 文件操作的基本概念 文件的打开与关闭 读取文件内容 写入文件内容 文件操作的高级技巧 总结与建议 文件操作的基本概念 在Python中,文件操作主要涉及以下几个步骤: 打开文件(open…...
【再读】R1-Onevision通过跨模态形式化为复杂多模态推理任务提供了系统性解决方案
R1-Onevision:跨模态形式化驱动的多模态推理技术突破,R1-Onevision通过跨模态形式化、双阶段训练和教育级基准测试,为多模态推理树立了新标杆。其技术创新不仅提升了模型在复杂任务中的表现,更重要的是为行业提供了一种可解释、可迁移的多模态处理范式。随着形式化方法的不断…...
【AWS入门】2025 AWS亚马逊云科技账户注册指南
【AWS入门】2025 AWS亚马逊云科技账户注册指南 A Guide To Register a New account on AWS By JacksonML 0. AWS亚马逊云科技简介 Amazon Web Service(AWS) 即亚马逊云科技,其在全球Cloud Computing(云计算)市场占有最为重要的地位。 AWS连续13年被Gartner评为…...
重生之我在学Vue--第18天 Vue 3 项目功能扩展
重生之我在学Vue–第18天 Vue 3 项目功能扩展 文章目录 重生之我在学Vue--第18天 Vue 3 项目功能扩展前言一、权限管理系统1.1 用户角色体系设计1.2 路由权限控制1.3 组件级权限控制 二、分页与搜索系统2.1 分页类型对比2.2 分页组件实现2.3 搜索功能实现 三、文件上传系统3.1 …...
基于SpringBoot的房地产销售管理系统【附源码】
基于SpringBoot的房地产销售管理系统(源码L文说明文档) 目录 4 系统设计 4.1用户登录功能的详细实现 4.2管理员权限的功能实现 4.2.1客户信息管理功能的详细实现 4.2.2房产管理功能的详细实现 4.2.3预约看房功能的详细实现 4.2.4论…...
数组题型-二分查找-JS
二分查找伪代码 1.定义 target 是在⼀个在左闭右闭的区间⾥,也就是[left, right] let left0;let rightnums.length-1;// 定义target在左闭右闭的区间⾥,[left, right]while(left<right){// 当leftright,区间[left, right]依然有效&#x…...
STL——vector
目录 1 vector介绍 2 vector使用 2.1 vector的定义 2.1.1 无参构造 2.1.2 构造并初始化N个Val 2.1.3 拷贝构造 2.1.4 使用迭代器初始化构造 2.1.5 使用大括号初始化构造 2.2 vector的迭代器 2.2.1 const 迭代器 2.3 vector的空间增长 2.4 vector的增删改查 2.5 ve…...
国内首款载重1吨级无人运输机TP1000首飞成功 2026年投入应急救援
大湾区经济网珠海快讯,据央视新闻报道,3月15日上午,国内首款载重1吨级大型无人运输机TP1000在山东成功首飞。该机由中国民航适航标准完全自主研发,起飞重量3.3吨,满载航程达1000公里,具备智能空投功能&…...
python-leetcode 54.全排列
题目: 给定不含重复数字的数组nums,返回其所有可能的全排列,可以按任意顺序返回答案 回溯法 一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解(或者至少不是最后一个解),回溯算法会通…...
人工智能实现电脑任务自动化的开源软件
人工智能实现电脑任务自动化的开源软件 hallo大家好,我是星哥,今天给大家介绍一个开源软件,融合了人工智能与机器人流程自动化(AIRPA)的开源软件autoMate! autoMate是什么 autoMate 是一款由开源开发的本地自动化工…...
串口烧录出现频繁回复乱码 频繁回复一个数字且烧录失败 字节混乱
这是因为你的芯片没有处于系统存储区启动一直未进入bootloader 解决办法是检查boot引脚接正确没,要在系统存储器启动...
ens33没有分配到IPV4问题
方法一:手动为 ens33 接口分配 IP 地址 你能够借助 ip 命令手动给 ens33 接口分配 IP 地址。不过这种方式在系统重启之后就会失效。 步骤 查看网络信息 先查看一下当前网络的子网信息,例如网关地址和子网掩码等,你可以通过路由器管理界面或…...
搭建主从服务器
任务需求 客户端通过访问 www.nihao.com 后,能够通过 dns 域名解析,访问到 nginx 服务中由 nfs 共享的首页文件,内容为:Very good, you have successfully set up the system. 各个主机能够实现时间同步,并且都开启防…...
【实测闭坑】LazyGraphRAG利用本地ollama提供Embedding model服务和火山引擎的deepseek API构建本地知识库
LazyGraphRAG 2024年4月,为解决传统RAG在全局性的查询总结任务上表现不佳,微软多部门联合提出Project GraphRAG(大模型驱动的KG);2024年7月,微软正式开源GraphRAG项目,引起极大关注,…...