Day 2. 02/09/20
tech-cow opened this issue · 7 comments
tech-cow commented
- 257 | Binary Tree Paths (Recurisive + Iterative)
- 34 Find First and Last Position of Element in Sorted Array
- 67 Add Binary
- 297 | Serialize and Deserialize Binary Tree
- 273. Integer to English Words
- 76 Minimum Window Substring
tech-cow commented
257 | Binary Tree Paths (Recurisive + Iterative)
[7:57] - [8:02] Brainstorming
[8:02] Solution 1: Recursive DFS
Bug 1
[8:09] Bug 1:
line: self.dfsHelper(root.left, tempPath + root.val + "->", res)
bug: cannot concatenate "str" and "int" objects[8:10] Recursive DFS Bug Free
class Solution(object):
def binaryTreePaths(self, root):
if not root: return ""
res = []
self.dfsHelper(root, "", res)
return res
def dfsHelper(self, root, tempPath, res):
if not root: return
if not root.left and not root.right:
res.append(tempPath + str(root.val))
return
if root.left:
self.dfsHelper(root.left, tempPath + str(root.val) + "->", res)
if root.right:
self.dfsHelper(root.right, tempPath + str(root.val) + "->", res)[8:11] Solution 2 : Iterative BFS
[8:20] Bug 1
Line: queue = deque([(root, str(root.val) + "->")])
bug :
getting ["1->1->3","1->1->2->5"] as output
shouldn't need to initialize from scractch, just "" since root itself
will be added later[8:22] BFS Bugfree
from collections import deque
class Solution(object):
def binaryTreePaths(self, root):
if not root: return ""
queue = deque([(root, "")])
res = []
while queue:
node, curPath = queue.popleft()
if not node.left and not node.right:
res.append(curPath + str(node.val))
if node.left:
queue.append((node.left, curPath + str(node.val) + "->"))
if node.right:
queue.append((node.right, curPath + str(node.val) + "->"))
return res[8:23] Solution 3 : Stack Bugfree
class Solution(object):
def binaryTreePaths(self, root):
if not root: return ""
stack = [(root, "")]
res = []
while stack:
node, curPath = stack.pop()
if not node.left and not node.right:
res.append(curPath + str(node.val))
if node.left:
stack.append((node.left, curPath + str(node.val) + "->"))
if node.right:
stack.append((node.right, curPath + str(node.val) + "->"))
return resAftermath
Duration: [8:25 Finish] Total 28 mins
Bug retrospect:
- check type when adding elements.
- thinking twice about queue/stack initialization.
tech-cow commented
34 Find First and Last Position of Element in Sorted Array
Bug-free
"""
[Start] | 11:47
"""
class Solution(object):
def searchRange(self, nums, target):
if not nums: return [-1, -1]
leftIndex = self.findLeftIndex(nums, target)
rightIndex = self.findRightIndex(nums, target)
return [leftIndex , rightIndex]
def findLeftIndex(self, nums, target):
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
right = mid
elif nums[mid] < target:
left = mid
else:
right = mid
# Post
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
def findRightIndex(self, nums, target):
left, right = 0, len(nums) - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
left = mid
elif nums[mid] < target:
left = mid
else:
right = mid
# Post
if nums[right] == target:
return right
if nums[left] == target:
return left
return -1tech-cow commented
67 Add Binary
class Solution(object):
def addBinary(self, a, b):
a, b = a[::-1], b[::-1]
m, n = len(a), len(b)
diff = max(m, n) - min(m, n)
for i in range(diff):
if m < n :
a += "0"
else:
b += "0"
carry = 0
res = ""
for i in range(max(m, n)):
curSum = int(a[i]) + int(b[i]) + carry
carry = 0
if curSum == 3:
carry += 1
res += "1"
elif curSum >= 2:
carry += 1
res += "0"
else:
carry = 0
res += str(curSum)
if carry:
res += str(carry)
return res[::-1]看答案以后更近
class Solution(object):
def addBinary(self, a, b):
i , j = len(a) - 1, len(b) - 1
carry = 0
res = ""
while i >= 0 or j >= 0 or carry:
if i >= 0:
carry += int(a[i])
i -= 1
if j >= 0:
carry += int(b[j])
j -= 1
res = str(carry % 2) + res
carry //= 2
return res
记得找找有没有Follow up
tech-cow commented
297 | Serialize and Deserialize Binary Tree
Struggle a bit, but figure out later, a bit rusty |
Need to code again + try DFS
from collections import deque
class Codec:
def serialize(self, root):
if not root: return ""
res = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
res.append("x")
return ",".join(res)
def deserialize(self, nums):
if not nums: return None
nums = nums.split(",")
index = 0
root = TreeNode(nums[index])
queue = deque([root])
while queue:
node = queue.popleft()
index += 1
if index < len(nums) and nums[index] != "x":
node.left = TreeNode(nums[index])
queue.append(node.left)
index += 1
if index < len(nums) and nums[index] != "x":
node.right = TreeNode(nums[index])
queue.append(node.right)
return rootTry DFS below
class Codec:
def serialize(self, root):
def helper(node):
if not node:
return ["None"]
res = [str(node.val)]
res.extend(helper(node.left))
res.extend(helper(node.right))
return res
return ",".join(helper(root))
def deserialize(self, data):
if not data:
return None
def helper(data):
if not data:
return None
cur = data.pop(0)
if cur == "None":
return None
node = TreeNode(cur)
node.left = helper(data)
node.right = helper(data)
return node
return helper(data.split(","))tech-cow commented
273. Integer to English Words
'''
[8:41] Start
Thoughts (Didn't execute since not sure?):
Use a stack, and looking @ elements from the end
Having a hashmap
{
key | val
reverse index of input | assoicated english words (ex: "hundred", "thousand")
}
manually input some logic around index
[8:44] a bit cancer, give up | Solution Checking & retrospect
[8:44 - 10:52] Eat, Shower, think about this shit, and having brain fart but finally crack it
[10:53] Start Coding again
Problem Soving:
1. digits rules : name changes every thousands
1,000,000,000
b m t
2. Using divide and conquer to continue breaking large number to smaller instance
and have a few base case to handle any numbers smaller than hundreds
[11:41] FUCK it, so many edge case... why?
'''
# dfs: make sure to keep track of parameter passing
class Solution(object):
def numberToWords(self, num):
less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen", "Twenty"]
tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
thousands = ["" , "Thousand", "Million", "Billion"]
res = ""
if num == 0: return "Zero"
for i in range(len(thousands)):
if num % 1000 != 0:
res = self.dfsHelper(num % 1000, less_than_20, tens).strip() + " " + thousands[i] + " " + res
num //= 1000
return res.strip()
def dfsHelper(self, num, less_than_20, tens):
if num < 20:
return less_than_20[num]
elif 20 <= num < 100:
return tens[num // 10] + " " + less_than_20[num % 10]
elif 100 <= num <= 999:
return less_than_20[num // 100] + " Hundred " + self.dfsHelper(num % 100, less_than_20, tens)tech-cow commented
76 Minimum Window Substring
'''
start[6:12]
Problem Solving:
[?] Sliding window algorithm
* Potentially scan through with 2 pointers
- left being the window shrinker
- right being the window extender
extend right point until meeting the condition of S contains all T
take GlobalMin
then shrink the size of left
2 pointer algorithm takes O(N), not sure yet for checking S contains all T part, I am a bit stuck here.
Stuck:
One way to verify Target in S, is the making a set of every window
but that takes O(len(window)) time complexity for convertion
Can we make a dictionary of S before hand
"ADOBECODEBANC"
{
char : count
A : 1
}
I can think of a way in which having Target becomes a hashset
Having a fixed hashtable to store S's state initially
Having a second hashtable to change count frequency
If visted, count of associated element decrement by 1
Each time, for loop -> Target hashset:
then find comparision of inital hashtable & frequently changed hastable to get the diff
If diff more than 1 for every element in hashset
Meet the condition
Time Complexity:
O(N) + O(size of Target)
[6:26] Ok, having brainfart , solution time?
[7:06] Done, need to re-do
'''
from collections import Counter
class Solution:
def minWindow(self, nums , target):
if nums is None: return ""
targetHash = Counter(target)
curHash = {}
targetCount = len(targetHash)
matched = 0
globalMin = float("inf")
size = len(nums)
res = ""
j = 0
for i in range(size):
# 不断增大窗口大小，知道满足所有Match需求
while j < size and matched < targetCount:
if nums[j] in targetHash:
curHash[nums[j]] = curHash.get(nums[j], 0) + 1
if curHash[nums[j]] == targetHash[nums[j]]:
matched += 1
j += 1
# 更新最小值
if j - i < globalMin and matched == targetCount:
globalMin = j - i
res = nums[i:j]
# 删除left的一个元素，使得窗口继续滑动
if nums[i] in targetHash:
if curHash[nums[i]] == targetHash[nums[i]]:
matched -= 1
curHash[nums[i]] -= 1
return restech-cow commented
Sliding Window Template
"""
[start] 12:34
Problem Solving Thought Process:
1. Brute Force
Using 2 for loops to find out 2 element that sums up to the target
Constantly update the minimum length in a globalMin
globalMin = infi
for i -> n
for j -> n
cur_sum += nums[j]
if cur_sum > target:
globalMin = min(globalMin, cur_sum)
break
return globalMin
Time: O(N^2)
Space: O(1)
2. Two Pointer
We can potentially only iterate "j" from beginning to end once by moving "i" along the way
Time: O(N)
Space: O(1)
"""
#[Coding Start] 12:39
#[Coding Finish] 12:43
#[Eyeballing code] 12:43 - 12:46
# Bug
"""
globalMin = float('inf')
curSum = 0
j = 0
for i in range(len(nums)):
while j < len(nums) and curSum < target:
curSum += nums[j]
j += 1
if curSum >= target:
globalMin = min(globalMin, j - i)
curSum -= nums[i]
return globalMin -> bug1. 如果没有找到合适的结果，应该返回0而不是初始值的infinite
fail testcases:
3
[1,1]
"""
class Solution(object):
def minSubArrayLen(self, target, nums):
globalMin = float('inf')
curSum = 0
j = 0
for i in range(len(nums)):
while j < len(nums) and curSum < target:
curSum += nums[j]
j += 1
if curSum >= target:
globalMin = min(globalMin, j - i)
curSum -= nums[i]
return globalMin if globalMin != float('inf') else 0