我正在尝试在testdome.com中解决C#编程的问题,但是我发现了有关性能的问题。怎么解决呢?

BinarySearchTree

using System;

public class Node
{
    public int Value { get; set; }

    public Node Left { get; set; }

    public Node Right { get; set; }

    public Node(int value, Node left, Node right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

public class BinarySearchTree
{
    public static bool Contains(Node root, int value)
    {
        Console.WriteLine("value=" + value);
        if(root == null)
            return false;
        else if(root.Value == value)
            return true;
        else if(root.Value != value)
        {
            return Contains(root.Left, value) | Contains(root.Right, value);
        }
        return false;
    }

    public static void Main(string[] args)
    {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        Console.WriteLine(Contains(n2, 3));
    }
}

Performance test on a large tree: Memory limit exceeded
https://www.testdome.com/for-developers/solve-question/7482

TwoSum
using System;
using System.Collections.Generic;

class TwoSum
{
    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
    {
        for(int ctr1=0; ctr1<list.Count; ctr1++)
        {
            for(int ctr2=0; ctr2<list.Count; ctr2++)
            {
                if ((ctr1 != ctr2) && (list[ctr1]+list[ctr2] == sum))
                    return new Tuple<int, int>(ctr1, ctr2);
            }
        }
        return null;
    }

    public static void Main(string[] args)
    {
        Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);
        Console.WriteLine(indices.Item1 + " " + indices.Item2);
    }
}

Performance test with a large number of elements: Time limit exceeded
https://www.testdome.com/for-developers/solve-question/8125

最佳答案

对于二进制搜索树,testdome.com提供了一个提示:“如果要搜索的值小于节点的值,则可以忽略右子树。”这将内存消耗减少了一半。

public static bool Contains(Node root, int value) {
    Console.WriteLine("value=" + value);
    if (root == null) {
        return false;
    }
    else if (value == root.Value) {
        return true;
    }
    else if (value < root.Value) {
        // Hint 2: If a value being searched for is smaller than the value of the node,
        // then the right subtree can be ignored.
        return Contains(root.Left, value);
    }
    else {
        return Contains(root.Right, value);
    }
    return false;
}
对于TwoSum,如果我们假设输入数组中的值是唯一的,则可以使用字典根据其值(在O(1)时间中)查找索引。这与提示“字典可用于存储预先计算的值,这可能允许具有O(N)复杂度的解决方案”有关。
// Write a function that, when passed a list and a target sum,
// returns, efficiently with respect to time used,
// two distinct zero-based indices of any two of the numbers,
// whose sum is equal to the target sum.
// If there are no two numbers, the function should return null.
public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) {

    if (list.Count < 2) {
        return null;
    }

    // Hint 2: A dictionary can be used to store pre-calculated values,
    // this may allow a solution with O(N) complexity.
    var indexByValue = new Dictionary<int, int>();
    for (var i = 0; i < list.Count; i++) {
        var value = list[i];
        // ensure that the values used as keys are unique
        // this is OK because we only have to return any tuple matching the sum,
        // therefore we can ignore any duplicate values
        if (!indexByValue.ContainsKey(value)) {
            indexByValue.Add(value, i);
        }
    }

    for (var j = 0; j < list.Count; j++) {
        var remainder = sum - list[j];
        if (indexByValue.ContainsKey(remainder)) {
            return new Tuple<int, int> (j, indexByValue[remainder]);
        }
    }

    return null;
}

关于c# - testdome.com中的TwoSum和BinarySearchTree;如何解决警告消息: Performance test?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42897865/

10-12 04:13
查看更多