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: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

GIS图形库更新2024.8.4-9.9

更多精彩内容请访问 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信:digital_twin123 Cesium 本期发布了1.121 版本。重大新闻,Cesium被Bentley收购。 ✨ 功能和改进 默认启用 MSAA,采样 4 次。若要关闭 MSAA,则可以设置scene.msaaSamples = 1。但是通过比较,发现并没有多大改善。