贸易公司网站建设要多少钱,网站开发效率,泰国网站后缀,阿里巴巴logo发展史1.最大连续1的个数
给定一个二进制数组 nums 和一个整数 k#xff0c;如果可以翻转最多 k 个 0 #xff0c;则返回 数组中连续 1 的最大个数 。 示例 1#xff1a; 输入#xff1a;nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出#xff1a;6 解释#xff1a;[1,1,1,0,0,1,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:nlen(nums)for i in range(n):nums[i]nums[i]^1num_1,left0,0res0for right in range(n):if nums[right]1:num_11while num_1k:if nums[left]1:num_1-1left1resmax(res,right-left1)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:nlen(nums)P[0]for num in nums:P.append(P[-1](1-num)) #注意这里的1-num等价于num^1ans0for right in range(n):leftbisect.bisect_left(P,P[right1]-k)ansmax(ans,right-left1)return ans注意因为P[0]0也就是说关于数列的前n项和在P中应该是n1比如到0项和应该是P[1]所以本来要找的是right的前n项和减去left-1要等于k现在就变成了P[right1]-P[left]k这里的加一减一确实不好想那不如在实际操作的时候看和结果差多少通过debug来找这个问题。 关于这个bisect.bisect_left这个是二分查找代码实现如下
def find(self,nums:List[int],k:int)-int:nlen(nums)left0rightn-1while leftright:mid(leftright)//2if nums[mid]k:leftmid1else:rightmidreturn 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)):step0PosstartPos #应该改为PosstartPos[:]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 0Pos[0]n and 0Pos[1]n:step1else: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:nlen(nums)res1left0right1while 1rightlen(nums):if right!left:if self.check(nums[left:right1]):resmax((right-left1),res)right1 else:left1else:right1return resdef check(self,nums:List[int])-bool:nlen(nums)i0j0for i in range(len(nums)-1):for j in range(i1,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:ansleftor_list0while rightlen(nums):while or_list nums[right]:or_list^nums[left]left1or_list|nums[right]ansmax(ans,right-left1)right1return 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[i1:])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[i1:]) 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_longself.combine(nums,3)nlen(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[i1:])backtrack([], nums)return res代码逻辑 这个是我写的我先组合然后判断其中比较重要的是这个地方res.append(tuple(sorted(nums_long[i])))然后res list(set(res))再转回列表res [list(t) for t in res]这步操作用来降重。
