Chương trình tìm số lượng danh sách con chứa tối đa và tối thiểu sau khi xóa chỉ một phần tử trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và chúng ta có thể xóa nhiều nhất một phần tử trong danh sách. Chúng tôi phải tìm số lượng danh sách con tối đa chứa cả giá trị lớn nhất và nhỏ nhất của danh sách kết quả.

Vì vậy, nếu đầu vào là nums =[3, 2, 6, 2, 4, 10], thì đầu ra sẽ là 8, như nếu chúng ta loại bỏ 10, chúng ta sẽ nhận được [3, 2, 6, 2, 4] và có tám danh sách con trong đó nó chứa cả giá trị lớn nhất và giá trị tối thiểu -

• [2, 6]

• [6, 2]

• [2, 6, 2]

• [3, 2, 6]

• [6, 2, 4]

• [2, 6, 2, 4]

• [3, 2, 6, 2]

• [3, 2, 6, 2, 4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một kiểm tra hàm (). Điều này sẽ mất khoảng

• mn:=tối thiểu lst, mx:=tối đa lst

• min_pos:=null, max_pos:=null

• ret:=0

• cho mỗi chỉ số i và giá trị num trong lst, thực hiện

  • nếu num giống với mn, thì

    • min_pos:=i

  • nếu num giống với mx thì

    • max_pos:=i

  • nếu min_pos là null hoặc max_pos là null thì

    • chuyển sang lần lặp tiếp theo

  • ret:=ret + tối thiểu min_pos và (max_pos + 1)

• trả lại ret

• Từ phương thức chính, hãy làm như sau -

• nếu kích thước của nums <=1, thì

  • trả về kích thước của nums

• ret:=check (nums)

• cho mỗi rem_cand trong [tối thiểu nums, tối đa nums], thực hiện

  • nếu sự xuất hiện của rem_cand là 1, thì

    • idx:=index of rem_cand in nums

    • ret:=tối đa ret và kiểm tra (nums [từ index 0 đến idx - 1] nối nums [từ index idx + 1 đến end]

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

class Solution:
   def solve(self, nums):
      if len(nums) <= 1:
         return len(nums)
      def check(lst):
         mn, mx = min(lst), max(lst)
         min_pos, max_pos = None, None
         ret = 0
         for i, num in enumerate(lst):
            if num == mn:
               min_pos = i
            if num == mx:
               max_pos = i
            if min_pos is None or max_pos is None:
               continue
            ret += min(min_pos, max_pos) + 1
         return ret
      ret = check(nums)
      for rem_cand in [min(nums), max(nums)]:
         if nums.count(rem_cand) == 1:
            idx = nums.index(rem_cand)
            ret = max(ret, check(nums[:idx] + nums[idx + 1 :]))
      return ret
ob = Solution()
nums = [3, 2, 6, 2, 4, 10]
print(ob.solve(nums))

Đầu vào

[3, 2, 6, 2, 4, 10]

Đầu ra

8