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.

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:

GitHub address:https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MergeSort.java

Maximum Subarray Java version:

GitHub address:https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MaximumSubarray.java

Strassen’s algorithm for matrix multiplication Java version:

GitHub address:https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/SquareMatrixMultiply.java

Brute fore

Simple recursive

Helper functions

Matrix split and combine functions

Matrix add and minus functions

Strassen’s algorithm for matrix multiplication

LeetCode divide and conquer problems list

4Median of Two Sorted ArraysHard
23Merge k Sorted ListsHard
53Maximum SubarrayEasy
169Majority ElementEasy
215Kth Largest Element in an ArrayMedium
218The Skyline ProblemHard
240Search a 2D Matrix IIMedium
241Different Ways to Add ParenthesesMedium
282Expression Add OperatorsHard
312Burst BalloonsHard
315Count of Smaller Numbers After SelfHard
327Count of Range SumHard
493Reverse PairsHard
514Freedom TrailHard
426Convert Binary Search Tree to Sorted Doubly Linked ListMedium
903Valid Permutations for DI SequenceHard
932Beautiful ArrayMedium
973K Closest Points to Origin

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.