When we have a string pattern and want to match it with the substring of a given string, what can we do? The tuition way is that we could use substring() to match in a for loop. But the Time Complexity would be O(N* L), N refer to the string length, L refer to the …
Algorithm Pattern – Island Programs LC 200 1254 1020 695 1905 694
Algorithm Pattern In a traditional way, we can use a visited array to mark if a cell has been visited. However, if it is allowed, we can also set the visited cell as 0 (ocean indicator) as well. And in some special cases, like if you need to know if a visited cell is valid …
Continue reading “Algorithm Pattern – Island Programs LC 200 1254 1020 695 1905 694”
Algorithm Pattern – Binary Search
Algorithm Pattern 1 – Find the target element class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length – 1; while(left <= right){ int mid = left + (right – left) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target){ left = mid + 1; …
Algorithm Pattern – Sliding Window
Problem Usually if you are asked to find out substring based on one string pattern in another string, it means you have to check all possible substring in one string, so you should maintain a sliding window to check each substring candidate. Thought For convenience, I call two strings as pattern string and explore string. …
Algorithm Pattern – Rotate & Spiral Array (LC 48 54 59)
Thought For the rotation question, we could get an easy approach by observing the rotation result. For the Spiral question, we should set the four dimension ranges and keep updating them. Example 48. Rotate Image (https://leetcode.com/problems/rotate-image/) You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). …
Continue reading “Algorithm Pattern – Rotate & Spiral Array (LC 48 54 59)”
Algorithm Pattern – Monotone Stack (LC 496 739 503)
Question Monotone Stack question usually ask you to find the next greater integer in an array. Approach Maintain a monotone stack, which stores index of descending integers, and while you face an element greater than the top of stack, we could assign this element as the next greater integer. Algorithm Pattern Deque<Integer> stack = new …
Continue reading “Algorithm Pattern – Monotone Stack (LC 496 739 503)”
What is difference between Linked List and Array List
Permutation – Java
What is the algorithm if we want to get the whole permutation combinations from a given array in java? I will introduce the algorithm in my own word: We take [a, b, c] as an example. We initialize an variable named as "cur", which means the current index we are concerning about how many different …
How to reverse String in java
Use the code below: // conversion from String object to StringBuffer StringBuffer sbr = new StringBuffer(str); // To reverse the string sbr.reverse();
How to convert Array to List
Plain Java public void givenUsingCoreJava_whenArrayConvertedToList_thenCorrect() { Integer[] sourceArray = { 0, 1, 2, 3, 4, 5 }; List<Integer> targetList = Arrays.asList(sourceArray); } Commons Collection public void givenUsingCommonsCollections_whenArrayConvertedToList_thenCorrect() { Integer[] sourceArray = { 0, 1, 2, 3, 4, 5 }; List<Integer> targetList = new ArrayList<>(6); CollectionUtils.addAll(targetList, sourceArray); } Guava public void givenUsingGuava_whenListConvertedToArray_thenCorrect() { List<Integer> sourceList = …