본문 바로가기

LeetCode

 (40)
[Medium] Kth Largest Element in an Array (아마존/구글) #문제 설명 Leetcode 215번 문제는 정수로 채워진 배열 nums와 정수 k가 주어진다. 주어진 배열안에서 k번째로 큰 정수를 return하면 된다. 위에 예시를 보면 [3,2,1,5,6,4] 의 배열과 k=2가 주어진다 이경우 에는 배열에서 2번째로 큰 숫자를 return하면 되기에 5를 return해야한다. #문제 풀이 Min-heap 풀이: class Solution { public int findKthLargest(int[] nums, int k) { //min-heap PriorityQueue minHeap = new PriorityQueue(); for(int i = 0; i < k;i++){ minHeap.add(nums[i]); } for(int i = k; i < nums.leng..
[Medium] 49. Group Anagrams (Amazon) #문제 설명 Leetcode 49번 문제에서는 여러개의 문자열이 주어진다. 주어진 문자열로 anagram을 만들수있는 문자열들끼리 묶은 sublist를 담은 list를 return 하는 문제이다. 여기서 anagram이란 주어진 철자들로 다른 단어를 만든다는 뜻이다. 예를 들어 race는 r, a, c, e를 사용해 care라는 단어를 만들수 있다, 이런것들이 anagram이다. 그래서 위에 주어진 예시 1번을 보면 nat을 n,a,t를 사용해 tan를 만들수있기때문에 묶고 (이 문제에서는 말이 안되는 단어여도 상관없다, 모든 문자만 겹치면 anagram으로 침), ate는 a,t,e를 사용해 eat과 tea를 만들수있기 때문에 묶는다, bat으로는 주어진 array의 문자열들의 anagram으론 바꾸지..
[Medium] 1663. Smallest String With A Given Numeric Value (Microsoft) #문제 설명 Leetcode 1663번 문제에서는 문자열 길이 n과 정수 k가 주어진다. 이 문제에서 각 소문자 알파벳들에게는 1부터26의 값이 부여된다 (예: a는 1, b는 2, ... , z는 26). 이 문제에서는 주어진 n과 k에 맞는 문자열을 return해야한다. 예를 들어 n = 3과 m은 27이 주어지면 "aay"라는 문자열을 return해야된다. 왜냐하면 문자열 길이는 3이어야하고 a = 1 + a = 1 + y = 25 = 27이기 때문이다. #문제 풀이 class Solution { public String getSmallestString(int n, int k) { char[] result = new char[n]; for (int position = n - 1; position >..
[Medium] 48. Rotate Image (Amazon/Microsoft) #문제 설명 Leetcode 48번 문제에서는, n x n 2d array, 즉 matrix가 주어진다. Matrix의 각 index는 정수들로 채워져 있다. 그 주어진 matrix를 위의 예시 저럼 90도 오른쪽으로 뒤 집은 matrix를 return 하는 문제이다. 루빅스 큐브 앞면에 숫자들이 적혀저 있고 그 루빅스 큐브 오른쪽으로 한번 돌린다고 생각하면된다. #문제 풀이 #Transpose후 horizontally swapping풀이 Linear Algebra (선형 대수학)을 배울때 transpose (전치) 라는 것을 배운다. Transpose란 matrix의 행과 렬을 바꾸는 행위이다. 이 문제는 transpose를 사용해 풀 수있다. 먼저 matrix를 transpose 하고 matrix를 ..
[Medium] 92. Reverse Linked List II #문제 설명 Leetcode 92번 문제는 1부터 n까지 정렬된 Linked List와 left와right 값이 주어진다. 그럼 left부터right까지의 노드들을 reverse하면 된다. #문제 풀이 List list = new ArrayList(); ListNode curr = head; while (curr != null) { list.add(curr); curr = curr.next; } Object[] arr = list.toArray(); left = left - 1; right = right - 1; while (left < right) { ListNode temp = (ListNode) arr[left]; arr[left] = arr[right]; arr[right] = (ListNode)..
[Easy] 217. Contains Duplicate #문제 설명 Leetcode 217번 문제는 주어진 정수 배열에 중복된 숫자가 들어있는지 알아내는 문제이다. 배열에서 중복이 발생되면 true, 중복이 없다면 false를 return 하면 된다. #문제 풀이 1. HashSet이용 풀이 Set에는 중복 데이터를 담을 수 없다는 특성이 있다. 이 특성을 활용하면 문제를 쉽게 풀수있다. class Solution { public boolean containsDuplicate(int[] nums) { Set set = new HashSet(); for(int i = 0; i < nums.length;i++){ if(!set.add(nums[i])){ return true; } } return false; } } 먼저 HashSet를 만들고 array의 각 정..
[Medium] 856. Score of Parentheses #문제 설명 Leetcode 856번 문제는 괄호로 구성된 문자열이 구성된다. 이 괄호들 패턴에는 점수가 있다. () 는 1 점, ()() 는 1 + 1 = 2, (()) = 2 * 1 = 2 이다. 예를 들어 (()()) 라는 문자열이 주어지면 () + () = 2 이고 (2) 는 2 * 2 이기때문에 4가 정답이다. #문제 풀이 class Solution { public int scoreOfParentheses(String s) { Stack st = new Stack(); int score = 0; for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if(ch == '('){ st.push(score); score = 0; } else { sc..
[Medium] 5. Longest Palindromic Substring (구글 코딩 테스트 기출 문제) #문제 설명 Leetcode 5번 문제는 주어진 문자열에서 가장 긴 palindrome을 찾는 문제이다. 여기서 Palindrome이란 거꾸로 읽어도 똑바로 읽어도 같은 문자열이다 (예: 기러기 토마토 스위스 인도인 별똥별 우영우, 'Kayak', 'deed', 'rotator', 'noon', 'racecar 등등) #풀이 class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len..

티스토리툴바