본문 바로가기

풀어본 Algorithm 문제 정리

[OJ.leetcode] binary-tree-preorder-traversal https://oj.leetcode.com/problems/binary-tree-preorder-traversal/ Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? /* preorder를 loop로 구현하기 위해서 stack을 이용하여 실제 recursive call과 함수 콜스택의 동작을 모방하여 그대로 적용하면 될것. loop로 구현시, 실제로 return 시 스택에서 unwindin.. 더보기
[OJ.leetcode] maximum-depth-of-binary-tree https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/ Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solut.. 더보기
[OJ.leetcode] add two numbers https://oj.leetcode.com/problems/add-two-numbers/ You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 /* 생각해야할 케이스 : 두 number의 길이가 다를 경우, carry 처리 발생한 Errors: 1)list pointer 처리 미숙 2)wh.. 더보기
[OJ.leetcode] search-in-rotated-sorted-array https://oj.leetcode.com/problems/search-in-rotated-sorted-array/ Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. /* binary search를 응용하여 해결 가능. test case [4,5,6,7,8,1,2,3] .. 더보기
[OJ.leetcode] combinations https://oj.leetcode.com/problems/combinations/ Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] /* 시간/공간 복잡도 : O(nCk) nCk = (n!/k!(n-k)!)? 시간 복잡도 계산이 은근히 복잡하다. n회 루프 중 현재 원소의 갯수 n이 < k 일때까지 계속해서 재귀호출을 하므로..으 순열/조합 을 한번에 짜는게 의외로 잘 안된다. 이번에도 대여섯번 컴파일러에 의존해서 버그 수정 후 .. 더보기
[OJ.leetcode] sort-colors https://oj.leetcode.com/problems/sort-colors/ Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. click to show follow up.Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and.. 더보기
[OJ.leetcode] substring-with-concatenation-of-all-words https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/ You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For example, given: S: "barfoothefoobarman" L: ["foo", "bar"] You should return the indices: [0,.. 더보기
[OJ.leetcode] flatten-binary-tree-to-linked-list https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/ Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 /* 대충 구현하여도 O(n)에 다 수행가능함. "문제는 어떻게 하면 elegant하게 구현할 수 있을까?" preorder로 돌면서, 1) parent의 leftchild가 있을 경우, left subtree의 rightmost 를 가리키는 포인터를 하나 두고, 2) parent->right를 righ.. 더보기
[OJ.leetcode] jump-game https://oj.leetcode.com/problems/jump-game/ Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. /* A[i]가 0인 elemant가 있을때, 이를 jump할 수 있는지 여부만 없.. 더보기
[OJ.leetcode] merge-sorted-array https://oj.leetcode.com/problems/merge-sorted-array/ Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively. /* 간단히 O(m+n) 알고리즘으로 해결하자면, mergesort에서 merge 알고리즘과 같이 하나씩 비교해서 채워나가고, 2개의 .. 더보기

티스토리툴바