본문 바로가기

Coding Test103

[LeetCode] 876. Middle of the Linked List [JAVA(자바)] 문제 👉 1. 문제 (링크드리스트의 중간) 링크드리스트의 중간을 반환하라. Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL. Input: [1,2,3,4,5,6] Output: Node 4 from this list (S.. 2021. 11. 24.
[LeetCode] 589. N-ary Tree Preorder Traversal [JAVA(자바)] 문제 👉 1. 문제 n 항 트리의 루트가 주어지면 노드 값의 사전 순회(Preorder)를 반환합니다. Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4] Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10] 2. 풀이 preorder 를 이용한 풀이 self -> children 3. 코드 /* // Definition for a Node. class Node { public int val; public List children; public.. 2021. 11. 24.
[LeetCode] 530. Minimum Absolute Difference in BST [JAVA(자바)] 문제 👉 1. 문제 (BST의 최소 절대 차이) 이진 검색 트리 (BST)의 루트가 주어지면 트리에 있는 두 개의 서로 다른 노드 값 간의 최소 절대 차이를 반환합니다. Input: root = [4,2,6,1,3] Output: 1 Input: root = [1,0,48,null,null,12,49] Output: 1 2. 풀이 이진검색트리 - inorder 를 이용한 풀이 이진 검색 트리의 inorder -> 오름차순 정렬이 됨! 트리 순회 preorder : self -> left -> right inorder : left -> self -> right postorder : left -> right -> self 3. 코드 class Solution { int minValue, preValue; b.. 2021. 11. 24.
[LeetCode] 461. Hamming Distance [JAVA(자바)] 문제 👉 1. 문제 (Hamming Distance (XOR)) 두 정수 사이의 해밍 거리는 해당 비트가 다른 위치의 수입니다. 두 개의 정수 x와 y가 주어지면 그 사이의 해밍 거리를 반환합니다. Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑2. 풀이 비트 연산 을 이용한 풀이 AND (&) : 두 비트가 모두 1이면 1, 아니면 0 OR (|) : 두 비트중 하나라도 1이면 1, 아니면 0 XOR (^) : 두 비트가 다르면 1, 아니면 0 Int 는 4bit (4*8 = 32 bytes) 이므로 32자리까지의 비트를 확인한다. 3. 코드 class Solution { public int hammingDistance(in.. 2021. 11. 24.
[LeetCode] 107. Binary Tree Level Order Traversal II [JAVA(자바)] 문제 👉 1. 문제 (Binary Tree Level Order) 이진 트리의 루트가 주어지면 노드 값의 상향식(bottom-up) 순서 순회를 반환합니다. (i.e., from left to right, level by level from leaf to root) Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]2. 풀이 BFS 를 이용한 풀이 Queue 에서 노드를 순서대로 꺼내 list 에 추가한다. Queue 에 left, right 순서로 자식 노드를 추가한다. Bottom-up 순서로 출력하기 위해 각 층을 나타나내는 list를 ret의 0번 인덱스에 추가한다. 3. 코드 /** * Definition for a binary .. 2021. 11. 24.
[LeetCode] 94. Binary Tree Inorder Traversal [JAVA(자바)] 문제 👉 1. 문제 이진 트리의 루트가 주어지면 노드 값의 순회 순회를 반환합니다. Input: root = [1,null,2,3] Output: [1,3,2]2. 풀이 Inorder : left -> self -> right 3. 코드 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * thi.. 2021. 11. 24.
[LeetCode] 70. Climbing Stairs [JAVA(자바)] 문제 👉 1. 문제 (계단 오르기) 계단을 매번 1개 혹은 2개를 오를 수 있을 때, 계단을 오르는 방법은 몇개인가? Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step2. 풀이 다이나믹 프로그래밍 (DP) 을 이용한 풀이 피보나치 수열 (단순 재귀 함수) f(n) = f(n-1) + f(n-2) f(5) = f(4) + f(3) -> 재귀함수를 통해 반복적인 연산 수행 f(4) = f(4) + f(2) f(3) = f(2) + f(1) f(5)를 구하기 위해 이전에 연산을 했던 f(4), f(3).. 2021. 11. 24.
[LeetCode] 110. Balanced Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (균형 이진 트리) 이진 트리가 높이 균형(Height-Balanced)인지 판단하라. 높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 마한다. 2. 풀이 재귀탐색을 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNo.. 2021. 11. 24.
[LeetCode] 39. Combination Sum [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (조합의 합) 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(csum, idx, path): if csum < 0: return if csum == 0: ret.append(path[:]) return for i in range(idx, len(candidates)): dfs(csum - candidates[i], i, path +.. 2021. 11. 23.

티스토리툴바