[Mock] Adobe 1

717. 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

My Answer 1: Accepted (Runtime: 196 ms - 6.06% / Memory Usage: 19.6 MB - 5.03%)

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        # 문제 이해가 안됨둥
        
        def decode(bits, ch):
            if len(bits) == 0 and (ch == "" or ch == "0"):
                return True
            
            if len(bits) == 0 and ch == "1":
                return False
            
            if ch == "10" or ch == "11" or ch == "0":
                ch = ""
            
            if len(bits) > 0:
                return decode(bits[1:], ch + str(bits[0]))
        
        return decode(bits, "")

재귀 이용

맨 마지막 character 만 남을 때까지 10, 11, 0 의 조합들은 모두 패스하고

마지막 character 가 two bit 일지, one bit 일지 확인해줌

남아있는 ch 가 없거나 0 이면 마지막 자리가 one bit 가 되니까 return True

남아있는 ch 가 1 이면 마지막 자리가 two bit 10 만 가능하므로 return False

---

703. Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Returns the element representing the kth largest element in the stream.

My Answer 1: Accepted (Runtime: 1056 ms - 10.90% / Memory Usage: 18.4 MB - 54.31%)

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.nums = sorted(nums)
        self.k = k
        print(self.nums)

    def add(self, val: int) -> int:
        self.nums.append(val)
        self.nums.sort()
        return self.nums[len(self.nums)-self.k]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

정렬한 nums 에 val 를 add 하면 다시 정렬해서 KthLargest return

...양심이 찔려서 Binary Search 써서 add 해주려고 했는데 시간이 부족했네요..ㅎ

값을 넣을때마다 자동으로 정렬해주는 것도 생각났는데 뭔지 정확히 기억이 안남..^^
min-heap 이었나 암튼 그것도 좋을듯