Old/LeetCode

LeetCode - 997. Find the Town Judge

문제 In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person l..

LeetCode - 746. Min Cost Climbing Stairs

문제 On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1. 풀이 기초적인 DP 문제이다. 한번에 올라갈 수 있는 계단의 수는 한칸 또는 두칸이며, 해당 칸을 밟을 경우 그만큼의 코스트를 사용한다. 이 때, 최소 코스트를 사용하여 가장 윗 칸까지 이동..

LeetCode - 303. Range Sum Query

문제 풀이 가장 기초적인 DP 문제이다. 0부터 배열의 끝까지의 합을 구한 배열을 하나 선언하여, sumRange 함수가 호출 될 때 사용하면 된다. sum 배열은 0 ~ num.length + 1 값이 존재하며, sum[i]는 num[0]~num[i-1]까지의 합을 의미한다. 따라서 sumRange(i,j)는 sum[j + 1] - sum[i]를 반환하면 원하는 결과를 얻을 수 있다. 코드 더보기 class NumArray { int []nums; int []sum; public NumArray(int[] nums) { this.nums = nums; sum = new int[nums.length + 1]; for(int i=1;i

LeetCode - 226. Invert Binary Tree

문제 풀이 해당 노드의 leftChild와 rightChild를 서로 swap하는 문제이다. 재귀함수를 이용하여 노드가 null이 아닌 경우, leaf node까지 모두 바꿔준 뒤, 해당 노드의 leftChild와 rightChild를 바꾸는 방법을 사용하였다. 코드 더보기 class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; root.left = invertTree(root.left); root.right = invertTree(root.right); TreeNode temp = root.left; root.left = root.right; root.right = temp; return root..

LeetCode - 217. Contains Duplicate

문제 Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. Example 1: Input: [1,2,3,1] Output: true Example 2: Input: [1,2,3,4] Output: false Example 3: Input: [1,1,1,3,3,4,3,2,4,2] Output: true 풀이 배열에서 중복된 값이 있는지를 찾는 문제이다. 배열을 정렬한 뒤, 하나씩 탐색하며..

LeetCode - 50. Pow(x, n) // Java

문제 Implement pow(x, n), which calculates x raised to the power n (i.e. x^n). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2^(-2) = 1/(2^2) = 1/4 = 0.25 Constraints: -100.0

LeetCode - 19. Remove Nth Node From End of List // Java

문제 Given the head of a linked list, remove the nth node from the end of the list and return its head. Follow up: Could you do this in one pass? Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] Constraints: The number of nodes in the list is sz. 1