leetcode 365天 #Day107

本人发呆写程式的过程
顺便知道一件事情，听音乐时还是不要开声音，版权炮会让影片消失很久XD
喔对了附上确实有百天练习的图。

---

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) 

---

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

---

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 = Falseclass 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

---

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))

以上为今天的练习，请多多指教