W porządku, więc to tylko niewielka część interesującego problemu, który rozwiązałem kilka dni temu. Wyobraź sobie, że mamy tablicę N elementów. Tablica składa się tylko z jedynek i -1s. Wygląda to mniej więcej tak:

int[] arr = new int[] { -1, 1, -1, 1, 1, -1 };

Naszym zadaniem jest znalezienie maksymalnej liczby kolejnych elementów (od lewej do prawej), które utrzymują (wyobrażony) licznik >= 0, a następnie wycięcie tablicy tak, aby pozostały tylko te elementy.

W naszym przypadku zaczynamy od licznika 0:

Licznik = 0

Pierwszy element: -1 -> Licznik = -1 (co jest poniżej 0, więc resetujemy licznik)

Drugi: 1 -> Licznik = 1

Po trzecie: -1 -> Licznik = 0

Czwarte: 1 -> Licznik = 1

Itp..

W powyższym przykładzie odpowiedź brzmi:

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };

Mój sposób na zrobienie tego był podobny do:

public static List<int> Solve(int[] input)
{
   List<List<int>> compare = new List<List<int>>();
   List<int> temp = new List<int>();
   for(int i = 0, c = 0; i < input.Length; i++)
   {
       if(input[i] == 1)
       {
           c++;
           temp.Add(input[i]);
       }
       else if(input[i] == -1)
       {
           c--;
           if (c >= 0)
               temp.Add(input[i]);
           else
           {
              c = 0;
              compare.Add(temp);
              temp = new List<int>();
           }
       }
   }

   compare.Add(temp);
   return compare.OrderByDescending(x => x.Count).First();
}

Więcej przypadków testowych:

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };

Solve(new int[] { 1, 1, -1, -1, 1, 1 }); // => new int[] { 1, 1, -1, -1, 1, 1 };

Solve(new int[] { 1, -1, 1, -1, 1, -1, -1, 1, 1, 1 }); // => new int[] { 1, -1, 1, -1, 1, -1 };

Solve(new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, -1 } 
// => new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1 };

Solve(new int[] { -1, -1, -1 }); // => new int[] { };

Ale moje pytanie do was wszystkich, mistrzów Linq, brzmi: Czy jest jakiś sposób, aby to zrobić w 1 linijce kodu, używając naszego ukochanego Linqa?

Byłoby to bardzo mile widziane :D

1
Plus 15 czerwiec 2021, 17:14

4 odpowiedzi

Najlepsza odpowiedź

Jeśli MUSISZ używać Linq i możesz oszukiwać i używać MoreLinq, to ​​ten brzydki bałagan zadziała (oddaje wiele kolekcji, ponieważ teoretycznie możesz mieć wiele przebiegów o tym samym maksymalnym rozmiarze)

Enumerable.Range(0, input.Count())
    .Select(i =>
        input.Skip(i)
             .Scan((Current: 0, Total: 0), (x, y) => (y, x.Total + y))
             .Skip(1)
             .TakeWhile(x => x.Total >= 0))
    .MaxBy(x => x.Count())
    .Select(x => x.Select(y => y.Current));
1
user2051770 15 czerwiec 2021, 20:14

W tym konkretnym przypadku, ze względu na dość złożoną logikę warunków, powiedziałbym, że stosowanie podejść iteracyjnych jest lepszą alternatywą, ale niektóre podobne zadania można rozwiązać za pomocą funkcje Aggregate, które stosują funkcję akumulatora do sekwencji i pozwalają na przekazywanie stanu między krokami . W twoim przypadku może to wyglądać mniej więcej tak (przy użyciu niektórych Funkcje C# 9):

var result = arr
    .Select((i, index) => (i, index))
    .Aggregate(
        (Sum: 0, Ranges: new List<List<int>> {new()}), // state holder 
        (agg, curr) =>
        {
            var sum = curr.i + agg.Sum;
            if (sum >= 0) agg.Ranges.Last().Add(curr.i);
            if (sum < 0)
            {
                sum = 0;
                agg.Ranges.Add(new());
            }

            return (sum, agg.Ranges);
        })
    .Ranges
    .Aggregate((agg, curr) => curr.Count > agg.Count ? curr : agg); // MaxBy via Aggregate
1
Guru Stron 15 czerwiec 2021, 16:04

Zgadzam się z innymi odpowiedziami sugerującymi, że LINQ nie jest prawdopodobnie najlepszym podejściem. Oto moje ujęcie. Ta wersja zastępuje tylko krótszą sekwencję dłuższą sekwencją, aby uniknąć nadmiaru pamięci, a krok OrderByDescending można wtedy również pominąć.

public static List<int> Solve(int[] input)
{
    var temp = new List<int>();
    var longestSequence = new List<int>();

    for (int i = 0, c = 0; i < input.Length; i++)
    {
        c += input[i];

        if (c >= 0)
            temp.Add(input[i]);
        else
        {
            c = 0;
            if (temp.Count > longestSequence.Count)
                longestSequence = temp;
            temp = new List<int>();
        }
    }

    return longestSequence;
}

Jeśli naprawdę przejmujesz się alokacjami pamięci, takimi jak kopiowanie do listy tymczasowej i operacje zmiany rozmiaru listy pod okładkami, możesz zamiast tego śledzić początek i koniec sekwencji, a następnie zapętlić tę, zwracając podsekwencję.

1
Kit 15 czerwiec 2021, 16:45

Ostatnio spotkałem się z tym problemem podczas testu umiejętności, który musiałem wykonać, starając się o pracę. Aby go rozwiązać, potrzebujesz bardzo mało kodu i nie jest wymagane LINQ.

int currentLevel = 0;
List<int> lst = new List<int>();
for(int x = 0; x < input.length; x++) {
  currentLevel += input[x];
  if (currentLevel >= 0) {
    lst.Add(input[x]);
  }
}
return lst.ToArray();
1
Dave Holden 15 czerwiec 2021, 19:03