hash
-
[LeetCode] Longest Consecutive Sequence알고리즘 2019. 12. 6. 21:54
문제 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Approach 배열이 sorting되어있으면 아주 쉽다. priority queue를 활용한 heap에 배열을 옮겨 담고 하나씩 빼면서 연속인지 아닌지 확인하면 됨 하지만 이 방법은..
-
[LeetCode] Minimum Window Substring알고리즘 2019. 11. 5. 22:18
문제 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. Ap..
-
[LeetCode] Group Anagrams알고리즘 2019. 10. 29. 16:37
문제 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. Approach 각 string을 sort해보고 그 결과가 같으면 같은 그룹으로 묶는다. 이를 위해 map (혹은 unorderd_map)을 사용하였다. 시간복잡도는 총 string의 개수가 N개, string 하나의 최대 길이가 K일때 O(NKlogK)이다 O..
-
[LeetCode] First Missing Positive알고리즘 2019. 10. 22. 23:56
문제 Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. Approach 메모리를 O(n)만큼 더 쓰면 map등을 사용해서 쉽게 풀겠지만 상수 크기만큼밖에 사용하지 못하므로 어려운 문제. 답은 Hash를 제시된 배열에 직접 구현하는 것이었다. 배열을 탐색하는 index를 i, 제시..
-
[LeetCode] Valid Sudoku알고리즘 2019. 10. 21. 20:31
문제 Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. A partially filled sudoku which is valid. The Sudoku board could be par..