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 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.