[leetcode] 17, 19, 26, 28

shsh·2021년 7월 30일

leetcode

목록 보기

135/161

26. Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

My Answer 1: Time Limit Exceeded (361 / 362 test cases passed.)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        ans = 1
        prev = nums[0]
        right = len(nums)-1
        i = 1
        while i <= right:
            if prev == nums[i]:
                for j in range(i, right):
                    nums[j], nums[j+1] = nums[j+1], nums[j]
                right -= 1
            elif prev > nums[i]:
                break
            else:
                ans += 1
                prev = nums[i]
                i += 1
        
        return ans

prev 값이랑 비교해서 같으면 뒤로 쭉 옮겨주기
그나마 적게 움직이려고 right 변수 설정해서 옮길 위치 정해줌

decreasing 하면 break
increasing 하면 prev 재설정 & 한칸 앞으로

in-place 에 너무 신경을 써서 뇌정지가 왔나봅니다..

Solution 1: Accepted (Runtime: 80 ms - 88.59% / Memory Usage: 15.7 MB - 67.60%)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[j-1]:
                i += 1
                nums[i] = nums[j]
        return i+1

바로 앞의 값이랑 비교해서 다르면 nums[i] 로 이동시킴

이렇게 간단한 걸 넘 어렵게 생각했나봐요...

28. Implement strStr()

https://leetcode.com/problems/implement-strstr/

My Answer 1: Accepted (Runtime: 32 ms - 77.62% / Memory Usage: 14.6 MB - 28.13%)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:
            return haystack.index(needle)
        elif haystack == needle:
            return 0
        else:
            return -1

needle 이 haystack 에 존재하면 그때의 인덱스 return

같으면 0, 없으면 -1 return

17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

My Answer 1: Accepted (Runtime: 24 ms - 96.33% / Memory Usage: 14.2 MB - 63.01%)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
        
        if len(digits) == 0:
            return []
        
        lists = []
        for i in range(len(digits)):
            lists += [phone[digits[i]]]
        
        self.ans = []
        def comb(l, c):
            if len(c) == len(digits):
                self.ans.append(c)
                return
            if len(l) == 0:
                return
            
            for i in range(len(l)):
                for j in range(len(l[i])):
                    comb(l[i+1:], c + l[i][j])
        
        comb(lists, "")
        
        return self.ans

딕셔너리에 대응하는 값들 정리

사용할 딕셔너리 값들만 lists 에 추가

재귀 함수 돌려서 combination 찾아주기

19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

My Answer 1: Accepted (Runtime: 36 ms - 51.65% / Memory Usage: 13.9 MB - 98.79%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        h = head
        length = 0
        while h:
            length += 1
            h = h.next
        
        h = ListNode(-1, head)
        h2 = h
        for i in range(length-n):
            h = h.next
        
        if h.next == head:
            h.next = head.next
            return h.next
        
        h.next = h.next.next
        
        return h2.next