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

知识储备--基础算法篇-数组

1.学习

2.数组

2.1第53题-最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

心得:一直在纠结这个连续的事情,最后发现根本没必要管,因为如果前一个数与当前数相加小于当前数,前面的部分就会直接被舍弃,如果相加大于当前数则会一直叠加。

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""dp = copy.deepcopy(nums)max_ = dp[0]for i in range(1,len(nums)):dp[i] = max(dp[i-1]+nums[i], dp[i])if max_ < dp[i]:max_ = dp[i]return max_

时间和内存占用太多,根本没必要再生成一个dp数组,直接用nums数组更新就行。 

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""# dp = copy.deepcopy(nums)max_ = nums[0]for i in range(1,len(nums)):nums[i] = max(nums[i-1]+nums[i], nums[i])if max_ < nums[i]:max_ = nums[i]return max_

 

2.2第56题-合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution(object):def merge(self, intervals):""":type intervals: List[List[int]]:rtype: List[List[int]]"""new_int = []a = []intervals.sort()for i in range(1,len(intervals)):# 前一个end大于后一个startif intervals[i-1][1] > intervals[i][0]:# 前一个end小于后一个endif intervals[i-1][1] <= intervals[i][1]:intervals[i] = [intervals[i-1][0], intervals[i][1]]else:intervals[i] = intervals[i-1]elif intervals[i-1][1] == intervals[i][0]:intervals[i] = [intervals[i-1][0], intervals[i][1]]else:new_int.append(intervals[i-1])new_int.append(intervals[-1])return new_int

2.3第189题-轮转数组

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
class Solution(object):def rotate(self, nums, k):""":type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead."""# if k == 0:#     return numsnums1 = copy.deepcopy(nums)k = k % len(nums)start = len(nums)-k# nums2 = []# nums1 = nums[:start]# nums2 = nums[start:]for i in range(len(nums)):if i < k:nums[i] = nums[start+i]else:nums[i] = nums1[i-k]

感觉不用深拷贝整个数组

class Solution(object):def rotate(self, nums, k):""":type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead."""k = k % len(nums)start = len(nums)-knums1 = nums[:start]nums2 = nums[start:]for i in range(len(nums2)):nums[i] = nums2[i]for j in range(len(nums1)):nums[j+k] = nums1[j]

看了答案,发现我最早想出的方法就是最简单的答案,nums[:]=nums[start:]+nums[:start],但是发现一直不能修改nums的值,看了答案发现nums忘记加[:]了,吐了。

class Solution(object):def rotate(self, nums, k):""":type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead."""k = k % len(nums)start = len(nums)-knums[:] = nums[start:] + nums[:start]

2.4除自身以外数组的乘积

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

不要使用除法,且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

先用最简单的遍历法,果然超时。

class Solution(object):def productExceptSelf(self, nums):""":type nums: List[int]:rtype: List[int]"""len_ = len(nums)answer = [1]*len_for i in range(len_):for j in range(len_):if j != i:answer[i] = answer[i]*nums[j]return answer

 然后把数组分为i点的前半部分和后半部分相乘来计算,这样的话减少很多重复计算的时间。

class Solution(object):def productExceptSelf(self, nums):""":type nums: List[int]:rtype: List[int]"""# 可以把乘积分为前半部分和后半部分len_ = len(nums)answer = [1]*len_forward = [1]*len_back = [1]*len_for i in range(1,len_):forward[i] = forward[i-1]*nums[i-1]for j in reversed(range(len_-1)):back[j] = back[j+1]*nums[j+1]for k in range(len_):answer[k] = forward[k]*back[k]return answer

看了答案,知道了左边的乘积其实可以动态的变化

class Solution(object):def productExceptSelf(self, nums):""":type nums: List[int]:rtype: List[int]"""# 可以把乘积分为前半部分和后半部分len_ = len(nums)answer = [1]*len_back = 1for i in range(1,len_):answer[i] = answer[i-1]*nums[i-1]for j in reversed(range(len_)):answer[j] = answer[j]*backback = back * nums[j]return answer

2.5第41题-缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

输入:nums = [1,2,0]
输出:3

用最朴素的方法来寻找,不出所料,超时。

