递归列表-计算所有元素的总和，包括最后一次出现的元素
递归列表-计算所有元素的总和，包括最后一次出现的元素
提问于 2019-05-26 10:44:51
这不仅仅是一个Java问题。一般来说，这是一个算法问题：
任务是计算所有元素的总和，包括最后出现的值"val"，它是该方法中的一个参数。
方法如下所示：
int sumLastOcc (节点n，int val)
// n是列表的节点。从调用方法时的头部开始。
// val为合计总和的值
示例:3 5 2 7 5 1 4
结果: val =5时为22 (调用: sumLastOcc (head，5))
结果:0，val =9(调用: sumLastOcc (head，9))
public class RecursiveList {
static Node head;
static boolean found = false;
public static void main(String[] args) {
RecursiveList list = new RecursiveList();
list.addNumber(3);
list.addNumber(5);
list.addNumber(2);
list.addNumber(7);
list.addNumber(5);
list.addNumber(1);
list.addNumber(4);
list.printList();
int result = list.sumLastOcc(head, 5);
System.out.println();
System.out.println(result);
}
private int sumLastOcc(Node n, int val) {
// CODE TO IMPLEMENT
}
return sum;
}
private void addNumber(int number) {
Node curr = head;
Node prev = null;
if (head == null) {
head = new Node(number, null);
} else {
while (curr != null) {
prev = curr;
curr = curr.next;
}
Node newNode = new Node(number, null);
prev.next = newNode;
}
}
// inner node class
private class Node {
Node next;
int value;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
private void printList() {
Node curr = head;
Node prev = null;
while (curr != null) {
System.out.print(curr.value + " ");
prev = curr;
curr = curr.next;
}
}
}可以使用/添加任何全局静态变量，如：
找到静态布尔值= false；
正如已经定义的那样。我们不应该使用循环(for，while，...)而且我们也不应该使用额外的方法。只需使用"private int sumLastOcc(Node n，int val)“方法就可以做到这一点。
回答 2
Stack Overflow用户
发布于 2019-05-26 17:12:22
我可以解释-遍历列表直到末尾，并继续添加值。另外，从匹配中设置标志(found设置为true)以跟踪扣减，直到您到达终点或找到另一个匹配。找到匹配项时重置计数器。
在伪代码中，比如
private int sumLastOcc(Node n, int val) {
if n.next != null
//traverse the list until the end
//add the value to sum
sum = sum + n.value
//keep track of values from the match
if(found)
deduct = deduct + n.value;
//reset the flag when match found
deduct = 0
found = true
//call until reach the end
sumLastOcc(n.next, val)
else
//add the last node value
sum = sum + n.value
//even for the deduct
if (found)
deduct = deduct + n.value;
//lastly return sum - deduct
return found?sum - deduct:0
}Stack Overflow用户
发布于 2019-05-27 03:29:26
感谢你们的快速和友好的回应。我根据Alexander Pavlov的解释写了类似的方法。我认为这是一种非常好的方式：
private int sumLastOcc(Node n, int val) {
int sumUpTo = 0;
int sumAfter = 0;
if (n.next != null) {
sumAfter = sumAfter + n.value + sumLastOcc(n.next, val);
if (n.value == val) {
found = true;
}
if (found) {
sumUpTo = sumUpTo + sumAfter;
}
} else {
sumAfter = sumAfter + n.value;
if (n.value == val) {
sumUpTo = sumUpTo + sumAfter;
found = true;
}
}
return sumUpTo;
}所以这个问题已经解决了:-)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56310238
复制相关文章
相似问题