Trả lời đệ quy một mảng các vị trí mà tôi xảy ra trong j

Question

Tôi không giỏi Java nên tôi chỉ muốn nói trước "ĐÂY LÀ HOMEWORK CỦA TÔI" và làm ơn "KHÔNG LÀM HOMEWORK", đây là lần đầu tiên bài tập về nhà trên đệ quy vì vậy đây là lần đầu tiên của tôi. Có nói rằng, đây là những hướng dẫn của bài tập về nhà của tôi nhưng tôi không chắc chắn các bước mà tôi cần phải thực hiện để đạt được mục tiêu. Tất cả những gì tôi cần là một chàng trai/cô gái tuyệt vời có thể cho tôi biết chi tiết về cách hoàn thành bài tập về nhà của tôi, loại bước. Tôi đã đọc cuốn sách, kiểm tra một số trang web về đệ quy, nhưng tôi cảm thấy rằng tôi cần thêm một chút trợ giúp.

Viết phương pháp tĩnh đệ qui, được cho hai chuỗi s và t, trả về một mảng của tất cả các vị trí mà t xảy ra trong s. Ví dụ: findLocations ("Frances chạy và chạy", "chạy") trả về [1, 8, 16].

Answer 1

tôi có lẽ sẽ tiếp cận nó như thế này:

1. Với argumets inputString và substring, gọi index = inputString.indexOf(substring).

2. Nếu substring được không tìm thấy (index = -1), bạn nên trả lại mảng rỗng (new int[0]), vì không có sự xuất hiện của các chuỗi con tồn tại trong inputString.

3. Nếu không substringkhông tồn tại, trong trường hợp này bạn nên làm như sau:

   1. Lấy loạt các chỉ số cho các phần còn lại của chuỗi, sử dụng một cái gì đó giống như arr = findLocations(inputString.substring(index+1), substring)

   2. Điều chỉnh các chỉ mục trong arr bằng cách thêm index vào từng phần tử.

   3. trả lại index, được ghép với arr.

Answer 2

Cách đệ quy hoạt động là nó thường được thực hiện với một phương pháp kiểm soát, và sau đó là một phương pháp hành động. Phương thức điều khiển giữ cuộc gọi đệ quy (gọi là đệ quy đuôi). Sử dụng đệ quy đuôi để giải quyết vấn đề này rất có thể sẽ liên quan đến một cửa sổ trượt. Trang web này có một số thông tin tốt về đệ quy trong Java: http://www.danzig.us/java_class/recursion.html

Lưu ý: Xin lỗi, nhưng bằng cách viết một số psuedo tôi đã đến để sản xuất mã này. Tôi thực sự thích đệ quy. Tôi rời nó ở đây sloppily để nếu bạn muốn nhìn thấy nó có lẽ là một tấm séc sau đó bạn có thể định dạng nó

findLocations ArrayList công cộng (string mục tiêu, chuỗi cửa sổ) { địa điểm ArrayList = new ArrayList(); trả lại (recurseLocations (mục tiêu, cửa sổ, 0, vị trí)); }
công khai ArrayList recurseLocations (chuỗi mục tiêu, chuỗi cửa sổ, int offset, ArrayList địa điểm) { nếu (window.length + offset < target.chiều dài) địa điểm trả lại; bool hit = true; cho (int i = 0; i < window.length; i ++) if (target.charAt (i + offset)! = Window.charAt (i)) hit = false; if (hit) locations.add (offset); recurseLocations (mục tiêu, cửa sổ, (offset + 1), vị trí); }

Answer 3

Khi bạn sẽ đệ quy thông qua chuỗi đầu tiên và chủ động thêm chỉ mục, tôi khuyên bạn nên sử dụng điều gì đó có thể thay đổi, chẳng hạn như Danh sách.

Đối với phương pháp đệ quy của bạn, sau đây là một số lời khuyên:

// Initialize results list first 
// Start the search using index = 0 and your empty results list. 
ArrayList<Integer> recurSearch(String input, String search, int index, ArrayList<Integer> results) 

// Inside recurSearch() 
int index = inputString.indexOf(search string, index); 
// Here check the index. If it equals -1, no more matches. Return your result List. 
// If does not equal -1, add to result list and return findLocations() using index + 1. 

Tôi hy vọng điều này có ý nghĩa. Vì bạn rõ ràng muốn tự mình giải quyết hầu hết vấn đề này, tôi đã cố gắng bao gồm ít mã nhất có thể. Tôi bao gồm chữ ký phương pháp của tôi vì tôi hy vọng điều này sẽ chỉ cho bạn đi đúng hướng.