23.02.07 Today’s Leetcode

904. Fruit Into Baskets (medium)

time exceeded 같은 느낌의 풀이.

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        counter = collections.Counter()
        n = len(fruits)
        types = [-1, -1]
        res = -1
        for i in range(n):
            new_type = fruits[i]
            if new_type not in types:
                types[1], types[0] = types[0], fruits[i]
                if types[1] != -1:
                    temp = 0
                    j = i - 1
                    while j >= 0 and fruits[j] == types[1]:
                        j -= 1
                        temp += 1
                    counter = collections.Counter()
                    counter[types[1]] = temp
            elif new_type == types[1]:
                types[0], types[1] = types[1], types[0]

            counter[new_type] += 1
            print(counter)
            res = max(res, counter[types[0]] + counter[types[1]])
        
        return res

다른 풀이. 왜 잘 돌아가는지 이해하지 못했어요.

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        basket = {}
        left = 0
        res = 0
        for right, fruit in enumerate(fruits):
            basket[fruit] = basket.get(fruit, 0) + 1
            if len(basket) > 2:
                basket[fruits[left]] -= 1
                if basket[fruits[left]] == 0:
                    basket.pop(fruits[left])
                left += 1
            # print(basket)
        # print(len(fruits))
        # print(right, left)
        return right - left + 1

52. N-Queens II (hard)

N-Queens I 과 유사하게 풀었읍니다.

class Solution:
    def totalNQueens(self, n: int) -> int:
        res = 0

        def help(index, position):
            nonlocal res
            if index == n:
                res += 1
                return

            position.append(-99)
            for i in range(n):
                if not valid(position, index, i):
                    continue
                position[index] = i
                help(index + 1, position)

        def valid(position, index, i):
            for col in range(index):
                pos = position[col]
                if pos == i or abs(col - index) == abs(pos - i):
                    return False
            return True
        
        for i in range(n):
            help(1, [i])
        return res

66.Plus One (easy)

[9,9,9,9] -> [1,0,0,0,0]

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        temp = digits[::-1]
        temp[0] += 1
        temp.append(0)
        for i in range(len(temp) - 1):
            if temp[i] == 10:
                temp[i] = 0
                temp[i + 1] += 1
        if temp[-1] == 0:
            temp.pop(-1)
        return temp[::-1]

69. Sqrt(x) (easy)

Binary Search 처럼 풀었어요.

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        if x == 1: return 1
        temp = [0, x]
        while (temp[1] - temp[0]) > 1:
            i = (temp[0] + temp[1]) // 2
            n = i * i
            if n == x:
                return i
            elif n > x:
                temp[1] = i
            else:
                temp[0] = i
            print(temp)
        return temp[0]

86. Partition List (medium)

less, greater than equal node를 각각 만들어서 greater than equal node를 less node에 연결시켜 문제를 풀었어요.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less, greater = ListNode(0), ListNode(0)
        _less, _greater = less, greater
        while head:
            if head.val < x:
                _less.next = ListNode(head.val)
                _less = _less.next
            else:
                _greater.next = ListNode(head.val)
                _greater = _greater.next
            head = head.next
        
        # print(less)
        # print(greater)

        _less.next = greater.next

        return less.next

92. Reverse Linked List II (medium)

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """

        if not head:
            return None

        left, right = head, head
        stop = False
        def recurseAndReverse(right, m, n):
            nonlocal left, stop

            # base case. Don't proceed any further
            if n == 1:
                return

            # Keep moving the right pointer one step forward until (n == 1)
            right = right.next

            # Keep moving left pointer to the right until we reach the proper node
            # from where the reversal is to start.
            if m > 1:
                left = left.next

            # Recurse with m and n reduced.
            recurseAndReverse(right, m - 1, n - 1)

            # In case both the pointers cross each other or become equal, we
            # stop i.e. don't swap data any further. We are done reversing at this
            # point.
            if left == right or right.next == left:
                stop = True

            # Until the boolean stop is false, swap data between the two pointers     
            if not stop:
                left.val, right.val = right.val, left.val

                # Move left one step to the right.
                # The right pointer moves one step back via backtracking.
                left = left.next           

        recurseAndReverse(right, m, n)
        return head

217. Contains Duplicate (easy)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        temp = set()
        for num in nums:
            if num in temp:
                return True
            temp.add(num)
        return False

53. Maximum Subarray (medium)

kadane’s algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        total = 0
        res = -10**9
        min_value = 10**9
        for index, num in enumerate(nums):
            total += num
            res = max(res, total - min_value, total, num)
            min_value = min(min_value, total)
        return res