Hello backEnd

304. Range Sum Query 2D - Immutable Java 풀이

쉬운 풀이class NumMatrix { // y1 x1 y2 x2 // int[][] matrix; public NumMatrix(int[][] matrix) { this.matrix = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; int x1 = Math.max(row1, row2); int x2 = Math.min(row1, row2); int y2 = Math.min(col1, col2); int y1 = Math.max(col1, col2); for(int i=x..

284. Peeking Iterator java 풀이

이게 왜 미디엄..? 이라는 생각이 들정도로 다른 것들이랑 차이가 많이 나는 문제이다.솔직히 풀이랄것도 없다. 그냥 맨 위 값을 캐싱하면 해결된다. // Java Iterator interface reference:// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.htmlclass PeekingIterator implements Iterator { Iterator iterator; Integer cache; public PeekingIterator(Iterator iterator) { this.iterator = iterator; cache = iterator.next(); } // Returns ..

211. Design Add and Search Words Data Structure java 풀이

이거는 앞의 문제 https://hello-backend.tistory.com/423 이거를 풀었으면 매우 쉽다.그냥 저장은 똑같고, DFS 찾을 때에 . 이면 거기 싹다 찾으면 된다. class Word { boolean isEnd; Word[] word = new Word[26];}class WordDictionary { Word root; public WordDictionary() { root = new Word(); } // 객체가 객체를 저장하는 형태 // 결국 특정 알파뱃에 대하여 그 아래에 객체가 존재하고 ... -> 반복 시 모든 문자열의 형태가 저장된다. // 그렇다면 어떻게 확인할 수 있을까? // DFS 를 통..

208. Implement Trie (Prefix Tree)

대체 뭐 어떻게 하는건지 감도 안왔었다.결국 중요한건 1. 단어를 만들 때 각 알파뱃까지로 만들어진 객체가 있는지를 보고2. 그 아래로 쭉쭉 만들어가면서 만들고 확인할 때에는 1. DFS 를 써서 확인할 단어로 보다가2. 정확히 일치하면 맞는거3. prefix 인 경우는 그거만 확인하면 됨 으로 진행하면 된다.뭔가 지금까지 하면서 느낀게, 이런 구현들은 객체를 어떻게 만들지를 보는 것 같다.요구조건에 따라 객체를 잘 만들면 해결 자체는 수월해 보임. class Word { boolean isEnd; Word[] cha = new Word[26]; // a ~ z 까지, 그리고 그 내부로 들어가면 그것 또한 트리의 형태.}class Trie { // 처음부터 확인한다. // 노드로 ..

LeetCode - 173. Binary Search Tree Iterator java 풀이

푸는 방법을 생각해 내는게 어려운 문제.방법을 알면 푸는건 간단한데 생각하기가 참 어렵다. 중요한건 노드 기준으로 볼 때 현재 노드의 왼쪽 아래 : 이것보다 작음왼쪽의 왼쪽 아래 : 더 작음현재 노드의 오른쪽 아래 : 이것보다 큼현재 노드의 오른쪽 아래 : 내 위보다는 작음 이거를 기억하면 된다. 스택에 노드에서 왼쪽으로 가면서 쭉 넣어주고next 할 때에는 노드에서 값을 꺼내서 보여주고, 현재 기준 오른쪽 노드를 기준으로도 쭉 확인해보기hasNext 는 스택이 비어있지 않으면 가능/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; *..

LeetCode - LRU Cache java 문제풀이

내가 이런 구현에 재능이 없었다.참 오래 공부를 안했다.강의를 대충 보고 풀었는데도 1시간 정도 소요되었다. 문제를 보고 풀이를 할 때 좀 더 확실히 보고 풀어야겠다는 생각이 든다. import java.util.*;// 이중 LinkedList 를 구현할 Classclass CacheItem { CacheItem prev; CacheItem next; int key; int value; public CacheItem(int key, int value) { this.key = key; this.value = value; }}class LRUCache { // 맨 앞, 맨 뒤에 접근해야 한다. // Double Linked Lis..