421. Maximum XOR of Two Numbers in an Array （Medium）

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

 class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        res=0
        L=len(bin(max(nums)))-2
        for i in range(L-1,-1,-1):
            res <<=1
            cur_xor = res | 1
            prefixes = {n >> i  for n in nums}
            res |= any(cur_xor^p in prefixes for p in prefixes)
        return res
        
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        L = len(bin(max(nums))) - 2
        max_xor = 0
        
        for i in reversed(range(L)):
            max_xor <<= 1
            # Set comprehension is used for speed purposes
            # List comprehension is what most pythonic users are used too imo
            prefixes = {num >> i for num in nums}
            curr_xor = max_xor | 1
            
            for p in prefixes:
                # if p1 ^ p2 == curr_xor then
                # p1 ^ curr_xor == p2 ( p2 is in prefixes)
                if p ^ curr_xor in prefixes:
                    # Set the last bit to 1
                    max_xor |= 1
                    
            
        return max_xor

没思路，看答案。

422. Valid Word Square (Easy)

Given an array of strings words, return true if it forms a valid word square.
A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).

class Solution:
    def validWordSquare(self, words: List[str]) -> bool:
        L = max([len(word) for word in words])
        words = [w if len(w)==L else w+' '*(L-len(w)) for w in words]
        for i,w in enumerate(zip(*words)):
            #print(i,''.join(w),words[i])
            if ''.join(w)!=words[i]:
                return False
        return True


public class Solution {
    public boolean validWordSquare(List<String> words) {
        if(words == null || words.size() == 0){
            return true;
        }
        int n = words.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<words.get(i).length(); j++){
                if(j >= n || words.get(j).length() <= i || words.get(j).charAt(i) != words.get(i).charAt(j))
                    return false;
            }
        }
        return true;
    }
}

有corner case。。。Java 答案更正确

423. Reconstruct Original Digits from English （Medium)

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.

class Solution:
    def originalDigits(self, s: 'str') -> 'str':
        # building hashmap letter -> its frequency
        count = collections.Counter(s)
        
        # building hashmap digit -> its frequency 
        out = {}
        # letter "z" is present only in "zero"
        out["0"] = count["z"]
        # letter "w" is present only in "two"
        out["2"] = count["w"]
        # letter "u" is present only in "four"
        out["4"] = count["u"]
        # letter "x" is present only in "six"
        out["6"] = count["x"]
        # letter "g" is present only in "eight"
        out["8"] = count["g"]
        # letter "h" is present only in "three" and "eight"
        out["3"] = count["h"] - out["8"]
        # letter "f" is present only in "five" and "four"
        out["5"] = count["f"] - out["4"]
        # letter "s" is present only in "seven" and "six"
        out["7"] = count["s"] - out["6"]
        # letter "i" is present in "nine", "five", "six", and "eight"
        out["9"] = count["i"] - out["5"] - out["6"] - out["8"]
        # letter "n" is present in "one", "nine", and "seven"
        out["1"] = count["n"] - out["7"] - 2 * out["9"]

        # building output string
        output = [key * out[key] for key in sorted(out.keys())]
        return "".join(output)


