본문 바로가기
[JAVA] LeetCode 94 - Binary Tree Inorder Traversal 문제 Given the root of a binary tree, return the inorder traversal of its nodes' values. 이진 트리의 루트가 주어지면, 중위 순회(inorder traversal)하여 노드의 값을 출력하라. 풀이 방법 트리를 순회 하는 방법에는 대표적으로 3가지 방법이 있는데 각각 전위(preorder), 중위(inorder), 후위 순회(postorder)이다. 전위의 경우, ROOT를 가장 먼저 탐색하는 방법으로 ROOT -> LEFT 자식 노드 -> RIGHT 자식 노드 순으로 탐색하며, 후위의 경우, ROOT를 가장 나중에 탐색하는 방법으로 LEFT 자식 노드 -> RIGHT 자식 노드 -> ROOT 순으로 탐색한다. 오늘 문제에 주어진 중위 순회..
[JAVA] LeetCode 101 - Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). 이진 트리가 주어질 때, 대칭 되는지 확인하여라. (가운데를 중심으로) 풀이 방법 트리가 대칭이 되기 위한 조건들을 뽑아보자. 그림을 그려보면 아래 코드를 이해하기 더 쉬울 것! /** * 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,..
[JAVA] LeetCode 70 - Climbing Stairs You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 너는 계단을 오르고 있다. 정상에 오르려면 n개의 계단을 올라야 한다. 매 타임마다 너는 1개 또는 2개의 계단만을 오를 수 있다. 정상에 오를 수 있는 방법의 가짓수를 구하라. 풀이 방법 n의 값에 따른 방법의 가짓수를 정리해보면 아래와 같다. n = 1일 때 1, n = 2일 때 2, n = 3일 때 3, n = 4일 때 5 ... 위와 같이 증가하는 방법의 가짓수를 미루어보아 n = (n-1) + (n-2) 라는 ..
[JAVA] LeetCode 202 - Happy Number Write an algorithm to determine if a number n is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are ha..
[JAVA] LeetCode 121 - Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. i일의 주식의 가격이 주어진 배열이 있다고 하자. 최대 한 번의 거래만 가능할 경우, 최대 이익을 얻기 위한 알고리즘을 작성하라. 단, 주식을 사기 전에는 주식을 팔 수 없..
[JAVA] LeetCode 191 - Number of 1 Bits Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). 부호 없는 정수가 가지는 1 비트 수를 반환하는 함수를 작성하라 (Hamming Weight 이라고도 함) # Hamming Weight 이라는 알고리즘이 생소해 구글링을 해보니 2진수로 바꾸었을 때 길이가 n인 정수에서 1인 bit만 세어보는 알고리즘 이라고 한다. 풀이 방법 n이 0이 아닐 때까지, 비트 연산을 수행하며 카운팅을 수행한다. public class Solution { public int hammingWeight(int n) { int cnt = 0; while(n ..
[JAVA] LeetCode 350 - Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. 두 배열이 주어지면, 그 중 중복되는 항목들을 반환하는 함수를 작성하라. 풀이 방법 1. 두 배열을 리스트로 변환한다. 2. 두 리스트 중 사이즈가 더 작은 리스트의 길이만큼 반복문을 수행한다. 3. 사이즈가 작은 리스트에 있는 항목을 사이즈가 큰 리스트에서 찾는다. 4. 같은 항목이 존재할 경우, 결과 리스트에 add한다. 5. 리스트 타입인 result를 배열로 변환하여 리턴한다. class Solution { public int[] intersect(int[] nums1, int[] nums2) { List list1 = Arrays.stream(nums1).boxed().colle..
[JAVA] LeetCode 268 - Missing Number Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. [0, n] 범위의 고유 숫자 n개를 포함하는 배열이 주어지면, 배열에서 누락된 숫자를 반환하라. 풀이 방법 1. 배열의 길이만큼 반복문을 수행하며 0부터 n까지의 합과, 배열의 요소의 합을 구한다. 2. 두 수의 차를 반환한다. (두 수의 차는 누락된 수이므로) class Solution { public int missingNumber(int[] nums) { int sum = 0, arr = 0; for(int i=0; i

티스토리툴바