2024.8.30 Python 最大连续1的个数,滑动窗口,排列组合,三数之和

本文主要是介绍2024.8.30 Python 最大连续1的个数,滑动窗口,排列组合,三数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.最大连续1的个数

给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。
示例 1:
输入:nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出:6
解释:[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:
输入:nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出:10
解释:[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。

分析:这个题在27号的文章中写道过,但是我的掌握还是很差,包括之后的二叉树染色题,所以这两道题我会重新再写一遍,这个题的关键在于去找连续1的个数很难与k对应起来,所以不如翻转列表,直接找0的个数,把0变成1,数1,然后这时候就是,窗口中不超过k个1,最大的窗口就是最大连续1的个数。
***方法一:***下面是我自己写的双指针的方法

class Solution:def longestOnes(self,nums:List[int],k:int)->int:n=len(nums)for i in range(n):nums[i]=nums[i]^1num_1,left=0,0res=0for right in range(n):if nums[right]==1:num_1+=1while num_1>k:if nums[left]==1:num_1-=1left+=1res=max(res,right-left+1)return res

代码逻辑:
1.循环遍历翻转
2.右边遇见一个1就计数,当计数超过k的时候就移左边的,直到计数降下来,则继续循环,算每次的最大res
3.其实我如果使用双指针计算的话我完全没有必要去做翻转,没有必要。
方法二:二分查找
这个方法非常的巧妙,有点动态规划的思路,他是通过前n项和来进行计算的,首先是生成这个数列的前n项和的列表,然后此时的P就是一个单调递增的列表,那么就有right所在位置的n项和减left-1所在位置的n项和,就为这中间的1的数量,注意是left-1,因为left自己是要加上的,所以你减的时候应该减去left-1的n项和,left到right中间包括两边的所有列表元素就能包含进去了。

class Solution:def longestOnes(self, nums: List[int], k: int) -> int:n=len(nums)P=[0]for num in nums:P.append(P[-1]+(1-num))  #注意这里的1-num,等价于num^1ans=0for right in range(n):left=bisect.bisect_left(P,P[right+1]-k)ans=max(ans,right-left+1)return ans

注意,因为P[0]=0,也就是说,关于数列的前n项和在P中应该是n+1,比如到0项和,应该是P[1],所以本来要找的是,right的前n项和,减去left-1要等于k,现在就变成了P[right+1]-P[left]==k,这里的加一减一确实不好想,那不如在实际操作的时候看和结果差多少,通过debug来找这个问题。
关于这个bisect.bisect_left这个是二分查找,代码实现如下:

def find(self,nums:List[int],k:int)->int:n=len(nums)left=0right=n-1while left<right:mid=(left+right)//2if nums[mid]<k:left=mid+1else:right=midreturn left 

2.执行所有后缀指令

现有一个 n x n 大小的网格,左上角单元格坐标 (0, 0) ,右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos ,其中 startPos = [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。
另给你一个长度为 m 、下标从 0 开始的字符串 s ,其中 s[i] 是对机器人的第 i 条指令:‘L’(向左移动),‘R’(向右移动),‘U’(向上移动)和 ‘D’(向下移动)。
机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾,但在满足下述条件之一时,机器人将会停止:
下一条指令将会导致机器人移动到网格外。
没有指令可以执行。
返回一个长度为 m 的数组 answer ,其中 answer[i] 是机器人从第 i 条指令 开始 ,可以执行的 指令数目 。

分析:这个题没啥好说的,挺简单的,按照题目说法一个一个写就好了,问题是在我写的时候出现了问题:

#以下代码是错误的
class Solution:def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:res=[]for start in range(len(s)):step=0Pos=startPos #应该改为Pos=startPos[:]for i in range(start,len(s)):if s[i]=='L':Pos[1]-=1elif s[i]=='U':Pos[0]-=1elif s[i]=='R':Pos[1]+=1elif s[i]=='D':Pos[0]+=1if 0<=Pos[0]<n and 0<=Pos[1]<n:step+=1else:breakres.append(step)return res

这个代码在执行的过程中,我开始忘记把startPos单独拉出来了,直接在startPos上面进行操作了,但是你想,在第二轮的时候,startPos应该归位重新计算,但是我没记录的情况下,startPos最开始的记录已经没了,所以我就定义了个pos来复制startPos,这样每轮都会能回去读startPos,然后编译之后结果没有任何变化。去debug才发现,startPos竟然都赋值给Pos了,Pos变他竟然还在变,我当时就懵了,chat的解释如下:
在 Python 中,Pos = startPos[:] 和 Pos = startPos 的区别在于如何处理列表的引用。当你写 Pos = startPos 时,Pos 和 startPos 都指向同一个列表对象,这意味着对 Pos 的任何修改都会直接影响到 startPos,因为它们引用的是同一个内存地址。在这种情况下,Pos 和 startPos 是同一个对象的两个引用。任何对 Pos 的修改都会影响到 startPos,反之亦然。所以改成startPos[:]即可。

3.最长优雅子数组

提示
给你一个由 正 整数组成的数组 nums 。
如果 nums 的子数组中位于 不同 位置的每对元素按位 与(AND)运算的结果等于 0 ,则称该子数组为 优雅 子数组。
返回 最长 的优雅子数组的长度。
子数组 是数组中的一个 连续 部分。
注意:长度为 1 的子数组始终视作优雅子数组。
方法一:暴力法

class Solution:def longestNiceSubarray(self, nums: List[int]) -> int:n=len(nums)res=1left=0right=1while 1<=right<len(nums):if right!=left:if self.check(nums[left:right+1]):res=max((right-left+1),res)right+=1                    else:left+=1else:right+=1return resdef check(self,nums:List[int])->bool:n=len(nums)i=0j=0for i in range(len(nums)-1):for j in range(i+1,len(nums)):if nums[j]&nums[i]!=0:breakif nums[j]&nums[i]!=0:breakif nums[j]&nums[i]!=0:return Falseelse:return True

开始写的时候循环套循环,给哥们逻辑套懵了,后来想了下不如把函数调出来。
方法二:滑动窗口
其实这个滑动窗口和我写的没啥太大区别,代码量少了好多的原因是因为,他在判断的时候,用了一个很神奇的东西,判断新加入的这个的办法是直接和按位或进行按位和操作,如果错了就用异或弹出左边的,如果成了就按位或加入,代码如下:

class Solution:def longestNiceSubarray(self, nums: List[int]) -> int:ans=left=or_list=0while right<len(nums):while or_list & nums[right]:or_list^=nums[left]left+=1or_list|=nums[right]ans=max(ans,right-left+1)right+1return ans

题没啥难得,但是很巧就是了。

4.排列和组合

我先手写排列的代码

def A(self,nums:List[int])->List[List[int]]:res=[]def backtrack(path,remaining):if not remaining:res.append(path)returnfor i in range(len(remaining)):backtrack(path+[remaining[i]],remaining[:i]+remaining[i+1:])backtrack([],nums)return res

那么组合的代码如下:

class Solution:def combine(self, nums: List[int], k: int) -> List[List[int]]:res = []def backtrack(path, remaining):if len(path) == k:  # 当当前组合长度达到k时,加入结果集res.append(path)return            for i in range(len(remaining)):# 选择当前元素,递归求剩余部分的组合backtrack(path + [remaining[i]], remaining[i+1:])        backtrack([], nums)return res

可以看到,排列的时候的remaining是剔除了当前值以后的remain,组合的时候,直接i前的全剃了。

5.三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums_long=self.combine(nums,3)n=len(nums_long)res=[]for i in range (n):if nums_long[i][0]+ nums_long[i][1]+ nums_long[i][2]==0:#res.append(nums_long[i])res.append(tuple(sorted(nums_long[i])))res = list(set(res))res = [list(t) for t in res]return resdef combine(self, nums: List[int], k: int) -> List[List[int]]:res = []def backtrack(path, remaining):if len(path) == k:  # 当当前组合长度达到k时,加入结果集res.append(path)returnfor i in range(len(remaining)):# 选择当前元素,递归求剩余部分的组合backtrack(path + [remaining[i]], remaining[i+1:])backtrack([], nums)return res

代码逻辑:
这个是我写的,我先组合,然后判断,其中比较重要的是这个地方res.append(tuple(sorted(nums_long[i])))然后res = list(set(res))再转回列表res = [list(t) for t in res],这步操作用来降重。

这篇关于2024.8.30 Python 最大连续1的个数,滑动窗口,排列组合,三数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122490

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Python下载Pandas包的步骤

《Python下载Pandas包的步骤》:本文主要介绍Python下载Pandas包的步骤,在python中安装pandas库,我采取的方法是用PIP的方法在Python目标位置进行安装,本文给大... 目录安装步骤1、首先找到我们安装python的目录2、使用命令行到Python安装目录下3、我们回到Py

Python GUI框架中的PyQt详解

《PythonGUI框架中的PyQt详解》PyQt是Python语言中最强大且广泛应用的GUI框架之一,基于Qt库的Python绑定实现,本文将深入解析PyQt的核心模块,并通过代码示例展示其应用场... 目录一、PyQt核心模块概览二、核心模块详解与示例1. QtCore - 核心基础模块2. QtWid