从三角形的每一行中获取最高数字并将其相加

本文关键字：数字 高数字 三角形 一行 获取 | 更新日期: 2023-09-27 18:22:44

我有下面的三角形数字，将作为参数发送到function 

5
9 6
4 6 8
0 7 1 5

现在，这将在下面的函数中以字符串的形式接收，格式为5#9#6#4#6#8#0#7#1#5。到目前为止，我试图只从#中涟漪

数字 
public class Sample
{
    public static string validtrianglesum(string input)
    {
        string sum="0";
        foreach(char num in input)
        {
            if(!num.Equals('#'))
            {
                Console.PrintLine(num); //here am getting only the nums excluding #
                //How to sum up based on each row
            }
        }
        return sum; //return 
    }
}

如何从每行中得出最高数字并将它们相加，以及如何识别行以求和？希望能找到一些帮助。

从三角形的每一行中获取最高数字并将其相加

让我们将其分解如下：

首先，将输入转换为数字数组：

string input = "5#9#6#4#6#8#0#7#1#5";
var numbers = input.Split('#').Select(int.Parse).ToArray();

现在让我们假设我们有一个MakeTriangular(int[])方法，它将一个数字数组转换为一个行序列，第一行的长度为 1，第二行的长度为 2，依此类推，以便它返回 IEnumerable<IEnumerable<int>> 。

然后，我们可以将其与 Linq 一起使用来计算每行中最大值的总和，如下所示：

int sum = MakeTriangular(numbers).Sum(row => row.Max());

这给出了答案。

MakeTriangular()的实现可能如下所示：

public static IEnumerable<IEnumerable<int>> MakeTriangular(int[] numbers)
{
    for (int i = 0, len = 1; i < numbers.Length; i += len, ++len)
        yield return new ArraySegment<int>(numbers, i, len);
}
将所有

内容组合到可编译的控制台应用中：

using System;
using System.Collections.Generic;
using System.Linq;
namespace Demo
{
    class Program
    {
        public static void Main()
        {
            string input = "5#9#6#4#6#8#0#7#1#5";
            var numbers = input.Split('#').Select(int.Parse).ToArray();
            int sum = MakeTriangular(numbers).Sum(row => row.Max());
            Console.WriteLine(sum);
        }
        public static IEnumerable<IEnumerable<int>> MakeTriangular(int[] numbers)
        {
            for (int i = 0, len = 1; i < numbers.Length; i += len, ++len)
                yield return new ArraySegment<int>(numbers, i, len);
        }
    }
}

对每行中的所有值求和：

private static IEnumerable<int> Sum(string input)
{
    int i = 0, s = 0, z = 1;
    foreach (var v in input.Split('#').Select(int.Parse))
    {
        s += v;
        if (++i != z) continue;
        z++;
        yield return s;
        s = i = 0;
    }
}

一行相同：

private static IEnumerable<int> Sum(string input) => new Func<int, int, IEnumerable<int>>((i, z) => input.Split('#').Select(int.Parse).GroupBy(e => i++ == z && (i = 1) != null ? ++z : z, e => e).Select(e => e.Sum()))(0, 1);

对每行中的所有最大值求和：

private static int Sum(string input)
{
    int i = 0, s = 0, z = 1, m = 0;
    foreach (var v in input.Split('#').Select(int.Parse))
    {
        if (v > m) m = v;
        if (++i != z) continue;
        z++;
        s += m;
        i = m = 0;
    }
    return s;
}

一行相同：

private static int Sum(string input) => new Func<int, int, int>((i, z) => input.Split('#').Select(int.Parse).GroupBy(e => i++ == z && (i = 1) != null ? ++z : z, e => e).Select(e => e.Max()).Sum())(0, 1);

我以IEnumerable<int>和yield return的形式退还款项.如果您只想打印答案，请将返回类型更改为void并删除yield return s;行。

解决此问题的一种方法是确定三角形的大小。我所说的尺寸是指高度/宽度。例如，提供的三角形的大小为 4。

如果大小n则三角形中的元素数将n(n + 1)/2 。当输入中的元素数量已知时，可以通过求解二次多项式并选择正解(下面的表达式涉及平方根(来确定n(大小(：

var triangle = "5#9#6#4#6#8#0#7#1#5";
var values = triangle.Split('#').Select(Int32.Parse).ToList();
var sizeAsDouble = (-1 + Math.Sqrt(1 + 8*values.Count))/2;
var size = (Int32) sizeAsDouble;
if (sizeAsDouble != size)
  throw new ArgumentException("Input data is not a triangle.");

因此，使用提供的输入size将4。然后，您可以使用大小选择三角形中的每一行并执行所需的算术：

var maxValues = Enumerable
  .Range(0, size)
  .Select(i => new { Start = i*(i + 1)/2, Count = i + 1 })
  .Select(x => values.Skip(x.Start).Take(x.Count))
  .Select(v => v.Max());

第一个Select将计算必要的索引，以正确切片在第二个Select中完成的值数组。再次使用公式n(n + 1)/2。如果你愿意，你可以合并其中一些Select操作，但我认为将它们分开可以更清楚地了解正在发生的事情。

其输出将是数字5, 9, 8, 7。如果你想总结这些，你可以这样做：

return maxValues.Sum();

您可以使用 LINQ：

string input = "5#9#6#4#6#8#0#7#1#5";
var nums = input.Split('#').Select(s => Int32.Parse(s));
var res = Enumerable.Range(0, nums.Count())
                    .Select(n => nums.Skip(Enumerable.Range(0, n).Sum()).Take(n));
                    .Where(x => x.Any());  // here you have IEnumerable<int> for every row 
                    .Select(arr => arr.Max());

請表揚Widi :)但这是你的要求

var rows = Sum("5#9#6#4#6#8#0#7#1#5");
var total = rows.Sum();
private static IEnumerable<int> Sum(string inp)
{
    int i = 0, s = 0, z = 1;
    foreach (var v in inp.Split('#').Select(int.Parse))
    {
        s = Math.Max(s, v);
        if (++i == z)
        {
            z++;
            yield return s;
            s = i = 0;
        }
    }
}

我会使用 2 个函数：

第一个将字符串转换为树表示形式： 

  List<List<int>> GetTree(string data)
    {
        List<List<int>> CompleteTree = new List<List<int>>();
        List<int> ValuesInLine = new List<int>();
        int partsinrow = 1;
        int counter = 0;
        foreach (string part in data.Split('#'))
        {
            int value = int.Parse(part);
            ValuesInLine.Add(value);
            if (++counter == partsinrow)
            {
                CompleteTree.Add(ValuesInLine);
                ValuesInLine = new List<int>();
                counter = 0;
                partsinrow++;
            }
        }
        return CompleteTree;
    }

第二个来总结行的最大值：

    int GetSumOfTree(List<List<int>> tree)
    {
        int sum = 0;
        foreach (List<int> line in tree)
        {
            line.Sort();
            int max = line[line.Count - 1];
            sum += max;
        }
        return sum;
    }
相关文章：