23.07.19 Today’s Leetcode

435. Non-overlapping Intervals (medium)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)  return 0;

        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int end = intervals[0][1];
        int count = 1;

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.length - count;
    }
}

2446. Determine if Two Events Have Conflict (easy)

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        def convert(time):
            return int(time[0:2]) * 60 + int(time[3:])

        event1 = [convert(time) for time in event1]
        event2 = [convert(time) for time in event2]
        print(event1, event2)

        return not (event1[1] < event2[0] or event2[1] < event1[0])

437. Path Sum III (medium)

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:

        def dfs(cur, num):
            if not cur: return 0
            temp = 0
            num += cur.val
            if num == targetSum:
                temp += 1

            temp += dfs(cur.left, num)
            temp += dfs(cur.right, num)
            return temp

        def help(cur):
            res = 0
            q = deque([cur])
            while q:
                tar = q.pop()
                res += dfs(tar, 0)
                if tar.left:
                    q.append(tar.left)
                if tar.right:
                    q.append(tar.right)
            
            return res
        
        return help(root) if root else 0

with HashMap

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        hashMap = {}
        self.count = 0

        def dfs(node, targetSum, acculatedSum, hashMap):
            if node == None:
                return
            newAcSum = node.val + acculatedSum
            if acculatedSum in hashMap:
                hashMap[acculatedSum] = hashMap[acculatedSum] + 1
            else:
                hashMap[acculatedSum] = 1
            
            if newAcSum - targetSum in hashMap and hashMap[newAcSum - targetSum] > 0:
                self.count = self.count + hashMap[newAcSum - targetSum]

            dfs(node.left, targetSum, newAcSum, hashMap)
            dfs(node.right, targetSum, newAcSum, hashMap)
            
            hashMap[acculatedSum] = hashMap[acculatedSum] - 1
            
        dfs(root, targetSum, 0, hashMap)
        return self.count