如何使用递归找到出现次数最多的首字母?

Question

给定一个句子，该句子分布在一个链表中，链表中的每一项都是一个单词，例如:

Hello -> Everybody -> How -> Are -> You -> Feeling -> |

给定该列表已排序，例如:

Are -> Everybody -> Feeling -> Hello -> How -> You -> |

你如何写递归来找到在句子中出现最多的首字母(在这个例子中，字母H来自Hello &如何)?

Answer 1

Edit:我已将代码更新为递归版本。

为了运行它，你调用

GetMostLetterRecursion(rootNode , '0', 0, '0', 0)

代码本身是这样的:

public char GetMostLetterRecursion(LinkedListNode<String> node, char currentChar, int currentCount, char maxChar, int maxCount)
{
    if (node == null) return maxChar;
    char c = node.Value[0];
    if (c == currentChar)
    {
        return GetMostLetterRecursion(node.Next, currentChar, currentCount++, maxChar, maxCount);
    }
    if(currentCount > maxCount)
    {
        return GetMostLetterRecursion(node.Next, c, 1, currentChar, currentCount);
    }
    return GetMostLetterRecursion(node.Next, c, 1, maxChar, maxCount);
}

Answer 2

解决方案1

遍历单词，记录以每个字母开头的单词的数量。根据计数返回最流行的字母(如果使用优先级队列进行计数，则很容易)。

这需要O(n)个时间(单词数)和O(26)个内存(字母表中的字母数)。

解决方案2

按字母顺序排序。循环遍历单词。记录下当前收到的信件及其出现的频率，以及迄今为止最受欢迎的信件及其出现的频率。在循环的最后，这是整个列表中最受欢迎的字母。

这需要O(n log n)时间和O(1)内存

Answer 3

保存一个数组来存储出现次数的计数，并遍历链表一次来计数。最后循环遍历数组，找到最高的那个。

C文字草图:

int count[26]={0};
While ( head->next != NULL)
{
  count[head->word[0] - 'A']++; // Assuming 'word' is string in each node
  head = head->next;
}
max = count[0];
for (i=0;i<26;i++)
{
  if(max<a[i])
    max = a[i];
}

您可以修改它以使用递归并处理小写字母。

Answer 4

这是一个纯递归的Python实现。我还没有测试它，但它应该工作模输入错误或语法错误。我使用Dictionary来存储计数，因此它也可以处理Unicode单词。这个问题被分成两个函数:一个计算每个字母出现的次数，另一个递归地找到最大的。

# returns a dictionary where dict[letter] contains the count of letter
def count_first_letters(words):
    def count_first_letters_rec(words, count_so_far):
        if len(words) == 0:
            return count_so_far
        first_letter = words[0][0]
        # could use defaultdict but this is an exercise :)
        try:
            count_so_far[first_letter] += 1
        except KeyError:
            count_so_far[first_letter] = 1
        # recursive call
        return count_first_letters_rec(words[1:], count_so_far)
    return count_first_letters(words, {})

# takes a list of (item, count) pairs and returns the item with largest count.
def argmax(item_count_pairs):
    def argmax_rec(item_count_pairs, max_so_far, argmax_so_far):
        if len(item_count_pairs) == 0:
            return argmax_so_far
        item, count = item_count_pairs[0]
        if count > max_so_far:
            max_so_far = count
            argmax_so_far = item
        # recursive call
        return argmax_rec(item_count_pairs[1:], max_so_far, argmax_so_far)
    return argmax_rec(item_count_pairs, 0, None)

def most_common_first_letter(words);
    counts = count_first_letters(words)
    # this returns a dictionary, but we need to convert to
    # a list of (key, value) tuples because recursively iterating
    # over a dictionary is not so easy
    kvpairs = counts.items()
    # counts.iteritems() for Python 2
    return argmax(kvpairs)

Answer 5

我有一个长度为26的数组(作为英文字母，因此索引1用于'a'，索引2用于'b'，以此类推)。． 每出现一个字母，我就增加它在数组中的值。如果该值大于最大值，则更新最大值并将该字母作为出现次数最多的字母。然后调用下一个节点的方法。

这是Java中的代码:

import java.util.LinkedList;

public class MostOccurance {
    char mostOccured;
    int maxOccurance;
    LinkedList<String> list= new LinkedList<String>();
    int[] letters= new int[26];

 public void start(){
     findMostOccuredChar( 0, '0', 0);
 }
 public char findMostOccuredChar ( int node, char most, int max){
     if(node>=list.size())
         return most;
     String string=list.get(node);
     if (string.charAt(0)== most)
         {max++;
         letters[Character.getNumericValue(most)-10]++; 
         }
     else{
         letters[Character.getNumericValue(most)-10]++;
         if (letters[Character.getNumericValue(most)-10]++>max){
             max=letters[Character.getNumericValue(most)-10];
             most=string.charAt(0);
         }
     }
     findMostOccuredChar( node++, most, max);
     return most;
      }

  }

当然，你必须将每个单词添加到你的链接列表中。我没有那样做，因为我只是在展示一个例子。