Day 4. 02/11/20
tech-cow opened this issue · 5 comments
Leetcode
- 160 Intersection of Two Linked Lists (x2 Apperence)
- 116 | Populating Next Right Pointers in Each Node
- 543 Diameter of Binary Tree
- 560 | Subarray Sum Equals K (Can you solve it in O(1) Space?)
160 Intersection of Two Linked Lists (x2 Apperence)
'''
[8:23] Start
Thoughts:
[8:23] Sol 1 (Hashtable):
looping A and B seperately and store hashtable of
{
node reference : index of passing
}
Looping again on shorter linked list and find first intersection
Time: O(len(A)) + O(len(B))
Space: O(len(A)) + O(len(B)) -> Hashmap
[8:26] is O1 space possible?
[8:30] Sol 2 (Two Pointers):
Using slow fast pointer to reverse the pointer.
A -> all the way to c, increment each tiem by 1
B -> all the way to c, increment each tiem by 1
if either A or B hits the end of c, rotate to other track
A -> B track or B -> A track
Because the velocity of each node are different, eventually they would cross each other
Time: O(len(A)) + O(len(B))
Space: O(1)
'''
# [8:35] Start Coding
# [8:47] Bug-free
class Solution(object):
def getIntersectionNode(self, head1, head2):
cur1, cur2 = head1, head2
lastNode1, lastNode2 = None, None
while cur1:
if cur1.next == None:
lastNode1 = cur1
cur1 = cur1.next
while cur2:
if cur2.next == None:
lastNode2 = cur2
cur2 = cur2.next
if lastNode1 != lastNode2:
return None
cur1, cur2 = head1, head2
while cur1 != cur2:
if cur1 and cur1.next == None:
cur1 = head2
if cur2 and cur2.next == None:
cur2 = head1
else:
cur2 = cur2.next
elif cur2 and cur2.next == None:
cur2 = head1
if cur1 and cur1.next == None:
cur1 = head2
else:
cur1 = cur1.next
else:
cur1 = cur1.next
cur2 = cur2.next
return cur1116 | Populating Next Right Pointers in Each Node
This is cancer, looking @ Solution now
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
[8:51] Start
[9:43] Lots of bug, bad implementation, but got it to work with O(Height) Space
You kind of need left and right children to be able to process the
"""
class Solution(object):
def connect(self, root):
if not root: return None
height = self.getHeight(root)
newRoot = Node(root.val)
self.makeBinaryTree(root, newRoot)
lastUnlinkedNode = [None] * (height * 20)
level = 0
self.connectHorizontalNode(newRoot, lastUnlinkedNode, level)
return newRoot
def getHeight(self, root):
height = 0
if root and root.left:
height += 1
root = root.left
return height + 1
def makeBinaryTree(self, root, newRoot):
if not root: return
if root.left:
newRoot.left = Node(root.left.val)
if root.right:
newRoot.right = Node(root.right.val)
left = self.makeBinaryTree(root.left, newRoot.left)
right = self.makeBinaryTree(root.right, newRoot.right)
def connectHorizontalNode(self, newRoot, lastUnlinkedNode, level):
if not newRoot: return
level += 1
left = self.connectHorizontalNode(newRoot.left, lastUnlinkedNode, level)
right = self.connectHorizontalNode(newRoot.right, lastUnlinkedNode, level)
if left and right:
if lastUnlinkedNode[level]:
lastUnlinkedNode[level].next = left
left.next = right
lastUnlinkedNode[level] = right
return newRoot116 | Populating Next Right Pointers in Each Node
BFS Solution
class Solution(object):
def connect(self, root):
if not root:
return
queue = [root]
while queue:
curr = queue.pop(0)
if curr.left and curr.right:
curr.left.next = curr.right
if curr.next:
curr.right.next = curr.next.left
queue.append(curr.left)
queue.append(curr.right)
543. Diameter of Binary Tree
bug-free
class Solution(object):
def diameterOfBinaryTree(self, root):
if not root: return 0
globalMax = [-float('inf')]
self.dfsHelper(root, globalMax)
return globalMax[0]
def dfsHelper(self, root, globalMax):
if not root: return 0
left = self.dfsHelper(root.left, globalMax)
right = self.dfsHelper(root.right, globalMax)
curMax = left + right
globalMax[0] = max(curMax , globalMax[0])
return max(left, right) + 1560. Subarray Sum Equals K
直接看答案，没有除暴力解法以外更好的思路，引用下面文章
作者：charon____
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/c-nshi-jian-nkong-jian-xiang-jie-by-charon____/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
首先对于这类题，暴力的做法是嵌套循环，以每个元素为起始点遍历扫描，检查子数组和是否满足情况。时间复杂度为 O(n^2)，空间复杂度为O(1)。
进一步的优化思路：
首先：优化什么？
目前时间复杂度高，空间复杂度是常数，所以优化点在时间上
时间复杂度的优化都是通过空间来换取时间，而占用存储空间的数据结构应该满足常数时间查找
然后：怎么优化？
暴力算法中有没有重复运算？简单来看，有很多重复的加法运算。例如，在下标为0的时候，运算过 nums[0] + nums[1] + nums[2]，在下标为1的时候，又算了一次nums[1] + nums[2]
找到重复运算后怎么消除重复运算？上例中，重复计算了nums[1] + nums[2]，换一种思路，实际上不需要加法，只需要 nums[0] + nums[1] + nums[2] - nums[0]，再写的清晰一些，用sum[i]表示从0到i所有元素的和，那么nums[1] + nums[2] = sum[2] - sum[0]。这里的sum[i]实际上就是一种前缀和的思路，只需要遍历一次就可以知道所有的前缀和，存在map里，用的时候就可以实现在常数时间的查找。
有了大体的方向后，具体的map怎么存，key是什么，value是什么？对于这个问题来说，我们需要找到的是target k，即sum[j] - sum[i] = k (j > i)，k已知，sum[j]在迭代过程中逐步计算。需要存储的就只有sum[i]，查找sum[i]要常数时间，那么map的key应该是sum[i]。根据约束条件，value应该是当前值的下标。但是在实际实现的时候可以把这个约束隐藏在循环中，对于当前问题，要找到满足子数组的个数，value可以用来存储到当前位置，前缀和的个数，那么在找到满足的sum[i] = sum[j] - k的时候，最后的结果只需要加上map[sum[j] - k]即可。
class Solution:
def subarraySum(self, nums, target):
'''
dic structure
{
preSum at ith element for i in range(len(nums)) : apperence count
}
'''
dic = {0:1} # Sum of 0 already exist to be 1.
res = preSum = 0
for num in nums:
preSum += num
# Similar to 2Sum here
if (preSum - target) in dic:
res += dic[preSum - target]
dic[preSum] = dic.get(preSum, 0) + 1
return res