Back to basics

문제 풀이 오름차순으로 정렬된 배열에 원하는 값을 찾는 문제이다. 문제 이름대로 이진 탐색을 이용해서 풀면 되는 문제다. 이진 탐색은 정렬된 리스트에서 값을 탐색하는 알고리즘이다. 아래와 같이 매번 탐색이 진행될 때마다 범위를 1/2씩 좁혀서 가면서 탐색한다. 그래서 시간 복잡도는 O(logN)이다. 배열에 원하는 값이 존재하면 원하는 값의 인덱스를 반환하고 아니면 -1을 반환하면 된다. 그래서 해당 문제의 종료 조건은 아래와 같이 구현할 수 있다. 원하는 값을 찾았을 때 return 원하는 값의 인덱스 왼쪽인덱스가 오른쪽 인덱스보다 큰 경우, 원하는 값이 배열에 없는 경우이다. return -1 코드 class Solution { public int search(int[] nums, int target..

문제 You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor. Example 1: Input: cost = [10,15,20] Output: 15 Explanation: Cheapest is: start on cost[1], pay that cost, and go ..

문제 leetcode.com/problems/minimum-depth-of-binary-tree/ Minimum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 Root 노드에서 Leaf 노드로 가는 가장 짧은 거리를 찾는 문제이다. 문제자체는 BFS만 알면 풀 수 있는 수준이다.BFS(Breadth-first search) 이용해서 풀었다. 코드 Depth를 계산하다가 Leaf 노드가 없는 경우 값을 반환하면 된다...

문제 Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. 풀이 Anagram 은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 놀이이다. 주어진 input에서 Anagram 인 것들만 모아주면 되는 문제이다. input이 모두 소문자이기 떄문에 대소문자를 구분할 필요가 없다. map를 이..

문제 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example : Consider the following matrix: ] Given target = 5, return true. Given target = 20, return false. 풀이 주어진 matrix에서 target 값이 존재하는 지를 찾는 문..

문제 Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1: .val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL. Example 2: Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, ..