[已解决]Python：每日一题 386

zltzlt

今天的题目：

给定一个整数数组，判断这个数组中是否有 132 模式的子序列。

一个 132 模式的子序列 a[m], a[n], a[o] 被定义为：m < n < o 并且 a[m] < a[o] < a[n] 。

注意：子序列在原数组中不一定是连续的。

示例 1：

输入：[1, 2, 3, 4]
输出：False

示例 2：

输入：[3, 1, 4, 2]
输出：True
解释：序列中有 1 个 132 模式的子序列：[1, 4, 2] 。

示例 3：

输入：[-1, 3, 2, 0]
输出：True
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0] 。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-4-29 14:40:15

跑起来估计会比较慢

def f386(nums):
    if len(set(nums)) <= 2:
        return False
    n = len(nums)
    left = nums[0]
    for i in range(1, n - 2):
        left = min(left, nums[i])
        if left < max(nums[i:]):
            mid, right = i + 1, n - 1
            while mid < right:
                while mid < right and nums[right] < left:
                    right -= 1
                while mid < right and nums[mid] <= nums[right]:
                    mid += 1
                if mid < right:
                    return True
    return False

来个双针

def f386(nums):
    n = len(nums)
    if len(set(nums)) <= 2:
        return False    
    left, right = 0, n - 1
    while left + 1 < right:
        if nums[left] < nums[right] < max(nums[left + 1:right]):
            return True
        if nums[left] >= nums[right]:
            left += 1
        elif nums[left] < nums[right]:
            right -= 1
            
    return False

跳转到最佳答案楼层

Twilight6

def func(array):
    for i1 in array:
        temp = array[array.index(i1):]
        for i2 in temp:
            temp = array[array.index(i2):]
            for i3 in temp:
                if i1 < i3 < i2 :
                    return True
    return False

嘿嘿，写的丑，不过做出来很开心

1815702237

原谅我的数学能力不足。。

weiter

占楼

weiter

看懂了……但是不会

永恒的蓝色梦想

占楼

March2615

绕远路了，差点没绕回来

def daily386(nums: list)->bool:
    # 解题思路：
    # 满足132模式 -> 最大值在中间且后面的值大于前面的值 -> 重点是找到132中的2
    # 方法肯定是遍历，固定m,n，去找到合适的o
    # m肯定最小，用一个数组m[]记录前面数的最小值
    # 然后从数组右边开始遍历，检查是否满足m[i] < nums[i] < max(num[j:i]) j为最小值在nums中的索引值
    # 找j比较困难（太麻烦了，坑了好久），所以考虑用栈，到最小值的位置就弹出更新最小值
    if len(nums) < 3:
        return False
    m = [nums[0]]
    for i in range(1, len(nums)):
        m.append(min(m[-1], nums[i]))

    stack = []  # stack[]中储存a[o]
    for i in range(len(nums)-1, -1,-1):
        while stack and stack[-1] <= m[i]:  # a[o] < a[m]的情况排除
            stack.pop()
        # 此时一定满足stack[-1] > m[i] 即 a[o] > a[m]
        if stack and stack[-1] < nums[i]: # a[n] > a[o]
            return True
        stack.append(nums[i])
    return False

kinkon

跑起来估计会比较慢

def f386(nums):
    if len(set(nums)) <= 2:
        return False
    n = len(nums)
    left = nums[0]
    for i in range(1, n - 2):
        left = min(left, nums[i])
        if left < max(nums[i:]):
            mid, right = i + 1, n - 1
            while mid < right:
                while mid < right and nums[right] < left:
                    right -= 1
                while mid < right and nums[mid] <= nums[right]:
                    mid += 1
                if mid < right:
                    return True
    return False

来个双针

def f386(nums):
    n = len(nums)
    if len(set(nums)) <= 2:
        return False    
    left, right = 0, n - 1
    while left + 1 < right:
        if nums[left] < nums[right] < max(nums[left + 1:right]):
            return True
        if nums[left] >= nums[right]:
            left += 1
        elif nums[left] < nums[right]:
            right -= 1
            
    return False

TJBEST

def fun386(a):
    M = len(a)
    if M < 3:
        return False
    for index in range(1,M-1):
        temp = a[index]
        left = min(a[:index])
        if left < temp:
            rightGroup = [each for each in a[(index + 1):] if (each < temp) and (each > left)]
            if rightGroup != []:
                return True
            else:
                pass
        else:
            pass
    return False

