tags: 阿瑜

Day 8: Recap Day [1-7] & Enhance

Day#	Title	Level
1	Day 1: Let's start !	None
2	Day 2: LeetCode 978. Longest Turbulent Subarray	Medium
3	Day 3: LeetCode 995. Minimum Number of K Consecutive Bit Flips	Hard
4	Day 4: LeetCode 995. Minimum Number of K Consecutive Bit Flips(v2)	Hard
5	Day 5: LeetCode 88. Merge Sorted Array	Easy
6	Day 6: LeetCode 54. Spiral Matrix	Medium
7	Day 7: LeetCode 485. Max Consecutive Ones	Easy

Enhance

• Day 2: LeetCode 978. Longest Turbulent Subarray

  • 思路(from Discuss)

    • either up or down begin

      • 🔼 🔽 🔼 🔽 …
      • 🔽 🔼 🔽 🔼 …

    • 繼承上一次(inc/dec)的數量，再加一

  • 程式碼

    ​​​​​​​​class Solution:
    ​​​​​​​​    def maxTurbulenceSize(self, arr: List[int]) -> int:
    ​​​​​​​​        inc = 1
    ​​​​​​​​        dec = 1
    ​​​​​​​​        res = 1
    ​​​​​​​​        for i in range(1,len(arr)):
    ​​​​​​​​            if arr[i] > arr[i-1]:
    ​​​​​​​​                inc = dec+1
    ​​​​​​​​                dec = 1
    ​​​​​​​​            elif arr[i] < arr[i-1]:
    ​​​​​​​​                dec = inc+1
    ​​​​​​​​                inc = 1
    ​​​​​​​​            else:
    ​​​​​​​​                inc = 1
    ​​​​​​​​                dec = 1
    ​​​​​​​​            print("i-inc-dec:",i,inc,dec)    
    ​​​​​​​​            #res = max(inc,dec)
    ​​​​​​​​            res = max([inc,dec,res])
    ​​​​​​​​            print("res:",res)
    ​​​​​​​​        return res    
    
    
    

  • Reference

    • 神人解-Java O(N) time O(1) space

What's more?

1. 每月挑戰(2021.09.22)

   • (Medium) LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

   • 題意

     • 求unique的最長長度
     • unique's element 怎麼組成?
       Ans: 自己碰其他element所組成
       1. 自己中的每個character需unique
       2. 碰其他時也需unique

   • 思路

     • List 中的每個element(set)都是不同組合，在組合中找最長長度
     • Python-set() Check 自己中是否有重複element
     • 碰前的Check:是否有一樣的character→使用&
     • 碰(concate)所用的運算子|
     • Reference
       • 花花醬-YT圖解
         

   • 程式碼

     ​​​​​​​​class Solution:
     ​​​​​​​​def maxLength(self, arr: List[str]) -> int:
     ​​​​​​​​    A = [set()] # set() => {}
     ​​​​​​​​    for a in arr:
     ​​​​​​​​        if len(set(a))!=len(a):
     ​​​​​​​​            continue
     
     ​​​​​​​​        for element in A[:]:
     ​​​​​​​​            if set(a)&element:
     ​​​​​​​​                continue
     ​​​​​​​​            A.append(set(a)|element)    
     ​​​​​​​​    print(A)            
     ​​​​​​​​    maxLen = (-1)            
     ​​​​​​​​    for _ in A:
     ​​​​​​​​        if len(_)>maxLen:
     ​​​​​​​​            maxLen = len(_)
     ​​​​​​​​    return  maxLen               
     

2. 目的刷
   • (Easy) LeetCode 104. Maximum Depth of Binary Tree
   • 思路
     • BFS-Queue
       • Initial: Queue 先加root
       1. 直到Queue為空
          • ans(Heigh)++
       2. Iterate(遍歷)每一層節點
          • 移除遍歷節點
          • 加入遍歷節點的child節點
   • We+夥伴
     • soft解(C language)
     • Casey解(Python)
   • 其他
     • Iterative Method to find Height of Binary Tree

What's Next?

面試:
Find Good Job!