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.
Divide and conquer is easy when you can easily find out how to divide a problem. But a lot of times how to divide a problem is hard. And different problem always needs a different divide approach. So if you want to master all divide and conquer problems you need to do a lot of practices. Only this way you can build a strong understanding of the thought of divide and conquer, and get more feeling of familiarity, and master more method to divide.
Chapter 2.3.1 of Introduction to Algorithms introduces Merge sort algorithm, Chapter 4 “Divide and conquer” introduces The maximum-subarray problem and Strassen’s algorithm for matrix multiplication.
I implement these three algorithms from pseudocode from the book to Java code:
Merge-Sort Java version：
Maximum Subarray Java version：
Strassen’s algorithm for matrix multiplication Java version:
Matrix split and combine functions
Matrix add and minus functions
Strassen’s algorithm for matrix multiplication
LeetCode divide and conquer problems list
|4||Median of Two Sorted Arrays||Hard|
|23||Merge k Sorted Lists||Hard|
|215||Kth Largest Element in an Array||Medium|
|218||The Skyline Problem||Hard|
|240||Search a 2D Matrix II||Medium|
|241||Different Ways to Add Parentheses||Medium|
|282||Expression Add Operators||Hard|
|315||Count of Smaller Numbers After Self||Hard|
|327||Count of Range Sum||Hard|
|426||Convert Binary Search Tree to Sorted Doubly Linked List||Medium|
|903||Valid Permutations for DI Sequence||Hard|
|973||K Closest Points to Origin|