kkk999de

def f386(l:list):
    import itertools
    for ls in itertools.combinations(l, 3):
        if ls[0] < ls[2] < ls[1]:
            return True
    return False

风魔孤行者

def f(s):
    if len(s)<3:
        return False
    else:
        m = max(s)
        if m in s[1:-1]:
            list1 = [index+1 for index,i in enumerate(s[1:-1]) if i == m]
            for each in list1:
                right = s[each+1:]
                right = sorted(set(right))
                if max(right) == m:
                    right = right[:-1]
                if right != []:
                    if min(s[:each])<max(right):
                        return True
            while m in s:
                s.remove(m)
            return f(s)
        else:
            s.remove(m)
            return f(s)

ouyunfu

先来个暴力的

from itertools import combinations as cb
def f386(ls):
    for i in cb(range(len(ls)),3):
        if ls[i[1]]>ls[i[2]]>ls[i[0]]:
            return True
    return False

moonishine

def f386(s):
    for i1 in range(0,len(s)-2):
        a1 = s[i1]
        
        for i2 in range(i1+1,len(s)-1):
            a2 = s[i2]
            
            for i3 in range(i2+1,len(s)):
                a3 = s[i3]
                
                if a1<a3<a2:
                 return True
    return False

刚入门的宝宝

xiangjianshinan

March2615 发表于 2020-4-29 14:15
绕远路了，差点没绕回来

看了题目！ 研究了答案。 仍然一脸蒙蔽~~~~~~~~

谢谢大佬的解题思路。

江少

def f386(L):
    for m in range(0,len(L)-2):
        a1 = L[m]
        for n in range(m+1,len(L)-1):
            a2 = L[n]
            for o in range(n+1,len(L)):
                a3 = L[o]
                if a1 < a3 < a2:
                    return True
    return False

还没入门的小宝宝

sjtuszy

def fun386(list1):
    while len(list1) >= 3:
        max_num, index_max = max(list1), list1.index(max(list1))
        try:
            left_min, right_max = min(list1[:index_max]), max(list1[index_max+1:])
            if max_num > right_max > left_min:
                return True
            else:
                list1.remove(max_num)
        except:
            list1.remove(max_num)
    return False

whosyourdaddy

def func386(n):
    m = len(n)
    minx = n[0]
    maxx = n[1] 
    for i in range(1,m-1):
        if n[i] < minx:
            minx = n[i]
        if n[i+1] > maxx:
            maxx = n[i+1]
        for j in range(i+1,m):
            if n[j]<maxx and n[j]>minx:
                print(maxx,minx,n[j])
                return True
    return False

旅途Z

最近好像总是想到递归的方法

def find132(array):
    length = len(array)
    if length < 3:
        return False
    # 找到第一个最大值，作为中间的3
    max_num = max(array)
    max_index = array.index(max_num)
    left_cp = array[:max_index]
    right_cp = array[max_index+1:]
    if len(left_cp) == 0:
        return find132(right_cp)
    # 去除右边部分重复的最大值，因为它们是3不是2 
    while max_num in right_cp:
        right_cp.remove(max_num)
    if len(right_cp) == 0:
        return find132(left_cp)
    left = min(left_cp)
    right = max(right_cp)
    # 若右边部分均小于左边，则任何同时包含两部分的元素的子序列都不可能是132 只可能是123 213 321 312 231 
    if left >= right:
        return find132(array[:max_index]) or find132(array[max_index+1:])
    else:
        return True

zltzlt

Twilight6 发表于 2020-4-29 14:05
嘿嘿，写的丑，不过做出来很开心

暴力方法，效率较低哦

findland

def f386(s):
    if len(set(s))<3:
        return False
    else:
        if max(s) ==s[0]:
            s.pop(0)
            return f386(s)
        elif max(s) == s[-1]:
            s.pop(-1)
            return f386(s)
        else:
            return True





if __name__ == "__main__":
    s = [1, 2, 3, 4]
    print(f386(s))
    s = [3, 1, 4, 2]
    print(f386(s))
    s = [-1, 3, 2, 0]
    print(f386(s))
    s = [3,1,2]
    print(f386(s))