class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""for i in range(len(nums)-1):j = 0while j < len(nums)-1-i:if nums[j] > nums[j+1]:temp = nums[j]nums[j] = nums[j+1]nums[j+1] = tempj = j + 1# print(nums)if nums[-1] <= 0:return 1index_1 = 0for j in range(len(nums)):if nums[j] > 0:if nums[j] != 1:return 1else:index_1 = jbreaka = 1# print(index_1)for k in range(index_1+1,len(nums)):a = a + 1if nums[k] == a:continueelif nums[k] == a-1:a = a - 1continueelse:return areturn a + 1

 看了解析,知道当nums长度为N时,正数的数目肯定在[1,N]范围内,这时候就可以用哈希表来查找,内存占用多但速度快。把nums中的数都放在哈希表中,然后遍历[1,N],如果有哈希表中不存在则返回i,若都存在则返回i+1。

class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""hash_table = set(nums)n = len(nums)a = 0for i in range(1,n+1):if i in hash_table:a = icontinueelse:return ireturn a + 1

相关文章:

知识储备--基础算法篇-数组

1.学习 2.数组 2.1第53题-最大子数组和 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 心得&#xff1a;一直在纠结这个连续的事情&…...

zookeeper 理论合集

目录 系统背景 集群结构 多个节点之间的角色 节点的状态 为什么引入 Observer 存储结构 ZNode 节点结构 ZNode 创建类型 内存数据存储 数据持久化 zookeeper 的容量大小 数据同步 消息广播 崩溃恢复 如何保证顺序一致性 核心流程 Leader 选举流程 脑裂问题 …...

【pyinstaller 怎么打包python,打包后程序闪退 不打日志 找不到自建模块等问题的踩坑解决】

程序打包踩坑解决的所有问题 问题1 多个目录怎么打包 不管你包含多个层目录&#xff0c;引用多么复杂&#xff0c;只需要打包主程序所在文件即可&#xff0c;pyinstaller会自动寻找依赖包&#xff0c;如果报错自建模块找不到&#xff0c;参照问题3 pyinstaller main.py问题2…...

【Docker】网络

文章目录 Docker 网络基础Docker网络管理Docker网络架构CNMLibnetwork驱动 常见的网络类型 Docker 网络管理命令docker network createdocker network inspectdocker network connectdocker network disconnectdocker network prunedocker network rmdocker network ls docker …...

Linux :realpath 命令

以后可以直接用于查找相关文件 例: 输入:realpath .repo/manifests/rv1126_rv1109_linux_release.xml 输出:/home/sdk/work/rk/rv1126_rv1109/.repo/manifests/rv1126_rv1109_linux/rv1126_rv1109_linux_v3.0.2_20230406.xml根据输入的文件找到对应复制过来的型号,这个命令不…...

react17:生命周期函数

挂载时更新时 setState触发更新、父组件重新渲染时触发更新forceUpdate触发更新卸载时 react&#xff08;v17.0.2&#xff09;的生命周期图谱如下。 相较于16版本&#xff0c;17版本生命周期函数有如下变化&#xff1a; componentWillMount() componentWillUpdate() compone…...

腾讯内部单边拥塞算法BBR-TCPA一键脚本安装

TCPA简介 腾讯内部使用的TCPA&#xff0c;由腾讯TEG操作系统组研发&#xff0c;基于RHEL7.4源码&#xff0c;定制化的TCPA。团队介绍&#xff1a;腾讯TEG操作系统组, 2010年成立&#xff0c;专业的内核团队,维护研发腾讯内部linux操作系统tlinux, 保证百万级server高效稳定运行…...

【LLM】chatglm-6B模型训练和推理

本篇文章记录下 chatglm-6B 训练和推理过程 环境&#xff1a;Ubuntu 20.04 1.13.0cu116 chatglm-6B 源代码仓库&#xff1a;链接 chatglm-6B 模型权重&#xff1a;链接 源代码及模型 clone 到本地 这里使用的是 THUDM 在 hugging face 开源的模型。 因为模型比较大&#xff…...

性能可靠it监控系统,性能监控软件的获得来源有哪些

性能可靠的IT监控系统是企业IT运维的重要保障之一。以下是一个性能可靠的IT监控系统应该具备的特点&#xff1a; 高可用性 高可用性是IT监控系统的一个重要特点&#xff0c;它可以保证系统在24小时不间断监控的同时&#xff0c;保证系统服务的可用性和稳定性。为了实现高可用性…...

TCP/IP网络编程(一) 理解网络编程和套接字

