Count Even Numbers
Với danh sách số nguyên không rỗng nums, hãy trả về số lượng giá trị chẵn trong danh sách. Một số là số chẵn khi chia cho 2 mà không dư, bao gồm cả 0 và các số âm như -4.
Hàm
- numsinteger-array
- danh sách số nguyên cần kiểm tra
- Trả vềinteger
- số lượng giá trị chẵn trong nums
Ràng buộc
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Ví dụ
- Đầu vào
- nums = [3, 8, 12, 5, 6]
- Đầu ra
- 3
- Giải thích
8,12và6chia hết cho2;3và5thì không. Đáp án là3.
- Đầu vào
- nums = [-4, -3, 0, 7]
- Đầu ra
- 2
- Giải thích
-4 = 2 × (-2)và0 = 2 × 0, nên cả hai đều là số chẵn.-3và7là số lẻ, và số lượng là2.
- Đầu vào
- nums = [1, 9, 15]
- Đầu ra
- 0
- Giải thích
1,9và15đều là số lẻ, nên đáp án là0.
Câu hỏi mở rộng
Bạn nhận được nhiều câu hỏi: có bao nhiêu giá trị chẵn nằm giữa chỉ số l và chỉ số r? Sau một lượt duyệt qua nums, bạn có thể trả lời mỗi câu hỏi trong thời gian O(1) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Còn lại bao nhiêu khi bạn chia một số chẵn cho
2?Giá trị
xlà số chẵn khi và chỉ khix % 2bằng0. Lưu ý: với số lẻ âm, một số ngôn ngữ cho kết quả phần dư là-1, không phải1.Bắt đầu bộ đếm ở
0, đọc mỗi giá trị một lần và cộng thêm1mỗi khi số dư khi chia cho2bằng0.
Lời giải
Kiểm tra mỗi giá trị một lần và đếm những giá trị có số dư bằng 0 khi chia cho 2. So sánh số dư với 0 thay vì kiểm tra số lẻ bằng 1 giúp xử lý đúng các số âm.
Thu thập các giá trị chẵn, rồi đếm chúng
Ý tưởng
Dùng bộ lọc để chọn các giá trị chẵn, rồi trả về độ dài của kết quả. Với [3, 8, 12, 5, 6], danh sách đã lọc là [8, 12, 6], nên đáp án là 3.
Thời gian chạy là O(n), nhưng danh sách mới tốn O(n) bộ nhớ, chứa tối đa 5000 giá trị, chỉ để đọc độ dài một lần.
Thuật toán
- Tạo một danh sách mới chứa mọi
xtrongnumsthỏa mãnx % 2 == 0. - Trả về độ dài của danh sách đó.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Đếm bằng bộ đếm tăng dần
Ý tưởng
Dùng một bộ đếm thay vì một danh sách, rồi cộng thêm 1 cho mỗi giá trị thỏa mãn x % 2 == 0. Số chẵn luôn có số dư bằng 0, bất kể dấu của nó, nên phép kiểm tra này đúng với cả -4 và 0 trong mọi ngôn ngữ. Phép kiểm tra số lẻ bằng x % 2 == 1 thì không đúng: trong C, Java, JavaScript và hầu hết các ngôn ngữ dạng C, số dư mang dấu của số đó, nên -3 % 2 bằng -1.
Một lượt duyệt và một số nguyên: thời gian O(n), bộ nhớ O(1).
Thuật toán
- Đặt
countthành0. - Lặp qua từng giá trị
xtrongnums. - Nếu
x % 2 == 0, cộng1vàocount. - Sau vòng lặp, trả về
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
Lỗi thường gặp và trường hợp biên
- Đếm các giá trị lẻ bằng
x % 2 == 1rồi lấy độ dài trừ đi số đó. Trong các ngôn ngữ giống C,-3 % 2là-1, nên[-3]trả về 1 thay vì 0. - Coi
0không phải là số chẵn cũng không phải số lẻ.0 = 2 × 0, nên[0]trả về1. - Viết phép kiểm tra bit là
x & 1 == 0. Trong C, C++ và JavaScript,==có độ ưu tiên cao hơn&, nên biểu thức này có nghĩa làx & (1 == 0), luôn cho kết quả0và không đếm được gì. Hãy viết(x & 1) == 0.
Câu hỏi thường gặp3
Làm thế nào để kiểm tra một số có phải là số chẵn trong code?
Kiểm tra xem số dư sau khi chia cho 2 có bằng không hay không: x % 2 == 0. Cách này hoạt động với số dương, số âm và số không, kể cả trong các ngôn ngữ mà -3 % 2 là -1. Bạn cũng có thể kiểm tra bit thấp nhất bằng (x & 1) == 0.
Số không có phải là số chẵn không?
Đúng vậy. Zero chia cho 2 bằng 0, không có số dư, nên thỏa mãn định nghĩa số chẵn. Zero cũng nằm giữa hai số lẻ -1 và 1, nơi có một số chẵn.
Độ phức tạp thời gian của việc đếm số chẵn trong mảng là gì?
Một lượt duyệt với biến đếm mất thời gian O(n) và dùng thêm O(1) bộ nhớ. Bạn phải kiểm tra mọi giá trị, nên không có phương pháp nào nhanh hơn O(n).
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def countEvens(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [3, 8, 12, 5, 6]
Đầu ra mong đợi
3