實現使用遞歸的StringBuilder刪除方法

Question

我想完成一個項目，要求我不使用任何類型的循環，而只使用遞歸。我必須使用LinkedLists而不是數組創建一個StringBuilder類。如果有人能夠幫助我在此方法delete（）中實現遞歸，我將不勝感激。

public MyStringBuilder delete(int start, int end) 
    { 
     if(!(start < 0 || start > length || end <= start)){ 
      CNode currNode = firstC; 
      CNode startNode = currNode; 
      if(start == 0){ 
       for(int i = 1; i < end +1; i++){ 
        currNode = currNode.next; 
        length -= 1; 
       } 
       firstC = currNode; 
      }else if (end > length){ 
       for(int i = 1; i < start; i++){ 
        currNode = currNode.next; 
       } 
       length = start; 
       currNode.next = null; 
       lastC = currNode; 
      } else { 
       for(int i = 0; i < end; i++){ 
        //find starting deletion point 
        if(i == (start - 1)){ 
         startNode = currNode; 
        } 
        currNode = currNode.next; 
       } 
       length = length - (end-start); 
       //actual deletion part 
       startNode.next = currNode; 
      } 
     } 
     return this; 
    } 

非常感謝。

Answer 1

即使您說不應該有任何循環，我仍然無法理解，但您仍然有一些在那裏提到的循環。

我試圖想出使用鏈表的問題的解決方案。我必須在這裏和那裏包含循環。所以，看看...

ListNode.java

public class ListNode<T>{ 
    public T data; 
    public ListNode<T> next; 
    public int nos; 
} 

MyStringBuilder.java

import java.util.*; 
public class MyStringBuilder { 
    ListNode<Character> list = new ListNode<Character>(); 

    public void add(String s){ 
     ListNode<Character> p1 = list; 
     for(int i=0; i<s.length(); i++){ 
      p1.data = s.charAt(i); 
      p1.next = new ListNode<Character>(); 
      p1 = p1.next; 
     } 
     list.nos=s.length(); 

    } 

    public void print(){ 
     ListNode<Character> p1 = list; 

     while(p1.next!=null){ 
      System.out.print(p1.data); 
      p1= p1.next; 
     } 
     System.out.println(); 
    } 

    public void delete(int start, int end){ 
     ListNode<Character> p1 = list; 
     ListNode<Character> p2; 
     ListNode<Character> prev =list; 
     if (start < 0){ 
      throw new IllegalArgumentException("first argument cannot be less than 0"); 
     } 
     if (start > end){ 
      throw new IllegalArgumentException("first argument cannot be greater than second"); 
     } 
     if (end > list.nos){ 
      throw new IllegalArgumentException("second argument cannot be greater than size of string"); 
     } 

     if(start==0){ 
      while(end!=0){ 
       p1=p1.next; 
       end--; 
      } 
      list = p1.next; 
      return; 
     } 

     //iterate over start steps 
     int i=start; 
     while(i!=0){ 
      prev = p1; 
      p1= p1.next; 
      i--; 
     } 

     p2 = p1.next; 

     end = end-start; 
     while(end!=0){ 
      p2 = p2.next; 
      end--; 
     } 
     prev.next = p2; 
    } 
} 

我希望解決方案適用於你。我嘗試了下面的示例來檢查它是否工作。我在main()

 MyStringBuilder abc = new MyStringBuilder(); 
     abc.add("apocalypto"); 

     abc.delete(2, 6); 
     abc.print(); 

寫這些代碼我得到了這樣的回答：appto

Answer 2

爲了實現這個使用遞歸，你必須做兩件事情：定義一個基本情況，並找出如何從去一個遞歸調用另一個。我不會寫出代碼，但這裏有一個大概的想法：

首先，我們來看看刪除方法的作用。它從刪除一個包括b排他性。因此，一個好的基本案例是我們到達我們的b並且我們停止刪除。

現在，從一個步驟到另一個步驟，我們可以簡單地刪除我們所在的節點，並遞歸調用我們的下一個節點的函數。

但是，執行邏輯時要小心;處理此問題的最佳方法是跟蹤要刪除多少個節點並將其用作基本情況。原因是刪除會在您瀏覽時修改列表，並且您需要跟蹤要刪除多少個節點，直到您點擊b。

如果你只是牢記這一般的指導方針，代碼應該有點自己寫。隨意問任何問題！