[leetcode] 73, 75, 141, 155

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/

My Answer 1: Accepted (Runtime: 52 ms - 80.25% / Memory Usage: 17.5 MB - 80.66%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        
        h1 = head
        h2 = head.next
        
        while h1 and h2:
            if h1 == h2:
                return True
            h1 = h1.next if h1.next else h2.next
            h2 = h2.next.next if h2.next and h2.next.next else h1.next
        
        return False

거북이와 토끼인가 slow and fast 를 이용해서

h1 은 한 노드씩 천천히 움직이고 h2 는 두 노드씩 빠르게 움직여서
둘이 같은 노드를 가리키면 return True

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        h1 = head
        h2 = head
        
        while h2 and h2.next:
            h1 = h1.next
            h2 = h2.next.next
            if h1 == h2:
                return True
        
        return False

이게 더 깔끔하니까 이걸로 외워두자!!

Solution 1: Accepted (Runtime: 60 ms - 26.49% / Memory Usage: 18 MB - 15.44%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        s = set()
        
        while head is not None:
            if head not in s:
                s.add(head)
            else:
                return True
            
            head = head.next
            
        return False

이거는 한번 만나본 노드들을 s 에 넣어서 또 만났을 때 return True 해주는 방식

---

155. Min Stack

https://leetcode.com/problems/min-stack/

My Answer 1: Accepted (Runtime: 624 ms - 6.94% / Memory Usage: 18.1 MB - 57.44%)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

문제 고대로...

Solution 1: Accepted (Runtime: 64 ms - 52.07% / Memory Usage: 17.9 MB - 93.65%)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.A = []
        self.M = []

    def push(self, val: int) -> None:
        self.A.append(val)
        self.M.append(val if not self.M else min(val, self.M[-1]) )

    def pop(self) -> None:
        self.A.pop()
        self.M.pop()

    def top(self) -> int:
        return self.A[-1]

    def getMin(self) -> int:
        return self.M[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

더 빠른 솔루션

두개의 리스트를 사용해서 A 에는 push 순서대로 넣고
M 에는 push 될 때마다 그 순간의 최솟값만 저장

---

73. Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/

My Answer 1: Accepted (Runtime: 124 ms - 88.72% / Memory Usage: 14.9 MB - 90.98%)

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        
        r = set()
        c = set()
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    r.add(i)
                    c.add(j)
        
        for i in range(m):
            if i in r:
                for j in range(n):
                    matrix[i][j] = 0
        
        for j in range(n):
            if j in c:
                for i in range(m):
                    matrix[i][j] = 0

0 인 값의 row, column 인덱스를 r, c 에 각각 넣어줘서
해당하는 행, 렬을 모두 0 으로 바꿔줌

---

75. Sort Colors

https://leetcode.com/problems/sort-colors/

My Answer 1: Accepted (Runtime: 32 ms - 73.89% / Memory Usage: 14.1 MB - 75.70%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                for j in range(i+1, 0, -1):
                    if nums[j] < nums[j-1]:
                        nums[j], nums[j-1] = nums[j-1], nums[j]
                    else:
                        break

전체 길이가 최대 300 이라 얼마 걸리지 않을 것 같아서...

i 값이 i+1 값 보다 크면 더 작은 i+1 값을 앞쪽으로 옮겨줌

1 은 그대로 두고 0 과 2 만 앞 뒤로 옮기는 방법도 생각남

Solution 1: Accepted (Runtime: 32 ms - 77.82% / Memory Usage: 14.1 MB - 76.43%)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low,mid,high = 0,0,len(nums)-1
        
        while(mid<=high):
            if nums[mid] == 0:
                nums[low],nums[mid] = nums[mid],nums[low]
                low+=1
                mid+=1
            elif nums[mid] == 1:
                mid+=1
            else:
                nums[mid],nums[high] = nums[high],nums[mid]
                high-=1

색깔이 0, 1, 2 만 있으므로 0 은 low, 1 은 mid, 2 는 high 를 맡음

중간 값이
0 이면 왼쪽 끝으로 가야하니까 low 값과 mid 값 바꿔주기 & low, mid + 1
1 이면 그대로 있으면 되므로 mid+1
2 면 오른쪽 끝으로 가야하니까 mid 값과 high 값 바꿔주기 & high - 1