C# 如何使用堆栈优化我的代码? (HackerRank "Equal Stacks" 问题)
C# How to optimize my code using stacks? (HackerRank "Equal Stacks" problem)
我已经解决了问题,但是 11/30 的测试用例因为“超出时间限制”而失败。我想知道是否有一种方法可以优化我的代码,使解决方案通过所有测试用例。
link问题来了:
https://www.hackerrank.com/challenges/equal-stacks/problem
我的做法:
正如问题的名称所暗示的那样,我想使用堆栈,即使方法中传递的参数是 List。
所以首先我按照以下方式将列表转换为堆栈:每个顶部元素代表堆栈的当前高度。因此,如果存在高度为 1、5、10 的块,则堆栈中的元素将为 1、6、16。
我的算法是从堆栈中弹出最大元素,直到所有堆栈具有相同的高度。
这是我的代码:
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3)
{
var result = 0;
if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
var h1Stack = GetStack(h1);
var h2Stack = GetStack(h2);
var h3Stack = GetStack(h3);
while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
{
var h1Height = LocalPeek(h1Stack);
var h2Height = LocalPeek(h2Stack);
var h3Height = LocalPeek(h3Stack);
if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
}
return 0;
}
static bool IsEmpty(List<int> stack)
{
return (!stack?.Any() ?? true);
}
static int LocalPeek(Stack<int> stack){
if (stack.Any()) return stack.Peek();
return 0;
}
static Stack<int> GetStack(List<int> numbers)
{
var stack = new Stack<int>(numbers.Count);
for (var i = numbers.Count - 1; i >= 0; --i)
{
stack.Push(numbers[i] + LocalPeek(stack));
}
return stack;
}
static int CountHeight(Stack<int> stack)
{
return stack.Any() ? stack.Peek() : 0;
}
如果我们有长度为 m、n、k 的列表作为输入,n 是它们的最大值,那么我认为我的算法在 O(n) 中执行;老实说,我认为这没有任何问题。
如果我做错了什么请告诉我,我该如何解决。
谢谢。
我建议从 最高 堆栈中移除圆柱体,而堆栈具有不同的高度:
// Assuming that we don't have cylinders of negative height
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3) {
if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
return 0;
int height1 = h1.Sum();
int height2 = h2.Sum();
int height3 = h3.Sum();
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (height1 != height2 || height1 != height3) {
if (height1 >= height2 && height1 >= height3)
height1 -= h1[p1++];
else if (height2 >= height1 && height2 >= height3)
height2 -= h2[p2++];
else
height3 -= h3[p3++];
}
return height1;
}
我还建议不要使用堆栈,这是一种非 linq 方法,每个列表(一个解析)上的 O(n),而且它分配的不超过计算变量。
public static int EqualStacks(int[] h1, int[] h2, int[] h3)
{
var a = new[] {h1, h2, h3};
var i = new int[3];
var c = new int[3];
var last = 0;
bool GetLowest(out int result)
{
result = -1;
if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length-1) result = 0;
else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
else if (i[2] < a[2].Length - 1) result = 2;
else return false;
return true;
}
while (true)
{
if (!GetLowest(out var index))
return last;
c[index] += a[index][i[index]];
i[index]++;
if (c[0] == c[1] && c[1] == c[2])
last = c[0];
// Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
}
}
用法
var result = EqualStacks(
new[] {1, 1, 1, 2, 3},
new[] {2, 3, 4},
new[] {1, 4, 1, 1});
Console.WriteLine(result);
结果
Current = 1, 0, 0, Index = 0, Last = 0
Current = 1, 2, 0, Index = 1, Last = 0
Current = 1, 2, 1, Index = 2, Last = 0
Current = 2, 2, 1, Index = 0, Last = 0
Current = 2, 2, 5, Index = 2, Last = 0
Current = 3, 2, 5, Index = 0, Last = 0
Current = 3, 5, 5, Index = 1, Last = 0
Current = 5, 5, 5, Index = 0, Last = 5
Current = 5, 5, 6, Index = 2, Last = 5
Result = 5, 5, 6, Last = 5
5
注意 :我还没有彻底测试过这个,虽然我的大脑说它有效..可能会出什么问题(不好意思地说)? ¯\_(ツ)_/¯
,
您还可以内联 GetLowest()
,这样可以避免烦人的堆栈调用和其他恶作剧,而且您可能会摆脱数组或堆栈分配它们
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)
基准
Method
N
Mean
Error
StdDev
Gen 0
Gen 1
Allocated
Mine
10
90.89 ns
0.581 ns
0.544 ns
0.0153
-
128 B
Yours
10
2,069.31 ns
13.881 ns
12.984 ns
0.0343
-
288 B
Dmitrys
10
304.75 ns
1.331 ns
1.245 ns
0.0143
-
120 B
Mine
1000
8,626.12 ns
108.481 ns
101.473 ns
0.0153
-
128 B
Yours
1000
43,196.78 ns
327.480 ns
290.302 ns
1.4038
-
12,168 B
Dmitrys
1000
20,563.90 ns
64.089 ns
53.517 ns
-
-
120 B
Mine
10000
202,904.36 ns
684.727 ns
571.778 ns
-
-
128 B
Yours
10000
402,362.80 ns
3,263.325 ns
3,052.517 ns
14.1602
1.4648
120,168 B
Dmitrys
10000
205,329.07 ns
1,014.000 ns
948.496 ns
-
-
120 B
代码
[SimpleJob(RuntimeMoniker.Net50)]
[MemoryDiagnoser]
public class WeirdStuff
{
private int[] data1;
private int[] data2;
private int[] data3;
private List<int> h1;
private List<int> h2;
private List<int> h3;
[Params(10, 1000, 10000)] public int N;
[GlobalSetup]
public void Setup()
{
var r = new Random(42);
data1 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
data2 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
data3 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
h1 = new List<int>(data1);
h2 = new List<int>(data2);
h3 = new List<int>(data3);
}
[Benchmark]
public int Mine()
{
var a = new[] {data1, data2, data3};
var i = new int[3];
var c = new int[3];
var last = 0;
while (true)
{
if (!GetLowest(out var index, c, i, a))
return last;
c[index] += a[index][i[index]];
i[index]++;
if (c[0] == c[1] && c[1] == c[2])
last = c[0];
//Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)
{
result = -1;
if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length - 1) result = 0;
else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
else if (i[2] < a[2].Length - 1) result = 2;
else return false;
return true;
}
[Benchmark]
public int Yours()
{
var result = 0;
if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
var h1Stack = GetStack(h1);
var h2Stack = GetStack(h2);
var h3Stack = GetStack(h3);
while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
{
var h1Height = LocalPeek(h1Stack);
var h2Height = LocalPeek(h2Stack);
var h3Height = LocalPeek(h3Stack);
if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
}
return 0;
}
bool IsEmpty(List<int> stack)
{
return (!stack?.Any() ?? true);
}
int LocalPeek(Stack<int> stack)
{
if (stack.Any()) return stack.Peek();
return 0;
}
Stack<int> GetStack(List<int> numbers)
{
var stack = new Stack<int>(numbers.Count);
for (var i = numbers.Count - 1; i >= 0; --i)
{
stack.Push(numbers[i] + LocalPeek(stack));
}
return stack;
}
static int CountHeight(Stack<int> stack)
{
return stack.Any() ? stack.Peek() : 0;
}
[Benchmark]
public int Dmitrys()
{
if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
return 0;
int height1 = h1.Sum();
int height2 = h2.Sum();
int height3 = h3.Sum();
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (height1 != height2 || height1 != height3)
{
if (height1 >= height2 && height1 >= height3)
height1 -= h1[p1++];
else if (height2 >= height1 && height2 >= height3)
height2 -= h2[p2++];
else
height3 -= h3[p3++];
}
return height1;
}
}
我已经解决了问题,但是 11/30 的测试用例因为“超出时间限制”而失败。我想知道是否有一种方法可以优化我的代码,使解决方案通过所有测试用例。
link问题来了: https://www.hackerrank.com/challenges/equal-stacks/problem
我的做法: 正如问题的名称所暗示的那样,我想使用堆栈,即使方法中传递的参数是 List。 所以首先我按照以下方式将列表转换为堆栈:每个顶部元素代表堆栈的当前高度。因此,如果存在高度为 1、5、10 的块,则堆栈中的元素将为 1、6、16。 我的算法是从堆栈中弹出最大元素,直到所有堆栈具有相同的高度。
这是我的代码:
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3)
{
var result = 0;
if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
var h1Stack = GetStack(h1);
var h2Stack = GetStack(h2);
var h3Stack = GetStack(h3);
while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
{
var h1Height = LocalPeek(h1Stack);
var h2Height = LocalPeek(h2Stack);
var h3Height = LocalPeek(h3Stack);
if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
}
return 0;
}
static bool IsEmpty(List<int> stack)
{
return (!stack?.Any() ?? true);
}
static int LocalPeek(Stack<int> stack){
if (stack.Any()) return stack.Peek();
return 0;
}
static Stack<int> GetStack(List<int> numbers)
{
var stack = new Stack<int>(numbers.Count);
for (var i = numbers.Count - 1; i >= 0; --i)
{
stack.Push(numbers[i] + LocalPeek(stack));
}
return stack;
}
static int CountHeight(Stack<int> stack)
{
return stack.Any() ? stack.Peek() : 0;
}
如果我们有长度为 m、n、k 的列表作为输入,n 是它们的最大值,那么我认为我的算法在 O(n) 中执行;老实说,我认为这没有任何问题。 如果我做错了什么请告诉我,我该如何解决。
谢谢。
我建议从 最高 堆栈中移除圆柱体,而堆栈具有不同的高度:
// Assuming that we don't have cylinders of negative height
public static int equalStacks(List<int> h1, List<int> h2, List<int> h3) {
if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
return 0;
int height1 = h1.Sum();
int height2 = h2.Sum();
int height3 = h3.Sum();
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (height1 != height2 || height1 != height3) {
if (height1 >= height2 && height1 >= height3)
height1 -= h1[p1++];
else if (height2 >= height1 && height2 >= height3)
height2 -= h2[p2++];
else
height3 -= h3[p3++];
}
return height1;
}
我还建议不要使用堆栈,这是一种非 linq 方法,每个列表(一个解析)上的 O(n),而且它分配的不超过计算变量。
public static int EqualStacks(int[] h1, int[] h2, int[] h3)
{
var a = new[] {h1, h2, h3};
var i = new int[3];
var c = new int[3];
var last = 0;
bool GetLowest(out int result)
{
result = -1;
if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length-1) result = 0;
else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
else if (i[2] < a[2].Length - 1) result = 2;
else return false;
return true;
}
while (true)
{
if (!GetLowest(out var index))
return last;
c[index] += a[index][i[index]];
i[index]++;
if (c[0] == c[1] && c[1] == c[2])
last = c[0];
// Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
}
}
用法
var result = EqualStacks(
new[] {1, 1, 1, 2, 3},
new[] {2, 3, 4},
new[] {1, 4, 1, 1});
Console.WriteLine(result);
结果
Current = 1, 0, 0, Index = 0, Last = 0
Current = 1, 2, 0, Index = 1, Last = 0
Current = 1, 2, 1, Index = 2, Last = 0
Current = 2, 2, 1, Index = 0, Last = 0
Current = 2, 2, 5, Index = 2, Last = 0
Current = 3, 2, 5, Index = 0, Last = 0
Current = 3, 5, 5, Index = 1, Last = 0
Current = 5, 5, 5, Index = 0, Last = 5
Current = 5, 5, 6, Index = 2, Last = 5
Result = 5, 5, 6, Last = 5
5
注意 :我还没有彻底测试过这个,虽然我的大脑说它有效..可能会出什么问题(不好意思地说)? ¯\_(ツ)_/¯
,
您还可以内联 GetLowest()
,这样可以避免烦人的堆栈调用和其他恶作剧,而且您可能会摆脱数组或堆栈分配它们
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)
基准
Method | N | Mean | Error | StdDev | Gen 0 | Gen 1 | Allocated |
---|---|---|---|---|---|---|---|
Mine | 10 | 90.89 ns | 0.581 ns | 0.544 ns | 0.0153 | - | 128 B |
Yours | 10 | 2,069.31 ns | 13.881 ns | 12.984 ns | 0.0343 | - | 288 B |
Dmitrys | 10 | 304.75 ns | 1.331 ns | 1.245 ns | 0.0143 | - | 120 B |
Mine | 1000 | 8,626.12 ns | 108.481 ns | 101.473 ns | 0.0153 | - | 128 B |
Yours | 1000 | 43,196.78 ns | 327.480 ns | 290.302 ns | 1.4038 | - | 12,168 B |
Dmitrys | 1000 | 20,563.90 ns | 64.089 ns | 53.517 ns | - | - | 120 B |
Mine | 10000 | 202,904.36 ns | 684.727 ns | 571.778 ns | - | - | 128 B |
Yours | 10000 | 402,362.80 ns | 3,263.325 ns | 3,052.517 ns | 14.1602 | 1.4648 | 120,168 B |
Dmitrys | 10000 | 205,329.07 ns | 1,014.000 ns | 948.496 ns | - | - | 120 B |
代码
[SimpleJob(RuntimeMoniker.Net50)]
[MemoryDiagnoser]
public class WeirdStuff
{
private int[] data1;
private int[] data2;
private int[] data3;
private List<int> h1;
private List<int> h2;
private List<int> h3;
[Params(10, 1000, 10000)] public int N;
[GlobalSetup]
public void Setup()
{
var r = new Random(42);
data1 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
data2 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
data3 = Enumerable.Range(0, N).Select(x => r.Next(1, 5)).ToArray();
h1 = new List<int>(data1);
h2 = new List<int>(data2);
h3 = new List<int>(data3);
}
[Benchmark]
public int Mine()
{
var a = new[] {data1, data2, data3};
var i = new int[3];
var c = new int[3];
var last = 0;
while (true)
{
if (!GetLowest(out var index, c, i, a))
return last;
c[index] += a[index][i[index]];
i[index]++;
if (c[0] == c[1] && c[1] == c[2])
last = c[0];
//Console.WriteLine($"Current = {string.Join(", ", c)}, Index = {index}, Last = {last}");
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool GetLowest(out int result, int[] c, int[] i, int[][] a)
{
result = -1;
if (c[0] <= c[1] && c[0] <= c[2] && i[0] < a[0].Length - 1) result = 0;
else if (c[1] <= c[0] && c[1] <= c[2] && i[1] < a[1].Length - 1) result = 1;
else if (i[2] < a[2].Length - 1) result = 2;
else return false;
return true;
}
[Benchmark]
public int Yours()
{
var result = 0;
if (IsEmpty(h1) || IsEmpty(h2) || IsEmpty(h3)) return result;
var h1Stack = GetStack(h1);
var h2Stack = GetStack(h2);
var h3Stack = GetStack(h3);
while (h1Stack.Any() && h2Stack.Any() && h3Stack.Any())
{
var h1Height = LocalPeek(h1Stack);
var h2Height = LocalPeek(h2Stack);
var h3Height = LocalPeek(h3Stack);
if (h1Height == h2Height && h1Height == h3Height) return CountHeight(h1Stack);
var max = Math.Max(h1Height, Math.Max(h2Height, h3Height));
if (h1Height == max && h1Stack.Any()) h1Stack.Pop();
if (h2Height == max && h2Stack.Any()) h2Stack.Pop();
if (h3Height == max && h3Stack.Any()) h3Stack.Pop();
}
return 0;
}
bool IsEmpty(List<int> stack)
{
return (!stack?.Any() ?? true);
}
int LocalPeek(Stack<int> stack)
{
if (stack.Any()) return stack.Peek();
return 0;
}
Stack<int> GetStack(List<int> numbers)
{
var stack = new Stack<int>(numbers.Count);
for (var i = numbers.Count - 1; i >= 0; --i)
{
stack.Push(numbers[i] + LocalPeek(stack));
}
return stack;
}
static int CountHeight(Stack<int> stack)
{
return stack.Any() ? stack.Peek() : 0;
}
[Benchmark]
public int Dmitrys()
{
if (h1.Count <= 0 || h2.Count <= 0 || h3.Count <= 0)
return 0;
int height1 = h1.Sum();
int height2 = h2.Sum();
int height3 = h3.Sum();
int p1 = 0;
int p2 = 0;
int p3 = 0;
while (height1 != height2 || height1 != height3)
{
if (height1 >= height2 && height1 >= height3)
height1 -= h1[p1++];
else if (height2 >= height1 && height2 >= height3)
height2 -= h2[p2++];
else
height3 -= h3[p3++];
}
return height1;
}
}