我正在try 解决LeetCode问题1493. Longest Subarray of 1's After Deleting One Element:

给出一个二进制数组nums,您应该从中删除一个元素.

返回the size of the longest non-empty subarray containing only 1's in the resulting array.返回0如果没有这样的子array.

思维过程

在数组的开头应用ij的滑动窗机制:

  • 如果array[j]不是0,我们将继续递增j,因为
  • 如果array[j]是0,这是第一次,我们仍然增加j,因为它是安全的,并增加count0
  • 如果array[j]是0并且是第二次0,如果array[i]是0,那么我们减少计数并增加i
  • 如果array[j]是0,并且是第二次0,如果array[i]不是0,那么我们只需增加i

我的代码

class Solution:
    def longestSubarrayOf1s(self, array):
        i,j = 0,0
        N = len(array)
        toReturn,count0,curr_count=0,0,0
        while j < N:
            if array[j] == 1:
                j+=1
            else:
                if count0 == 0:
                    j+=1
                    count0+=1
                else:
                    if array[i] == 0:
                        i+=1
                        count0-=1
                    else:
                        i+=1
            print('i am updating my max answer to ', j-i, 'in the window of ', i, j)
            toReturn = max(toReturn, j-i)
        return toReturn

测试数组

[1,1,1] #expected 2
[1,1,0,1] #expected 3
[0,1,1,1,0,1,1,0,1] #expected 5

问题

我的代码没有返回任何正确的答案.对于上面列出的三个测试用例,它返回3、4和6.

我的错误是什么?

推荐答案

您的算法很好,但挑战要求您返回resulting数组中的大小(最长的非空子数组仅包含1‘S).您返回了它在original数组中的大小.由于需要在找到的子数组中删除一项,因此应该比当前返回的项少一项:

toReturn = max(toReturn, j-i - 1)  # One less!

你可以通过避免使用i步来加快代码的速度,而只使用1步.因为你已经知道它必须继续这样做,直到遇到一个零,and你已经遇到了零之前与j索引,你可以只跟踪该索引,当你遇到它与j和有i"跳转"到该保存的索引一次go .

对于零的频率明显小于1的频率的数组,您将受益于使用index方法来查找下一个零的位置.

以下是这个 idea 的一个实现:

class Solution:
    def longestSubarray(self, array: List[int]) -> int:
        n = len(array)
        i = -1 # Index of a zero that is imagined in front of the array
        array.append(0)  # Add a dummy zero at the end
        j = array.index(0)
        toReturn = j - 1
        while j < n:  # As long as there are more zeroes...
            k = j  # Keep track of the current zero
            j = array.index(0, k + 1)  # ...and find the next one
            toReturn = max(toReturn, j - i - 2)
            i = k  # Have i "jump" to the next zero after it.
        return toReturn

Python相关问答推荐

如何让 turtle 通过点击和拖动来绘制?

线性模型PanelOLS和statmodels OLS之间的区别

即使在可见的情况下也不相互作用

重新匹配{ }中包含的文本,其中文本可能包含{{var}

计算组中唯一值的数量

Python虚拟环境的轻量级使用

ThreadPoolExecutor和单个线程的超时

如何使用scipy的curve_fit与约束,其中拟合的曲线总是在观测值之下?

在www.example.com中使用`package_data`包含不包含__init__. py的非Python文件

CommandeError:模块numba没有属性generated_jit''''

无论输入分辨率如何,稳定扩散管道始终输出512 * 512张图像

如何找出Pandas 图中的连续空值(NaN)?

并行编程:同步进程

我对这个简单的异步者的例子有什么错误的理解吗?

用两个字符串构建回文

如何将泛型类类型与函数返回类型结合使用?

按条件添加小计列

Stats.ttest_ind:提取df值

按最大属性值Django对对象进行排序

生产者/消费者-Queue.get by list