divide and conquer
-
[LeetCode] Maximum Subarray알고리즘 2019. 10. 29. 18:15
문제 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Approach nums[i..
-
[LeetCode] Merge k Sorted Lists알고리즘 2019. 9. 28. 20:39
문제 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 Approach Min heap에 list의 앞부분을 하나씩 담은 후 answer list에 min heap의 맨 위 원소를 넣어준다. answer에 들어간 원소는 next가 null이 아닌 경우 그 다음 원소를 다시 min heap에 넣는다. Code https://github.com/chi3236/algorithm/blob/master/LeetCode_MergeKSortedLists_MinH..