431. Encode N-ary Tree to Binary Tree （Hard）
Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-nary tree structure.
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
"""
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Codec:
# Encodes an n-ary tree to a binary tree.
def encode(self, root: 'Optional[Node]') -> Optional[TreeNode]:
if not root: return []
rootnode = TreeNode(root.val)
return_rootnode=rootnode
first=True
for node in root.children:
if first:
first=False
rootnode.left=self.encode(node)
rootnode=rootnode.left
else:
rootnode.right=self.encode(node)
rootnode=rootnode.right
return return_rootnode
# Decodes your binary tree to an n-ary tree.
def decode(self, data: Optional[TreeNode]) -> 'Optional[Node]':
if not data: return None
#print(data)
#print('#'*20)
root=data
root_node=Node(root.val,[])
if root.left:
root_node.children.append(self.decode(root.left))
root=root.left
while root.right:
root_node.children.append(self.decode(root.right))
root=root.right
return root_node
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(root))
#ANSWER
class Codec:
def encode(self, root):
if not root:
return None
binary = TreeNode(root.val) # create a binary root
if not root.children:
return binary
#Python - left child for children, right child for siblings
binary.left = self.encode(root.children[0]) # left child of binary is the encoding of all n-ary children,
node = binary.left # starting with the first child.
for child in root.children[1:]: # other children of n-ary root are right child of previous child
node.right = self.encode(child)
node = node.right
return binary
def decode(self, data):
if not data:
return None
nary = Node(data.val, []) # create n-ary root
node = data.left # move to first child of n-ary root
while node: # while more children of n-ary root
nary.children.append(self.decode(node)) # append to list
node = node.right # and move to next child
return nary
我得方法，把所有孩子都包含在下一层， root的left通向下一层，root.left.right和之后所有的right都是同一层的保存孩子。
432. All O`one Data Structure （Hard）
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
AllOne() Initializes the object of the data structure.
inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
class Node:
def __init__(self):
self.keys = set()
self.pre =None
self.next= None
def add_key(self,key):
self.keys.add(key)
def remove_key(self,key):
self.keys.remove(key)
def get_any_key(self):
if self.keys:
val = self.keys.pop()
self.keys.add(val)
return val
else:
None
def count(self):
return len(self.keys)
def is_empty(self):
return not bool(self.keys)
class DLL:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.pre = self.head
def insert_after(self,x):
# x - > N
node = Node()
x_next = x.next
x.next = node
node.pre = x
node.next = x_next
x_next.pre = node
return node
def insert_before(self,x):
return self.insert_after(x.pre)
def remove(self,x):
x.pre.next = x.next
x.next.pre = x.pre
def __repr__(self):
cur = self.head
res = []
c= 0
while cur:
c+=1
res.append('@'.join(cur.keys))
cur = cur.next
res = str(c)+'#'.join(res)
return res
class AllOne:
# head 1 <->2 tail
def __init__(self):
#key freq mapping
self.key2freq = defaultdict(int)
self.dll = DLL()
self.freq2node = {0: self.dll.head}
def _remove_key_preval_node(self,pre_val,key):
node = self.freq2node[pre_val]
node.remove_key(key)
if node.is_empty():
self.dll.remove(node)
del self.freq2node[pre_val]
def inc(self, key: str) -> None:
self.key2freq[key]+=1
pre_val = self.key2freq[key]-1
cur_val = self.key2freq[key]
if cur_val not in self.freq2node:
self.freq2node[cur_val] = self.dll.insert_after(self.freq2node[pre_val])
self.freq2node[cur_val].add_key(key)
if pre_val>0:
self._remove_key_preval_node(pre_val,key)
#print(self.dll)
def dec(self, key: str) -> None:
self.key2freq[key]-=1
cur_val = self.key2freq[key]
pre_val = self.key2freq[key]+1
if cur_val == 0: del self.key2freq[key]
if cur_val!=0:
if cur_val not in self.freq2node:
self.freq2node[cur_val] = self.dll.insert_before(self.freq2node[pre_val])
self.freq2node[cur_val].add_key(key)
self._remove_key_preval_node(pre_val,key)
#print(self.dll)
def getMaxKey(self) -> str:
return self.dll.tail.pre.get_any_key() or ''
def getMinKey(self) -> str:
return self.dll.head.next.get_any_key() or ''
感觉是个maxheap minheap。。。但不是all o（1）。。。 看答案了。。。答案果然完美
433. Minimum Genetic Mutation (Medium)
A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.
Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string.
For example, "AACCGGTT" --> "AACCGGTA" is one mutation.
There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.
Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1.
Note that the starting point is assumed to be valid, so it might not be included in the bank.
#ANSWER
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
queue = []
queue.append((start,0))
bankSet = set(bank)
while queue:
curr, step = queue.pop(0)
if curr == end:
return step
for i in range(len(curr)):
for c in "AGCT":
mutation = curr[:i] + c + curr[i+1:]
if mutation in bankSet:
bankSet.remove(mutation)
queue.append((mutation,step+1))
return -1
#MY ANSWER
class Solution:
def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
if endGene not in bank: return -1
bank = set(bank)
visited =set()
visited.add(startGene)
q = [startGene]
res = 0
while q:
res+=1
for _ in range(len(q)):
cur = q.pop(0)
for i in range(len(cur)):
for ch in 'ATGC':
if ch!= cur[i]:
key = cur[:i]+ch+cur[i+1:]
print(key)
if key == endGene: return res
if key in bank and key not in visited:
q.append(key)
visited.add(key)
return -1
bfs注意corner case，end必须in bank。 答案用remove mutaton方式避免用visited set，而且mutaion是直接算的，不是从bank中找的。
434. Number of Segments in a String （Easy）
Given a string s, return the number of segments in the string.
A segment is defined to be a contiguous sequence of non-space characters.
class Solution:
def countSegments(self, s: str) -> int:
return len(s.split())
class Solution:
def countSegments(self, s):
segment_count = 0
for i in range(len(s)):
if (i == 0 or s[i-1] == ' ') and s[i] != ' ':
segment_count += 1
return segment_count
435. Non-overlapping Intervals (Medium)
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
# min number of interval need to remove
# max number of interval I can keep
intervals = sorted(intervals)
# a, b
# a'b'
res = []
for a, b in intervals:
if res and res[-1][1]>a:
res[-1][1] = min(res[-1][1],b)
else:
res.append([a,b])
#print(res)
return len(intervals)-len(res)
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
#sort by start
# [1,2] [1,3] [2,3],[3,4]
#sort by end
# 找最小删除相当于找最大不overlap有多少个interval
#变成dp问题 dp[i]是最大的interval个数 用到ith interval
# dp【i】= max（dp【j】）+1 j<i interval i，j不overlap
intervals=sorted(intervals,key=lambda x:x[0])
dp = [0]*len(intervals)
dp[0]=1
ans=1
for i in range(1,len(dp)):
max_=0
for j in range(i):
if intervals[j][1]<=intervals[i][0]:
max_=max(dp[j],max_)
dp[i]=max_+1
ans=max(ans,dp[i])
return len(intervals)-ans
DP可以n^2， greedy也可以，Greedy nlogn
436. Find Right Interval (Medium)
You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j.
Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.
#TIME LIMIT EXCEEDED
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
maps=dict()
for i,interval in enumerate(intervals):
maps[tuple(interval)]=i
ans=[-1]*len(intervals)
intervals=sorted(intervals,key=lambda x:x[0])
for i in range(len(intervals)-1):
#i's right
j=i+1
while j<len(intervals) and intervals[j][0]<intervals[i][1]:
j+=1
if j<len(intervals):
ans[maps[tuple(intervals[i])]]=maps[tuple(intervals[j])]
return ans
#ANSWER BINARY SERACH
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
l = sorted((e[0], i) for i, e in enumerate(intervals))
res = []
for e in intervals:
r = bisect.bisect_left(l, (e[1],))
res.append(l[r][1] if r < len(l) else -1)
return res
#Heap法
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
heap, result = [], [-1] * len(intervals)
for idx, interval in sorted(enumerate(intervals), key=lambda enum: enum[1][0]):
while heap and heap[0][0] <= interval[0]:
_, i = heapq.heappop(heap)
if intervals[i][0]!=intervals[i][1]:
result[i] = idx
else:
result[i] = i
heapq.heappush(heap, (interval[1], idx))
return result
初次尝试 time limit exceeded 答案的bianry search法太厉害。
437. Path Sum III （Medium）
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
#post order botoom up save node val
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
#post order bottom up
self.res = 0
def post(node):
if not node: return
post(node.left)
post(node.right)
node.vals = defaultdict(int)
if node.left:
for v in node.left.vals:
node.vals[v+node.val]+=node.left.vals[v]
if node.right:
for v in node.right.vals:
node.vals[v+node.val]+=node.right.vals[v]
node.vals[node.val]+=1
if targetSum in node.vals:
self.res+=node.vals[targetSum]
post(root)
return self.res
#ANSWER PREFIX SUM in tree
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def preorder(node: TreeNode, curr_sum) -> None:
nonlocal count
if not node:
return
# current prefix sum
curr_sum += node.val
# here is the sum we're looking for
if curr_sum == k:
count += 1
# number of times the curr_sum − k has occurred already,
# determines the number of times a path with sum k
# has occurred up to the current node
count += h[curr_sum - k]
# add the current sum into hashmap
# to use it during the child nodes processing
h[curr_sum] += 1
# process left subtree
preorder(node.left, curr_sum)
# process right subtree
preorder(node.right, curr_sum)
# remove the current sum from the hashmap
# in order not to use it during
# the parallel subtree processing
h[curr_sum] -= 1
count, k = 0, sum
h = defaultdict(int)
preorder(root, 0)
return count
#上面这个解决方法基于
class Solution:
def subarraySum(self, nums, k):
count = curr_sum = 0
h = defaultdict(int)
for num in nums:
# current prefix sum
curr_sum += num
# situation 1:
# continuous subarray starts
# from the beginning of the array
if curr_sum == k:
count += 1
# situation 2:
# number of times the curr_sum − k has occurred already,
# determines the number of times a subarray with sum k
# has occurred up to the current index
count += h[curr_sum - k]
# add the current sum
h[curr_sum] += 1
return count
# PREORDER MY
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
# pre order
self.res = 0
dic = defaultdict(int)
def pre(node,val):
if not node: return
new_val = val+node.val
if new_val == targetSum:
self.res+=1
self.res+= dic[new_val-targetSum]
dic[new_val]+=1
pre(node.left,new_val)
pre(node.right,new_val)
dic[new_val]-=1
pre(root,0)
return self.res
我的解决方案是post order bottom up 扫，每个node存可以生成的pathsum值。答案是prefixsum。。
438. Find All Anagrams in a String （Medium）
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
res =[]
lp = len(p)
cp = Counter(p)
dic =defaultdict(int)
for i in range(len(s)):
dic[s[i]]+=1
if i-lp>=0:
dic[s[i-lp]]-=1
if dic[s[i-lp]]==0:
del dic[s[i-lp]]
if dic==cp:
res.append(i-lp+1)
return res
sliding window保持counter dict和p一样就可以。。。
439. Ternary Expression Parser （Medium）
Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression, and return the result of it.
You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false. All the numbers in the expression are one-digit numbers (i.e., in the range [0, 9]).
The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, 'T' or 'F'.
class Solution:
def parseTernary(self, expression: str) -> str:
#思路用stack，而且从后向前iterate
#T?a:b
if not expression: return expression
stack=[]
for char in expression[::-1]:
if stack and stack[-1]=='?':
stack.pop() #?
first=stack.pop()
stack.pop() #:
second=stack.pop()
if char=='T':
stack.append(first)
else:
stack.append(second)
else:
stack.append(char)
#print(stack)
return stack[-1]
T？（a）：（b） 形式，但a，b可以包含再包含。。。很难分辨哪个冒号是分界线。 用stack应该，看答案。关键是从后向前。
440. K-th Smallest in Lexicographical Order （Hard）
Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].
Example 1:
Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
#TLE TIRE
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
class T:
def __init__(self):
self.c = 0
self.children = defaultdict(T)
def insert(self,val):
val = str(val)
head = val[0]
tail = val[1:]
if head not in self.children:
self.children[head] = T()
self.children[head].c+=1
if tail:
self.children[head].insert(tail)
def search(self,id, tmp):
keys = [k for k in sorted(self.children.keys())]
vals = [self.children[k].c for k in keys]
# 1 2 3 4 5
# 0 1 3 6 10 15
cum_vals = [0]
for val in vals:
cum_vals.append(cum_vals[-1]+val)
new_id = bisect.bisect_left(cum_vals[1:],id)
if new_id >= len(cum_vals): new_id = len(cum_vals)-1
#print('keys',keys)
#print('cvls',cum_vals)
#print('id',id,'nid',new_id,'keys[new_id]',keys[new_id],'tmp',tmp)
if id-cum_vals[new_id]-1==0:
return tmp+keys[new_id]
if not self.children[keys[new_id]].children: return tmp+keys[new_id]
return self.children[keys[new_id]].search(id-cum_vals[new_id]-1, tmp+keys[new_id])
t = T()
for i in range(1,n +1):
t.insert(i)
return int(t.search(k,''))
#TLE TRIE#####################
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
class Trie:
def __init__(self):
self.children=collections.defaultdict(Trie)
self.val=0
trie=Trie()
def insert(i):
i=str(i)
root=trie
while i:
cur=i[0]
root=root.children[cur]
root.val+=1
i=i[1:]
for i in range(1,n+1):
insert(i)
path=[]
def search(k):
current_rank=0
children=trie.children
i=0
while current_rank<k:
key=sorted(children)[i]
if children[key].val+current_rank<k:
current_rank+=children[key].val
i+=1
else:
path.append(key)
current_rank+=1
children=children[key].children
i=0
search(k)
return int(''.join(path))
#ANSWER
'''
Initially, image you are at node 1 (variable: curr),
the goal is move (k - 1) steps to the target node x. (substract steps from k after moving)
when k is down to 0, curr will be finally at node x, there you get the result.
we don't really need to do a exact k steps preorder traverse of the denary tree, the idea is to calculate the steps between curr and curr + 1 (neighbor nodes in same level), in order to skip some unnecessary moves.
'''
def findKthNumber(self, n, k):
cur = 1
k = k - 1
while k > 0:
steps = self.calSteps(n, cur)
if steps <= k:
cur += 1
k -= steps
else:
cur *= 10
k -= 1
return cur
def calSteps(self, n, cur):
steps = 0
n1, n2 = cur, cur + 1
while n1 <= n:
steps += min(n + 1, n2) - n1
n1 *= 10
n2 *= 10
return steps
#ANSWER
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
def cal(cur):
#I am at cur, what the steps to cur+1
steps = 0
me = cur
next = cur+1
while me<=n:
if next>n:
steps+= n+1-me
else:
steps+=next-me
me = me*10
next = next*10
return steps
cur = 1
k = k-1
while k>0:
steps=cal(cur)
if k>=steps:
cur+=1
k-=steps
else:
cur*=10
k-=1
return cur
根据提示用了trie，思路是对的，，given k，what is the node positon of kth node。就算写出来也是TLE。。。看答案。
Main function
Firstly, calculate how many steps curr need to move to curr + 1.
if the steps <= k, we know we can move to curr + 1, and narrow down k to k - steps.
else if the steps > k, that means the curr + 1 is actually behind the target node x in the preorder path, we can't jump to curr + 1. What we have to do is to move forward only 1 step (curr * 10 is always next preorder node) and repeat the iteration.
calSteps function
how to calculate the steps between curr and curr + 1?
Here we come up a idea to calculate by level.
Let n1 = curr, n2 = curr + 1.
n2 is always the next right node beside n1's right most node (who shares the same ancestor "curr")
(refer to the pic, 2 is right next to 1, 20 is right next to 19, 200 is right next to 199).
so, if n2 <= n, what means n1's right most node exists, we can simply add the number of nodes from n1 to n2 to steps.
else if n2 > n, what means n (the biggest node) is on the path between n1 to n2, add (n + 1 - n1) to steps.
organize this flow to "steps += Math.min(n + 1, n2) - n1; n1 *= 10; n2 *= 10;"
Here is the code snippet:
public int findKthNumber(int n, int k) {
int curr = 1;
k = k - 1;
while (k > 0) {
int steps = calSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return curr;
}
//use long in case of overflow
public int calSteps(int n, long n1, long n2) {
int steps = 0;
while (n1 <= n) {
steps += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return steps;
}