23.05.23 Today’s Leetcode

703. Kth Largest Element in a Stream (easy)

class KthLargest:

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

    def add(self, val: int) -> int:
        index = bisect_right(self.d, val)
        self.d.insert(index, val)
        return self.d[-self.k]


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

372. Super Pow (medium)

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        d = [a % 1337]
        n = len(b)
        for i in range(n - 1):
            d.append((d[-1] ** 10) % 1337)
        
        print(d)
        res = 1
        d = d[::-1]
        for i in range(n):
            res *= (d[i] ** b[i])
            res %= 1337
        
        return res

371. Sum of Two Integers (medium)

class Solution:
    def getSum(self, a: int, b: int) -> int:
        f = 0
        if a < 0 and b < 0:
            f = 1
        mask = 0xffffffff
        add = a ^ b
        carry = (a & b) << 1
        while carry != 0:
            add, carry = (add ^ carry) & mask, ((add & carry) << 1) & mask      
        return ~(add ^ mask) if f else add

386. Lexicographical Numbers (medium)

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []
        
        @functools.lru_cache(None)
        def help(init):
            temp = []
            for i in range(10):
                num = 10 * init + i
                if num <= n and num > 0:
                    temp.append(num)
                    temp += help(num)

            return temp

        return help(0)

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        return sorted(list(range(1, n+1)), key=str)

397. Integer Replacement (medium)

class Solution:
    def integerReplacement(self, n: int) -> int:
        dp = {}
        dp[1] = 0
        def dfs(k):
            if k in dp:
                return dp[k]
            temp = 0
            if k % 2 == 0:
                temp = dfs(k // 2) + 1
            else:
                temp = min(dfs(k - 1), dfs(k + 1)) + 1
            
            dp[k] = temp
            return dp[k]
        
        return dfs(n)

409. Longest Palindrome (easy)

class Solution:
    def longestPalindrome(self, s: str) -> int:
        counter = Counter(s)
        res = 0
        check = False
        for v in counter.values():
            if v % 2 == 0:
                res += v
            else:
                res += (v - 1)
                check = True

        return res + 1 if check else res