This repository for the following:
- practice data structures and algorithm
- with multiple languages: java, scala, kotlin, python, c++, javascript
- and programming paradigms: functional, declarative, imperative, object-oriented
This part will be moved to scala directory
- features: immutability, tail recursion, highorder function, pattern match, lazy evaluation
Longest Increasing Subsequence (leetcode)
- functional and declarative style with scala
- highorder function: foldLeft, map, filter etc..
- immutable data structures: list, which is also persistent.
/*
DP solution
*/
def lengthOfLIS(nums: List[Int]): Int = {
// List[(Int, Int)] -> List[(maxLength, maxValue)]
nums.foldLeft(List[(Int, Int)]()) {
case (acc, e) => (acc.filter(_._2 < e).map(_._1).maxOption.getOrElse(0) + 1, e) :: acc
}
.map(_._1).max
}- imperative style with java
/*
DP solution
- f(i) represent the length of LIS ending at index i such that arr[i] is the last element of the LIS.
- f(i) = 1 + max( f(j) ) where 0 < j < i and arr[j] < arr[i] or L(i) = 1, if no such j exists
*/
public int lengthOfLIS(int[] nums) {
if (nums == null | nums.length == 0)
return 0;
final int N = nums.length;
final int[] f = new int[nums.length];
for (int i = 0; i < N; i++) {
int maxValue = 0;
for (int j = i -1; j >= 0; j--) {
if (nums[i] > nums[j]) maxValue = Math.max(maxValue, f[j]);
}
f[i] = maxValue + 1;
}
// return max of f
int res = 1;
for (int i = 1; i < N; i++) res = Math.max(res, f[i]);
return res;
}Of course, the solution can be improved with binary search. Let's focus on comparing programming styles.
Maximum Subarray (leetcode)
- tail recursion, pattern match
/*
- f(i) represents max sum of contiguous subarray ending at index i
- f(i) <- max (f(i - 1) + arr(i), arr(i))
return max of f
*/
def maxSubArray(nums: List[Int]): Int = {
@annotation.tailrec
def loop(xs: List[Int], acc: Int, m: Int): Int =
xs match {
case Nil => m
case h :: t =>
val lm = h max (acc + h)
loop(t, lm, m max lm)
}
loop(nums, 0, Int.MinValue)
}We can solve it with foldLeft as well.