Day 4. 02/11/20

[tech-cow]

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?)

[tech-cow]

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 cur1

[tech-cow]

116 | 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 newRoot

[tech-cow]

116 | 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)

---

[tech-cow]

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) + 1

[tech-cow]

560. 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