تنفيذ خوارزمياتArrayList
مُقدَّم| English | المعنى |
|---|---|
| shift/ʃɪft/ | الإزاحة |
| delete/dɪˈliːt/ | الحذف |
| insert/ˈɪnsɜːt/ | الإدراج |
Adjacent removals reveal a skipped element
- Starting with
[0, 0, 5], remove index 0 and then increment i. The second zero has shifted into index 0, so that forward loop skips it and leaves[0, 5]. - For the forward while-loop taught here, stay at the same index after removal and advance only when keeping an element. It then removes both zeros and finishes with
[5].
![Adjacent removals reveal the skipped-element bug: scanning [0, 0, 5] forwards, removing index 0 and then incrementing skips the second zero, which moved to index 0; keep the same index after a removal and increment only when keeping an item, giving [5]](/learn-media/ap_computer_science_a/assets/0410-skip-bug.png?v=1794647927)
Keep the current forward index after removal
- After
remove(i), every later element shifts one place left. If an element now occupies i, it has not yet been checked; inspect it on the next iteration. - The loop below accepts a non-null list of non-null Integers and removes every zero in place. It uses current size each iteration and performs no get call on an empty list.
import java.util.ArrayList;
public class RemoveZeros {
public static void removeZeros(ArrayList<Integer> list) {
int i = 0;
while (i < list.size()) {
if (list.get(i) == 0) {
list.remove(i);
} else {
i++;
}
}
}
}
Explain why this loop terminates
- Each iteration either removes one element and reduces size, or keeps one and increases i. Thus
size() - i, the number of positions still to check, decreases by one each iteration. - Starting with
[0, 0, 5], the states are[0, 5]at i=0,[5]at i=0, then[5]at i=1. The final condition is false, so no out-of-bounds access occurs.
A backward loop follows a different rule
- A reverse loop starts at the final existing index:
for (int i = list.size() - 1; i >= 0; i--). Remove matching elements withremove(i); the next i is always one lower. - Deleting at i shifts only later indices, which have already been checked. Earlier unchecked elements retain their indices, so decrementing after a removal is correct here; “never advance after removal” is not a universal rule.
Choose an index update that matches the direction of traversal. In the forward while-loop, stay after removal; in the backward for-loop, continue decrementing. Direct structural changes during an enhanced loop are a separate unsafe pattern, even when no fail-fast exception appears.
في حلقة while الأمامية الموضحة هنا، قدّم i فقط عندما...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
بعد remove(i) ، ينتقل العنصر التالي إلى موقع i — فلا تتخطّه.
حلقة Aمامية بدائية على [0, 0, 5] تقوم بالحذف عند i=0 ثم تزيدها تتخطى الصفر التالي.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
ينزلق الصفر المتبقي إلى الفهرس 0، لكن الاختبار التالي يكون عند الفهرس 1. تستخدم الحلقة الخلفية قاعدة فهرس صحيحة مختلفة.
بديل للإزالة في المكان يتجنب الإزاحة هو...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
إضافة العناصر المحتفظ بها إلى قائمة فارغة يتجاوز مشكلة الإزاحة.
تعيد خوارزمياتArrayList استخدام أنماط المصفوفة عبر...
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
استبدل مصفوفة [] وlength بـ get(i) وsize() .
طبيعةArrayList القابلة للتوسع تسمح لك بإدراج وحذف العناصر، بعكس المصفوفة الثابتة.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
تغيير add وremove حجم القائمة.
يجب أن تبقى حلقة الإزالة الخلفية التي تبدأ من size()-1 عند نفس الفهرس بعد كل حذف.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
خطأ: العناصر التي لم يتم فحصها سابقاً تحتفظ بفهارسها، لذا تنخفض الحلقة الخلفية بشكل طبيعي.
Build a new list when the original must remain
- To preserve the original list, create a fresh result and append every nonzero element while reading the original. This keeps the original sequence and its size unchanged; it uses additional list storage.
- For lists of mutable objects, copying retained references does not clone those objects. A new list structure may still share its element objects with the original; distinguish list identity from element identity.
الإزالة الأمامية تحافظ على الفهرس التالي بعد الحذف.
يتم التحقق من صفرين متجاورين عند الفهرس 0 قبل الاحتفاظ بـ 5.
Check the cases that expose the algorithm
- Test an empty list, all zeros, no zeros, adjacent zeros and a zero at the last index. For in-place removal, other references to the same list observe its change; a fresh result leaves that original structure intact.
- An ArrayList can insert 插入 or delete 删除 elements; those operations can shift 移位 later indices. A search may return a found index or -1 when absent; a maximum requires an explicit empty-list policy. Reusing array patterns through get/size helps, but each algorithm still needs its own bounds and contract.
Removing shifts indices. Explain which elements remain unchecked and choose the next index accordingly. Forward stay-or-increment and backward decrement are both valid patterns; a fresh list of keepers preserves the original structure but may share objects.
Order the states for the corrected removal loop on [0, 0, 5].
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Each removal rechecks the shifted value; keeping 5 finally advances the index.
كم عدد استدعاءات get التي تقوم بها طريقة removeZeros الأمامية الموضحة على قائمة فارغة؟
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
الشرط الأولي 0 < 0 غير صحيح، لذا لا يحدث أي استدعاء get.