乐趣区

关于python:Python题解LeetCode-No1567

jiezi

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 版本

>>> import sys
>>> print(sys.version)
3.7.6 (default, Jan  8 2020, 13:42:34) 
[Clang 4.0.1 (tags/RELEASE_401/final)]
退出移动版