Chương trình tìm số lượng danh sách con mà chúng ta có thể phân vùng để danh sách đã cho được sắp xếp cuối cùng trong python

Giả sử chúng ta có một danh sách các số được gọi là nums. Chúng ta có thể phân vùng danh sách thành một số danh sách con riêng lẻ sau đó sắp xếp từng phần. Chúng tôi phải tìm số lượng danh sách con tối đa mà chúng tôi có thể phân vùng sao cho tổng thể các số được sắp xếp sau đó.

Vì vậy, nếu đầu vào là nums =[4, 3, 2, 1, 7, 5], thì đầu ra sẽ là 2, vì chúng ta có thể sắp xếp các danh sách con như [4, 3, 2, 1] và [7, 5]

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

• số lượng:=0
• main_sum:=0, sorted_sum:=0
• đối với mỗi phần tử x từ nums và y từ dạng nums được sắp xếp, hãy thực hiện
  • main_sum:=main_sum + x
  • sorted_sum:=sorted_sum + y
  • nếu main_sum giống với sorted_sum, thì
    • count:=count + 1
• số lượng trả lại

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

Ví dụ

class Solution:
   def solve(self, nums):
      count = 0
      main_sum = sorted_sum = 0

      for x, y in zip(nums, sorted(nums)):
         main_sum += x
         sorted_sum += y
         if main_sum == sorted_sum:
            count += 1

      return count

ob = Solution()
nums = [4, 3, 2, 1, 7, 5]
print(ob.solve(nums))

Đầu vào

[4, 3, 2, 1, 7, 5]

Đầu ra

2