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.思路:

圖解:

作法:

• 分兩個部分:
  • 第一個部分:遍歷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:

Level:Medium

相關推薦:

LeetCode 付費版在坑錢? Is LeetCode Premium Worth It in 2021?