Python：每日一题 386,Python交流,编程语言专区,鱼C论坛

zltzlt 发表于 2020-4-29 14:00:25

Python：每日一题 386

今天的题目：

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

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

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

示例 1：

输入：
输出：False
示例 2：

输入：
输出：True
解释：序列中有 1 个 132 模式的子序列：。
示例 3：

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

{:10_298:}欢迎大家一起答题！{:10_298:}

Twilight6 发表于 2020-4-29 14:05:42

本帖最后由 Twilight6 于 2020-4-29 14:25 编辑

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

嘿嘿，写的丑，不过做出来很开心{:10_279:}

1815702237 发表于 2020-4-29 14:07:25

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

weiter 发表于 2020-4-29 14:09:10

占楼{:10_256:}

weiter 发表于 2020-4-29 14:10:15

看懂了……但是不会{:10_266:}

永恒的蓝色梦想 发表于 2020-4-29 14:14:59

占楼

March2615 发表于 2020-4-29 14:15:04

本帖最后由 March2615 于 2020-4-29 15:27 编辑

绕远路了，差点没绕回来

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

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

kinkon 发表于 2020-4-29 14:40:15

本帖最后由 kinkon 于 2020-4-30 08:01 编辑

跑起来估计会比较慢
def f386(nums):
if len(set(nums)) <= 2:
   return False
n = len(nums)
left = nums
for i in range(1, n - 2):
   left = min(left, nums)
   if left < max(nums):
         mid, right = i + 1, n - 1
         while mid < right:
            while mid < right and nums < left:
               right -= 1
            while mid < right and nums <= nums:
               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 < nums < max(nums):
         return True
   if nums >= nums:
         left += 1
   elif nums < nums:
         right -= 1

return False

TJBEST 发表于 2020-4-29 15:35:40

本帖最后由 TJBEST 于 2020-4-29 18:36 编辑

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

kkk999de 发表于 2020-4-29 16:41:19

本帖最后由 kkk999de 于 2020-4-29 16:43 编辑

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

风魔孤行者 发表于 2020-4-29 16:56:40

def f(s):
if len(s)<3:
   return False
else:
   m = max(s)
   if m in s:
         list1 = ) if i == m]
         for each in list1:
            right = s
            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 发表于 2020-4-29 17:23:03

先来个暴力的from itertools import combinations as cb
def f386(ls):
for i in cb(range(len(ls)),3):
if ls]>ls]>ls]:
return True
return False

moonishine 发表于 2020-4-29 17:40:31

def f386(s):
for i1 in range(0,len(s)-2):
   a1 = s

   for i2 in range(i1+1,len(s)-1):
         a2 = s

         for i3 in range(i2+1,len(s)):
            a3 = s

            if a1<a3<a2:
            return True
return False

刚入门的宝宝{:10_266:}

xiangjianshinan 发表于 2020-4-29 18:33:17

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

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

谢谢大佬的解题思路。{:7_112:}

江少发表于 2020-4-29 19:45:12

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

还没入门的小宝宝{:10_266:}

sjtuszy 发表于 2020-4-29 21:11:32

本帖最后由 sjtuszy 于 2020-4-30 05:19 编辑

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)
         if max_num > right_max > left_min:
            return True
         else:
            list1.remove(max_num)
   except:
         list1.remove(max_num)
return False

whosyourdaddy 发表于 2020-4-30 00:11:49

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

旅途Z 发表于 2020-4-30 11:14:06

本帖最后由旅途Z 于 2020-4-30 11:16 编辑

最近好像总是想到递归的方法
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
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)
else:
   return True

zltzlt 发表于 2020-4-30 13:23:46

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

暴力方法，效率较低哦

findland 发表于 2020-4-30 15:22:18

本帖最后由 findland 于 2020-4-30 15:41 编辑

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

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

页: [1] 2

鱼C论坛's Archiver

Python：每日一题 386