那最後兩天，我們來做幾個LeetCode簡單的練習題，可以順便增加信心，其他大家自行去挑戰，解法有很多，其他人的方法有很大的機會會比我的好~:
Linked List:
LeetCode 206. Reverse Linked List
這個問題是說，給定一個singly linked list (它已經寫好了，這個instance叫做head，回傳一個reversed list)。它給的示意圖像這樣: Input: head=[1,2,3,4,5], output: [5,4,3,2,1]，看起來像list其實不是，就是個linked list，否則你還要先把這個list做成linked list才能pass。(可以上去自己看看題目) ，那想法就可以是，你必須把所有node的next改成前一個值，所以你需要有個變數在暫存下一個值，一個變數在暫存現在的值，然後對每一個點做更改就行惹，下面的code要在LeetCode裡面跑才行，在VSCode裡跑會不work:

#這邊只是告訴你你在ListNode可以用的attribute有哪些(告訴你他的ListNode怎麼設的) 
#class ListNode:
#    def __init__(self, val=0, next=None):
#        self.val = val
#        self.next = next
        
class Solution:

# 這裡Optional[ListNode]的意思是，head的type可以是ListNode或是None
# -> Optional[ListNode]的意思是，回傳的內容可以是也可以是ListNode或是None
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        newlist=None
        current=head
        while current:
            temp=current.next
            current.next=newlist
            newlist=current
            current=temp
        return newlist

Queue:
LeetCode 225 Implement Stack using Queues.
這邊看起來是說是要用deque製作stack，所以就很直覺地做就對了。

from collections import deque
class MyStack:

    def __init__(self):
        self.customQueue=deque()

    def push(self, x: int) -> None:
        self.customQueue.append(x)
        
    def pop(self) -> int:
        if self.empty() == False:
            return self.customQueue.pop()

    def top(self) -> int:
        if self.empty()==False:
            return self.customQueue[-1]

    def empty(self) -> bool:
        if len(self.customQueue)==0:
            return True
        else:
            return False
        

Hashmap
LeetCode 1 Two sum
給定一個list (e.g.[2,7,11,15]和一個target(e.g. 9)，找到list裡兩個數(index要不同)，相加為target。這裡我們可以先建一個dictionary，以value為key，index為value。target減去list中的值後若在字典中找得到，回傳對應的index。

class Solution:
#這裡nums為一個由整數建成的list，target為整數，函式回傳的東西也是由整數建成的list
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        new_dict={}
        for index,value in enumerate(nums):
            new_dict[value]=index
        for i in range(len(nums)):
            if (target - nums[i]) in new_dict:
                if i!=new_dict[target-nums[i]]:
                    return [i,new_dict[target-nums[i]]]

LeetCode 146 LRU Cache
LRU (least recent used) Cache是一個有容量限制(capacity limit)的快取記憶體，它可以以key-value pair的形式存取資料，當記憶體滿了的時候，它會先刪除最不常用的資料，並以新資料取代。它有三個功能，分別為初始化、get和put。初始化的開始，必須給它一個容量限制。方法get，可以獲取記憶體對應key的值，若無則回傳-1。方法put，可以將資料存入，並在記憶體滿了的時候將就資料取代成新資料。看完題目後，我們可以考慮用python collections的OrderedDict (字典的key有先後插入的順序，popitems的時候可以是FIFO(first in first out)，只要last=False，文件如連結:https://docs.python.org/zh-tw/3/library/collections.html#collections.OrderedDict)
那想法就可以是我的所有方法裡，我都將操作的key移至最後，最前面者就是我最不常用的資料就可以了~

from collections import OrderedDict
class LRUCache:

    def __init__(self, capacity: int):
        self.mydict=OrderedDict()
        self.capacity=capacity

    def get(self, key: int) -> int:
        if key not in self.mydict:
            return -1
        else:
            self.mydict.move_to_end(key)
            return self.mydict[key] 
        
    def put(self, key: int, value: int) -> None:
        if len(self.mydict)==self.capacity and key not in self.mydict:
            self.mydict.popitem(last=False)
        self.mydict[key]=value
        self.mydict.move_to_end(key)

** Binary Search **
LeetCode 34 Find First and Last Position of Element in Sorted Array
題目是說，今天給定一個排序過後的陣列叫做nums，然後一個目標叫target，想在這個陣列找出這個目標起始到結束的index，陣列中沒有目標值，回傳[-1,-1]。要寫出一個演算法，讓時間複雜度為O(logn)。
那當我們看到題目已經給一個排序過後的陣列，你可能也馬上就想到二元搜尋，它的時間複雜度也確實是O(logn)，剩下的問題就會是找到目標後，怎麼找到最前面和最後面的index。那我們就馬上來看程式碼吧:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums)==0:
            return [-1,-1]
        else:
            start=0
            end=len(nums)-1
            mid=end//2
            while not (nums[mid]==target or start>=end):
                if target>nums[mid]:
                    start=mid+1
                elif target<nums[mid]:
                    end=mid-1
                mid=(start+end)//2
            if nums[mid]==target:
                front=mid
                end=mid
                while nums[front]==target:
                    if front==0:
                        front-=1
                        break
                    else:
                        front-=1
                while nums[end]==target:
                    if end==len(nums)-1:
                        end+=1
                        break
                    else:
                        end+=1
                return [front+1,end-1]

            else:
                return [-1,-1]

不知道新手們做完後有沒有信心大增，相信大家都能寫出比我更簡潔+有效率的程式碼~~
明天再繼續不同主題但簡單的LeetCode練習，湊完最後一天~~