118. مثلث پاسکال LeetCode – راه حل منطقی بسیار ساده 96٪ از راه حل های جاوا را در حافظه و زمان اجرا شکست می دهد.

مشکل تولید n ردیف اول مثلث پاسکال است که در آن هر عنصر مجموع دو عنصر بالای آن است. یکی از راه های ممکن برای حل این مشکل استفاده از لیستی از لیست ها (یا به عبارت دیگر، یک آرایه دو بعدی) برای ذخیره سطرها و تکرار از سطر اول تا ردیف n و افزودن عناصر جدید بر اساس سطر قبلی است.

• یک لیست خالی از لیست ها را برای ذخیره ردیف ها راه اندازی کنید.
• سطر اول را که یک لیست حاوی تنها 1 است به لیست سطرها اضافه کنید.
• برای هر ردیف از 1 تا n-1 موارد زیر را انجام دهید:
  • یک لیست خالی را برای ذخیره ردیف فعلی راه اندازی کنید.
  • 1 را به ابتدا و انتهای ردیف فعلی اضافه کنید.
  • برای هر عنصر از 1 تا i-1، جایی که i شاخص ردیف فعلی است، موارد زیر را انجام دهید:
    • ردیف قبلی را از لیست ردیف ها دریافت کنید.
    • عنصر را در اندیس j-1 و j از ردیف قبلی اضافه کنید و آن را به ردیف فعلی اضافه کنید.
  • ردیف فعلی را به لیست ردیف ها اضافه کنید.
• لیست سطرها را برگردانید.

ما باید روی n ردیف تکرار کنیم و برای هر ردیف i باید روی عناصر i تکرار کنیم. تعداد کل عناصر است n(n+1) / 2​، که است O(n^2) در نماد مجانبی

ما باید n ردیف را ذخیره کنیم و هر ردیف i دارای عناصر i است. کل فضای مورد نیاز است n(n+1) / 2​، که است O(n^2) در نماد مجانبی

public class Solution {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allRows = new ArrayList<>(numRows);
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        allRows.add(firstRow);
        for (int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            row.add(1);
            List<Integer> prevRow = allRows.get(i - 1);
            for (int j = 1; j < i; j++) {
                int sum = 0;
                if (j - 1 >= 0 && j - 1 < prevRow.size()) {
                    sum += prevRow.get(j - 1);
                }
                if (j >= 0 && j < prevRow.size()) {
                    sum += prevRow.get(j);
                }
                row.add(sum);
            }
            row.add(1);
            allRows.add(row);
        }
        return allRows;
    }
}

برای توضیح بیشتر، لطفاً پست LeetCode من را مشاهده کنید: https://leetcode.com/problems/pascals-triangle/solutions/3563758/pascal-s-triangle-extremely-simple-logic-solution-beats-96- راه حل های-جاوا-در-حافظه-ران/