본문 바로가기

풀어본 Algorithm 문제 정리

[google] the smallest range from k lists http://www.careercup.com/question?id=16759664 You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists. For example, List 1: [4, 10, 15, 24, 26] List 2: [0, 9, 12, 20] List 3: [5, 18, 22, 30] The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3. 더보기
[Oj.leetcode] generate-parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" /* "well-formed" 의미를 시작전 명확하게 인터뷰어와 논의. 여기서는 열고( 닫는) 한쌍의 괄호쌍 의미 좀 더 정확하게 정의해보면, 닫힌 괄호가 나왔을때, 앞에 매칭되는 열린괄호가 최소한 1개는 존재해야함. n=1 (), n=2 (()), ()() n=3 ()(()), (()()), ((())), (()()), (())(), ()()() n=4 .. 더보기
[OJ.leetcode] rotate-image https://oj.leetcode.com/problems/rotate-image/ You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? /* tese case 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 in-place 단순한 규칙을 찾고 loop를 2D로 구현하여야 함. */ class Solution { public: void rotate(vector &matrix) { int size = matrix.size().. 더보기
[OJ.leetcode] plus-one https://oj.leetcode.com/problems/plus-one/ Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. /* digit binaoperation은 언제나 carry 처리/자릿수 변경이 관건 맨 뒷자리부터 1씩 더해나가면서 carry 처리. O(n) carry 관련 문제는 언제나 loop끝나고 남은 carry를 처리해주는 것을 잊지 말것 001 111 101 */ class Solution { public: vector plu.. 더보기
[OJ.leetcode] remove-duplicates-from-sorted-array https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/ Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. /* 똑같은 문제.. 더보기
[OJ.leetcode] balanced-binary-tree https://oj.leetcode.com/problems/balanced-binary-tree/ Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. /* solution: modified preorder (O(n)) 매 순회마다 left, right 의 depth를 비교해서 >1 이면 return false more than 1 이라고 했으므로 인터뷰어와 1 와 같은 예제도 .. 더보기
[Oj.leetcode] remove-element https://oj.leetcode.com/problems/remove-element/ Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length. /* 이런 단순한 문제 일수록 문제의 의도를 정확하게 파악하기 위해 인터뷰어와 코딩 전 충분한 사전 토의가 필요. 단순히 주어진 element를 모두 지우고 새로운 length를 리턴하라는 것인지, remove후 정렬절차가 어떻게 될것인지 질문하기. "The order of el.. 더보기
[OJ.leetcode] merge-two-sorted-lists https://oj.leetcode.com/problems/merge-two-sorted-lists/ Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. /* 단순히 two runner를 이용해서 merge sort의 merge와 마찬가지로 O(n)에 sorted list를 merge 하는 알고리즘 한번에 accepted 했어야했는데.. linked list pointing 헷갈려서 2번 실패. 아직 pointer 부분 부족한듯 */ /** * Definition for singly-linked list... 더보기
[OJ.leetcode] single-number-ii https://oj.leetcode.com/problems/single-number-ii/ Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? /* 사고의 전환이 필요. 일종의 트릭인데, array를 element 단위보다 더 작은 bit level 에서 볼 수 있고 bit level operation을 할 수 있느냐를 보는 문제. "Given an array of integers.. 더보기
[OJ.leetcode] remove-duplicates-from-sorted-list https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/ Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. /* 반드시 인접해있는 두 노드만 duplicated 되어있는지? -> YES O(n) solution : 순회하면서 duplicated 노드 만나면 삭제(건너뛰고)연결 */ /** * Definition for singly-linked list. * struct ListNode { *.. 더보기

티스토리툴바