我的平等堆棧算法存在哪些缺陷？

這是存在氣瓶堆棧的問題，您需要卸下頂部氣瓶直到堆棧高度相等。我的平等堆棧算法存在哪些缺陷？

樣品輸入：

該堆疊具有5,3，和4個氣缸和這些氣缸的各自的高度被放在後面的行給出。

預期輸出：

我的程序的輸出：

我的程序：

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
class Solution 
{ 
    static void Main(String[] args) 
    { 
     Func<string,int[]> GetIntsFromLine = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse); 
     int numcyls = GetIntsFromLine(Console.ReadLine()).Length; 
     int[][] cyls = new int[numcyls][]; 
     for(int i = 0; i < numcyls; ++i) 
      cyls[i] = GetIntsFromLine(Console.ReadLine()); 
     // now the j-th cylinder stacked on the i-th stach has height cyls[i][j] 

     while(true) 
     { 
       var heights = from cyl in cyls 
          select cyl.Sum(); 
       int h1 = heights.First(); 
       if(heights.All(h => h == h1)) // if equal heights 
       { 
        Console.WriteLine(h1); 
        return; 
       } 
       // if here, "remove" the top cylinder from the stack with the largest height 
       int[] st = cyls[heights.ToList().IndexOf(heights.Max())]; 
       int j = Array.IndexOf(st, 0); 
       st[j == -1 ? (st.Length - 1) : j] = 0;    
     } 

    } 
}

來源

2016-08-01 user6048670

https://ericlippert.com/2014/03/ 05/how-to-debug-small-programs/ – David

@David我知道如何調試。這並不能解決它們在算法中存在缺陷的問題。 – user6048670

那麼特別是問題變得明顯嗎？當你*調試這個時，邏輯與你期望的有什麼不同？到目前爲止，這是一個經典的「這是我所有的代碼，爲我調試」的問題。 – David

OK，讓我們來解決這個問題。因此，我們有三個堆棧：

1, 1, 1, 2, 3 
2, 3, 4 
1, 4, 1, 1

通過採取0，1，2，3 ...（這等於除去5，4，3，2 ...）從我們能在第一堆疊物品

0     == 0 
1     == 1 
1 + 1    == 2 
1 + 1 + 1   == 3 
1 + 1 + 1 + 2  == 5 <- this is the solution 
1 + 1 + 1 + 2 + 3 == 8

subacks。因此，我們可以生產

0, 1, 2, 3, 5, 8 (from the 1st) 
0, 2, 5, 9  (from the 2nd) 
0, 1, 5, 6, 7 (from the 3d)

，我們應該採取在所有行（可能子堆）pesented最大值 - 5.實施：

String input = 
    "5 3 4\n" + 
    "3 2 1 1 1\n" + 
    "4 3 2\n" + 
    "1 1 4 1"; 

var raw = input.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries) 
    .Skip(1) // We don't need 1st control line 
    .Select(line => line 
    .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries) 
    .Reverse() // <- do not forget this! 
    .Select(x => int.Parse(x))); 

// All possible substacks per each stack 
List<HashSet<int>> data = new List<HashSet<int>>(); 

foreach (var record in raw) { 
    HashSet<int> hs = new HashSet<int>() { 0 }; 

    data.Add(hs); 

    int agg = 0; 

    foreach (var item in record) 
    hs.Add(agg += item); 
} 

// Values that are in all substacks: 
HashSet<int> intersect = new HashSet<int>(data[0]); 

foreach (var line in data) 
    intersect.IntersectWith(line); 

// And, finally, the maximum one: 
Console.Write(intersect.Max());

來源

2016-08-01 15:34:21

我的平等堆棧算法存在哪些缺陷？

回答

相關問題