Java的算法

Question

我有下類：（單鏈表）

public class class CharNode { 
    private char _value; 
    private CharNode _next; 

    public CharNode(char val, CharNode n) { 
     _value = val; 
     _next = n; 
    } 

    public CharNode(char val) { 
     _value = val; 
     _next = null; 
    } 

    public int getValue() { 
     return _value; 
    } 

    public CharNode getNext() { 
     return _next; 
    } 

    public void setValue(char v) { 
     _value = v; 
    } 

    public void setNext(CharNode node) { 
     _next = node; 
    } 
} 

這個類：

public class CharList { 
private CharNode _head; 

public CharList() 
{ 
    _head = null; 
} 
//methods 
} 

我需要寫一個方法（叫「什麼」），其獲取兩個字符並返回以這些字符開始和結束的可能列表數量。 例如，如果鏈表「ABBCD」的方法是什麼（A，B）將返回2，什麼（A，C）將返回1的方法，我看到了一個解決方案：

public int what(char start, char end) 
{ 
    int count = 0, countStart = 0; 
    CharNode temp = _head; 

    while(temp != null) 
    { 
     if(temp.getValue() == start){ 
      countStart++; 
      temp = temp.getNext(); 
      if(temp.getValue() == start && start == end) 
       countStart++; 
     } 

     if(temp.getValue() == end && countStart>0){ 
      count += countStart; 
     } 

     temp = temp.getNext(); 
    } 

    return count; 
} 

但問題是我無法理解他們如何獲得算法。換句話說，它是如何工作的「數學」？

Answer 1

自己張貼的答案算法：

每次找到的起始符，你增加你「多少啓動」發現櫃檯上。

然後，每當您找到'結束'字符時，您就知道必須添加當前計數器的字數，對應於此'結束'字符之前找到的'開始'字符的編號。

例子：

此字符串： 'ABABAB'

• 第一個 'B' 將給我們一個字，因爲他只有1 '一' 之前
• 的第二'b'會給我們2個單詞，因爲他有2'a'之前
• 第三個'b'會給我們3個單詞，因爲他有3個'a'之前
次

Answer 2

對於給定的這種方法的搜索通過使開始和端字符緊跟在List 2個字符。

public int what(char start, char end) 

計數變量是計算對字符的（開始&結束字符）的發生和重複的總數。因此，如果我們在abcabc中查找ab，則計數將增加兩次，因爲它發現兩次對ab。

int count = 0, 

並計算以防一個發生也可能通過兩種測試它們開始&結束字符被發現，隨後對方，我們使用：

countStart = 0; 

程序從列表頭開始，繼續搜索直到沒有下一個節點！這意味着temp.getNext()將返回null！

CharNode temp = _head; 
while(temp != null) 
    ..................... 
    CharNode temp = _head; 

現在對於每個當前值，如果它是開始字符，繼續並開始計數。否則，在所有情況下 - 只要有一個節點 - 獲取下一個節點temp = temp.getNext();

檢查，然後爲下一個節點，並將其分配給臨時，如果它的電流值（下一個節點的當前值）等於開始CHAR和開始字符類似於符合用戶請求的結束字符=例如：在abcaad中搜索aa，同時增加startCounter以公佈查找結果並將其包含在最終結果中。

if(temp.getValue() == start && start == end) 
    countStart++; 
} 

現在，我們仍然在下一節點，所以它的價值應該等於結束字符的開始和結束字符是否相似或不。但是爲了在結束char之前包括start char的出現，我們需要檢查大於零的countStart，這意味着上一個開始char已經被找到。 如果是這樣，請將一個事件添加到總數並增加總計數。

if(temp.getValue() == end && countStart>0){ 
     count += countStart; 
} 

在年底返回總數

return count; 

Answer 3

好吧，讓我們來看看代碼的各個部分。

int count = 0, countStart = 0; 
CharNode temp = _head; 

上面的代碼只是簡單的初始化。

while(temp != null) 
{ 
// .... 
    temp = temp.getNext(); 
} 

上面的代碼循環遍歷你的列表。

if(temp.getValue() == start){ 
     countStart++; 

上面的代碼記錄到目前爲止有多少可能的起始位置。

if(temp.getValue() == end && countStart>0){ 
     count += countStart; 
    } 

上面的代碼說，當有一個結束字符時，計數會增加到目前爲止的起始字符數。 （檢查countStart>0實際上是否不必要，因爲如果它是0，你只需加0，但它不會傷害任何東西。）這是有道理的 - 如果你有aaa，那麼b在那一點上會增加3種可能性。

 temp = temp.getNext(); 
     if(temp.getValue() == start && start == end) 
      countStart++; 

上面的代碼似乎是一個企圖說明開始和結束字符相同的特殊情況。我不相信這部分代碼是正確的 - 坦率地說，我認爲它會在開始和結束不同的情況下通過使用getNext()輪流引入錯誤。

Answer 4

正如我在評論中所述，它們的實現對我來說有點奇怪。希望我的意識更強。

這個想法是簡單地遍歷，直到找到一個有效的開始字符，然後計算所有有效的結束點。直到您到達列表末尾爲止。

public int what(char start, char end) 
{ 
    int count = 0; 
    CharNode currentNode = _head; 

    while(currentNode != null) 
    { 
     if(currentNode.getValue() == start) 
     { 
      CharNode potentialEnd = currentNode.getNext(); 

      while (potentialEnd != null) 
      { 
       if(potentialEnd.getValue() == end) count++; 

       potentialEnd = potentialEnd.getNext(); 
      } 
     } 
     currentNode = currentNode.getNext(); 
    } 

    return count; 
} 

Here's a runnable example。