#MY ANSWER
class Solution:
    def originalDigits(self, s: str) -> str:
        # zero      00）Z确定0个数
        # one
        # two       11） w知道 2 个数
        # three     5） r - 4中r 0中r 知道 3 个数
        # four      4） f - 5中f 确定 4 个数， 知道4中 r个数
        # five      3） V- seven 个数 确定 5  个数
        # six       33）  X 确定6 的个数
        # seven     2）  S-X 确定 7 个数
        # eight     22) g 确定 8 个数
        # nine      44） i he 33 确定9
       

        res = {str(i):0 for i in range(10)}
        C = Counter(s)
        
        # 0 
        res['0'] = C['z']
        C['z']-=res['0']
        C['e']-=res['0']
        C['r']-=res['0']
        C['o']-=res['0']
        # 2
        res['2'] = C['w']
        C['t']-=res['2']
        C['w']-=res['2']
        C['o']-=res['2']
        # 6 
        res['6'] = C['x']
        C['s']-=res['6']
        C['i']-=res['6']
        C['x']-=res['6']
        # 8 
        res['8'] = C['g']
        C['e'] -= res['8']
        C['i'] -= res['8']
        C['g'] -= res['8']
        C['h'] -= res['8']
        C['t'] -= res['8']
        # 7
        res['7'] = C['s']
        C['s']-=res['7'] 
        C['e']-=res['7'] 
        C['v']-=res['7'] 
        C['e']-=res['7'] 
        C['n']-=res['7'] 
        # 3
        res['3'] = C['t']
        C['t']-=res['3'] 
        C['h']-=res['3'] 
        C['r']-=res['3'] 
        C['e']-=res['3'] 
        C['e']-=res['3']
        # 4
        res['4'] = C['r']
        C['f'] -= res['4']
        C['o'] -= res['4']
        C['u'] -= res['4']
        C['r'] -= res['4']
        # 5
        res['5'] = C['f']
        C['f'] -= res['5']
        C['i'] -= res['5']
        C['v'] -= res['5']
        C['e'] -= res['5']
        # 1
        res['1'] = C['o']
        C['o']-=res['1']
        C['n']-=res['1']
        C['e']-=res['1']
        # 9 
        res['9'] = C['i']
        C['n']-=res['9'] 
        C['i']-=res['9'] 
        C['n']-=res['9'] 
        C['e']-=res['9'] 


        r = ''
        for key in sorted(res):
            if res[key]!=0:
                r+= key*res[key]
        return r

直接做会出现是否要再次使用当前数字然后继续，或者直接使用下个数字，当前数字不重复使用的问题。
解决方法。。。醉了

Letter "z" is present only in "zero".
Letter "w" is present only in "two".
Letter "u" is present only in "four".
Letter "x" is present only in "six".
Letter "g" is present only in "eight".

Hence there is a good way to count even numbers.

That is actually the key how to count 3s, 5s and 7s since some letters are present only in one odd and one even number (and all even numbers has already been counted) :

Letter "h" is present only in "three" and "eight".
Letter "f" is present only in "five" and "four".
Letter "s" is present only in "seven" and "six".

Now one needs to count 9s and 1s only, and the logic is basically the same :

Letter "i" is present in "nine", "five", "six", and "eight".
Letter "n" is present in "one", "seven", and "nine".

424. Longest Repeating Character Replacement （Medium）

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.

#BINARY SEARCH + Sliding Window
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 1
        r = len(s)-1
        

        def valid_length(m):
            start = 0
            freq = defaultdict(int)
            maxfreq = 0
            for end in range(len(s)):
                freq[s[end]]+=1
                if end -start+ 1>m:
                    freq[s[start]]-=1 
                    start+=1

                maxfreq = max(maxfreq,freq[s[end]])
                if m-maxfreq<=k:
                    return True
            return False

        while l<=r:
            m = (l+r)//2
            #print(l,r,m,valid_length(m))

            if valid_length(m):
                l=m+1
            else:
                r=m-1
        
        return l if valid_length(l) else l-1

#方法2 For loop + sliding window 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        set_s = set(s)
        res = 0

        def is_window_valid(start,end,count,k):
            return end-start+1-count<=k

        for ch in set_s:
            start = 0
            count = 0

            for end in range(len(s)):
                if s[end]==ch:
                    count+=1
                
                while not is_window_valid(start, end, count, k):
                    if s[start]==ch:
                        count-=1
                    start+=1
                
                res = max(res, end-start+1)
        return res

#方法三

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        
        res = 0
        start = 0
        freq = defaultdict(int)
        max_freq = 0
        for end in range(len(s)):
            #expand window
            freq[s[end]]+=1
            max_freq = max(max_freq,freq[s[end]])

            is_valid = end-start+1-max_freq<=k
            if not is_valid:
                #shrink
                freq[s[start]]-=1
                start+=1
            
            res = end-start+1
        return res

