[Mock] Microsoft 11

1446. Consecutive Characters

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.

Return the power of the string.

My Answer 1: Accepted (Runtime: 52 ms - 29.15% / Memory Usage: 14.2 MB - 42.53%)

class Solution:
    def maxPower(self, s: str) -> int:
        ans = 1
        prev = s[0]
        length = 1
        for i in range(1, len(s)):
            if prev == s[i]:
                length += 1
            else:
                ans = max(ans, length)
                length = 1
            prev = s[i]
        
        ans = max(ans, length)
        
        return ans

이전 문자값 prev 와 비교해서 연속되는지 확인

연속되지 않으면 ans 를 최댓값으로 update 해주고 length 는 초기화

---

1448. Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

My Answer 1: Accepted (Runtime: 240 ms - 79.47% / Memory Usage: 33.5 MB - 43.66%)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def func(root, greater):
            if root is None:
                return
            
            if greater <= root.val:
                self.ans += 1
                greater = root.val
            
            func(root.left, greater)
            func(root.right, greater)
        
        self.ans = 0
        func(root, root.val)
        
        return self.ans

DFS 로 보면서 루트값들 중 최댓값을 greater 에 넣어줌

if greater <= root.val: => ans += 1 & greater update

---

759. Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.
Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

My Answer 1: Accepted (Runtime: 81 ms / Memory Usage: 5.96 MB) - 97.88%

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param schedule: a list schedule of employees
    @return: Return a list of finite intervals 
    """
    def employeeFreeTime(self, schedule):
        # Write your code here

        slist = []
        # schedule interval 들끼리 묶어서 모두 slist 에 저장
        while len(schedule) != 0:
            for i in range(len(schedule)):
                if len(schedule[i]) == 0:
                    continue
                slist.append([schedule[i][0], schedule[i][1]])
                schedule[i].pop(0)
                schedule[i].pop(0)
            if [] in schedule:
                schedule.remove([])

        slist.sort()
        
        # 맨 처음 값으로 left, right 경계 설정
        left = Interval(-float('inf'), slist[0][0])
        right = Interval(slist[0][1], float('inf'))
        slist.pop(0)    # 초기화로 썼으니까 없애주기

        ans = []
        for a, b in slist:
            if left.end >= a:
                left.end = b
            if right.start < a:
                ans.append(Interval(right.start, a))
            if right.start <= b:
                right.start = b

        return ans

lintcode 야 오늘도 고맙다..^^

minheap 이런거도 생각했지만.. 굳이 필요없을듯

예시) [[1,2,5,6],[1,3],[4,10]]

1. schedule 은 2 개 단위로 뜯어서 slist 에 넣어줌
   => [1,2], [1,3], [4,10], [5,6]

2. 정렬 한번 해주기

3. 예시를 보니까 [-inf, 1], [3, 4], [10, inf] 이런 식으로 -inf 와 inf 도 고려하길래
   left = [-inf, 맨 처음 start], right = [맨 처음 end, inf] 를 잡아줌

4. left, right 와 비교하면서 free time 찾기

left.end 값 update => 사실상 필요 없음

비교대상 = [a, b] 라고 할 때,

비교대상이 right 의 범위 안에 포함되면
=> right.start ~ a 사이는 free time 이니까 ans 에 넣어주기

비교대상이 right 의 범위 안에 포함되거나 걸쳐지면 =>right.start update