gaki gaki

[LeetCode] 206. Reverse Linked List 풀이_#1 반복문 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: curr = head if (not curr): return None before = None while(curr): temp = curr.next curr.next = before before = curr curr = temp return..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: node = ListNode() r = node while (list1 or list2): num1, num2 = 101, 101 if (list1): num1 = list1.val if (list2): num2 = list2.val node.next = ListNod..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: node = ListNode() r = node while (list1 or list2): num1, num2 = 101, 101 if (list1): num1 = list1.val if (list2): num2 = list2.val node.next = ListNod..

[LeetCode] BFS 와 접근법 문제: 542. 01 Matrix 풀이: BFS 로 정답을 유추해야한다. 처음에 시간초과가 났었는데 그 이유는 0 이 아닌 모든 노드들을 기준으로 bfs 를 돌렸기 때문이다. 이렇게 되면 visited 배열을 1번 bfs 돌릴때마다 일일이 초기화 해야하는 비효율성이 있었고, 이미 탐색한 노드를 여러번 봐야한다. 물론 위의 풀이도 맞는 풀이긴 한데 비효율적이고 시간이 오래걸림 하지만, 0인 노드를 기준으로 bfs 를 돌리면, queue 특성상, dx,dy 로 move 한 노드의 값은 현재 노드의 값 + 1 이 된다. 따라서 이 특징을 활용하면 visited 배열을 딱 1번만 만들면 되고, 이미 방문했던 노드는 다시 방문할 필요가 없다는 장점이 있다. from colle..

이진트리 이진트리란? 컴퓨터 과학에서, 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 이진트리 관련 문제 https://leetcode.com/problems/merge-two-binary-trees/ 이진트리를 병합하는 방법 풀이법_#1. 재귀함수 사용 파이썬 클래스 매서드를 재귀호출하려면 함수이름앞에 self. 을 붙여야함. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left ..

[LeetCode] 557. Reverse Words in a String III 방법_#1 time O(N) space O(N) 스페이스를 기준으로 문자열을 분리한 뒤, 각각의 문자열을 리버스한 뒤 결합 class Solution(object): def reverseWord(self, word): return word[::-1] def reverseWords(self, s): """ :type s: str :rtype: str """ # time :O(N) space: O(N) arr = s.split() l = list(map(self.reverseWord, arr)) r = "" for k in range(len(l)): r += l[k] if (k != len(l) - 1): r += " " re..

167. Two Sum II - Input Array Is Sorted 방법_#1 투포인터 time : O(N) space: O(1) class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ n = len(numbers) low = 0 high = n - 1 while (low < high): value = numbers[low] + numbers[high] if (value == target): return [low + 1, high + 1] elif (value < target): low += 1 else: high -= 1 방법_..

[LeetCode] 283. Move Zeroes 방법_#1 remove 를 사용해서 0 을 제거한 다음, 처음 리스트 길이와 제거된 리스트 길이만큼 0을 추가하는 방법 time : O(N*K) space: O(1) class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ n = len(nums) while (nums.count(0) > 0): nums.remove(0) m = len(nums) for i in range(n-m): nums.append(0) 방법_#2 배열을 순회하면서 0이 아닌 ..