递归列表 - 计算直到并包括最后一次出现的所有元素的总和

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (44)

这不仅是一个Java问题。这是一般的算法问题:

任务是计算所有元素的总和,直到并包括最后出现的值“val”,这是方法中的参数。

方法如下:

int sumLastOcc(Node n,int val)

// n是列表的节点。调用方法时从头开始。

// val是将形成总和的值

示例:3 5 2 7 5 1 4

结果:22表示val = 5(电话: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;
        }
    }
}

可以使用/添加任何全局静态变量,例如:

static boolean found = false;

如已定义的那样。我们应该不使用循环(for,while,...),我们也不应该使用其他方法。只是方法“private int sumLastOcc(Node n,int val)”应该做那个魅力。

提问于
用户回答回答于

谢谢你们快速而好的回应。我根据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;
}

所以这解决了:-)

用户回答回答于

我可以解释 - 遍历列表直到结束并继续添加值。同样从比赛中设置标志(发现为真)以跟踪扣除,直到你到达终点或找到​​另一场比赛。找到匹配项时重置计数器。

在伪代码中

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
}

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励