Count Even Numbers
لديك قائمة غير فارغة من الأعداد الصحيحة nums. أعد عدد القيم الزوجية فيها. يكون العدد زوجيًا عندما لا يترك قسمته على 2 أي باقٍ، ويشمل ذلك 0 والأعداد السالبة مثل -4.
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة المطلوب التحقق منها
- تُرجعinteger
- عدد القيم الزوجية في nums
القيود
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
أمثلة
- المدخلات
- nums = [3, 8, 12, 5, 6]
- المخرجات
- 3
- الشرح
- تقبل
8و12و6القسمة على2دون باقٍ، بينما يتبقى باقٍ عند قسمة3و5. وهذا يعني أن هناك3قيم زوجية.
- المدخلات
- nums = [-4, -3, 0, 7]
- المخرجات
- 2
- الشرح
-4 = 2 × (-2)و0 = 2 × 0، لذا فكلاهما زوجي.-3و7فرديان، والعدد هو2.
- المدخلات
- nums = [1, 9, 15]
- المخرجات
- 0
- الشرح
1و9و15كلها أعداد فردية، لذا لا تُحتسب أي قيمة وتكون الإجابة0.
+12 اختبارات مخفية عند الإرسال
سؤال إضافي
تصلك أسئلة كثيرة من الشكل التالي: كم عدد القيم الزوجية الواقعة بين الفهرس l والفهرس r؟ بعد المرور مرة واحدة على nums، هل يمكنك الإجابة عن كل سؤال في زمن O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ما المتبقي عند قسمة عدد زوجي على
2؟تكون القيمة
xزوجية إذا وفقط إذا كانتx % 2تساوي0. انتبه: بالنسبة إلى عدد فردي سالب، تُعطي بعض اللغات-1كباقٍ، وليس1.ابدأ عدّادًا عند
0، واقرأ كل قيمة مرة واحدة، وأضف1كلما كان باقي القسمة على2هو0.
الحل
الحلقة سطر واحد؛ واختبار الزوجية هو ما تتعثر عنده الحلول. في كثير من اللغات، يكون باقي قسمة عدد سالب سالبًا، لذا فإن -3 % 2 تساوي -1. اختبار x % 2 == 0 صحيح لأي إشارة في جميع اللغات، ولا يحتاج العداد الجاري إلى ذاكرة إضافية.
اجمع القيم الزوجية، ثم احسب عددها
الفكرة
قسّم المهمة إلى خطوتين: اختر القيم الزوجية، ثم عُدّ ما اخترته. تكون القيمة x زوجية عندما x % 2 == 0. تحتوي معظم اللغات على دالة تصفية تُنشئ القائمة الجديدة في سطر واحد، ويكون طولها هو الإجابة. بالنسبة إلى [3, 8, 12, 5, 6]، تكون القائمة بعد التصفية [8, 12, 6]، لذا تكون الإجابة 3.
هذا صحيح وسهل القراءة، لكن القائمة الجديدة تستهلك ذاكرة بمقدار O(n)، تصل هنا إلى 5000 قيمة، لمجرد قراءة طولها مرة واحدة. لن تُستخدم القيم نفسها مرة أخرى.
الخوارزمية
- أنشئ قائمة جديدة تحتوي على كل
xفيnumsبحيث يكونx % 2 == 0. - أعِد طول تلك القائمة.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)العدّ باستخدام عدّاد متزايد
الفكرة
احتفظ بعدّاد بدلًا من قائمة. ابدأه عند 0، وافحص كل قيمة مرة واحدة، وأضف 1 عندما تكون القيمة زوجية. تُفحص كل قيمة مرة واحدة بالضبط، لذا يكون العدد دقيقًا، والذاكرة الوحيدة المستخدمة هي عدد صحيح واحد.
يتطلب الاختبار عناية. في C وC++ وJava وC# وJavaScript وGo وRust وSwift وPHP، تأخذ باقي القسمة إشارة العدد، لذا فإن -3 % 2 تساوي -1، وليس 1. العدد الزوجي يعطي باقيًا 0 مهما كانت إشارته، لذا فإن x % 2 == 0 صحيحة دائمًا، بينما اختبار الفردية المكتوب على صورة x % 2 == 1 لا يكتشف أي عدد فردي سالب. بالنسبة إلى [-4, -3, 0, 7]، تكون البواقي 0 و-1 و0 و1، لذا ينتهي العدّاد عند 2.
يُحتسب الصفر أيضًا: 0 % 2 تساوي 0، لذا فإن 0 زوجي.
الخوارزمية
- عيّن
countإلى0. - كرّر على كل قيمة
xفيnums. - إذا كان
x % 2 == 0، فأضف1إلىcount. - بعد الحلقة، أعد
count.
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
أخطاء شائعة وحالات حدّية
تأتي الأخطاء هنا من الأعداد السالبة ومن الصفر.
- عدّ القيم الفردية باستخدام
x % 2 == 1ثم طرحها من الطول. في اللغات الشبيهة بـ C، تكون نتيجة-3 % 2هي-1، لذا لا يُحتسب-3عددًا فرديًا أبدًا، وينتهي الأمر باحتسابه عددًا زوجيًا. - اعتبار
0لا زوجيًا ولا فرديًا.0 = 2 × 0، لذا فهو زوجي، وتُرجع[0]القيمة1. - كتابة اختبار البتات بالشكل
x & 1 == 0. في C وC++ وJavaScript، تكون أولوية==أعلى من أولوية&، لذا يعني ذلكx & (1 == 0)، وتكون نتيجته دائمًا0، فلا يُحتسب أي شيء. اكتب(x & 1) == 0. - بدء الحلقة عند الفهرس
1في لغة تبدأ الفهرسة فيها من0، ما يؤدي إلى تخطي القيمة الأولى، أو عند0في Lua وR، حيث تكون القيمة الأولى عند الفهرس1.
أسئلة شائعة4
كيف تتحقق برمجيًا مما إذا كان العدد زوجيًا؟
اختبر ما إذا كان باقي القسمة على 2 يساوي صفرًا: x % 2 == 0. تنجح هذه الطريقة مع الأعداد الموجبة والسالبة والصفر في كل لغة برمجة شائعة. وهناك طريقة أخرى، وهي التحقق من البت الأقل أهمية باستخدام (x & 1) == 0، لأن الأعداد الزوجية تنتهي ببت قيمته 0.
هل الصفر عدد زوجي؟
نعم. صفر مقسومًا على 2 يساوي 0 دون باقٍ، لذا فهو يطابق تعريف العدد الزوجي. كما أنه يقع بين العددين الفرديين -1 و1، في المكان الذي ينتمي إليه العدد الزوجي تمامًا.
لماذا يفشل x % 2 == 1 مع الأعداد السالبة؟
في C وC++ وJava وC# وJavaScript وGo وRust وSwift وPHP، تأخذ باقي القسمة إشارة العدد المقسوم، لذا فإن -3 % 2 تساوي -1. أما Python وRuby وDart وLua وR فتعيد 1 بدلًا من ذلك. واختبار x % 2 != 0 للفردي وx % 2 == 0 للزوجي يعطي النتيجة نفسها في جميع هذه اللغات.
ما هو التعقيد الزمني لعدّ الأعداد الزوجية في مصفوفة؟
يستغرق المرور مرة واحدة باستخدام عدّاد زمنًا قدره O(n) ومساحة إضافية قدرها O(1). يجب التحقق من كل قيمة، لذا لا توجد طريقة أسرع من O(n). يؤدي إنشاء قائمة مُصفّاة أولًا إلى الحصول على العدد نفسه، لكنه يستخدم ذاكرة إضافية قدرها O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def countEvens(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [3, 8, 12, 5, 6]
المتوقع
3