Day 2: LeetCode 978. Longest Turbulent Subarray

Tag:随意刷-每月挑战(2021.09.15)

Source:

978. Longest Turbulent Subarray

1.题意:

In: arr
Out: 最长turbulent subarray

符合条件1或是条件2即是turbulent.

条件1:
arr 中奇数位置(前)的值要比偶数位置(後)的值大
arr 中偶数位置(前)的值要比奇数位置(後)的值小
Or
条件2:
arr 中偶数位置(前)的值要比奇数位置(後)的值大
arr 中奇数位置(前)的值要比偶数位置(後)的值小

Note:

A subarray is a contiguous part of array.

2.思路:

图解:

https://ithelp.ithome.com.tw/upload/images/20210917/201115160VCA5eYAtz.png
https://ithelp.ithome.com.tw/upload/images/20210917/201115166NdtjF5H98.png

作法:

  • 分两个部分:
    • 第一个部分:遍历arr,检查目前所在的index,是even index还是odd index。
      • 无论是even index的话或是odd index的话,
        藉由检查符合条件1或是条件2,来设定状态.
      • 与上次(Previous)纪录状态(Status)是否相同,
        • 相同的话(或是上一状态属於初始状态): 将目前状态对应的Counter++,
          维持/切换成 目前条件的对应状态;
        • 不同的话: Reset成 初始Counter以及更新Status成 另一状态;
      • 过程即纪录最长的turbulent
    • 第二个部分:
      • 两个条件各有其存的最长turbulent(c1_max,c2_max),取大回传(max(c1_max,c2_max))
      • 如果c1_max与c2_max相等,
        • 没有符合条件1或条件2,回传1
        • 有则择1(c1_max,c2_max)回传即可

3.程序码:

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        
        c1 = 1 
        c2 = 1 
        c1_max = (-1)
        c2_max = (-1)
        
        if len(arr)==1:
            return 1
        
        status = (-1)
        
        for i in range(len(arr)-1):
            
            print("i-Status:",i,status)
            print("c1_max:",c1_max)
            print("c2_max:",c2_max)
            # if is even
            if i%2==0:
                if arr[i]>arr[i+1]:
                    if status==2 or status==(-1): 
                        c2+=1
                        status = 2
                    else:
                        c2+=1
                        c1 = 1
                        status = (2)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                elif arr[i]<arr[i+1]:
                    if status==1 or status==(-1): 
                        c1+=1
                        status = 1
                    else:
                        c1+=1
                        c2 = 1
                        status = (1)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                else:
                    
                    # end of subarry
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2
                    c1 = 1
                    c2 = 1
                    status = (-1)
            # if is odd
            elif i%2!=0:
                if arr[i]<arr[i+1]:
                    if status==2 or status==(-1): 
                        c2+=1
                        status = 2
                    else:
                        c2+=1
                        c1 = 1
                        status = (2)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:

                        c2_max = c2                        
                elif arr[i]>arr[i+1]:
                    if status==1 or status==(-1): 
                        c1+=1
                        status = 1
                    else:
                        c1+=1                        
                        c2 = 1  
                        status = (1)
                    if c1 > c1_max and status==1:
                        c1_max = c1
                    if c2 > c2_max and status==2:
                        c2_max = c2                        
                else:
                    status = (-1)
                    if c1 > c1_max:
                        c1_max = c1
                    if c2 > c2_max:
                        c2_max = c2
                    c1 = 1
                    c2 = 1
                    
        if c1_max > c2_max:
            print("c1")
            return c1_max
        elif c1_max == c2_max and c1_max==(-1):
            print("the same")
            return 1

        else: #c2_max > c1_max or (c1_max == c2_max and c1_max!=(-1))
            print("c2")
            return c2_max

Result:

https://ithelp.ithome.com.tw/upload/images/20210917/201115164ojz22iRqk.png

Level:Medium

相关推荐:

LeetCode 付费版在坑钱? Is LeetCode Premium Worth It in 2021?


<<:  群雄割据还是一统天下

>>:  Day02 工欲善其事必先利其器

重温-基本&UI

创立一个属於自己的App,那就需要两个必须的部份,设备与知识。 自己所使用的设备为Apple Mac...

ASP.NET MVC 从入门到放弃(Day24)-MVC删除资料介绍

接下来讲讲删除 部分... 在查询的View那边可以看到下方程序码 @Html.ActionLink...

20210208-台湾菁英圆桌分享会 (Elite Round Table in Taiwan)

这是我个人的考上Cissp的分享会,其中分享如何有效的念书,提供想考Cissp的朋友一些参考。 ...

Uniform - shader 之参数

大家好,我是西瓜,你现在看到的是 2021 iThome 铁人赛『如何在网页中绘制 3D 场景?从 ...

AE卷轴制作2-Day3

虽然我一直知道Null是一个空物体, 可以让物体多一个中心点,但透过练习才知道, 他可以中央控管涂层...