[leetcode] 131, 134, 217, 234

217. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

My Answer 1: Accepted (Runtime: 112 ms - 91.48% / Memory Usage: 21.4 MB - 18.67%)

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        count = collections.Counter(nums)
        
        for k, v in count.items():
            if v > 1:
                return True
        
        return False

Counter 로 중복 되는 숫자 찾기

그냥 딕셔너리 써서 이미 존재하는 숫자인지 확인해도 된다

if nums[i] in nums[i+1:] 로 확인하면 타임리밋 걸림

---

234. Palindrome Linked List

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

My Answer 1: Accepted (Runtime: 676 ms - 95.10% / Memory Usage: 31.5 MB - 95.01%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        h = head
        length = 0
        while head:
            length += 1
            head = head.next
            
        head = h
        prev = None
        for i in range(length//2):
            n = head.next
            head.next = prev
            prev = head
            head = n
            
        if length % 2 != 0:
            head = head.next
        
        while head and prev:
            if head.val != prev.val:
                return False
            head = head.next
            prev = prev.next
        
        return True

처음에는 노드의 value 값들만 리스트에 저장해서 palindrome 인지 확인하는게 먼저 생각났지만

Follow up: Could you do it in O(n) time and O(1) space?

를 만족시켜 보기 위해서... 추가 리스트를 사용하지 않음

1. 전체 노드 길이 계산 => length

2. 0 ~ length//2 까지의 노드들 reverse
   => prev 는 앞에 reverse 된 노드들을, head 는 나머지 절반 노드들을 가리킴
   => length 가 홀수개이면 중간 값은 비교할 필요가 없으므로 head = head.next

3. prev 와 head 값이 같은지 비교

Solution 1: Accepted (Runtime: 772 ms - 78.50% / Memory Usage: 39.2 MB - 84.56%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast = slow = head
        # find the mid node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # reverse the second half
        node = None
        while slow:
            nxt = slow.next
            slow.next = node
            node = slow
            slow = nxt
        # compare the first and second half nodes
        while node: # while node and head:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next
        return True

fast, slow 써서 중간 노드를 찾고 오른쪽 반을 reverse 한 후, 반끼리 비교

---

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

My Answer 1: Time Limit Exceeded (16 / 32 test cases passed.)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        
        def func(s):
            p = 1
            for i in range(len(s)):
                if s[i] == s[i][::-1]:
                    p = 1
                else:
                    p = 0
                    break
            if p and s not in ans:
                ans.append(s)
                
            if len(s) == 1:
                return
            
            for i in range(len(s)-1):
                func(s[:i]+[s[i]+s[i+1]]+s[i+2:])
        
        func(list(s))
        
        return ans

ex) s = "aab" => ["a","a","b"] 처럼 s 를 리스트로 바꿔서

재귀로 s[i] 에 한 문자씩 더 붙여주면서 조합들 찾아줌

s 의 값들을 매번 palindrome 인지 확인해줘서 더 느린 듯...^^

Solution 1: Accepted (Runtime: 628 ms - 64.90% / Memory Usage: 26.7 MB - 59.77%)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        self.backtrack(s, start=0, path=[], res=res)
        return res

    def backtrack(self, s, start, path, res):
        if start == len(s):
            res.append(path)
            return

        for end in range(start + 1, len(s) + 1):
            sub = s[start: end]
            if sub == sub[::-1]:    #isPalindrome
                self.backtrack(s, end, path + [sub], res)

start, end 를 잡아서 그 구간의 문자열이 palindrome 일때만 재귀

다음 번에는 end 앞은 볼 필요가 없으므로 다음 start 값으로 넘겨준다

이걸로 외워!!!

---

134. Gas Station

https://leetcode.com/problems/gas-station/

My Answer 1: Accepted (Runtime: 5184 ms - 5.92% / Memory Usage: 15.3 MB - 19.06%)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        ans = 0
        tank = 0
        i = 0
        while i < len(gas):
            if gas[i] >= cost[i]:
                tank = gas[i]
                tmp = gas[i]
                gas[i] = 0
                j = i
                for _ in range(len(gas)):
                    n = j+1 if j+1 < len(gas) else 0
                    if tank - cost[j] < 0:
                        break
                    tank = tank - cost[j] + gas[n]
                    j = n
                    if tank < 0:
                        break
                if j == i and tank >= gas[i]:
                    return i
                gas[i] = tmp
                    
            i += 1
            
        return -1

1. if gas[i] >= cost[i]: 일 때를 시작 값으로 잡음

2. tank 에 gas 를 넣어주고 0 으로 바꿔서 시작 표시를 남겨줌

3. for 문 돌려서 n 은 다음 인덱스를 가리키도록 함 (끝까지 가면 순회해야하니까 0 으로)
   tank 계산하면서 음수가 되면 break 로 빠져나가도록

4. 한바퀴 돌아서 원점(i) 으로 왔고 tank 도 부족하지 않으면 return
   아니면 다시 gas 를 원래 값으로 채워주고 다른 시작점 찾아가기

Solution 1: Accpeted (Runtime: 52 ms - 73.62% / Memory Usage: 15.3 MB - 27.97%)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if (sum(gas) - sum(cost) < 0):
            return -1
        
        gas_tank, start_index = 0, 0
        
        for i in range(len(gas)):
            gas_tank += gas[i] - cost[i]
            
            if gas_tank < 0:
                start_index = i+1
                gas_tank = 0
            
        return start_index

sum(gas) - sum(cost) < 0 일 때는 아예 성립할 수 없으니까 -1

그냥 0부터 시작해서 gas[i] - cost[i] 값들을 계속 더해주다가
gas_tank < 0 이면 start_index 를 옮겨주고 tank 도 초기화