1476. پرس و جوهای مستطیل فرعی LeetCode – 🔥راه حل ساده منطقی جاوا – بیت 66٪

برای توضیح عمیق تر، لطفاً مخزن GitHub من را مشاهده کنید: https://github.com/VerisimilitudeX/LeetCode

مشکل پیاده سازی کلاسی است که می تواند یک مستطیل فرعی از یک مستطیل معین را به روز کند و پرس و جو کند. یک مستطیل فرعی با چهار گوشه آن (ردیف 1، col1، ردیف 2، col2) تعریف می شود. یکی از راه های حل این مشکل، ذخیره مستطیل اصلی و لیستی از به روز رسانی ها در کلاس است. هر به روز رسانی شامل مختصات مستطیل فرعی و مقدار جدید برای پر کردن آن است. برای پرس و جو از یک مقدار در یک موقعیت معین (ردیف، ستون)، می‌توانیم به‌روزرسانی‌ها را به ترتیب معکوس تکرار کنیم و بررسی کنیم که آیا موقعیت در هر یک از مستطیل‌های فرعی قرار می‌گیرد یا خیر. اگر بله، مقدار مربوطه را برمی گردانیم. اگر نه، مقدار اصلی را از مستطیل برمی گردانیم.

برای پیاده سازی این رویکرد، به دو ساختار داده نیاز داریم: یک آرایه دو بعدی برای ذخیره مستطیل اصلی و یک لیست برای ذخیره به روز رسانی ها. سازنده مستطیل را به عنوان ورودی می گیرد و آرایه و لیست را مقداردهی اولیه می کند. متد updateSubrectangle یک به روز رسانی جدید با پارامترهای داده شده به لیست اضافه می کند. متد getValue از انتها در لیست تکرار می شود و بررسی می کند که آیا موقعیت داده شده در هر به روز رسانی قرار دارد یا خیر. اگر بله، مقدار آن به روز رسانی را برمی گرداند. اگر نه، مقدار را از آرایه برمی گرداند.

• پیچیدگی زمانی:
  پیچیدگی زمانی سازنده $$O(mn)$$ است که $$m$$ و $$n$$ به ترتیب تعداد سطرها و ستون های مستطیل هستند. پیچیدگی زمانی روش updateSubrectangle $$O(1)$$ است زیرا فقط به لیست اضافه می شود. پیچیدگی زمانی روش getValue $$O(k)$$ است که $$k$$ تعداد به‌روزرسانی‌های موجود در لیست است.

• پیچیدگی فضا:
  پیچیدگی فضای کلاس $$O(mn + k)$$ است که در آن $$m$$، $$n$$ و $$k$$ به صورت بالا تعریف شده است. برای ذخیره آرایه به فضای $$O(mn)$$ و برای ذخیره لیست به فضای $$O(k)$$ نیاز داریم.

import java.util.*;

class SubrectangleQueries {
 private int[][] rect;
 private List<int[]> updates;

 public SubrectangleQueries(int[][] rectangle) {
 rect = rectangle;
 updates = new ArrayList<>();
 }

 public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
 updates.add(new int[]{row1, col1, row2, col2, newValue});
 }

 public int getValue(int row, int col) {
 for (int i = updates.size() - 1; i >= 0; i--) {
 int[] update = updates.get(i);
 if (row >= update[0] && row <= update[2] && col >= update[1] && col <= update[3]) {
 return update[4];
 }
 }
 return rect[row][col];
 }
}

راه حل های LeetCode من: https://leetcode.com/VerisimilitudeX/