#。。。。
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        
        l=len(s)
        count = defaultdict(int)
        maxcount = 0
        res = 0
        start = 0
        for end in range(l):
            #expand
            count[s[end]]+=1
            maxcount = max(maxcount,count[s[end]])
            while end-start+1-maxcount>k:
                #srink
                count[s[start]]-=1
                start+=1

            res = max(res, end-start+1)

        return res

方法一，binary search+ sliding window， 最小1， 最大len（s）做binary seach 看 m长度是不是一个valid length， valid 是指 m长度的sliding window中，存在能变成同一个字符的substring，找出sliding window中的最freq的频率，m-频率 就是杂char的个数，如果小于等于k说明m长度是valid。
方法二： 对每一个unique char， 做for loop， 判断是不是valid window，如果不是就要缩小窗口，start+1.
方法三：
two pointer， expand更新最大频率，check是不是valid，如果不valid，减去一个必定又valid，所以start+1，更新freq。 然后计算result。
方法四：
expand end 更新最大freq， 然后发现不满足条件就shrink， start更新，然后计算结果。

425. Word Squares (Hard)

Given an array of unique strings words, return all the word squares you can build from words. The same word from words can be used multiple times. You can return the answer in any order.
A sequence of strings forms a valid word square if the kth row and column read the same string, where 0 <= k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        # a b c d
        # b d e f
        # c e g h 
        # d f h k
        
        # select abcd
        # next must select b
        # select abcd
        #        bdef
        # next must select ce
        # select abcd
        #        bdef
        #        cegh
        # next must selct dfh
        # select abcd
        #        bdef
        #        cegh
        #        dfhk
        #
        # need a trie tree to find prefix is valid or not
        # if valid prefix, for childern path, need to explore all possible combinations using bt
        
        class Trie:
            def __init__(self):
                self.children=dict()
                self.words=set()
                
            def search(self,string):
                if not string: return True
                if string[0] not in self.children:
                    return False
                return self.children[string[0]].search(string[1:])
            
            def getwords(self,string):
                if string is False: return True
                if len(string)==1:
                    return self.children[string].words
                
                return self.children[string[0]].getwords(string[1:])
                
                
        trie=Trie()
        #insert words to trie
        for word in words:
            cur=trie
            for w in word:
                if w not in cur.children:
                    cur.children[w] = Trie()
                cur.words.add(word)
                cur=cur.children[w]
            
        
        res=[]
        size=len(words[0])
        
        def bt(tmp,words):
            #backtracking to generate all possible word squares
            if len(tmp)==size:
                res.append(tmp[:])
                return
            if not words: return
            
            for word in words:
                tmp.append(word)
                level=len(tmp)
                searchkey=''.join([e[level] for e in tmp]) if level<size else False
                if trie.search(searchkey):
                    validwords=trie.getwords(searchkey)
                    bt(tmp,validwords)
                tmp.pop()
        
        bt([],set(words))
        
        return res

#ANSWER is faster...
class Solution:
    def wordSquares(self, words: 'List[str]') -> 'List[List[str]]':
        
        dic= collections.defaultdict(list)
        n=len(words[0])
        for word in words:
            for i in range(1,n):
                key=word[:i]
                dic[key].append(word)
        
        res=[]        
        def build(squre):
            #print(len(squre))
            if len(squre)==n:
                res.append(squre)
                return
            #print(n,len(squre),squre)
            for word in dic[''.join(list(zip(*squre))[len(squre)])]:
                new=squre[:]
                new.append(word)
                build(new)
        
        for word in words:
            build([word])
        
        return res

