Revision of Some Leet shit

1 file changed, 9 insertions, 2 deletions

leet.cs

			@@ -1,4 +1,5 @@
1		-	Array.Sort(arr2);
	1	+	int Foo(int[] arr1, int[] arr2) {
	2	+	Array.Sort(arr2);
2	3		Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();
3	4
4	5		int DP(int i, int prev) {
			@@ -27,4 +28,10 @@ Array.Sort(arr2);
27	28		}
28	29
29	30		int result = DP(0, int.MinValue);
30		-	return result == int.MaxValue ? -1 : result;
	31	+	return result == int.MaxValue ? -1 : result;
	32	+	}
	33	+
	34	+	int[] arr1 = { 0, 11, 6, 1, 4, 3 };
	35	+	int[] arr2 = { 5, 4, 11, 10, 1, 0 };
	36	+	int minOperations = Foo(arr1, arr2);
	37	+	Console.WriteLine(minOperations); // output: 5

1 file changed, 16 insertions, 17 deletions

leet.cs

			@@ -1,31 +1,30 @@
1		-	int Foo(int[] arr1, int[] arr2) {
2		-	Array.Sort(arr2);
3		-	Dictionary<(int, int), int> dictionary = new Dictionary<(int, int), int>();
	1	+	Array.Sort(arr2);
	2	+	Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();
4	3
5		-	int Bar(int i, int prev) {
	4	+	int DP(int i, int prev) {
6	5		if (i == arr1.Length) return 0;
7		-	if (dictionary.ContainsKey((i, prev))) return dictionary[(i, prev)];
	6	+	if (memo.ContainsKey((i, prev))) return memo[(i, prev)];
8	7
9	8		int cost = int.MaxValue;
10	9		if (arr1[i] > prev) {
11		-	cost = Bar(i + 1, arr1[i]);
	10	+	int nextCost = DP(i + 1, arr1[i]);
	11	+	if (nextCost != int.MaxValue) {
	12	+	cost = Math.Min(cost, nextCost);
	13	+	}
12	14		}
13		-
	15	+
14	16		int idx = Array.BinarySearch(arr2, prev + 1);
15	17		if (idx < 0) idx = ~idx;
16	18		if (idx < arr2.Length) {
17		-	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
	19	+	int nextCost = DP(i + 1, arr2[idx]);
	20	+	if (nextCost != int.MaxValue) {
	21	+	cost = Math.Min(cost, 1 + nextCost);
	22	+	}
18	23		}
19	24
20		-	dictionary[(i, prev)] = cost;
	25	+	memo[(i, prev)] = cost;
21	26		return cost;
22	27		}
23	28
24		-	int result = Bar(0, int.MinValue);
25		-	return result == int.MaxValue \|\| result == int.MinValue ? -1 : result;
26		-	}
27		-
28		-	int[] arr1 = {1,5,3,6,7};
29		-	int[] arr2 = {1,6,3,3};
30		-	int result = Foo(arr1, arr2);
31		-	Console.WriteLine(result);
	29	+	int result = DP(0, int.MinValue);
	30	+	return result == int.MaxValue ? -1 : result;

1 file changed, 2 insertions, 8 deletions

leet.cs

			@@ -14,13 +14,7 @@ int Foo(int[] arr1, int[] arr2) {
14	14		int idx = Array.BinarySearch(arr2, prev + 1);
15	15		if (idx < 0) idx = ~idx;
16	16		if (idx < arr2.Length) {
17		-	try {
18		-	checked {
19		-	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
20		-	}
21		-	} catch (OverflowException) {
22		-	return -1;
23		-	}
	17	+	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
24	18		}
25	19
26	20		dictionary[(i, prev)] = cost;
			@@ -28,7 +22,7 @@ int Foo(int[] arr1, int[] arr2) {
28	22		}
29	23
30	24		int result = Bar(0, int.MinValue);
31		-	return result == int.MaxValue ? -1 : result;
	25	+	return result == int.MaxValue \|\| result == int.MinValue ? -1 : result;
32	26		}
33	27
34	28		int[] arr1 = {1,5,3,6,7};

1 file changed, 9 insertions, 3 deletions

leet.cs

			@@ -14,7 +14,13 @@ int Foo(int[] arr1, int[] arr2) {
14	14		int idx = Array.BinarySearch(arr2, prev + 1);
15	15		if (idx < 0) idx = ~idx;
16	16		if (idx < arr2.Length) {
17		-	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
	17	+	try {
	18	+	checked {
	19	+	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
	20	+	}
	21	+	} catch (OverflowException) {
	22	+	return -1;
	23	+	}
18	24		}
19	25
20	26		dictionary[(i, prev)] = cost;
			@@ -25,7 +31,7 @@ int Foo(int[] arr1, int[] arr2) {
25	31		return result == int.MaxValue ? -1 : result;
26	32		}
27	33
28		-	int[] arr1 = {1, 5, 3, 6, 7};
29		-	int[] arr2 = {1, 3, 2, 4};
	34	+	int[] arr1 = {1,5,3,6,7};
	35	+	int[] arr2 = {1,6,3,3};
30	36		int result = Foo(arr1, arr2);
31	37		Console.WriteLine(result);

1 file changed, 31 insertions

leet.cs(file created)

		@@ -0,0 +1,31 @@
1	+	int Foo(int[] arr1, int[] arr2) {
2	+	Array.Sort(arr2);
3	+	Dictionary<(int, int), int> dictionary = new Dictionary<(int, int), int>();
4	+
5	+	int Bar(int i, int prev) {
6	+	if (i == arr1.Length) return 0;
7	+	if (dictionary.ContainsKey((i, prev))) return dictionary[(i, prev)];
8	+
9	+	int cost = int.MaxValue;
10	+	if (arr1[i] > prev) {
11	+	cost = Bar(i + 1, arr1[i]);
12	+	}
13	+
14	+	int idx = Array.BinarySearch(arr2, prev + 1);
15	+	if (idx < 0) idx = ~idx;
16	+	if (idx < arr2.Length) {
17	+	cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
18	+	}
19	+
20	+	dictionary[(i, prev)] = cost;
21	+	return cost;
22	+	}
23	+
24	+	int result = Bar(0, int.MinValue);
25	+	return result == int.MaxValue ? -1 : result;
26	+	}
27	+
28	+	int[] arr1 = {1, 5, 3, 6, 7};
29	+	int[] arr2 = {1, 3, 2, 4};
30	+	int result = Foo(arr1, arr2);
31	+	Console.WriteLine(result);

更新更早