本人發呆寫程式的過程
順便知道一件事情，聽音樂時還是不要開聲音，版權炮會讓影片消失很久XD
喔對了附上確實有百天練習的圖。

380. Insert Delete GetRandom O(1) (medium)
     https://leetcode.com/problems/insert-delete-getrandom-o1/
     Submission：https://leetcode.com/submissions/detail/851949420/

題目：
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.

基本上來說就是要寫個class，要跟Python的set一樣，有儲存、刪除、隨機獲取的功能，內容物不可以重複。
重點是Google的面試題，所以不會這麼簡單。
我一開始的想法就是，不就是set嗎?抄一抄就好了。對，這樣確實可以過，但是不會進步，而且不是最佳解，所以後來有改寫法。

#一開始的寫法，直接把set丟上去
class RandomizedSet:

    def __init__(self):
        self.rec = set()

    def insert(self, val: int) -> bool:
        if val in self.rec:
            return False
        else:
            self.rec.add(val)
            return True
    
    def remove(self, val: int) -> bool:
        if val in self.rec:
            self.rec.remove(val)
            return True
        else:
            return False

    def getRandom(self) -> int:
        return choice(list(self.rec))

#google面試題，有參考別人的寫法
class RandomizedSet:

    def __init__(self):
        self.rec = {}
        self.recV = []

    def insert(self, val: int) -> bool:
        if val in self.rec:
            return False
        else:
            self.recV.append(val)
            self.rec[val] = len(self.recV) - 1
            return True
            
    #如果直接用set.remove當然可以，但時間複雜度會變成O(n)，這是需要優化成O(1)
    def remove(self, val: int) -> bool:
        if val in self.rec:
            index = self.rec[val]
            self.recV[-1],self.recV[index] = self.recV[index],self.recV[-1] #把兩個值對調
            self.rec[self.recV[index]] = index #換位置後，rec所儲存的索引值也要更改
            self.recV.pop()
            self.rec.pop(val) #用pop速度會快於del
            return True
        else:
            return False

    def getRandom(self) -> int:
        return choice(self.recV) 

1064. Fixed Point (easy)
      https://leetcode.com/problems/fixed-point/
      Submission：https://leetcode.com/submissions/detail/851950895/

題目：
Given an array of distinct integers arr, where arr is sorted in ascending order, return the smallest index i that satisfies arr[i] == i. If there is no such index, return -1.

題目很簡單，在串列裡面找捯一個值的大小剛好等於索引值，回傳他。

class Solution:
    #回傳索引值等同於該位置數值的索引值
    def fixedPoint(self, arr: List[int]) -> int:
        i = 0
        while i < len(arr):
            if i == arr[i]:
                return i
            i+=1
        return -1

1065. Index Pairs of a String (easy)
      https://leetcode.com/problems/index-pairs-of-a-string/
      Submission：https://leetcode.com/submissions/detail/851976337/

題目：
Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.

Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).

Example 1:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

首先給予一段文字text，再給予一串列words裡面儲存多段文字，要從text當中找出words[i]的起始位置與終點位置，儲存為串列並回傳。
這題個人覺得滿喜歡的，算是trie的初始題目，不過為了方便我一開始是用迴圈寫，後來才想辦法寫出trie的寫法。

class Solution:
    #正常寫法
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        ans = []
        for i in words:
            end = len(i)
            for j in range(end,len(text)+1):
                if text[j-end:j] == i:
                    ans.append([j-end,j-1])
        return sorted(ans)

#這題也可以用trie解決
class Node:
    def __init__(self):
        self.children = {}
        self.flag = False
class Trie:
    def __init__(self):
        self.root = Node()
    
    #把單字不斷地往下一層包，在包的時候如果有遇到相同的就可以把flag改為True
    def insert(self,words):
        root = Node()
        for word in words:
            node = root
            for chracter in word:
                node.children.setdefault(chracter,Node())
                node = node.children[chracter]
            node.flag = True
        return root
    
class Solution:
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        ans = []
        trie = Trie()
        trie = trie.insert(words)
        for i in range(len(text)):
            node = trie
            for j in range(i,len(text)):#從第i個字母當作開始，如果不在就不用繼續找了
                if text[j] not in node.children:
                    break
                node = node.children[text[j]]
                if node.flag:
                    ans.append([i,j])
        return ans

3. Longest Substring Without Repeating Characters
   https://leetcode.com/problems/longest-substring-without-repeating-characters/
   Submission：https://leetcode.com/submissions/detail/846527076/

Given a string s, find the length of the longest substring without repeating characters.

給一字串s，找出裡面最長的子字串(其中字母不可以重複)

class Solution:
    #找到最長的子字串，裡面不可以有重複的
    #這題滿簡單的，我覺得是不到medium
    
    #做一個專門儲存的list，看東西有沒有在裡面
    #有的話重置，沒的話就放進去
    def lengthOfLongestSubstring(self, s: str) -> int:
        rec,ans = [],0
        for i in s:
            if i not in rec:
                rec.append(i)
            else:
                ans = max(ans,len(rec))
                temp = rec.index(i)
                rec = rec[temp+1:] + [i]
            # print(rec)
        return max(ans,len(rec))

以上為今天的練習，請多多指教