381. Insert Delete GetRandom O(1) - Duplicates allowed （Hard）

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also removing a random element.
Implement the RandomizedCollection class:
RandomizedCollection() Initializes the empty RandomizedCollection object.
bool insert(int val) Inserts an item val into the multiset, even if the item is already present. Returns true if the item is not present, false otherwise.
bool remove(int val) Removes an item val from the multiset if present. Returns true if the item is present, false otherwise. Note that if val has multiple occurrences in the multiset, we only remove one of them.
int getRandom() Returns a random element from the current multiset of elements. The probability of each element being returned is linearly related to the number of same values the multiset contains.
You must implement the functions of the class such that each function works on average O(1) time complexity.

class RandomizedCollection:

    def __init__(self):
        self.lst = []
        self.idx = defaultdict(set)
        

    def insert(self, val: int) -> bool:
        self.idx[val].add(len(self.lst))
        self.lst.append(val)
        return len(self.idx[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.idx[val]: return False
        remove, last = self.idx[val].pop(), self.lst[-1]
        self.lst[remove] = last
        self.idx[last].add(remove)
        self.idx[last].remove(len(self.lst) - 1)

        self.lst.pop()
        return True

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


# MY ANSWER
class RandomizedCollection:

    def __init__(self):
        self.dic = defaultdict(set)
        self.li = []
        
    def insert(self, val: int) -> bool:
        res = True
        if val in self.dic:
            res = False
        self.dic[val].add(len(self.li))
        self.li.append(val)
        return res
        
    def remove(self, val: int) -> bool:
        if val in self.dic:
            if val == self.li[-1]:
                self.li.pop()
                idx = len(self.li)
                self.dic[val].remove(idx)
                if len(self.dic[val])==0:
                    del self.dic[val]
            else:
                pos_val = self.dic[val].pop()
                if len(self.dic[val])==0:
                    del self.dic[val]
                last_val = self.li[-1]
                pos_last_val = len(self.li)-1
                #move val to last_val
                self.li[pos_val],self.li[pos_last_val] = self.li[pos_last_val],self.li[pos_val]
                #update lastval pos to pos_val
                self.dic[last_val].remove(pos_last_val)
                self.dic[last_val].add(pos_val)
                #li pop
                self.li.pop()
            return True
        return False
        

    def getRandom(self) -> int:
        idx = random.randint(0,len(self.li)-1)
        return self.li[idx]


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

用list和defaultdict（set），insert很简单，难的是remove。 先找出remove val的index并从dict中pop，和array last 元素交换， array last元素的dict添加index，array last 元素dict.remove(len(self.lst) - 1）, len(self.lst) - 1是last元素的idx。

382. Linked List Random Node （Medium）

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Implement the Solution class:
Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.dic=dict()
        ind=0
        while head:
            self.dic[ind]=head.val
            ind+=1
            head=head.next
        self.ind=ind
        

    def getRandom(self) -> int:
        return self.dic[random.randint(0,self.ind-1)]  

#ANSER of Reservor sampling      
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head
        

    def getRandom(self) -> int:
        scope = 1
        chosen_value = 0
        curr = self.head

        while curr:
            # decide whether to include the element in reservoir
            if random.random() < 1 / scope:
                chosen_value = curr.val
            # move on to the next node
            curr = curr.next
            scope += 1
        return chosen_value
        

follow up说如果linkedlist很大而且不知道长度。。。如何random 取样。。。
忘记了有一个随机取样法 Reservoir sampling，需要复习, 当rand小于1/scope时候，说明当前值可以以1/scope的概率保留下来：

# S has items to sample, R will contain the result
def ReservoirSample(S[1..n], R[1..k])
  # fill the reservoir array
  for i := 1 to k
      R[i] := S[i]

  # replace elements with gradually decreasing probability
  for i := k+1 to n
    # randomInteger(a, b) generates a uniform integer
    #   from the inclusive range {a, ..., b} *)
    j := randomInteger(1, i)
    if j <= k
        R[j] := S[i]

383. Ransom Note （Easy）

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        a = Counter(ransomNote)
        b = Counter(magazine)
        for k,v in a.items():
            if k not in b or b[k]<v:
                return False
        return  True

384. Shuffle an Array (Medium)

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the integer array nums.
int[] reset() Resets the array to its original configuration and returns it.
int[] shuffle() Returns a random shuffling of the array.

class Solution:

    def __init__(self, nums: List[int]):
        self.array = nums
        self.original = nums[:]
       
 
    def reset(self) -> List[int]:
        self.array = self.original
        self.original = self.original[:]
        return self.array
   
    def shuffle(self) -> List[int]:
        aux = self.array[:]

        for idx in range(len(self.array)):
            remove_idx = random.randint(0,len(aux)-1)
            self.array[idx] = aux.pop(remove_idx)

        return self.array

#BEST ANSWER  Fisher-Yates Algorithm
class Solution:

    def __init__(self, nums: List[int]):
        self.array = nums
        self.original = nums[:]
       
 
    def reset(self) -> List[int]:
        self.array = self.original
        self.original = self.original[:]
        return self.array
   
    def shuffle(self) -> List[int]:
        for idx in range(len(self.array)):
            swap_idx=random.randint(idx,len(self.array)-1)
            self.array[idx],self.array[swap_idx]=self.array[swap_idx],self.array[idx]
        return self.array

感觉思路是找到以n！为base的数，然后还原出suffled array但是写不出来。。。想的过于复杂了。这个就是个随机算法。 元素e在第k轮被抽中概率是 k在前k-1轮不中但在k轮中。 (n-1/n ) (n-2/n-1)...(n-k)/(n-k+1))* 1/n-k = 1/n 所以按照 剩下的有效数字中选1个的概率去组成array就可以保证每个数字是等概率选取。这样总体就是random shuffle了。
1）先建立一个AUX array， 2）从AUX中无放回随机选一个数字 重复直到填满list。
第二个算法高明在用了two pointer 思想，一个是顺序扫填入数字，另一个是找到要填入的数字，这样填入时候，自然没被用到的数字被swap到后面去了，相当于无放回抽样。

385. Mini Parser （Medium）

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.
Each element is either an integer or a list whose elements may also be integers or other lists.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        # '-1' is not digit
        if s and s[-1].isdigit():
            return  NestedInteger(int(s))

        nested_integer = None
        digits = ''
        stack = []
        for c in s:
            if c.isdigit() or c == '-':
                digits += c
            elif c == '[':
                if nested_integer:
                    stack.append(nested_integer)
                nested_integer = NestedInteger()
            elif c == ']':
                if digits:
                    nested_integer.add(NestedInteger(int(digits)))
                    digits = ''
                if stack:
                    previous_nested_integer = stack.pop()
                    previous_nested_integer.add(nested_integer)
                    nested_integer = previous_nested_integer
            elif c == ',':
                if digits:
                    nested_integer.add(NestedInteger(int(digits)))
                    digits = ''

        return nested_integer

#作弊写法用eval
def deserialize(self, s):
    def nestedInteger(x):
        if isinstance(x, int):
            return NestedInteger(x)
        lst = NestedInteger()
        for y in x:
            lst.add(nestedInteger(y))
        return lst
    return nestedInteger(eval(s))




# MY ANSWER
class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        #1) convert string to list using stack
        res =  []
        stack = []
        sign = 1
        i=0
        while i<len(s):
            
            if s[i]=='-':
                sign = -1
            elif s[i].isdigit():
                i_old = i
                while i+1<len(s) and s[i+1].isdigit():
                    i+=1
                stack.append(sign*int(s[i_old:i+1]))
                sign=1
            elif s[i]=='[':
                stack.append('[') 
            elif s[i]==']':
                tmp = []
                while stack[-1]!='[':
                    tmp.append(stack.pop())
                #pop [
                stack.pop()
                tmp = tmp[::-1]    
                stack.append(tmp)

            i+=1
 
        while stack:
            res.append(stack.pop())

        result = res[0]
        print(result)

        #2) convert to NestedInteger()
        def convert(res):
            if type(res)==int:
                return  NestedInteger(res)
            else:
                r = NestedInteger()
                for x in res:
                    r.add(convert(x))
                return r
        return  convert(result)

想写正确并不容易。。。

386. Lexicographical Numbers （median）

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.

class Trie:
    def __init__(self):
        self.data = collections.defaultdict(Trie)
        self.isword = False
    
    def insert(self,w):
        if not w:
            self.isword = True
            return
        head =w[0]
        rest =w[1:]
        if head not in self.data:
            self.data[head] = Trie()
        self.data[head].insert(rest)


class Solution:
    def lexicalOrder(self, n: int) -> List[int]:

        res = []
        T =Trie()

        for i in range(1,n+1):
            T.insert(str(i))

        
        def pre(node,tmp):
            
            if node.isword:
                res.append(int(tmp))
                node.isword=False
            
            for key in sorted(node.data):
                pre(node.data[key],tmp+key)
        
        pre(T,'')

        return res

#ANSWER DFS
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        self.res = []
        for i in range(1, 10):
            self.helper(i, n)
        return self.res
    
    def helper(self, start, end):
        if start > end:
            return
        self.res.append(start)
        for i in range(0, 10):
            if 10 * start + i > end:
                return
            self.helper(10 * start + i, end)

用的trie做出来的，写的磕磕绊绊。。。
答案用的DFS， 很好的思路。。。
The idea is pretty simple. If we look at the order we can find out we just keep adding digit from 0 to 9 to every digit and make it a tree.
Then we visit every node in pre-order.
1 2 3 ...
/\ /\ /
10 ...19 20...29 30...39 ....

387. First Unique Character in a String （Easy）

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        c=Counter(s)
        for i,char in enumerate(s):
            if c[char]==1:
                return i
        return -1

388. Longest Absolute File Path (Medium)

Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:
Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext

If we were to write this representation in code, it will look like this: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext". Note that the '\n' and '\t' are the new-line and tab characters.
Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s. Using the above example, the absolute path to file2.ext is "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.
Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        maxlen = 0
        pathlen = {0: 0}
        for line in input.split('\n'):
            depth = line.count('\t')
            name = line.lstrip('\t')
            if '.' in name:
                maxlen = max(maxlen, pathlen[depth] + len(name))
            else:
                pathlen[depth + 1] = pathlen[depth] + len(name) + 1
        return maxlen


#MY ANSWER
class Solution:
    def lengthLongestPath(self, input: str) -> int:

        level_length =  dict()
        res = 0
        for me in input.split('\n'):
            c = 0
            while me[0]=='\t':
                c+=1
                me=me[1:]
            
            level_length[c] = len(me)
            #print( '#'+me+'#',len(me),c, level_length)
            if '.' in me:
                res = max(res, len(me)+c+ sum([level_length[ii] for ii in range(c)]))
        
        return res

level根据string前有多少个tab定，长度是 当前string长度+depth+比depth小的的父目录长度，跳转到下一个folder时候字典更新了level的长度，这样直接继续计算。。。

389. Find the Difference （Easy）

You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s=Counter(s)
        t=Counter(t)
        for key in s:
            t[key]-=s[key]
            if t[key]==0:
                del t[key]
        
        return  list(t.keys())[0]

#ANSER NLOGN
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:

        # Sort both the strings
        sorted_s = sorted(s)
        sorted_t = sorted(t)

        # Character by character comparison
        i = 0
        while i < len(s):
            if sorted_s[i] != sorted_t[i]:
                return sorted_t[i]
            i += 1

        return sorted_t[i]

#DICT O(n)
from collections import Counter

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        # Prepare a counter for string s.
        # This holds the characters as keys and respective frequency as value.
        counter_s = Counter(s)

        # Iterate through string t and find the character which is not in s.
        for ch in t:
            if ch not in counter_s or counter_s[ch] == 0:
                return ch
            else:
                # Once a match is found we reduce frequency left.
                # This eliminates the possibility of a false match later.
                counter_s[ch] -= 1

#XOR O（n）
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:

        # Initialize ch with 0, because 0 ^ X = X
        # 0 when XORed with any bit would not change the bits value.
        ch = 0

        # XOR all the characters of both s and t.
        for char_ in s:
            ch ^= ord(char_)

        for char_ in t:
            ch ^= ord(char_)

        # What is left after XORing everything is the difference.
        return chr(ch)

390. Elimination Game （Medium)

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.

#Navie not work memery exceeded
class Solution:
    def lastRemaining(self, n: int) -> int:
        li = [i for i in range(1,n+1)]
        
        def helper(li,forward=True):
            if len(li)==1: return li[0]
            if forward:
                #print(li[1::2],not forward)
                return helper(li[1::2],not forward)
            else:
                li=li[::-1]
                li=li[1::2]
                #print(li[::-1],not forward)
                return helper(li[::-1],not forward)
                
        return helper(li,True)


#Perfect ANSWER
class Solution:
    def lastRemaining(self, n: int) -> int:
 
        head, left, step, remaining = 1, True, 1, n
        while remaining > 1:
            if left or remaining % 2: 
                #when to update head
                #go from left or remaining is odd
                head += step
            left = not left
            step *= 2
            remaining //= 2
        return head

按照题目意思直接搞时间复杂度和空间复杂度都太大。。，
看答案：
update and record head in each turn. when the total number becomes 1, head is the only number left.

When will head be updated?

if we move from left
if we move from right and the total remaining number % 2 == 1
like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2

then we find a rule to update our head.