#MY ANSWER
class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        #A B C D
        #B E F G
        #C F J I
        
        l = len(words[0])
        
        prefix = defaultdict(list)
        
        for i in range(1,l):
            for w in words:
                prefix[w[:i]].append(w)
        
  
        res = []
        def bt(row_id,tmp):
            if row_id==l:
                res.append(tmp[:])
                return

            if row_id ==0:
                for w in words:
                    bt(row_id+1, tmp+[w]) 
            else:
                key = ''
                for row in tmp:
                    key+=row[row_id]
                if key in prefix:
                    for w in prefix[key]:
                        bt(row_id+1,tmp+[w])
        
        bt(0,[])
        return res

很明显backtracking问题。。。

426. Convert Binary Search Tree to Sorted Doubly Linked List (Medium)

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

class Solution:
    def treeToDoublyList(self, root: 'Optional[Node]') -> 'Optional[Node]':
        #inorder
        # pre >   <cur

        if not root: return root

        head = None
        stack = []
        pre =None
        while stack or root:
            while root:
                stack.append(root)
                root=root.left
            
            root = stack.pop()
            if not head: head = root

            if pre:
                pre.right = root
                root.left = pre

            pre = root
            root = root.right
        
        pre.right = head
        head.left = pre

        return head

#ANSER RECURSION METHOD
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def helper(node):
            """
            Performs standard inorder traversal:
            left -> node -> right
            and links all nodes into DLL
            """
            nonlocal last, first
            if node:
                # left
                helper(node.left)
                # node 
                if last:
                    # link the previous node (last)
                    # with the current one (node)
                    last.right = node
                    node.left = last
                else:
                    # keep the smallest node
                    # to close DLL later on
                    first = node        
                last = node
                # right
                helper(node.right)
        
        if not root:
            return None
        
        # the smallest (first) and the largest (last) nodes
        first, last = None, None
        helper(root)
        # close DLL
        last.right = first
        first.left = last
        return first

corner case 要想清楚。。 而且node要call right left时候node必须存在。

