java - 如何比较 ArrayList 中的整数元素？

Question

我试图通过从三角形的每一行中获取最大数量来解决问题。到目前为止，我能够生成一个三角形，但我如何从每一行中获取最大数量？

这是我的代码


private static Integer solve(Triangle triangle)
{
//triangle is extending an ArrayList
System.out.println(triangle);
return 0;
}

这是目前正在生产的：

              6
            3  5
          9  7  1
        4  6  8  4

但现在我想得到结果：

“在这个三角形中，最大总数是：6 + 5 + 9 + 8 = 26”

这是完整的代码：

public class HellTriangle {
private static final int TRIANGLE_HEIGHT = 10;


public static void start() {
    Triangle triangle = generateTriangle();
    //System.out.println(triangle);

    long start = System.currentTimeMillis();
    Integer result = solve(triangle);
    long end = System.currentTimeMillis();

    System.out.println("Result:" + result);
    System.out.println("Resolution time: " + (end - start) + "ms");
}

private static Triangle generateTriangle() {
    Triangle triangle = new Triangle();

    Random random = new Random();

    for (int i = 0; i < TRIANGLE_HEIGHT; i++) {

        Row row = new Row();

        for (int j = 0; j <= i; j++) {
            row.add(random.nextInt(100));
        }
        triangle.add(row);
    }
    return triangle;
}

private static class Row extends ArrayList<Integer> {
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < size(); i++) {

            sb.append(String.format("%02d", get(i)));
            //rows.add(get(i));
            if (i < (size() - 1)) {
                sb.append("  ");
            }
        }
        return sb.toString();
    }
}

private static class Triangle extends ArrayList<Row> {

    public String toString() {

        // sb is used to make modification to the String
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < size(); i++) {

            for (int j = 0; j < (TRIANGLE_HEIGHT - 1 - i); j++) {
                sb.append("  ");
            }

            sb.append(get(i));

            if (i < (size() - 1)) {
                sb.append("\n");
            }
        }
        return sb.toString();
    }
}

private static Integer solve(Triangle triangle) {

    System.out.println(triangle);
    return 0;
}

public static void main(String[] args) {
    start();
}
}

任何帮助，将不胜感激！

Answer 1

由于您的行中没有排序，这将导致 O(n) 获得每行的最大值，我将在插入期间查找最大值。类似的东西（未经测试，您可能还必须覆盖其他添加方法，具体取决于您的用例）：

public class Row extends ArrayList<Integer> {
    public String toString() {
        ...
    }

    private Integer max = null;

    @Override
    public boolean add(Integer elem) {
        if (elem != null && (max == null || max < elem)) {
            max = elem;
        }
        return super.add(elem);
    }

    public Integer getMax() {
        return max;
    }

}

Answer 2

在这里，只需改变你的solve()

private static void solve(Triangle triangle) {

    System.out.println(triangle);

    ArrayList<Integer> result = new ArrayList<Integer>();
    int total = 0;

    for(Row row  : triangle){
        Collections.sort(row);
        total += row.get(row.size()-1);
        result.add(row.get(row.size()-1));
    }

    for(Integer intr : result)
        System.out.println("Largest elements of the rows: " + intr);
    System.out.println("Total: " + total);
}

Answer 3

尝试

private static int getTriangleMax(final Triangle rows)
  {
    int max = 0;

    for (final Row row : rows)
    {
      final int rowMax = getRowMax(row);
      max += rowMax;
    }

    return max;
  }

  private static int getRowMax(final Row row)
  {
    int rowMax = Integer.MIN_VALUE;

    for (final Integer integer : row)
    {
      if (rowMax < integer)
      {
        rowMax = integer;
      }
    }

    return rowMax;
  }

Answer 4

简单的解决方案：

1.添加静态列表如下：

private static List maxRowVal=new ArrayList();

2.用这个替换你的 generateTriangle() 函数：

private static Triangle generateTriangle() 
{
            Triangle triangle = new Triangle();

        Random random = new Random();

        for (int i = 0; i < TRIANGLE_HEIGHT; i++) {

            Row row = new Row();
            int maxTemp=0;
            for (int j = 0; j <= i; j++) {
                int rand=random.nextInt(100);
                row.add(rand);
                if(rand>maxTemp)
                    maxTemp=rand;     //will get max value for the row
            }
            maxRowVal.add(maxTemp);
            triangle.add(row);
        }
        return triangle;
    }

确实很简单！！

Answer 5

这不完全是您所要求的，但我想向您展示解决此问题的不同方法。人们以前为我做过这件事，我真的很高兴看到解决问题的不同方法。祝你编码好运！

下面是完整的代码，所以你可以复制、粘贴和运行它。

public class SSCCE {
    public static void main(String[] args) {

        // Here you specify the size of your triangle. Change the number dim to
        // whatever you want. The triangle will be represented by a 2d-array.
        final int dim = 5;
        int[][] triangle = new int[dim][dim];

        // Walks through the triangle and fills it with random numbers from 1-9.
        for (int r = 0; r < dim; r++) {
            for (int c = 0; c < r + 1; c++) {
                triangle[r][c] = (int) (9 * Math.random()) + 1;
            }
        }

        // This piece just prints the triangle so you can see what's in it.
        for (int r = 0; r < dim; r++) {
            for (int c = 0; c < r + 1; c++) {
                System.out.print(triangle[r][c] + " ");
            }
            System.out.println();
        }

        // This part finds the maximum of each row. It prints each rows maximum
        // as well as the sum of all the maximums at the end.
        int sum = 0;
        System.out.print("\nIn this triangle the maximum total is: ");
        for (int r = 0; r < dim; r++) {
            int currentMax = 0;
            for (int c = 0; c < r + 1; c++) {
                if (triangle[r][c] > currentMax) {
                    currentMax = triangle[r][c];
                }
            }
            sum += currentMax;
            if (r != 0) {
                System.out.print(" + ");
            }
            System.out.print(currentMax);
        }
        System.out.println(" = " + sum + ".");
    }
}

输出：

9 
9 2 
1 7 3 
1 7 3 3 
5 7 5 1 9 

In this triangle the maximum total is: 9 + 9 + 7 + 7 + 9 = 41.