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) が行ごとに最大値を取得することにつながるため、挿入中に最大値を検索します。そのようなもの（テストされておらず、ユースケースに応じて、おそらく他の add メソッドもオーバーライドする必要があります）：

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.