关于python:Python题解LeetCode-No1567

LeetCode随机一题：No.1567 乘积为负数的最长子数组长度。属于数组类题目，难度中等。

原题请戳这里：
1567. 乘积为负数的最长子数组长度

题目形容

给你一个整数数组 nums ，请你求出乘积为负数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个间断数字组成的数组。 请你返回乘积为负数的最长子数组长度。

• 示例 1： 输出：nums = [1,-2,-3,4] 输入：4 解释：数组自身乘积就是负数，值为 24 。
• 示例 2： 输出：nums = [0,1,-2,-3,-4] 输入：3 解释：最长乘积为负数的子数组为 [1,-2,-3] ，乘积为 6 。 留神，咱们不能把 0 也包含到子数组中，因为这样乘积为 0 ，不是负数。
• 示例 3： 输出：nums = [-1,-2,-3,0,1] 输入：2 解释：乘积为负数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
• 示例 4： 输出：nums = [-1,2] 输入：1
• 示例 5： 输出：nums = [1,2,3,5,-6,4,0,10] 输入：4
• 在测试中发现LeetCode应用的性能测试例：长度为100000的数组，除了nums[3000]为-1，其余均为1。

解题思路

问题焦点：

1. 一个不蕴含0的数组，乘积是否为负数，取决于其中正数的个数，正数为偶数个时数组的乘积为正。
2. 乘积是否为负数，与数字的绝对值大小无关，与数组中的数字的符号无关，所以，能够把所有负数化为1，所有正数转化为-1。
3. 题目中要求是间断数字组成的数组，那么呈现0的中央肯定天然切离开。而切离开的子数组中如果有惟一一个-1，意味着这个子数组的乘积为负（其它数字都是1或者没有其余数字），须要从-1的地位切离开。
4. 在遍历子数组找符合条件的子数组长度时，先依照数组的长度排序（Python排序很不便），从最长的数组开始找，能够尽快完结遍历。

解题流程如下图所示：

首先写一些办法，实现每个小性能点

1. format_nums转化数字的办法，输出的n为数字，将负数转化为1，正数转化为-1，0不变

def format_nums(n):
    if n > 0:
        return 1
    if n < 0:
        return -1
    return 0

2. 切分子数组，先按0切分，再按惟一的-1切分。

首先是被调用的cut_by_single_negative办法，它负责查看数组中是否只有惟一的一个-1，是的话就将数组切离开，返回值对立为list的list。

# 子数组曾经没有0了，查看是否存在惟一一个-1
# 如果有且仅有一个-1，意味着这个子数组乘积必定为正数，须要再次切分
# 有多个正数的话，就没方法了
def cut_by_single_negative(sub_ls):
    ret_ls = []
    if sub_ls.count(-1) == 1:
        idx = sub_ls.index(-1)
        ret_ls.append(sub_ls[:idx])
        ret_ls.append(sub_ls[idx+1:])
    else:
        ret_ls.append(sub_ls) 
    return ret_ls

能够验证一下这个办法：

>>>cut_by_single_negative([1, 1, 1, 1, -1, 1])
[[1, 1, 1, 1], [1]]

而后是外层的调用办法cut_by_zero，它依照0来切分数组。

# 对输出的数组按0天然切分为子数组
# 对每个子数组再检查一下是否只有一个-1，有的话也要切分
def cut_by_zero(nums):
    # 没有0的数组，查看-1
    if 0 not in nums:
        return cut_by_single_negative(nums)

    # 没有什么技巧，遍历数组，长期寄存在tmp中
    ret_ls = []
    tmp = []
    for i in nums:
        if i == 0:
            # 如果遍历到0，则检查一下tmp中有没有惟一的-1
            if len(tmp) != 0:
                ret_ls += cut_by_single_negative(tmp)
                tmp = []
        else:
            tmp.append(i)
    # 不要遗记尾巴
    if len(tmp) != 0:
        ret_ls += cut_by_single_negative(tmp)
    return ret_ls

验证一下这个办法：

>>>cut_by_zero([1, 1, 1, 1, -1, 1, 0, 1])
[[1, 1, 1, 1], [1], [1]]

