[已解决]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

跑起来估计会比较慢

1. def f386(nums):
   
2.     if len(set(nums)) <= 2:
   
3.         return False
   
4.     n = len(nums)
   
5.     left = nums[0]
   
6.     for i in range(1, n - 2):
   
7.         left = min(left, nums[i])
   
8.         if left < max(nums[i:]):
   
9.             mid, right = i + 1, n - 1
   
10.             while mid < right:
    
11.                 while mid < right and nums[right] < left:
    
12.                     right -= 1
    
13.                 while mid < right and nums[mid] <= nums[right]:
    
14.                     mid += 1
    
15.                 if mid < right:
    
16.                     return True
    
17.     return False

复制代码

来个双针

1. def f386(nums):
   
2.     n = len(nums)
   
3.     if len(set(nums)) <= 2:
   
4.         return False   
   
5.     left, right = 0, n - 1
   
6.     while left + 1 < right:
   
7.         if nums[left] < nums[right] < max(nums[left + 1:right]):
   
8.             return True
   
9.         if nums[left] >= nums[right]:
   
10.             left += 1
    
11.         elif nums[left] < nums[right]:
    
12.             right -= 1
    
13.             
    
14.     return False

复制代码

跳转到最佳答案楼层

Twilight6

1. def func(array):
   
2.     for i1 in array:
   
3.         temp = array[array.index(i1):]
   
4.         for i2 in temp:
   
5.             temp = array[array.index(i2):]
   
6.             for i3 in temp:
   
7.                 if i1 < i3 < i2 :
   
8.                     return True
   
9.     return False

复制代码

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

1815702237

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

weiter

占楼

weiter

看懂了……但是不会

永恒的蓝色梦想

占楼

March2615

绕远路了，差点没绕回来

1. def daily386(nums: list)->bool:
   
2.     # 解题思路：
   
3.     # 满足132模式 -> 最大值在中间且后面的值大于前面的值 -> 重点是找到132中的2
   
4.     # 方法肯定是遍历，固定m,n，去找到合适的o
   
5.     # m肯定最小，用一个数组m[]记录前面数的最小值
   
6.     # 然后从数组右边开始遍历，检查是否满足m[i] < nums[i] < max(num[j:i]) j为最小值在nums中的索引值
   
7.     # 找j比较困难（太麻烦了，坑了好久），所以考虑用栈，到最小值的位置就弹出更新最小值
   
8.     if len(nums) < 3:
   
9.         return False
   
10.     m = [nums[0]]
    
11.     for i in range(1, len(nums)):
    
12.         m.append(min(m[-1], nums[i]))
    
13. 
    
14.     stack = []  # stack[]中储存a[o]
    
15.     for i in range(len(nums)-1, -1,-1):
    
16.         while stack and stack[-1] <= m[i]:  # a[o] < a[m]的情况排除
    
17.             stack.pop()
    
18.         # 此时一定满足stack[-1] > m[i] 即 a[o] > a[m]
    
19.         if stack and stack[-1] < nums[i]: # a[n] > a[o]
    
20.             return True
    
21.         stack.append(nums[i])
    
22.     return False

复制代码

kinkon

跑起来估计会比较慢

1. def f386(nums):
   
2.     if len(set(nums)) <= 2:
   
3.         return False
   
4.     n = len(nums)
   
5.     left = nums[0]
   
6.     for i in range(1, n - 2):
   
7.         left = min(left, nums[i])
   
8.         if left < max(nums[i:]):
   
9.             mid, right = i + 1, n - 1
   
10.             while mid < right:
    
11.                 while mid < right and nums[right] < left:
    
12.                     right -= 1
    
13.                 while mid < right and nums[mid] <= nums[right]:
    
14.                     mid += 1
    
15.                 if mid < right:
    
16.                     return True
    
17.     return False

复制代码

来个双针

1. def f386(nums):
   
2.     n = len(nums)
   
3.     if len(set(nums)) <= 2:
   
4.         return False   
   
5.     left, right = 0, n - 1
   
6.     while left + 1 < right:
   
7.         if nums[left] < nums[right] < max(nums[left + 1:right]):
   
8.             return True
   
9.         if nums[left] >= nums[right]:
   
10.             left += 1
    
11.         elif nums[left] < nums[right]:
    
12.             right -= 1
    
13.             
    
14.     return False

复制代码

TJBEST

