Created
June 23, 2020 06:26
-
-
Save wmhtet/a74974741980497240ac9a877f4c38c0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import collections | |
from helperlc import print_l | |
from helperlc import print_tree | |
from helperlc import TreeNode | |
from helperlc import Node | |
from helperlc import ListNode | |
from helperlc import get_tree_node_levelorder | |
from typing import List | |
import timeit | |
def main(): | |
sol = Solution() # None | |
arg = [1, None, 5, 2] | |
root = get_tree_node_levelorder(arg) | |
arg1 = "segmentation" | |
arg2 = ["bbbbbxbbbbb1"] | |
# t = timeit.timeit("sol = Solution(); rs = sol.solveNQueens(4)", number=5 , | |
# setup="from pie import Solution") print(t) | |
rs = sol.generateAbbreviations(arg1) | |
# print_tree(root) | |
print(rs) | |
# print(len(rs)) | |
# next Greater element, net permutation, permutation, combination | |
# for i, num in enumerate(nums[1:], 1): | |
# https://zxi.mytechroad.com/blog/two-pointers/leetcode-1385-find-the-distance-value-between-two-arrays/ | |
# sum(all(abs(x - y) > d for y in arr2) for x in arr1) | |
# [ch if not ch.isdigit() else '*' * int(ch) for ch in abbr] | |
# backtracking, bisect, min - priority queue | |
class Solution: | |
def generateAbbreviations(self, word): | |
def abbr(word): | |
if not word: return [] | |
ls = [] | |
wl = len(word) | |
for i in range(wl): | |
aword = word | |
k = 0 | |
while k + i < len(aword): | |
aword = aword[:k] + str(i + 1) + aword[k + i + 1:] | |
ls.append(aword) | |
k += 1 | |
if i >= 9: | |
k += 1 | |
if aword[:2] == "1e": | |
print(aword[:k], aword[k:], k) | |
if len(aword) >= k: | |
temp = abbr(aword[k:]) | |
rs = [] | |
if aword[:2] == "1e": | |
print(":", aword[:k], aword[k:]) | |
for tword in temp: | |
if not tword.isdigit() and not tword[0].isdigit(): | |
rs.append(aword[:k] + tword) | |
ls += rs | |
aword = word | |
return ls | |
return abbr(word) + [word] | |
def wordsAbbreviation(self, dict): | |
temp = {} | |
for word in dict: | |
if len(word) > 3: | |
key = word[0] + str(len(word) -2) + word[-1] | |
else: | |
key = word | |
temp.setdefault(key, []).append(word) | |
def conflict_resolution(dic, ls): | |
size = len(ls[0]) - 2 | |
front = -1 | |
for i in range(1, size): | |
num = size - i | |
stemp = set() | |
for word in ls: | |
abbr = word[:i] + str(num + 1) + word[-1] | |
stemp.add(abbr) | |
if len(stemp) == len(ls): | |
front = i | |
break | |
for word in ls: | |
if front == -1: | |
dic[word] = word | |
else: | |
abbr = word[:front] + str(size - front + 1) + word[-1] | |
dic[word] = abbr | |
dic = {} | |
for key, val in temp.items(): | |
if len(val) > 1: | |
conflict_resolution(dic, val) | |
else: | |
dic[val[0]] = key | |
return [dic[word] for word in dict] | |
def partition(seq): | |
pi, seq = seq[0], seq[1:] # Pick and remove the pivot | |
lo = [x for x in seq if x <= pi] # All the small elements | |
hi = [x for x in seq if x > pi] # All the large ones | |
return lo, pi, hi # pi is "in the right place" | |
def select(seq, k): | |
lo, pi, hi = partition(seq) # [<= pi], pi, [>pi] | |
m = len(lo) | |
if m == k: | |
return pi # We found the kth smallest | |
elif m < k: # Too far to the left | |
return select(hi, k - m - 1) # Remember to adjust k | |
else: # Too far to the right | |
return select(lo, k) # Just use original k here | |
def minAbbreviation(self, target, dictionary): | |
def abbr(word): | |
if not word: return [] | |
ls = [] | |
wl = len(word) | |
for i in range(wl): | |
aword = word | |
k = 0 | |
while k + i < len(aword): | |
aword = aword[:k] + str(i + 1) + aword[k + i + 1:] | |
ls.append(aword) | |
k += 1 | |
if len(aword) - 1 - i >= k: | |
temp = abbr(aword[k:]) | |
rs = [] | |
# print(aword[:k], aword[k:], temp ) | |
for tword in temp: | |
if not tword.isdigit() and not tword[0].isdigit(): | |
rs.append(aword[:k] + tword) | |
ls += rs | |
aword = word | |
return ls | |
targets = abbr(target) + [target] | |
targets.sort(key=len) | |
for small in targets: | |
if not sum(self.validWordAbbreviation(word, small) for word in dictionary): | |
return small | |
return dics | |
def minAbbreviation_(self, target, dictionary): | |
def abbr(word): | |
if not word: return [] | |
ls = [] | |
wl = len(word) | |
for i in range(wl): | |
aword = word | |
k = 0 | |
while k + i < len(aword): | |
aword = aword[:k] + str(i + 1) + aword[k + i + 1:] | |
ls.append(aword) | |
k += 1 | |
if len(aword) - 1 - i >= k: | |
temp = abbr(aword[k:]) | |
rs = [] | |
for tword in temp: | |
if not tword.isdigit() and not tword[0].isdigit(): | |
rs.append(aword[:k] + tword) | |
ls += rs | |
aword = word | |
return ls | |
targets = abbr(target) + [target] | |
targets.sort(key=len) | |
dics = [] | |
for dword in dictionary: | |
dics += abbr(dword) + [dword] | |
dics = set(dics) | |
for small in targets: | |
if small not in dics: | |
return small | |
return dics | |
def validWordAbbreviation(self, word, abbr): | |
i, j = 0, 0 | |
wl = len(word) | |
while i < len(abbr): | |
num = "" | |
while i < len(abbr) and abbr[i].isdigit(): | |
if not num and abbr[i] == '0': | |
break | |
num += abbr[i] | |
i += 1 | |
if num: | |
j += int(num) | |
else: | |
if j < wl and abbr[i] != word[j]: | |
return False | |
i += 1 | |
j += 1 | |
return wl == j | |
def wordSquares(self, words): | |
if not words: return words | |
from collections import defaultdict | |
ans = [] | |
n = len(words[0]) | |
dic = defaultdict(list) | |
for word in words: | |
for i in range(1, n): | |
dic[word[:i]].append(word) | |
def backtrack(arr): | |
length = len(arr) | |
if length == n: | |
ans.append(arr) | |
else: | |
key = '' | |
for word in arr: | |
key += word[length] | |
if dic[key]: | |
for word in dic[key]: | |
backtrack(arr + [word]) | |
for word in words: | |
backtrack([word]) | |
return ans | |
def wordSquares_(self, words: List[str]): | |
size = len(words[0]) | |
if size == 1: return words | |
res = [] | |
def check(ls): | |
tsize = len(ls) - 1 | |
if tsize < 1: | |
return True | |
for row in range(tsize): | |
if ls[row][tsize] != ls[tsize][row]: | |
return False | |
return True | |
def backtracking(ls): | |
tsize = len(ls) | |
if not check(ls): | |
return | |
if tsize == size: | |
nonlocal res | |
res.append(list(ls)) | |
return | |
for word in words: | |
ls.append(word) | |
backtracking(ls) | |
ls.pop() | |
backtracking([]) | |
return res | |
def wordBreak(self, s: str, wordDict: List[str]) -> bool: | |
wordDict = set(wordDict) | |
memo = {} | |
def backtracking(input): | |
if not input: return True | |
nonlocal memo | |
if input in wordDict: return True | |
for pos in range(len(input), -1, -1): | |
lefts, right = input[:pos], input[pos:] | |
if right in wordDict: | |
flag = backtracking(lefts) | |
if flag: return True | |
memo[input] = False | |
return False | |
return backtracking(s) | |
def wordBreak_(self, s: str, wordDict: List[str]) -> List[str]: | |
wordDict = set(wordDict) | |
memo = {} | |
def backtracking(input): | |
if not input: return [] | |
nonlocal memo | |
if input in memo: return memo[input] | |
res = [] | |
if input in wordDict: | |
res.append(input) | |
for pos in range(len(input)): | |
lefts, right = input[:pos], input[pos:] | |
if right in wordDict: | |
ls = backtracking(lefts) | |
for left in ls: | |
res.append(left + " " + right) | |
memo[input] = res | |
return res | |
return backtracking(s) | |
def isMatch(self, s: str, p: str) -> bool: | |
memo = {} | |
def _isMatch(s: str, p: str) -> bool: | |
nonlocal memo | |
if (s, p) in memo: | |
return memo[(s, p)] | |
if not p: return s == "" | |
if len(p) >= 2 and p[1] == "*": | |
res = _isMatch(s, p[2:]) or \ | |
(s != "" | |
and (s[0] == p[0] or '.' == p[0]) | |
and _isMatch(s[1:], p)) | |
else: | |
res = s != "" \ | |
and (s[0] == p[0] or '.' == p[0]) \ | |
and _isMatch(s[1:], p[1:]) | |
memo[(s, p)] = res | |
return res | |
return _isMatch(s, p) | |
def isMatch___(self, s: str, p: str) -> bool: | |
memo = {} | |
def isMatch(s: str, p: str) -> bool: | |
nonlocal memo | |
if (s, p) in memo: | |
return memo[(s, p)] | |
if not p: return s == "" | |
if not s: | |
res = p[0] == '*' and isMatch(s, p[1:]) | |
elif p[0] == "*": | |
res = isMatch(s[1:], p) or isMatch(s, p[1:]) | |
else: | |
res = (s[0] == p[0] or '?' == p[0]) \ | |
and isMatch(s[1:], p[1:]) | |
memo[(s, p)] = res | |
return res | |
return isMatch(s, p) | |
def isMatch__(self, s: str, p: str) -> bool: | |
if not p: return s == "" | |
if not s: | |
return p[0] == '*' and self.isMatch(s, p[1:]) | |
if p[0] == "*": | |
return self.isMatch(s[1:], p) or self.isMatch(s, p[1:]) | |
else: | |
return (s[0] == p[0] or '?' == p[0]) \ | |
and self.isMatch(s[1:], p[1:]) | |
def isMatch_(self, s: str, p: str) -> bool: | |
if not p: return s == "" | |
if len(p) >= 2 and p[1] == "*": | |
return self.isMatch(s, p[2:]) or \ | |
(s != "" | |
and (s[0] == p[0] or '.' == p[0]) | |
and self.isMatch(s[1:], p)) | |
else: | |
return s != "" \ | |
and (s[0] == p[0] or '.' == p[0]) \ | |
and self.isMatch(s[1:], p[1:]) | |
def findLadders(self, beginWord, endWord, wordList): | |
""" | |
:type beginWord: str | |
:type endWord: str | |
:type wordList: List[str] | |
:rtype: List[List[str]] | |
""" | |
if endWord not in wordList: | |
return [] | |
wordList = set(wordList) # convert to set for O(1) lookup | |
left, right = {beginWord}, {endWord} # frontiers at both ends | |
left_parents, right_parents = defaultdict(set), defaultdict( | |
set) # map word to its parent | |
swapped = False # have the frontiers been swapped? | |
while left and right and not ( | |
left & right): # while both frontiers and no intersection | |
if len(right) < len(left): # swap to expand smaller frontier | |
left, right = right, left | |
left_parents, right_parents = right_parents, left_parents | |
swapped = not swapped | |
next_left = defaultdict(set) | |
for word in left: | |
for char in string.ascii_lowercase: | |
for i in range(len(beginWord)): | |
n = word[:i] + char + word[ | |
i + 1:] # replace every position with every char | |
if n in wordList and n not in left_parents: # valid word not been used | |
next_left[n].add(word) | |
left_parents.update(next_left) | |
left = set(next_left.keys()) | |
if swapped: # swap back | |
left, right = right, left | |
left_parents, right_parents = right_parents, left_parents | |
ladders = [[word] for word in | |
left & right] # start from central intersection | |
while ladders and ladders[0][ | |
0] not in beginWord: # extend ladders left to start | |
ladders = [[p] + l for l in ladders for p in left_parents[l[0]]] | |
while ladders and ladders[0][-1] != endWord: # extend ladders right to end | |
ladders = [l + [p] for l in ladders for p in right_parents[l[-1]]] | |
return ladders | |
def solveNQueens(self, arg: int) -> List[List[str]]: | |
sols = [] | |
def check_slope(sol): | |
if not sol: | |
return False | |
new_q = sol[-1] | |
for q in sol[:-1]: | |
slope = (q[1] - new_q[1]) / (q[0] - new_q[0]) | |
if slope == 1 or slope == -1: | |
return True | |
return False | |
def backtrack(rows, cols, sol): | |
nonlocal sols | |
print(rows, cols, sol) | |
if check_slope(sol): | |
return | |
if len(sol) == arg: | |
ls = [] | |
for (i, j) in sol: | |
ls.append('.' * j + 'Q' + '.' * (arg - 1 - j)) | |
sols.append(ls) | |
print("solutions : ", sol) | |
return | |
for row in sorted(rows): | |
for col in cols: | |
if sol: | |
if row <= sol[-1][0]: | |
break | |
sol.append((row, col)) | |
nrows = set(rows) | |
nrows.remove(row) | |
ncols = set(cols) | |
ncols.remove(col) | |
backtrack(nrows, ncols, sol) | |
sol.pop() | |
nums = range(arg) | |
rows, cols = set(nums), set(nums) | |
backtrack(rows, cols, []) | |
return sols | |
def solveNQueens_(self, arg: int) -> List[List[str]]: | |
sols = [] | |
def check_slope(sol): | |
if not sol: | |
return False | |
new_q = sol[-1] | |
for q in sol[:-1]: | |
slope = (q[1] - new_q[1]) / (q[0] - new_q[0]) | |
if slope == 1 or slope == -1: | |
return True | |
return False | |
def backtrack(rows, cols, sol): | |
nonlocal sols | |
if check_slope(sol): | |
return | |
if len(sol) == arg: | |
ls = [] | |
for (i, j) in sol: | |
ls.append('.' * j + 'Q' + '.' * (arg - 1 - j)) | |
sols.append(ls) | |
return | |
for i, row in enumerate(rows): | |
for j, col in enumerate(cols): | |
if sol: | |
if i <= sol[-1][0]: | |
break | |
if not row and not col: | |
sol.append((i, j)) | |
nrows = list(rows) | |
ncols = list(cols) | |
nrows[i] = 1 | |
ncols[j] = 1 | |
backtrack(nrows, ncols, sol) | |
sol.pop() | |
rows, cols = [0] * arg, [0] * arg | |
backtrack(rows, cols, []) | |
return sols | |
def ladderLengthII(self, beginWord: str, endWord: str, wordList: List[str]): | |
ws = set(wordList) | |
if endWord not in ws: | |
return [] | |
if beginWord in ws: | |
ws.remove(beginWord) | |
from collections import deque | |
from string import ascii_lowercase | |
q = deque() | |
q.append(beginWord) | |
seen = {} | |
level = 1 | |
rs = [] | |
dic = {} | |
level_dic = {} | |
end_word_found = False | |
while q and not end_word_found: | |
level += 1 | |
for _ in range(len(q)): | |
word = q.popleft() | |
temp = [] | |
for pos in range(len(word)): | |
if word in seen and seen[word] == pos: | |
continue | |
for ch in ascii_lowercase: | |
wls = list(word) | |
wls[pos] = ch | |
new_ch_word = ''.join(wls) | |
if new_ch_word in ws or new_ch_word == endWord: | |
level_dic[new_ch_word] = level + 1 | |
temp.append(new_ch_word) | |
if new_ch_word == endWord: | |
end_word_found = True | |
else: | |
ws.remove(new_ch_word) | |
seen[new_ch_word] = pos | |
q.append(new_ch_word) | |
else: | |
if new_ch_word in level_dic \ | |
and level_dic[new_ch_word] == level + 1: | |
temp.append(new_ch_word) | |
if temp: | |
dic[word] = temp | |
def backtrack(rs, ls, word): | |
if word == endWord: | |
rs.append(list(ls)) | |
return | |
if word not in dic: | |
return | |
for next in dic[word]: | |
ls.append(next) | |
backtrack(rs, ls, next) | |
ls.pop() | |
backtrack(rs, [beginWord], beginWord) | |
return rs | |
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: | |
ws = set(wordList) | |
if endWord not in ws: | |
return 0 | |
from collections import deque | |
from string import ascii_lowercase | |
q = deque() | |
q.append(beginWord) | |
seen = {} | |
level = 1 | |
while q: | |
level += 1 | |
for _ in range(len(q)): | |
word = q.popleft() | |
for pos in range(len(word)): | |
if word in seen and seen[word] == pos: | |
continue | |
for ch in ascii_lowercase: | |
wls = list(word) | |
wls[pos] = ch | |
new_ch_word = ''.join(wls) | |
if new_ch_word == endWord: | |
return level | |
if new_ch_word in ws: | |
ws.remove(new_ch_word) | |
seen[new_ch_word] = pos | |
q.append(new_ch_word) | |
return 0 | |
def ladderLength1(self, beginWord: str, endWord: str, | |
wordList: List[str]) -> int: | |
wordSet = set(wordList) | |
if endWord not in wordSet: | |
return 0 | |
from string import ascii_lowercase | |
front = set() | |
front.add(beginWord) | |
back = set() | |
back.add(endWord) | |
level = 0 | |
ht = {beginWord: -1, endWord: -1} | |
while front and back: | |
level += 1 | |
if len(front) > len(back): | |
temp = front.copy() | |
front = back | |
back = temp | |
new_front = set() | |
print(front, back) | |
for _ in range(len(front)): | |
each = front.pop() | |
for pos in range(len(each)): | |
if ht[each] == pos: | |
continue | |
print(ht) | |
for c in ascii_lowercase: | |
temp = list(each) | |
temp[pos] = c | |
t_word = ''.join(temp) | |
if t_word in back: | |
return level + 1 | |
if t_word in wordSet: | |
wordSet.remove(t_word) | |
new_front.add(t_word) | |
ht[t_word] = pos | |
if new_front: | |
print(new_front, wordSet) | |
front = new_front | |
return 0 | |
class BSTIterator: | |
def __init__(self, root: TreeNode): | |
self.ls = [] | |
def inorder(root: TreeNode, ls): | |
if not root: | |
return | |
inorder(root.left, ls) | |
ls.append(root.val) | |
inorder(root.right, ls) | |
inorder(root, self.ls) | |
def next(self) -> int: | |
""" | |
@return the next smallest number | |
""" | |
return self.ls.pop(0) | |
def hasNext(self) -> bool: | |
""" | |
@return whether we have a next smallest number | |
""" | |
return len(self.ls) > 0 | |
def findKthLargest(self, nums, k): | |
import random | |
l, r = 0, len(nums) - 1 | |
k = len(nums) - k | |
def partition(arr, l, r): | |
ri = random.randint(l, r) | |
piv = arr[ri] | |
arr[ri], arr[r] = arr[r], arr[ri] | |
pos_piv = l | |
for i in range(l, r): | |
if arr[i] <= piv: | |
arr[i], arr[pos_piv] = arr[pos_piv], arr[i] | |
pos_piv += 1 | |
arr[pos_piv], arr[r] = arr[r], arr[pos_piv] | |
return pos_piv | |
while True: | |
index = partition(nums, l, r) | |
if index == k: | |
return nums[index] | |
if index < k: | |
l = index + 1 | |
else: | |
r = index - 1 | |
def findMin(self, nums): | |
left, right = 0, len(nums) - 1 | |
while left < right: | |
if nums[left] < nums[right]: # already sorted | |
break | |
mid = (left + right) // 2 | |
if nums[right] < nums[mid]: | |
left = mid + 1 # discontinuity on RHS of mid | |
elif nums[right] > nums[mid] or nums[left] > nums[mid]: | |
right = mid # discontinuity is mid or LHS | |
else: # nums[right] == nums[mid] == nums[left] | |
left += 1 | |
right -= 1 | |
return nums[left] | |
def findMedianSortedArrays(self, nums1, nums2): | |
len1, len2 = len(nums1), len(nums2) | |
if len1 > len2: | |
return self.findMedianSortedArrays(nums2, nums1) | |
i, j = 0, 0 | |
k, r = divmod(len1 + len2, 2) | |
rs = [] | |
if not nums1: | |
rs = nums2[0:k + 1] | |
else: | |
while i + j <= k: | |
if i <= len1 - 1 and (j >= len2 or nums1[i] <= nums2[j]): | |
rs.append(nums1[i]) | |
i += 1 | |
else: | |
rs.append(nums2[j]) | |
j += 1 | |
if r: | |
return rs[-1] | |
else: | |
return (rs[-1] + rs[-2]) / 2 | |
def test(self, arg1): | |
rs = [] | |
lfu = Solution.LFUCache(3) | |
lfu.set(2, 2) | |
lfu.set(1, 1) | |
rs.append(lfu.get(2)) | |
rs.append(lfu.get(1)) | |
rs.append(lfu.get(2)) | |
lfu.set(3, 3) | |
lfu.set(4, 4) | |
rs.append(lfu.get(3)) | |
rs.append(lfu.get(2)) | |
rs.append(lfu.get(1)) | |
rs.append(lfu.get(4)) | |
return rs | |
import heapq | |
class MinStack: | |
def __init__(self): | |
self.ls = [] | |
self.heap = [] | |
heapq.heapify(self.heap) | |
def push(self, x: int) -> None: | |
self.ls.append(x) | |
heapq.heappush(self.heap, x) | |
def pop(self) -> None: | |
self.heap.remove(self.ls.pop()) | |
heapq.heapify(self.heap) | |
def top(self) -> int: | |
self.ls[-1] | |
def getMin(self) -> int: | |
if len(self.ls) == 0: | |
return 0 | |
else: | |
return self.heap[0] | |
class LRUCache: | |
def __init__(self, capacity: int): | |
self.size = capacity | |
self.dic = {} | |
self.time = 0 | |
def get(self, key: int) -> int: | |
self.time += 1 | |
if key in self.dic: | |
p = self.dic[key] | |
p[0] = self.time | |
return p[1] | |
else: | |
return -1 | |
def put(self, key: int, value: int) -> None: | |
if self.size <= 0: | |
return | |
self.time += 1 | |
if len(self.dic) == self.size and key not in self.dic: | |
vals = list(self.dic.values()) | |
heapq.heapify(vals) | |
evt = heapq.heappop(vals) | |
del self.dic[evt[2]] | |
if key not in self.dic: | |
self.dic[key] = [self.time, value, key] | |
else: | |
p = self.dic[key] | |
p[1] = value | |
p[0] = self.time | |
class LFUCache: | |
""" | |
@param: capacity: An integer | |
""" | |
def __init__(self, capacity): | |
self.size = capacity | |
self.dic = {} | |
self.time = 0 | |
""" | |
@param: key: An integer | |
@param: value: An integer | |
@return: nothing | |
""" | |
def put(self, key, value): | |
if self.size <= 0: | |
return | |
self.time += 1 | |
if len(self.dic) == self.size and key not in self.dic: | |
vals = list(self.dic.values()) | |
heapq.heapify(vals) | |
evt = heapq.heappop(vals) | |
del self.dic[evt[3]] | |
if key not in self.dic: | |
self.dic[key] = [0, self.time, value, key] | |
else: | |
p = self.dic[key] | |
p[2] = value | |
p[0] += 1 | |
p[1] = self.time | |
""" | |
@param: key: An integer | |
@return: An integer | |
""" | |
def get(self, key): | |
self.time += 1 | |
if key in self.dic: | |
p = self.dic[key] | |
p[0] += 1 | |
p[1] = self.time | |
return p[2] | |
else: | |
return -1 | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment