# Online Assesement 2021-06-11 (Google)
###### tags: `leetcode` `google` `assesement`

* 兩題題目，一個小時，這兩題我都沒有寫過。

## :memo: 第一題


## :memo: 題意
* :medal: 我一開始有點看不懂題目，**good number** 的定義看清楚，一個數字裡面的每個數字被**旋轉180度後**，會變成另一個數字那就是好數字，那如果給你數字 n，請你找出 1~n 裡面有幾個好數字。

* 他有舉例
* 0,1,8: 轉了之後不變
* 2: 變成 5
* 5: 變成 2
* 6: 變成 9
* 9: 變成 6

## :memo: My solution
* :medal: **思考一**: 所以這個數字至少有一個 [2,5,9,6]，其他是 [0,1,8]，就會成立。

class Solution:
    def rotatedDigits(self, n: int) -> int:
        
        may = ['0','1','8']
        good = ['2','5','6','9']
        
        ans = 0
        for i in range(1, n+1):
            mayc = 0
            goodc = 0
            for char in str(i):
                if char in may:
                    mayc += 1
                elif char in good:
                    goodc += 1
                else:
                    break
                    
            if len(str(i)) == mayc + goodc and goodc > 0:
                ans += 1
            
        return ans

## :memo: 檢討
* 這個題目我第一次 submit 失敗是在程式第八行那邊，我沒注意到是從1開始。
* 然後 may 和 good 可以改成 dictionary，速度會更快。
## :memo: better solution

class Solution:
    def rotatedDigits(self, n: int) -> int:
        
        may = {'0':True, '1':True, '8': True}
        good = {'2':True, '5':True, '6': True, '9': True}
        
        ans = 0
        for i in range(1, n+1):
            mayc = 0
            goodc = 0
            for char in str(i):
                if char in may:
                    mayc += 1
                elif char in good:
                    goodc += 1
                else:
                    break
                    
            if len(str(i)) == mayc + goodc and goodc > 0:
                ans += 1
            
        return ans

## :memo: BigO
* 時間複雜度: O(n)
* 空間複雜度: O(1)

## :memo: 第二題


## :memo: 題意
* :medal: 找一個位置可以讓 alex 與其他人離的最遠的距離，那距離是多少。

## :memo: My solution
* :medal: **思考一**: 那我就是紀錄 0 的 list。
* :medal: **思考二**: 如果有這種 [0,0,0,0,0,0,1,0,0,0,0,0,0,0,1]，就要選 index = 0 ~ 5 的這個 list 或是 [1,0,0,0,0,0,1,0,0,0,0]，因此要記錄只有 0 的 list 開始位置和最後的位置。

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        import math
        
        first = 0 
        last = 0 
        seat = 0
        ans = []
        
        for index, value in enumerate(seats):
            if value == 0 and seat:
                seat += 1
            elif value == 0 and not seat:
                first = index
                seat += 1
            elif index and value == 1 and seats[index-1] == 0:
                last = index - 1
                ans.append([first, last, seat])
                first = 0
                last = 0
                seat = 0
 
        if seat:
            last = index
            ans.append([first, last, seat])
            
        final = 0
        for a,b,c in ans:
            if a == 0 or b == len(seats) - 1:
                final = max(c, final)
            else:
                final = max(math.ceil(c/2), final)
                
        return final

## :memo: BigO
* 時間複雜度: O(n)
* 空間複雜度: O(1)

## :memo: 真正操作的時間
* 每題都花 25 分鐘，總共 50 分鐘。第一題應該要花更少時間。