공부기록

문제 https://leetcode.com/problems/range-sum-query-mutable/ 피드백 팬윅 트리 (binary index tree) 로 일단 풀었다. read : log(N), wirte : log(N) T[N] = T[lsb[N1]] + T[lsb[N2]] ... 총 연산 수가 log(N) 이 됨. 세그먼트 트리도 솔루션에 있다. 개인적으로 아이디어가 더 직관적임 input 원소를 리프 노드로 둠, 그리고 위에 이진 B+트리를 만드는 것 처럼 부모 노드들을 생성 각 노드들은 자식노드들의 인덱스 범위와, 그 원소들의 합을 속성으로 가짐 [left, right] 범위를 주면, 리프 노드부터 시작해서 [left,k], [k,right] 가 되는 부모노드 2개를 찾아 원소합을 더한다...

1. 문제 https://leetcode.com/problems/out-of-boundary-paths/

https://leetcode.com/problems/shortest-distance-to-a-character/solution/ Shortest Distance to a Character - 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 복습 필요.

문제 https://leetcode.com/problems/search-a-2d-matrix/ 코드 import java.util.*; class Solution { public boolean searchMatrix(int[][] matrix, int target) { int M = matrix.length; int N = matrix[0].length; int start=0; int end=M-1; int mid = 0; while(start = target){ end = mid; }else{ start = mid+1; } } int curRow = end; start = 0; end = N-1; while(sta..

문제 https://leetcode.com/problems/group-anagrams/ 코드 import java.util.*; class Solution { public List groupAnagrams(String[] strs) { Map m = new HashMap(); List res = new ArrayList(); for(String str : strs){ char[] tmp = str.toCharArray(); Arrays.sort(tmp); String k = new String(tmp); if(m.get(k) == null) m.put(k, new ArrayList()); m.get(k).add(str); } for(String key : m.keySet()) res.add(m.get(k..

문제 https://leetcode.com/problems/top-k-frequent-elements/ 코드 import java.util.*; class Solution { class Node implements Comparable{ int num; int count; public Node(int num, int count){ this.num = num; this.count = count; } @Override public int compareTo(Node n){ if(this.count < n.count) return 1; else if(this.count == n.count) return 0; return -1; } } public int[] topKFrequent(int[] nums, int k)..

문제 https://leetcode.com/problems/largest-number/ 코드 import java.util.*; class Solution { public String largestNumber(int[] nums) { List list = new ArrayList(); if(nums.length == 1) return String.valueOf(nums[0]); list.add(String.valueOf(nums[0])); for(int i=1; i

문제 https://leetcode.com/problems/shuffle-an-array/ 코드 import java.util.*; class Solution { private List prevRes; private List res; private List resIdx; private int[] nums; private boolean visit[]; private boolean isSet = false; private boolean isEnd = false; public Solution(int[] nums) { this.nums = nums; this.res = new ArrayList(); this.resIdx = new ArrayList(); this.visit = new boolean[nums.le..