文章目录 理解网络编程和套接字网络编程和套接字概要构建套接字编写 Hello World 服务器端构建请求连接套接字在Linux平台下运行 基于Linux的文件操作打开文件关闭文件将数据写入文件读取文件中的数据 理解网络编程和套接字 网络编程和套接字概要 网络编程就是编写程序使两台…...

Python 潮流周刊#18:Flask、Streamlit、Polars 的学习教程

你好&#xff0c;我是猫哥。这里每周分享优质的 Python、AI 及通用技术内容&#xff0c;大部分为英文。标题取自其中三则分享&#xff0c;不代表全部内容都是该主题&#xff0c;特此声明。 本周刊由 Python猫 出品&#xff0c;精心筛选国内外的 250 信息源&#xff0c;为你挑选…...

装备一台ubuntu

配置远程连接&#xff1a; ubuntu的root用户无法远程登入问题&#xff1a; openssh安装命令&#xff1a; sudo apt-get install openssh-server 安装完成通过以下命令查看SSH是否启动 ps -e | grep ssh 如果只有ssh-agent表示还没启动&#xff0c;需要&#xff1a; /etc/i…...

为了更好和大家交流,欢迎大家加我的微信账户

因为一些懂的都懂的原因&#xff0c;如果我的账户显示为 此时我无法通过站内信、留言或者任何方式和大家联系。 如果看到这样的内容&#xff0c;可以在此评论区留下你的微信账户&#xff0c;我看到后会添加你。为防止其他人冒充我&#xff0c;我的微信号以2206结尾。...

MS1826A HDMI 多功能视频处理器 HDMI4进1出画面分割芯片

基本介绍 MS1826A 是一款多功能视频处理器&#xff0c;包含 4 路独立 HDMI 音视频输入通道、1 路 HDMI 音视 频输出通道以及 1 路独立可配置为输入或者输出的 SPDIF、I2S 音频信号。支持 4 个独立的字库定 制型 OSD&#xff1b;可处理隔行和逐行视频或者图形输入信号&#xff1…...

最新文献怎么找|学术最新前沿文献哪里找

查找下载最新文献最好、最快、最省事的方法就是去收录该文献的官方数据库中下载。举例说明&#xff1a; 有位同学求助下载一篇2023年新文献&#xff0c;只有DOI号10.1038/s41586-023-06281-4&#xff0c;遇到这种情况可以在DOI号前加上http://doi.org/输入地址栏查询该文献的篇…...

ctfshow 红包题

前言&#xff1a; 最近一直在搞java很少刷题&#xff0c;看见ctfshow的活动赶紧来复现一波~ ctfshow 红包挑战7 <?php highlight_file(__FILE__); error_reporting(2); extract($_GET); ini_set($name,$value); system("ls ".filter($_GET[1])."" )…...

SpringBoot项目(jar)部署,启动脚本

需求 SpringBoot项目&#xff08;jar&#xff09;部署&#xff0c;需要先关闭原来启动的项目&#xff0c;再启动新的项目。直接输入命令&#xff0c;费时费力&#xff0c;还容易出错。所以&#xff0c;使用脚本启动。 脚本 脚本名&#xff1a;start.sh 此脚本需要放置在jar包…...

大数据(四)主流大数据技术

大数据&#xff08;四&#xff09;主流大数据技术 一、写在前面的话 To 那些被折磨打击的好女孩&#xff08;好男孩&#xff09;&#xff1a; 有些事情我们无法选择&#xff0c;也无法逃避伤害。 但请你在任何时候都记住&#xff1a; 你可能在一些人面前&#xff0c;一文不值&a…...

【已解决】激活虚拟环境报错:此时不应有Anaconda3\envs\[envs]\Library\ssl\cacert.pem。

新建虚拟环境后&#xff0c;进入虚拟环境的时候出现这样的报错&#xff1a; 此时不应有Anaconda3 envs yolov5 Library ssl cacert.pem。 但是之前装的虚拟环境也还能再次激活&#xff0c;base环境也无任何问题&#xff0c;仅新装的虚拟环境无法激活。 查遍了百度谷歌&#xff…...

Vue安装过程的困惑解答——nodejs和vue关系、webpack、vue-cli、vue的项目结构

文章目录 1、为什么在使用vue前要下载nodejs&#xff1f;2、为什么安装nodejs后就能使用NPM包管理工具&#xff1f;3、为什么是V8引擎并且使用C实现&#xff1f;4、为什么会安装淘宝镜像&#xff1f;5、什么是webpack模板&#xff1f;6、什么是脚手架 vue-cli&#xff1f;6.1 安…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...