Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm bước nhảy tối thiểu cần thiết để quay trở lại từ một thư mục về nhà bằng Python

Giả sử chúng ta có một nhật ký mà chúng ta có đường dẫn để nhập vào các thư mục, có thể có các ký hiệu khác nhau như -

  • "../":Di chuyển đến thư mục mẹ từ thư mục hiện tại. (Nếu chúng tôi đang ở thư mục chính, không thay đổi vị trí).

  • "./":Vẫn còn trong thư mục hiện tại.

  • "x /":Di chuyển đến thư mục con có tên x.

Từ nhật ký, chúng tôi phải tìm số lượng thao tác tối thiểu cần thiết để quay lại thư mục cuối cùng nơi chúng tôi dừng lại đến thư mục chính.

Vì vậy, nếu đầu vào giống như logs =["Dir1 /", "Dir2 /","../", "Dir2 /", "Dir3 /","./"], thì đầu ra sẽ là 3

Chương trình tìm bước nhảy tối thiểu cần thiết để quay trở lại từ một thư mục về nhà bằng Python

từ hình ảnh có thể thấy, chúng tôi phải lùi lại ba lần để về đến nhà.

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

  • stk:=một danh sách mới

  • đối với mỗi mục tôi trong nhật ký, hãy thực hiện

    • nếu tôi giống với "../" và kích thước của stk> 0, thì

      • xóa phần tử cuối cùng khỏi stk

    • ngược lại khi tôi không giống với "./" và tôi không giống với "../" thì

      • chèn tôi vào cuối stk

    • nếu không,

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

  • trả lại số mặt hàng trong stk

Ví dụ (Python)

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

def solve(logs):
   stk = []
   for i in logs:
      if i == "../" and len(stk) > 0:
         stk.pop()
      elif i != "./" and i != "../":
         stk.append(i)
      else:
         continue
   return len(stk)

logs = ["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]
print(solve(logs))

Đầu vào 

["Dir1/","Dir2/","../","Dir2/","Dir3/","./"]

Đầu ra 

3