作为一项家庭作业，我假设返回字母倒数第二个出现的位置——以了解要检查的字母是作为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进行比较，这永远不会是真的。我不知道的是如何做到这一点。任何指导都会很棒。
您使用的是单链表，这意味着您只能在一个方向上遍历它，即向前，即从第一个节点到最后一个节点。
然后，算法是从第一个节点遍历列表到最后一个节点，并将每个节点的item与您正在搜索的项目进行比较。此外，您还需要两个变量，它们将在您搜索的项目的最后一次(即最终(和倒数第二次(即倒数第二(出现的列表中保持索引。这两个变量的初始值都应该是-1(减去一(。
当第一次出现搜索到的项时，更新最终索引变量。当您遇到下一个事件时，将倒数第二个索引设置为最终索引，然后更新最终索引。
对搜索项目的每一次后续出现重复此操作，即将倒数第二个索引设置为最终索引，然后将最终索引设置为列表中当前节点的索引。因此，如果搜索的项目在列表中只出现一次，或者根本不出现，则倒数第二个索引将为-1。
在编写递归方法时，首先需要的是终止递归的条件。如果条件为true，则返回适当的值。如果条件为false，请更改方法参数，并使用修改后的参数调用相同的方法。在您的情况下，终止条件是一个null节点。
由于列表不是数组，因此还需要跟踪当前节点的索引，以便能够从递归方法返回它。
这是我的实现。我创建了一个LinkList类，其中包含您的Node类的列表。LinkList类允许我最初创建一个链表。我还将方法toString()添加到Node和LinkList类中，以帮助可视化列表。main()方法作为递归方法的测试。递归方法的第一次调用使用列表中的第一个节点，该节点的索引为0(零(。
public class Penultim {
public static void main(String[] args) {
LinkList list = new LinkList();
list.append('a');
list.append('b');
list.append('a');
list.append('b');
list.append('c');
list.append('d');
list.append('e');
list.append('f');
list.append('b');
System.out.println(list);
System.out.println(list.getPenultimateOccurrenceIndex('b', list.getHead(), 0, -1, -1));
}
}
class Node {
private char item;
private Node next;
public Node(char item, Node next) {
this.item = item;
this.next = next;
}
public char getItem() {
return item;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String toString() {
return item + "->";
}
}
class LinkList {
private Node head;
public void append(char item) {
if (head == null) {
head = new Node(item, null);
}
else if (head.getNext() == null) {
head.setNext(new Node(item, null));
}
else {
Node node = head.getNext();
while (node != null) {
if (node.getNext() == null) {
node.setNext(new Node(item, null));
break;
}
node = node.getNext();
}
}
}
public Node getHead() {
return head;
}
public int getPenultimateOccurrenceIndex(char item,
Node node,
int ndx,
int penultimate,
int ultimate) {
if (node == null) {
return penultimate;
}
else {
if (node.getItem() == item) {
if (ultimate >= 0) {
penultimate = ultimate;
}
ultimate = ndx;
}
return getPenultimateOccurrenceIndex(item,
node.getNext(),
ndx + 1,
penultimate,
ultimate);
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = head;
while (node != null) {
sb.append(node);
node = node.getNext();
}
return sb.toString();
}
}
运行上述代码时的输出为
a->b->a->b->c->d->e->f->b->
3
我会用更小的步骤来完成。我会先写一个positionOfLastOccurrence(char letter)。将其作为递归方法编写应该会教给您一些positionOfSecondToLastOccurrence()所需的技术。
接下来的大部分挑战在于一个或多个helper方法的良好设计。我想我应该写一个positionOfLastOccurrenceBeforePosition(int pos, char letter)，它应该返回letter最后一次出现的位置，严格在位置pos之前。因此，给定您的示例列表，ababcdefb、positionOfLastOccurrenceBeforePosition(0, 'b')将返回-1，positionOfLastOccurrenceBeforePosition(2, 'b')将产生1，positionOfLastOccurrenceBeforePosition(100, 'b')将产生8。我相信，这种方法也应该是递归的，因为这将是最终完成实际工作的方法。
现在，找到倒数第二次事件就是先找到最后一次事件，然后找到在那次事件之前的最后一次。