在实现这个办法中的遍历流程时，曾应用记录下标的办法代替长期list变量tmp，以升高额定的内存开销，但依照提交后果来看，内存节俭无限，而工夫开销上涨较多，揣测与Python的list实现机制无关，故此处保留应用长期变量的办法。

3.is_positive办法，判断一个不蕴含0的子数组的乘积是否为负数，只有判断一下正数的个数是否为偶数即可。

def is_positive(sub_nums):
    negative_count = sub_nums.count(-1)
    if negative_count%2 == 0:
        return True
    else:
        return False

同样验证一下

>>>print(is_positive([1, 1, 1, 1]))
>>>print(is_positive([-1, -1, 1, -1]))
True
False

4.getMaxLenofSub找到一个不蕴含0的子数组里满足条件的最长子数组，入参sub_nums是切分后的一个子数组，它外面没有0，-1的个数不为1。通过先判断一些非凡状况来实现尽早返回。

def getMaxLenofSub(sub_nums):
    len_sub = len(sub_nums)
    # 如果这个子数组自身乘积为正，返回数组长度
    if is_positive(sub_nums): 
        return len_sub
    # 解决非凡状况，子数组长度只有1的时候，肯定只有一个1
    if len(sub_nums) == 1:
        return 1
    # 满足条件的子数组，最长就是子数组的长度
    # 从最大长度开始向下递加，只有找到一个满足条件的子数组,即为最长的子数组
    for l in range(len_sub-1, 0, -1):
        for index in range(len_sub-l+1):
            if is_positive(sub_nums[index:index+l]):
                return l
    return 1

验证一下：

>>>print(getMaxLenofSub([1, 1, 1, 1]))
>>>print(getMaxLenofSub([-1, -1, 1, -1]))
4
3

5.最初是总体的流程，先做数字的转化，而后切分为子数组，而后依照子数组的长度排序，以便前面尽早的完结遍历的流程。最初是遍历所有的子数组，找到符合条件的数组长度。

def getMaxLen(nums):
    # 先把正负整数替换为1和-1
    nums = [format_nums(x) for x in nums]
    # 按0切分为子数组
    ls = cut_by_zero(nums)
    # 按子数组的长度排序
    ls.sort(key=lambda x:len(x),reverse=True)
    
    # 记录下以后最长的满足条件的子数组长度，初始值为0
    max_len_of_all = 0
    # 遍历所有子数组
    for sub_nums in ls:
        # 如果遍历到的子数组的长度小于max_len_of_all
        # 意味着不可能失去更长的符合条件的子数组了
        # 而数组又是按长度排序的，所以能够判定max_len_of_all即为符合条件最大值
        if len(sub_nums) < max_len_of_all:
            return max_len_of_all
        # 从子数组里找出符合条件的最大长度，并和max_len_of_all比拟
        sub_max = getMaxLenofSub(sub_nums)
        if sub_max > max_len_of_all:
            max_len_of_all = sub_max

    return max_len_of_all

验证

题目中提到的几个示例：

>>>nums = [1,-2,-3,4]
>>>getMaxLen(nums)
4

>>>nums = [0,1,-2,-3,-4]
>>>getMaxLen(nums)
3

>>>nums = [-1,-2,-3,0,1] 
>>>getMaxLen(nums)
2

>>>nums = [-1,2]
>>>getMaxLen(nums)
1

>>>nums = [1,2,3,5,-6,4,0,10]
>>>getMaxLen(nums)
4

最初是性能测试用例，长度为10万的数组，找出符合条件的最长子数组长度：

%%time
nums = [1]*100000
nums[3000] = -1
getMaxLen(nums)

CPU times: user 14 ms, sys: 1.27 ms, total: 15.3 ms
Wall time: 15.1 ms

提交

提交到LeetCode的后果如下图所示，每次提交的后果可能会有轻微浮动。

我的Python版本

<code class="Python">>>> import sys
>>> print(sys.version)
3.7.6 (default, Jan  8 2020, 13:42:34) 
[Clang 4.0.1 (tags/RELEASE_401/final)]

喜欢 (0)赏

[搞代码]

分享 (0)