1. def fun386(a):
   
2.     M = len(a)
   
3.     if M < 3:
   
4.         return False
   
5.     for index in range(1,M-1):
   
6.         temp = a[index]
   
7.         left = min(a[:index])
   
8.         if left < temp:
   
9.             rightGroup = [each for each in a[(index + 1):] if (each < temp) and (each > left)]
   
10.             if rightGroup != []:
    
11.                 return True
    
12.             else:
    
13.                 pass
    
14.         else:
    
15.             pass
    
16.     return False

复制代码

kkk999de

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

复制代码

风魔孤行者

1. def f(s):
   
2.     if len(s)<3:
   
3.         return False
   
4.     else:
   
5.         m = max(s)
   
6.         if m in s[1:-1]:
   
7.             list1 = [index+1 for index,i in enumerate(s[1:-1]) if i == m]
   
8.             for each in list1:
   
9.                 right = s[each+1:]
   
10.                 right = sorted(set(right))
    
11.                 if max(right) == m:
    
12.                     right = right[:-1]
    
13.                 if right != []:
    
14.                     if min(s[:each])<max(right):
    
15.                         return True
    
16.             while m in s:
    
17.                 s.remove(m)
    
18.             return f(s)
    
19.         else:
    
20.             s.remove(m)
    
21.             return f(s)

复制代码

ouyunfu

先来个暴力的

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

复制代码

moonishine

1. def f386(s):
   
2.     for i1 in range(0,len(s)-2):
   
3.         a1 = s[i1]
   
4.         
   
5.         for i2 in range(i1+1,len(s)-1):
   
6.             a2 = s[i2]
   
7.             
   
8.             for i3 in range(i2+1,len(s)):
   
9.                 a3 = s[i3]
   
10.                
    
11.                 if a1<a3<a2:
    
12.                  return True
    
13.     return False
    

复制代码

刚入门的宝宝

xiangjianshinan

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

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

谢谢大佬的解题思路。

江少

1. def f386(L):
   
2.     for m in range(0,len(L)-2):
   
3.         a1 = L[m]
   
4.         for n in range(m+1,len(L)-1):
   
5.             a2 = L[n]
   
6.             for o in range(n+1,len(L)):
   
7.                 a3 = L[o]
   
8.                 if a1 < a3 < a2:
   
9.                     return True
   
10.     return False
    

复制代码

还没入门的小宝宝

sjtuszy

1. def fun386(list1):
   
2.     while len(list1) >= 3:
   
3.         max_num, index_max = max(list1), list1.index(max(list1))
   
4.         try:
   
5.             left_min, right_max = min(list1[:index_max]), max(list1[index_max+1:])
   
6.             if max_num > right_max > left_min:
   
7.                 return True
   
8.             else:
   
9.                 list1.remove(max_num)
   
10.         except:
    
11.             list1.remove(max_num)
    
12.     return False

复制代码

whosyourdaddy

1. def func386(n):
   
2.     m = len(n)
   
3.     minx = n[0]
   
4.     maxx = n[1]
   
5.     for i in range(1,m-1):
   
6.         if n[i] < minx:
   
7.             minx = n[i]
   
8.         if n[i+1] > maxx:
   
9.             maxx = n[i+1]
   
10.         for j in range(i+1,m):
    
11.             if n[j]<maxx and n[j]>minx:
    
12.                 print(maxx,minx,n[j])
    
13.                 return True
    
14.     return False

复制代码

旅途Z

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

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

复制代码

zltzlt

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

暴力方法，效率较低哦

findland

1. def f386(s):
   
2.     if len(set(s))<3:
   
3.         return False
   
4.     else:
   
5.         if max(s) ==s[0]:
   
6.             s.pop(0)
   
7.             return f386(s)
   
8.         elif max(s) == s[-1]:
   
9.             s.pop(-1)
   
10.             return f386(s)
    
11.         else:
    
12.             return True
    
13. 
    
14. 
    
15. 
    
16. 
    
17. 
    
18. if __name__ == "__main__":
    
19.     s = [1, 2, 3, 4]
    
20.     print(f386(s))
    
21.     s = [3, 1, 4, 2]
    
22.     print(f386(s))
    
23.     s = [-1, 3, 2, 0]
    
24.     print(f386(s))
    
25.     s = [3,1,2]
    
26.     print(f386(s))
    
27. 
    

复制代码