Categories
LeetCode

Leecode problem 53 Maximum Subarray [Divide and conquer](Java)

原题:https://leetcode.com/problems/maximum-subarray/

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.

Categories
LeetCode

LeetCode problem 23 Merge k Sorted Lists [Divide and conquer][Min-Heap](Java)

Source Url:https://leetcode.com/problems/merge-k-sorted-lists/

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

Categories
LeetCode

Divide and conquer algorithm (Java code and Leetcode problems)

I am trying to solve every problem of Leetcode and write blogs to record it. Now I plan to read Introduction to Algorithms and solve problems match the book contents.

What is Divide and conquer?

Divide and conquer is a method to solve a complex problem. When we think of a problem too complex or too big, we can try to divide the problem to some easy problems or small problems. Then we try to solve these small/easy problems and combine the results to solve the complex/big problem.

Categories
LeetCode

LeetCode problem 21 Merge Two Sorted Lists(Java)

Source url:https://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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4