427. Construct Quad Tree （Medium）

Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.
Return the root of the Quad-Tree representing the grid.

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        size=len(grid)
        if len({e for row in grid for e in row})==1:
            val=grid[0][0]==1
            isLeaf=True
            topLeft=None
            topRight=None
            bottomLeft=None
            bottomRight=None
            return Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight)
        else:
            isLeaf=False
            val=True
            topLeft=self.construct([row[:size//2] for row in grid[:size//2]])
            topRight=self.construct([row[size//2:] for row in grid[:size//2]])
            bottomLeft=self.construct([row[:size//2] for row in grid[size//2:]])
            bottomRight=self.construct([row[size//2:] for row in grid[size//2:]])
            return Node(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight)

428. Serialize and Deserialize N-ary Tree (Hard)

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        r=[]
        if not root: return r
        q=[root]
        while q:
            node=q.pop(0)
            if node !=',':
                r.append(str(node.val))
                for child in node.children:
                    q.append(child)
                q.append(',')
            else:
                r.append(',')
                
        return '#'.join(r)
        
 
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        if not data: return None
        pieces=data.split('#')
        root = Node(int(pieces[0]), [])
        idx = 1
        q=[root]
        while q:
            node=q.pop(0)
            while pieces[idx] != ',':
                child=Node(int(pieces[idx]), [])
                node.children.append(child)
                q.append(child)
                idx += 1
            idx += 1
        return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))


#BFS MY ANSWER

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        if not root: return ''
        
        code=lambda node: str(node.val)+'+'+str(len(node.children))
        
        res = []
        q = [root]
        while q:
            for _ in range(len(q)):
                cur = q.pop(0)
                res.append(code(cur))
                for node in cur.children:
                    q.append(node)

        return ','.join(res)
        
        
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        #print(data)
        if not data: return None
        dic = dict()
        data = data.split(',')
        root = None
        q = []
        c = 0
        while data:
            #print(data)
            val,n = data.pop(0).split('+')
            val = int(val)
            n = int(n)
            node = Node(val)
            dic[node] = n
            if not root: root = node
            
            if q :
                #print('me',q[0].val,'nc',dic[q[0]],'child',node.val)
                q[0].children.append(node)
                dic[q[0]]-=1
                if dic[q[0]]==0:
                    q.pop(0)
            
            if n:
                q.append(node)

        return root 

第一种 答案写的更简洁

429. N-ary Tree Level Order Traversal (Medium)

Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        q=[root]
        res=[]
        while q:
            l=len(q)
            level=[]
            for _ in range(l):
                cur=q.pop(0)
                level.append(cur.val)
                for child in cur.children:
                    q.append(child)
            res.append(level)
        return res

#RECURSION ANSWER
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:

        def traverse_node(node, level):
            if len(result) == level:
                result.append([])
            result[level].append(node.val)
            for child in node.children:
                traverse_node(child, level + 1)

        result = []

        if root is not None:
            traverse_node(root, 0)
        return result

BFS

430. Flatten a Multilevel Doubly Linked List (Medium)

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.
Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        stack=[]
        cur=head
        pre=None
        while cur or stack:
            if not cur:
                cur=stack.pop()
                cur.prev=pre
                pre.next=cur
                
            while cur.child:
                if cur.next:
                    stack.append(cur.next)
                curnext=cur.child
                curchild=cur.child
                cur.child=None
                curchild.prev=cur
                cur.next=curnext
                cur=curnext
               
            if not cur.child:
                pre=cur
                cur=cur.next
                
            
        return head


#

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        
        #DFS...
        curr=head
        tempStack = []
        while curr:
            if curr.child:
                if curr.next:
                    tempStack.append(curr.next);
                curr.next, curr.child.prev, curr.child = curr.child, curr, None;
            if not curr.next and len(tempStack):
                temp = tempStack.pop();
                temp.prev, curr.next = curr, temp
            curr = curr.next
        return head


 #ANSWER PREORDER   child is left tree next is right tree
 """
# Definition for a Node.
class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution(object):

    def flatten(self, head):
        if not head:
            return head

        # pseudo head to ensure the `prev` pointer is never none
        pseudoHead = Node(None, None, head, None)
        self.flatten_dfs(pseudoHead, head)

        # detach the pseudo head from the real head
        pseudoHead.next.prev = None
        return pseudoHead.next


    def flatten_dfs(self, prev, curr):
        """ return the tail of the flatten list """
        if not curr:
            return prev

        curr.prev = prev
        prev.next = curr

        # the curr.next would be tempered in the recursive function
        tempNext = curr.next
        tail = self.flatten_dfs(curr, curr.child)
        curr.child = None
        return self.flatten_dfs(tail, tempNext)        

#preorder interative 
class Solution(object):
    def flatten(self, head):
        if not head:
            return

        pseudoHead = Node(0,None,head,None)
        prev = pseudoHead

        stack = []
        stack.append(head)

        while stack:
            curr = stack.pop()

            prev.next = curr
            curr.prev = prev

            if curr.next:
                stack.append(curr.next)
 
            if curr.child:
                stack.append(curr.child)
                # don't forget to remove all child pointers.
                curr.child = None

            prev = curr
        # detach the pseudo head node from the result.
        pseudoHead.next.prev = None
        return pseudoHead.next


###USING STACK
class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return head
        res = head
        stack = []
        pre = None
        while head:
            if head.child:
                next = head.child
                stack.append(head.next)
                if head.next:
                    head.next.prev = None
                
                head.next = head.child
                head.child.prev = head
                head.child = None
            else:
                next = head.next
            
            pre = head
            head = next
        
        cur = pre
        while stack:
            cur.next = stack.pop()
            if cur.next:
                cur.next.prev =cur
            while cur.next:
                cur = cur.next
            
        #cur = res
        #while cur:
        #    print(cur.val,cur.prev.val if cur.prev else ',', cur.next.val if cur.next else ',')
        #    cur = cur.next

        return res