This is No.148 Problem in LeetCode. Here are two approaches as below: Top Down Merge Sort Recursively split the original list into two halves. The split continues until there is only one node in the linked list (Divide phase). To split the list into two halves, we find the middle of the linked list using …
How to construct a BST with a given pre-order array?
Code is below: // build the tree private TreeNode build_tree( String[] node, int min, int max ){ // invalid corner case if( idx >= node.length ){ return null; } TreeNode root = null; // valid value if( Integer.valueOf(node[idx]) > min && Integer.valueOf(node[idx]) < max ){ // build the root root = new TreeNode( Integer.valueOf( node[idx]) …
Continue reading “How to construct a BST with a given pre-order array?”
How to find Maximum AND XOR value of two elements in array?
I always feel confused when I face bit manipulation algorithm problems. Even the solution post in discussion forum is hard for me to understand. When I was trying to figure out the daily challenge, ofc it is a bit manipulation problem, I do more research because I still can’t understand the solution post in discussion …
Continue reading “How to find Maximum AND XOR value of two elements in array?”
Notes on reviewing Dynamic Programming
I believe the topic of Dynamic Programming is a hard part of Algorithm. For this reason, I plan to read the related content in Introduction To Algorithm first and take some notes before I start solving problems in LeetCode. What is Dynamic Programming Dynamic programming typically applies to optimization problems in which we make a …
When I try to add List to List in Java
I faced a problem when I try to add List to List< List > in java, and it did consume some my time. It is a common problem and I even can remember I got stuck on debugging because of this "feature" at least twice. To let me remember this problem and avoid making it …
Course Schedule II
This is No.210 in LeetCode. I can’t solve this problem by self, but I found a real solid solution and explanation. This is our "main" function: public int[] findOrder(int numCourses, int[][] prerequisites) { int[] incLinkCounts = new int[numCourses]; // incoming edges List<List<Integer>> adjs = new ArrayList<>(numCourses); initialiseGraph(incLinkCounts, adjs, prerequisites); //return solveByBFS(incLinkCounts, adjs); return solveByDFS(adjs); } …
Perfect Squares
This in No.279 in LeetCode. The math theory is: dp[0] = 0 dp[1] = dp[0]+1 = 1 dp[2] = dp[1]+1 = 2 dp[3] = dp[2]+1 = 3 dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } = Min{ dp[3]+1, dp[0]+1 } = 1 dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } = Min{ dp[4]+1, dp[1]+1 } = 2 . . …
Number of Islands
This is No.200 in LeetCode. The solution is below: public class Solution { private int y; private int x; public int numIslands(char[][] grid) { int res = 0; y = grid.length; if (y == 0) return 0; x = grid[0].length; for (int i = 0; i < y; i++){ for (int j = 0; j …
Circular Array Loop
This is No.457 in LeetCode. The solution is post below: public class Solution { public boolean circularArrayLoop(int[] nums) { if (nums == null || nums.length < 2) return false; int n = nums.length; for (int i = 0; i < n; i++) { if (nums[i] == 0) { continue; } // slow/fast pointer int j …
List in Java
List Interface in Java with Examples The List interface provides a way to store the ordered collection. It is a child interface of Collection. It is an ordered collection of objects in which duplicate values can be stored. Since List preserves the insertion order, it allows positional access and insertion of elements. List<Integer> l1 = …