diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/LCS2.java | 56 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java | 52 |
2 files changed, 95 insertions, 13 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java index d214eff..e2a882c 100644 --- a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java +++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java @@ -1,4 +1,6 @@ +import java.util.Arrays; import java.util.Scanner; +//import java.util.concurrent.ThreadLocalRandom; public class LCS2 { @@ -16,7 +18,33 @@ public class LCS2 { b[i] = scanner.nextInt(); } - System.out.println(lcs2(a, b)); + System.out.println(third_lcs2(a, b)); +// System.out.println(alt_lcs2(a, b, n, m)); + +// while (true) { +//// int n = ThreadLocalRandom.current().nextInt(1, 101); +//// int m = ThreadLocalRandom.current().nextInt(1, 101); +// int n = ThreadLocalRandom.current().nextInt(1, 20); +// int m = ThreadLocalRandom.current().nextInt(1, 20); +// int[] a = new int[n]; +// int[] b = new int[m]; +// for (int i = 0; i < a.length; i++) { +// a[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000); +// } +// for (int i = 0; i < b.length; i++) { +// b[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000); +// } +// int r1 = lcs2(a, b); +// int r2 = alt_lcs2(a, b, n, m); +// if (r1 == r2) +// System.out.println("ok"); +// else { +// System.out.println(Arrays.toString(a)); +// System.out.println(Arrays.toString(b)); +// System.out.println("Wrong answer " + r1 + " " + r2); +// break; +// } +// } } public static int[][] editDistance(int[] A, int[] B) { @@ -66,4 +94,30 @@ public class LCS2 { return lcs2(i - 1, j - 1, D); } + public static int alt_lcs2(int[] a, int[] b, int i, int j) { + if (i == 0 || j == 0) + return 0; + if (a[i - 1] == b[j - 1]) + return 1 + alt_lcs2(a, b, i - 1, j - 1); + else + return Math.max(alt_lcs2(a, b, i, j - 1), alt_lcs2(a, b, i - 1, j)); + } + + public static int third_lcs2(int[] a, int[] b) { + int m = b.length; + int n = a.length; + int[][] D = new int[n + 1][m + 1]; + for (int j = 1; j < m + 1; j++) { + for (int i = 1; i < n + 1; i++) { + if (a[i - 1] == b[j - 1]) { + D[i][j] = D[i - 1][j - 1] + 1; + } else { + D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]); + } + } + } + + return D[n][m]; + } + } diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java index bdfa799..83de106 100644 --- a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java +++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java @@ -6,30 +6,58 @@ class LCS2Test { @Test void test() { - int[] a = {2, 7, 5}; - int[] b = {2, 5}; - assertEquals(2, LCS2.lcs2(a,b)); + int[] a = { 2, 7, 5 }; + int[] b = { 2, 5 }; + assertEquals(2, LCS2.lcs2(a, b)); + assertEquals(2, LCS2.third_lcs2(a, b)); + assertEquals(2, LCS2.alt_lcs2(a, b, 3, 2)); } @Test void test1() { - int[] a = {7}; - int[] b = {1, 2, 3, 4}; - assertEquals(0, LCS2.lcs2(a,b)); + int[] a = { 7 }; + int[] b = { 1, 2, 3, 4 }; + assertEquals(0, LCS2.lcs2(a, b)); + assertEquals(0, LCS2.third_lcs2(a, b)); + assertEquals(0, LCS2.alt_lcs2(a, b, 1, 4)); } @Test void test2() { - int[] a = {2, 7, 8, 3}; - int[] b = {5, 2, 8, 7}; - assertEquals(2, LCS2.lcs2(a,b)); + int[] a = { 2, 7, 8, 3 }; + int[] b = { 5, 2, 8, 7 }; + assertEquals(2, LCS2.lcs2(a, b)); + assertEquals(2, LCS2.third_lcs2(a, b)); + assertEquals(2, LCS2.alt_lcs2(a, b, 4, 4)); } @Test void test3() { - int[] a = {1, 2, 3, 4, 5, 6, 7}; - int[] b = {1, 2, 8, 4, 5, 6}; - assertEquals(5, LCS2.lcs2(a,b)); + int[] a = { 1, 2, 3, 4, 5, 6, 7 }; + int[] b = { 1, 2, 8, 4, 5, 6 }; + assertEquals(5, LCS2.lcs2(a, b)); + assertEquals(5, LCS2.third_lcs2(a, b)); + assertEquals(5, LCS2.alt_lcs2(a, b, 7, 6)); + } + + @Test + void test4() { + int[] a = { 1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6, + 7 }; + int[] b = { 6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5, + 6, 1, 6, 3, 1, 6, 7, 3 }; + assertEquals(16, LCS2.lcs2(a, b)); + assertEquals(17, LCS2.third_lcs2(a, b)); +// assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length)); + } + + @Test + void test5() { + int[] a = { 2, 4, 3, 3 }; + int[] b = { 1, 4, 3 }; + assertEquals(2, LCS2.lcs2(a, b)); + assertEquals(2, LCS2.third_lcs2(a, b)); +// assertEquals(5, LCS2.alt_lcs2(a, b, a.length, b.length)); } } |