时间戳

首页 > 解决方案 > 如何递归地查找链表中倒数第二个 Char 出现？

java - 如何递归地查找链表中倒数第二个 Char 出现？

问题描述

作为一项家庭作业，我想返回一个字母倒数第二个出现的位置——以知道要检查的字母是作为 Char 类型参数传递的。我正在搜索的是一个自编码的链表。它还必须以递归方式完成，我一直在努力完全理解。这是我到目前为止所做的。

注意：如果一个字母出现 0 次或 1 次，则返回 -1。

例如 ["ababcdefb"].positionOfSecondToLastOccurrence('b') == 3

static class Node {
        public Node (char item, Node next) { this.item = item; this.next = next; }
        public char item;
        public Node next;
    }

Node first;

public int positionOfSecondToLastOccurrence (char letter) {

        if (first == null)
            return -1;

        return positionOfSecondToLastOccurrenceHelper(letter, first, 0);
    }

private int positionOfSecondToLastOccurrenceHelper(char c, Node n, int pos) {

        if (n.next == null)
            return n.item;

        return pos += compare(n.item, positionHelper(c, n.next, pos));

    }

private int compare(char c, int p) {

        int result = 0;

        if (c == p)
            return result += 1;

        return 0;
    }

我明白为什么这不起作用；我返回 1 的结果，然后在返回上一个函数调用时将其与 n.item 进行比较，这永远不会是真的。我不知道如何使这项工作。任何指导都会很棒。

标签： javarecursionsingly-linked-list

解决方案

我会以更小的步骤来做这件事。我会先写一个positionOfLastOccurrence(char letter). 将其编写为递归方法应该会教给您一些您也需要的技术positionOfSecondToLastOccurrence()。

接下来的大部分挑战是帮助方法或方法的良好设计。我认为我会写一个positionOfLastOccurrenceBeforePosition(int pos, char letter)应该letter严格在 position 之前返回最后一次出现的位置pos。因此，给定您的示例列表，ababcdefb将positionOfLastOccurrenceBeforePosition(0, 'b')返回 -1，positionOfLastOccurrenceBeforePosition(2, 'b')将产生 1 并positionOfLastOccurrenceBeforePosition(100, 'b')给出 8。我相信，这种方法也应该是递归的，因为这将最终完成实际工作。

现在找到倒数第二个是首先找到最后一个事件，然后找到最后一个事件之前的最后一个事件。

推荐阅读