[Mock] Random 8

17分ほど遊んだらほどけました…^^

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: 56 ms - 15.23% / Memory Usage: 14.3 MB - 39.69%)

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        tmp = []
        t = ""
        carry = 1
        for i in range(len(bits)):
            if t == "10" or t == "11" or t == "0":
                tmp.append(t)
                t = ""
                
            t += str(bits[i])
            
        tmp.append(t)
        
        if tmp[-1] != "0":
            return False
        return True

tの値で10、11、0に分けられます.
最後の値は1 bit
int型を使用可能

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: 960 ms - 11.26% / Memory Usage: 18.7 MB - 8.77%)

class KthLargest:

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

    def add(self, val: int) -> int:
        self.arr.append(val)
        self.arr.sort()
        ans = self.arr[len(self.arr) - self.kth]
        return ans


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

時間がないので、超低効率コードが登場^^
まずsortとして挿入してソートし、k番目の大きな値を返します.
この場合、k番目の小さな値だと思って挿入しましたが...ううう

My Answer 2: Accepted (Runtime: 180 ms - 19.68% / Memory Usage: 18.7 MB - 14.81%)

class KthLargest:

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

    def add(self, val: int) -> int:
        l = 0
        r = len(self.arr)-1
        
        while l <= r:
            m = (l+r) // 2
            
            if self.arr[m] > val:
                r = m - 1
            else:
                l = m + 1
        
        self.arr.insert(l, val)
        
        ans = self.arr[len(self.arr) - self.kth]
        return ans


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

最後の分にBinary Searchで探してINSERTに変更します
ちょっと早い^^
まだ時間があればmin-heapを使うかもしれません

Solution 1: Accepted (Runtime: 96 ms - 71.63% / Memory Usage: 18.4 MB - 51.87%)

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.heap = nums
        heapq.heapify(self.heap)
        self.k = k

    def add(self, val: int) -> int:
        heapq.heappush(self.heap,val)
        # if heap grows bigger then k remove elements
        while len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]


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

Min-Heapの使用
追加するたびにpopを使用してcarry値をk番目に大きく維持します.