본문 바로가기

LeetCode

(40)
[Easy] 125. Valid Palindrome #문제설명 #문제 풀이 풀이 1. class Solution { public boolean isPalindrome(String s) { s = s.toLowerCase().replaceAll("[^a-z0-9]", ""); int right = s.length() - 1, left = 0; while(right >= left){ if(s.charAt(left) != s.charAt(right)){ return false; } right--; left++; } return true; } } 풀이 2. public class Solution { public boolean isPalindrome(String s) { if (s.isEmpty()) { return true; } int head = 0, tail..
[Easy] 21. Merge Two Sorted Lists #문제 설명 #문제 풀이 #Iterative 풀이 public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(0); ListNode handler = head; while(l1 != null && l2 != null) { if (l1.val
[Easy] 20. Valid Parentheses #문제 설명 #문제 풀이 class Solution { public boolean isValid(String s) { Stack stack = new Stack(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '{') stack.push('}'); else if (c == '[') stack.push(']'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); } } 위와 같이 Stack을 사용하면 쉽게 풀 수 있다.
[Hard] 295. Find Median from Data Stream (Microsoft 기출 문제) #문제 설명 #문제 풀이 class MedianFinder { PriorityQueue minHeap = new PriorityQueue(); PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); public MedianFinder() { } public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll()); } public double findMedian() { if (maxHeap.size() > minHeap.size()) retu..
[Medium] 451. Sort Characters By Frequency #문제 설명 #문제 풀이 HashMap + Heap class Solution { public String frequencySort(String s) { Map map = new HashMap(); for (char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); } PriorityQueue pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a)); for (char c : map.keySet()) { pq.offer(c); } StringBuilder sb = new StringBuilder(); while (!pq.isEmpty()) { char c = pq.poll(); for (int i ..
[Medium] 1046. Last Stone Weight (구글 코딩 테스트 기출문제) #문제 설명 #문제 풀이 class Solution { public int lastStoneWeight(int[] stones) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); int sum = 0; for(int i = 0; i 1){ int num1 = 0; int num2 = 0; if(maxHeap.size() >= 2){ num1 = maxHeap.poll(); num2 = maxHeap.poll(); } m..
[Medium] 1337. The K Weakest Rows in a Matrix #문제 설명 1337번 문제는 정수 k와 n x m matrix가 주어진다. 각 열은 0과 1로 구성 돼있다. 1은 군인을 나타내고 0은 시민을 나타낸다. 각 열에서 1 (군인)보다 먼저 0 (시민)이 나올 순 없다 (열에서 1이 다 나열된 뒤 0이 나열됨). 이 문제에선 주어진 정수 k번째로 "약한" (군인이 적은) 열 들을 담은 array를 return 시켜주면 된다. #문제 풀이 #Heap 사용 풀이 class Solution { public int[] kWeakestRows(int[][] mat, int k) { int m = mat.length; int n = mat[0].length; // Create a Priority Queue that measures firstly on strength ..
[Medium] 347. Top K Frequent Elements (애플/MS/메타/아마존) #문제 설명 Leetcode 347번 문제는 array와 정수 k가 주어진다. 배열에서 가장 빈도가 높은 k개의 요소를 return하면된다. 예를 들어 [1,1,1,2,2,3]이 라는 배열에 k=2가 주어지면 1 (빈도 3번) 과 2 (빈도 2번)을 반환해주면 된다. 만약 k=3이라면 1,2,3 모두 반환 해주면 된다 #문제 풀이 class Solution { public int[] topKFrequent(int[] nums, int k) { // O(1) time if (k == nums.length) { return nums; } // 1. build hash map : character and how often it appears // O(N) time Map count = new HashMap()..