Tìm số có số chữ số chẵn - leetcode Giải pháp Python

Trong bài đăng này, chúng tôi sẽ giải Tìm số có số chữ số chẵn từ leetcode và tính toán độ phức tạp về thời gian và không gian của nó. Hãy bắt đầu nào

Câu hỏi có thể được tìm thấy tại leetcode Bài toán tìm số có số chữ số chẵn

Vấn đề nói rằng chúng ta được cung cấp một dãy số và chúng ta cần trả về số lượng các số có số chữ số chẵn

Cách tiếp cận vấn đề này rất đơn giản. Chúng tôi lặp lại mảng và đối với mỗi số, chúng tôi đếm số chữ số trong số và kiểm tra xem nó có chẵn không

Để có được tất cả các chữ số trong số, chúng ta có thể lấy mô đun của số đó bằng 10 và điều đó sẽ cho chúng ta chữ số cuối cùng. Tiếp theo, chúng tôi chia số cho 10 và nó cho số mới không có chữ số cuối cùng và chúng tôi lặp lại quy trình cho đến khi số đó là

Status: Accepted
Runtime: 68ms
Memory: 36.5MB

Chúng tôi đã thảo luận về cách tiếp cận, tôi khuyên bạn nên tiếp tục sử dụng leetcode và thử lại lần nữa.

Trong bài viết này, chúng ta sẽ giải Bài toán Leetcode -1295 “Tìm số có số chữ số chẵn” và sau đó chúng ta sẽ tính toán độ phức tạp về thời gian và không gian của nó

Vì vậy, hãy bắt đầu ngay bây giờ-

Báo cáo vấn đề- Cho một mảng

Status: Accepted
Runtime: 68ms
Memory: 36.5MB

Giải thích về Báo cáo sự cố- Một mảng có tên nums sẽ được cung cấp và chúng ta cần tìm số đếm của tất cả các số có các chữ số riêng lẻ của chúng được tính là số chẵn

Định dạng đầu vào- Danh sách kích thước n

Định dạng đầu ra- Một số nguyên duy nhất cho biết số lượng có số chữ số chẵn

Hãy hiểu với các ví dụ-

ví dụ 1

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits [even number of digits]. 
345 contains 3 digits [odd number of digits]. 
2 contains 1 digit [odd number of digits]. 
6 contains 1 digit [odd number of digits]. 
7896 contains 4 digits [even number of digits]. 
Therefore only 12 and 7896 contain an even number of digits.

ví dụ 2

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Hạn chế

• Status: Accepted
  Runtime: 68ms
  Memory: 36.5MB

  7

• Status: Accepted
  Runtime: 68ms
  Memory: 36.5MB

  8

Giải pháp- Vấn đề là một vấn đề dễ dàng và giải pháp cho vấn đề này rất đơn giản. Có thể có hai cách tiếp cận để giải quyết vấn đề này và chúng ta sẽ thảo luận về cả hai cách tiếp cận ở đây

Cách tiếp cận 1- Cách tiếp cận này bao gồm các bước sau

Bước 1- Duy trì bộ đếm [giả sử c=0]

Bước 2- Lặp lại danh sách và đánh máy từng số [ở đây là các phần tử của danh sách] thành chuỗi và lưu chuỗi vào một biến

Bước 3- Kiểm tra xem độ dài của chuỗi có chẵn không. e. nếu chia hết cho 2

Bước 4- Nếu bước 2 giữ True, hãy tăng giá trị bộ đếm lên 1

Bước 5- Trả về bộ đếm c

Giải pháp Python sử dụng Phương pháp tiếp cận 1-

class Solution:
    def findNumbers[self, nums: List[int]] -> int:
        c=0
        for i in nums:
            j=str[i]
            x=len[j]
            if x%2==0:
                c=c+1
        return c

Cách tiếp cận 2- Cách tiếp cận này bao gồm các bước sau

Bước 1- Duy trì bộ đếm [giả sử c=0]

Bước 2- Lặp lại danh sách và lưu từng số vào một biến [giả sử D]

Bước 3- Lặp trong khi D>0

Bước 4- Chia đi chia lại một số cho 10 để được số chữ số

Bước 5- Đếm số chữ số và lưu trữ số chữ số trong một biến [giả sử chữ số]

Bước 6- Kiểm tra xem chữ số có chẵn không

Bước 7- Nếu bước 6 giữ đúng, tăng giá trị c của bộ đếm lên 1

Bước 8- Quay lại c

Giải pháp Python sử dụng Phương pháp tiếp cận 2-

Bây giờ hãy thảo luận về sự phức tạp của thời gian và không gian-

Thời gian phức tạp. O[N * logD] — Phép lặp trên mảng là O[N] trong đó n là kích thước của mảng và với mỗi số, chúng tôi đang tính số chữ số trong đó. Vì chúng tôi đang lặp qua từng chữ số, nên nó cũng làm tăng thêm độ phức tạp về thời gian. Có gần như log chữ số D trong một số D. Vì vậy, Phép lặp mảng + phép lặp qua mỗi phép cộng lên đến độ phức tạp thời gian O[N * log D]

Độ phức tạp không gian. O[1] — Vì không có không gian phụ liên quan đến thuật toán trên, nên độ phức tạp của không gian trở thành O[1]

Vì vậy, ở đây chúng ta đã thấy cách Tìm số có số chữ số chẵn cũng như độ phức tạp về thời gian và không gian tương ứng

Mã này có sẵn trong repo GitHub của tôi, bạn có thể lấy nó tại đây

Đó là tất cả. Cảm ơn bạn đã đọc

Tôi đã cố gắng hết sức để giải thích vấn đề. Nếu bạn có bất kỳ thắc mắc hoặc nghi ngờ nào, bạn có thể liên hệ với tôi tại Linkedin hoặc Instagram