iT邦幫忙

2021 iThome 鐵人賽

DAY 2
1
自我挑戰組

FRIENDS系列 第 2

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?


上一篇
Day 1: Let's start !
下一篇
Day 3: LeetCode 995. Minimum Number of K Consecutive Bit Flips
系列文
FRIENDS30

1 則留言

1
soft_soft
iT邦新手 5 級 ‧ 2021-09-17 15:24:55

好厲害呀

阿瑜 iT邦新手 2 級 ‧ 2021-09-17 16:23:02 檢舉

Really?!

我要留言

立即登入留言