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; …
Longest Increasing Subsequence
This No.300 in LeetCode. Here are two approaches for this problem, I will introduce both of them here. Dynamic Programming – O(n^2) The first solution using Dynamic Programming. We will create a one-dimension dp array. We will go over the whole array, and store the numbers of greater number in dp array. class Solution { …
A simple Binary Search Template
def lower_bound(array, first, last, value) # return first !< val in [first, last) while first < last: # not empty mid = first + (last – first)/2. # no overflow if array[mid] < val : first = mid + 1 else: last = mid return first. # or last No need to worry about onverflow: …