12/20/2022 Two Leetcode Problems

[box-lin]

• 841. Keys and Rooms
• 978. Longest Turbulent Subarray

Instruction: Participant please comment with your solutions provided with your explanation below! Go leetcode.

[137thphxx]

841.

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        total_room = len(rooms)
        visited = set()
        to_visit = [0]

        while to_visit:
            room = to_visit.pop()
            if room in visited:
                continue
            visited.add(room)
            to_visit.extend(rooms[room])       
        return len(visited) == total_room

978.

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        length = len(arr)
        result = 0
        temp = 0
        for i in range(length):
            if i > 1 and (arr[i-2] > arr[i-1] < arr[i] or arr[i-2] < arr[i-1] > arr[i]):
                temp += 1
            elif i > 0 and (arr[i-1] != arr[i]):
                temp = 2
            else:
                temp = 1  
            result = max(temp, result)

        if length == 1:
            result = 1    
        return result

[box-lin]

# 841
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(idx):
            visited.add(idx)
            for k in rooms[idx]:
                if k in visited:
                    continue
                dfs(k)
        visited = set() 
        dfs(0)
        return len(visited) == len(rooms)

# 978 
class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        l, r = 0, 0
        ans = 1
        if n == 1: return ans
        while r < n:
            while l < n - 1 and arr[l] == arr[l+1]:
                l += 1
            r = max(r, l)
            while r > 0 and r < n - 1 and (arr[r-1] > arr[r] < arr[r+1] or arr[r-1] < arr[r] > arr[r+1]):
                r += 1
            ans=max(ans, r - l + 1)
            l = r # 如果[r+1]不符合l从r开始。。。 也有可能从r+1开始如何arr[r] == arr[r+1] 但是这部分line8解决
            r += 1
        return ans