# Online Assesement 2021-07-04
###### tags: `leetcode` `assesement`

* 兩題題目，一個小時，兩題 easy，都有 follow up

## :memo: 第一題


## :memo: 題意
* :medal: 題目很簡單，就是問你他給你的數，可不可為 2＾x 次方。

## :memo: My solution
* :medal: **思考一**: 就一直 /2 然後用 %2 判斷是不是有餘數不等於零的情況。

## :memo: Code

class Solution(object):
    def isPowerOfTwo(self, n):
        if n == 0:
            return False
        while n % 2 == 0:
            n /= 2
        return n == 1

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

## :memo: My solution2
* :medal: **思考一**: 如果是2^n 次方，那這個數的 binary 一定是 100000.....，所以還可以這樣寫。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0: return False
        
        binn = bin(n)
        for i in range(2,len(binn)):
            if i == 2 and binn[i] != '1':
                return False
            elif i != 2 and binn[i] != '0':
                return False
        
        return True

## :memo: follow up solution
* :medal: **思考一**: 如果是 2^n 次方，舉例來說 8 代表是從 '111' => '1000'，因此 n & (n-1) 如果等於 0 的話，一定是 2^n 次方，這個一定要記在腦海裡要向反射動作一樣，做過蠻多應用這觀念的題目了，但我常常還是想不到。

class Solution(object):
    def isPowerOfTwo(self, n):
        if n == 0:
            return False
        return n & (n - 1) == 0

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

## :memo: 第二題


## :memo: 題意
* :medal: 給你一個 numslist，然後這個 list 如果有 n 長度，那裡面應該要有 1~n 的數字，如果沒有這些數字的話請 return。

## :memo: My solution
* :medal: **思考一**: 使用 hash table 將應該要有的數字放到這個 hash table，然後forloop numslist，如果有在 hash table 裡的則 remove 裡面的的數字，最後return hash table，這邊我用 set 來做 hash table。

## :memo: Code

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        

        dset = set([n for n in range(1, len(nums)+1)])

        
        for i in nums:
            if i in dset:
                dset.remove(i)
                
                
        return list(dset)

## :memo: BigO
* 時間複雜度: O(len(nums))
* 空間複雜度: O(len(nums))

## :memo: leetcode follow up solution
* :medal: **限制**: 如果不能額外空間且時間複雜度為 n 要怎麼實作？

class Solution(object):
    def findDisappearedNumbers(self, nums):

        for i in range(len(nums)):
   
            new_index = abs(nums[i]) - 1

            if nums[new_index] > 0:
                nums[new_index] *= -1

        result = []    

        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                result.append(i)
                
        return result      

## :memo: BigO
* 時間複雜度: O(len(nums))。
* 空間複雜度: O(1)

## :memo: 真正操作的時間
* 總共 15 分鐘。